Astaraki

مقدمه‌اي بر خوشه‌بندي

خوشه‌بندي را مي‌توان به عنوان مهمترين مسئله در يادگيري بدون نظارت در نظر گرفت. خوشه‌بندي با يافتن يک ساختار درون يک مجموعه از داده‌هاي بدون برچسب درگير است. خوشه‌ به مجموعه‌اي از داده‌ها گفته مي‌شود که به هم شباهت داشته باشند. در خوشه‌بندي سعي مي‌شود تا دادهها به خوشه‌هايي تقسيم شوند که شباهت بين داده‌هاي درون هر خوشه حداکثر و شباهت بين داده‌هاي درون خوشه‌هاي متفاوت حداقل شود.


شکل 1: در اين شکل نمونه‌اي از اعمال خوشه‌بندي روي يک مجموعه از داده‌ها مشخص شده است که از معيار فاصله(Distance) به عنوان عدم شباهت(Dissimilarity) بين داده‌ها استفاده شده است.

خوشه‌بندي در مقابل طبقه‌‌بندي

در طبقه‌بندي هر داده به يک طبقه (کلاس) از پيشين مشخص شده تخصيص مي‌يابد ولي در خوشه‌بندي هيچ اطلاعي از کلاسهاي موجود درون داده‌ها وجود ندارد و به عبارتي خود خوشه‌ها نيز از داده‌ها استخراج مي‌شوند. در شکل زير تفاوت بين خوشه‌بندي و طبقه‌بندي بهتر نشان داده شده است.


a


b

شکل 2: a) در طبقه‌بندي با استفاده يک سري اطلاعات اوليه داده‌ها به دسته‌هاي معلومي نسبت داده‌ مي‌شوند. در خوشه‌بندي داده‌ها با توجه به الگوريتم انتخاب شده به خوشه‌هايي نسبت داده‌ مي‌شوند

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

Astaraki

يادگيري با نظارت در مقابل يادگيري بدون‌نظارت

در يادگيري با نظارت از ابتدا دسته‌ها مشخص هستند و هر يک از داده‌هاي آموزشي به دسته‌اي خاص نسبت داده شده است و اصطلاحأ گفته مي‌شود ناظري وجود دارد که در هنگام آموزش اطلاعاتي علاوه بر داده‌هاي آموزش در اختيار يادگيرنده (Learner) قرار مي‌دهد. ولي در يادگيري بدون نظارت هيچ اطلاعاتي بجز داده‌هاي آموزشي در اختيار يادگيرنده قرار ندارد و اين يادگيرنده است که بايستي در داده‌ها به دنبال ساختاري خاص بگردد.

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

Astaraki

کاربردها

از آنجا که خوشه‌بندي يک روش يادگيري بدون نظارت محسوب مي‌گردد، در موارد بسياري مي‌تواند کاربرد داشته‌ باشد

*

در بازاريابي (Marketing): دسته‌‌بندي مشتري‌ها به دسته‌هايي بر حسب رفتارها و نيازهاي آنها از طريق مجموعه زيادي از ويژگي‌ها و آخرين خريد‌هاي آنها.
*

زيست‌‌‌شناسي (Biology): دسته‌بندي حيوانات و گياهان از روي ويژگي‌هاي آنها
*

کتابداري : دسته‌بندي کتابها
*

نقشه‌برداري شهري (City-Planning): دسته‌بندي خانه‌ها بر اساس نوع و موقعيت جغرافيايي آنها.
*

مطالعات زلزله‌نگاري (Earthquake studies): تشخيص مناطق حادثه‌خيز بر اساس مشاهدات قبلي.
*

وب (WWW): دسته‌بندي اسناد و يا دسته‌بندي مشتريان به سايتها و ....
*

داده کاوي (Data Mining): کشف اطلاعات و ساختار جديد از داده‌هاي موجود
*

در تشخيص گفتار (Speech Recognition): در ساخت کتاب کد از بردارهاي ويژگي، در تقسيم کردن گفتار بر حسب گويندگان آن و يا فشرده‌سازي گفتار
*

در تقسيم‌بندي تصاوير(Image Segmentation): تقسيم‌بندي تصاوير پزشکي و يا ماهواره‌اي

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

Astaraki

مسائل درگير با روش‌هاي خوشه‌بندي موجود

متأسفانه چندين مسئاله در خصوص روش‌هاي خوشه‌بندي مطرح است که هنوز به شکل کامل پاسخ داده نشده‌اند. و همچنان تلاش‌هاي بسياري به منظور حل آنها انجام مي‌گيرد.

· روش‌هاي خوشه‌بندي قادر نيستند تمامي نيازهاي مسائل را به طور هم‌زمان برآورده‌کنند.

· به دليل پيچيدگي‌ محاسباتي زياد در برخورد با مجموعه داده‌هاي بزرگ با تعداد داده ‌زياد و تعداد ويژگي‌هاي زياد براي هر داده عملي نيستند.

· به دليل وابستگي‌ شديد به تعريف معيار شباهت بين داده‌ها در مسائلي که تعريف معيار شباهت مشکل باشد نتايج مطلوبي توليد نمي‌کنند.(در داده‌ها با تعداد ويژگي‌ زياد)

· براي نتايج آنها مي‌توان تفسيرهاي مختلفي بيان کرد.


خوشه‌بندي در مقابل چندي‌سازي برداري

همان‌گونه که بحث شد، خوشه‌بندي نوعي سازماندهي داده‌ها است، بر اساس شباهتي که بين آنها تعريف مي‌شود به گونه‌اي که شباهت بين داده‌هايي که درون يک خوشه قرار مي‌گيرند، نسبت به داده‌هايي که درون خوشه‌هاي متفاوت قرار مي‌گيرند، بيشتر باشد.

در کاربردهاي ارتباطي و فشرده‌سازي داده‌ها از روشهايي به نام چندي‌سازي برداري استفاده مي‌شود که از بعضي جنبه‌ها مي‌توان آنها را معادل خوشه‌بندي در نظر گرفت. در چندي‌سازي برداري نيز داده‌ها بر اساس ميزان شباهت بين آنها به دسته‌هايي تقسيم مي شوند و هر دسته بوسيله يک بردار که به آن کلمه کد (CodeWord) گفته مي‌شود جايگزين مي‌گردد. به مجموعة اين کلماتِ کد اصطلاحأ کتابِ کد(CodeBook) گفته مي‌شود.

دربعضي از بخث‌هاي علمي بين خوشه‌بندي و چندي‌سازي برداري تفاوتهايي قائل مي‌شوند. زيرا خوشه‌بندي را يک رهيافت بدون نظارت براي تحليل داده‌ها در نظر مي‌گيرند ولي چندي‌سازي برداري را روشي براي کشف خوشه‌ها نمي‌شناسند بلکه آن را راهي براي نمايش داده‌ها با تعداد عناصر کمتر به گونه‌اي که اطلاعات از دست رفته حداقل شود، مي‌شناسند. علي‌رغم تفاوت بيان شده مي‌توان روشهاي بکار رفته در هر يک آنها را در ديگر نيز بکار برد در اينجا بين خوشه‌بندي و چندي‌سازي برداري تفاوتي قائل نمي‌شويم.

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

Astaraki

روش‌هاي خوشه‌بندي

روش‌هاي خوشه‌بندي را مي‌توان از چندين جنبه تقسيم‌بندي کرد:



1- خوشه‌بندي انحصاري (Exclusive or Hard Clustering) و خوشه‌بندي با هم‌پوشي (Overlapping or Soft Clustering)

در روش خوشه‌بندي انحصاري پس از خوشه‌بندي هر داده دقيقأ به يک خوشه تعلق مي‌گيرد مانند روش خوشه‌بندي K-Means. ولي در خوشه‌بندي با همپوشي پس از خوشه‌بندي به هر داده يک درجه تعلق بازاء هر خوشه نسبت داده مي‌شود. به عبارتي يک داده مي‌تواند با نسبتهاي متفاوتي به چندين خوشه تعلق داشته باشد. نمونه‌اي از آن خوشه‌بندي فازي است.



2- خوشه‌بندي سلسله مراتبي (Hierarchical) و خوشه‌بندي مسطح(Flat)

در روش خوشه بندي سلسله مراتبي، به خوشه‌هاي نهايي بر اساس ميزان عموميت آنها ساختاري سلسله‌ مراتبي نسبت داده مي‌شود. مانند روش Single Link. ولي در خوشه‌بندي مسطح تمامي خوشه‌هاي نهايي داراي يک ميزان عموميت هستند مانند K-Means. به ساختار سلسله مراتبي حاصل از روشهاي خوشه‌بندي سلسله مراتبي دندوگرام (Dendogram) گفته مي‌شود.

با توجه با اينکه روش‌هاي خوشه‌بندي سلسله مراتبي اطلاعات بيشتر و دقيق‌تري توليد مي‌کنند براي تحليل داده‌هاي با جزئيات پيشنهاد مي‌شوند ولي از طرفي چون پيچيدگي محاسباتي بالايي دارند براي مجموعه داده‌هاي بزرگ روش‌هاي خوشه‌بندي مسطح پيشنهاد مي‌شوند.

روشهاي خوشه‌بندي سلسله مراتبي


همان گونه که بيان شد، در روش خوشه بندي سلسله مراتبي، به خوشه‌هاي نهايي بر اساس ميزان عموميت آنها ساختاري سلسله‌ مراتبي، معمولا به صورت درختي نسبت داده مي‌شود. به ا ين درخت سلسله مراتبي دندوگرام (dendogram) مي‌گويند. روش کار تکنيکهاي خوشه‌بندي سلسله‌مراتبي معمولا بر اساس الگوريتمهاي حريصانه (Greedy Algorithms) و بهينگي مرحله‌اي (stepwise-optimal) است. روشهاي خوشه‌بندي بر اساس ساختار سلسله مراتبي توليدي توسط آنها معمولا به دو دستة زير تقسيم مي‌شوند:



1.

بالا به پايين (Top-Down) يا تقسيم کننده (Divisive): در اين روش ابتدا تمام داده‌ها به عنوان يک خوشه در نظر گرفته مي‌شوند و سپس در طي يک فرايند تکراري در هر مرحله داده‌هايي شباهت کمتري به هم دارند به خوشه‌هاي مجزايي شکسته مي‌شوند و اين روال تا رسيدن به خوشه‌هايي که داراي يک عضو هستند ادامه پيدا مي‌کند.



2.

پايين به بالا (Bottom-Up) يا متراکم شونده (Agglomerative): در اين روش ابتدا هر داده‌ها به عنوان خوشه‌اي مجزا در نظر گرفته مي‌شود و در طي فرايندي تکراري در هر مرحله خوشه‌هايي که شباهت بيشتري با يکديگر با يکديگر ترکيب مي‌شوند تا در نهايت يک خوشه و يا تعداد مشخصي خوشه حاصل شود. از انواع الگوريتمهاي خوشه‌بندي سلسله مراتبي متراکم شونده رايج مي‌توان از الگوريتمهاي Single-Link، Average-Link و Complete-Link نام برد. تفاوت اصلي در بين تمام اين روشها به نحوة محاسبة شباهت بين خوشه‌ها مربوط مي‌شود. که در بخشهاي بعد به تشريح هر يک پرداخته خواهد شد.



نمونه‌اي از روش خوشه‌بندي سلسله مراتبي و تفاوت بين روشهاي بالا به پايين و پايين به بالا در شکل زير مشاهده مي‌شود.

شکل 3: تفاوت بين روشهاي بالا به پايين با روشهاي پايين به بالا

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

Astaraki

خوشه‌بندي با روش Single-Link

اين روش يکي از قديمي‌ترين و ساده‌ترين روشهاي خوشه‌بندي است و جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. به اين روش خوشه‌بندي، تکنيک نزديکترين همسايه (Nearest Neighbour) نيز گفته مي‌شود. در اين روش براي محاسبة شباهت بين دو خوشة A و B از معيار زير استفاده مي‌شود:



که i يک نمونه داده متعلق به خوشة A و j يک نمونه دادة متعلق به خوشة B مي‌باشد. در واقع در اين روش شباهت بين دو خوشه، کمترين فاصلة بين يک عضو از يکي با يک عضو از ديگري است. در شکل زير اين مفهوم بهتر نشان‌ داده شده است


شکل 4: شباهت بين دو خوشه در روش Single-Link برابر است با کمترين فاصلة بين داده‌هاي دو خوشه


1-1-1- مثال: در اين قسمت سعي شده است تا در مثالي با فرض داشتن 6 نمونه داده و ماتريس فاصلة بين آنها که در جدول 1 نشان‌داده شده است، نحوة اعمال روش خوشه‌بندي Single-Link بهتر تشريح شود

جدول 1: ماتريس فاصلة بين 6 نمونة داده


در ابتدا هر داده به عنوان يک خوشه در نظر گرفته مي‌شود و يافتن نزديکترين خوشه در واقع يافتن کمترين فاصلة بين داده‌هاي بالا خواهد بود. با توجه به جدول 1 مشخص است که داده‌هاي 3 و 5 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با کمترين فاصلة بين 3 و يا 5 از ساير خوشه‌ها. نتيجه در جدول 2 نشان ‌داده شده است.



با توجه به جدول 2 مشخص است که داده‌هاي 1 و 2 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با کمترين فاصلة بين 1 و يا 2 از ساير خوشه‌ها. نتيجه در جدول 3 نشان ‌داده شده است.


با توجه به جدول 3 مشخص است که خوشه‌هاي (3 و 5) و 4 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با کمترين فاصلة بين (3 و 5) و يا 4 از ساير خوشه‌ها. نتيجه در جدول 4 نشان ‌داده شده است.



با توجه به جدول 4 مشخص است که خوشه‌هاي (1 و 2) و 6 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با کمترين فاصلة بين (1 و 2) و يا 6 از ساير خوشه‌ها. نتيجه در جدول 5 نشان ‌داده شده است.

در نهايت اين دو خو‌شة حاصل ا هم ترکيب مي‌شوند. نتيجه در دندوگرام شکل 5 نشان داده شده است.


شکل 5: دندوگرام مثال Single-Link

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

Astaraki

خوشه‌بندي با روش Complete-Link

اين روش همانند Single-Link جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. به اين روش خوشه‌بندي، تکنيک دورترين همسايه (furthest Neighbour) نيز گفته مي‌شود. در اين روش براي محاسبة شباهت بين دو خوشة A و B از معيار زير استفاده مي‌شود:


که i يک نمونه داده متعلق به خوشة A و j يک نمونه دادة متعلق به خوشة B مي‌باشد. در واقع در اين روش شباهت بين دو خوشه بيشترين فاصلة بين يک عضو از يکي با يک عضو از ديگري است. در شکل زير اين مفهوم بهتر نشان‌ داده شده است.


شکل 6: شباهت بين دو خوشه در روش Complete-Link برابر است با بيشترين فاصلة بين داده‌هاي دو خوشه.



مثال: در اين قسمت سعي شده است تا در مثالي با فرض داشتن 6 نمونه داده و ماتريس فاصلة بين آنها که در جدول 6 نشان ‌داده شده است، نحوة اعمال روش خوشه‌بندي Complete-Link بهتر تشريح شود.


در ابتدا هر داده به عنوان يک خوشه در نظر گرفته مي‌شود و يافتن نزديکترين خوشه در واقع يافتن کمترين فاصلة بين داده‌هاي بالا خواهد بود. با توجه به جدول 6 مشخص است که داده‌هاي 3 و 5 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با بيشترين فاصلة بين 3 و يا 5 از ساير خوشه‌ها. نتيجه در جدول 7 نشان ‌داده شده است.



با توجه به جدول 7 مشخص است که داده‌هاي 1 و 2 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با بيشترين فاصلة بين 1 و يا 2 از ساير خوشه‌ها. نتيجه در جدول 8 نشان ‌داده شده است.


با توجه به جدول 8 مشخص است که خوشه‌هاي (3 و 5) و 4 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با بيشترين فاصلة بين (3 و 5) و يا 4 از ساير خوشه‌ها. نتيجه در جدول 9 نشان ‌داده شده است.


با توجه به جدول 9 مشخص است که خوشه‌هاي (1 و 2) و 6 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با بيشترين فاصلة بين (1 و 2) و يا 6 از ساير خوشه‌ها. نتيجه در جدول 10 نشان ‌داده شده است.

در نهايت اين دو خو‌شة حاصل ا هم ترکيب مي‌شوند. نتيجه در دندوگرام شکل 7 نشان داده شده است.


شکل 7: دندوگرام مثال Complete-Link

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

Astaraki

خوشه‌بندي با روش Average-Link
اين روش همانند Single-Link جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. از آنجا که هر دو روش خوشه‌بندي Single-link و Complete-link بشدت به نويز حساس مي‌باشد، اين روش که محاسبات بيشتري دارد، پيشنهاد شد. در اين روش براي محاسبة شباهت بين دو خوشة A و B از معيار زير استفاده مي‌شود:



که i يک نمونه داده متعلق به خوشة A و j يک نمونه دادة متعلق به خوشة B مي‌باشد. و NA تعداد اعضاء خوشة A و NB تعداد اعضاء خوشة B است. در واقع در اين روش، شباهت بين دو خوشه ميانگين فاصلة بين تمام اعضاء يکي با تمام اعضاء ديگري است. در شکل زير اين مفهوم بهتر نشان‌ داده شده است


شکل 8: شباهت بين دو خوشه در روش Average-Link برابر است با ميانگين فاصلة بين داده‌هاي دو خوشه



مثال: در اين قسمت سعي شده است تا در مثالي با فرض داشتن 6 نمونه داده و ماتريس فاصلة بين آنها که در جدول 11 نشان ‌داده شده است، نحوة اعمال روش خوشه‌بندي Average-Link بهتر تشريح شود


در ابتدا هر داده به عنوان يک خوشه در نظر گرفته مي‌شود و يافتن نزديکترين خوشه در واقع يافتن کمترين فاصلة بين داده‌هاي بالا خواهد بود. با توجه به جدول 11 مشخص است که داده‌هاي 3 و 5 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با ميانگين فاصلة بين 3 و 5 از ساير خوشه‌ها. نتيجه در جدول 12 نشان ‌داده شده است.

با توجه به جدول 12 مشخص است که داده‌هاي 1 و 2 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با بيشترين فاصلة بين 1 و يا 2 از ساير خوشه‌ها. نتيجه در جدول 13 نشان ‌داده شده است

با توجه به جدول 13 مشخص است که خوشه‌هاي (3 و 5) و 4 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با بيشترين فاصلة بين (3 و 5) و يا 4 از ساير خوشه‌ها. نتيجه در جدول 14 نشان ‌داده شده است.

با توجه به جدول 14 مشخص است که خوشه‌هاي (1 و 2) و 6 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با بيشترين فاصلة بين (1 و 2) و يا 6 از ساير خوشه‌ها. نتيجه در جدول 15 نشان ‌داده شده است.

در نهايت اين دو خو‌شة حاصل ا هم ترکيب مي‌شوند. نتيجه در دندوگرام شکل 9 نشان داده شده است.


شکل 9: دندوگرام مثال Average-Link

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

Astaraki

ديگر روشهاي خوشه بندي سلسله مراتبي

*خوشه‌بندي با روش Group Average Link: اين روش همانند Single-Link جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. [Webb] به اين روش Centriod Distance نيز گفته مي‌شود. در اين روش براي محاسبة شباهت بين دو خوشة A و B از معيار زير استفاده مي‌شود:


که Xi يک نمونه داده متعلق به خوشة A، Xj يک نمونه دادة متعلق به خوشة B، NA تعداد اعضاء خوشةA و NB تعداد اعضاء خوشة B است. در واقع در اين روش، شباهت بين دو خوشه فاصلة بين بردار ميانگينِ تمام اعضاء يکي با بردارِ ميانگينِ تمام اعضاء ديگري است. در شکل F4 اين مفهوم بهتر نشان‌ داده شده است.

*

خوشه‌بندي با روش Median Distance: اين روش نيز همانند Single-Link جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. در روش Group Average Link اگر يم خوشة کوچک با يک خوشة بزرگ ترکيب شود نقطة ميانگين خوشة حاصل نقطه‌اي نزديک ميانگين خوشة بزرگتر خواهد بود که در بعضي از کاربردها چندان مطلوب نيست. بدين منظور اين روش خوشه‌بندي پيشنهاد شده است که مشکل مذکور را ندارد. در اين روش از ميانة نقاط يک خوشه به‌ عنوان مرکز ثقل آن خوشه استفاده مي‌شود.


شکل 10: شباهت بين دو خوشه در روش Group Average Link برابر است با فاصله بين ميانگين نقاط دو خوشه

*

خوشه‌بندي با روش Ward:

اين روش نيز همانند Single-Link جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. در اين روش خوشه‌‌بندي براي کاهش تلفات ناشي داده‌هاي دور افتاده (Outlier) از معياري جديد براي محاسبة عدم‌شباهت بين خوشه‌ها استفاده مي‌کند. در روش Ward's از مجموع مربعات تفاضل هر داده از يک خوشه با بردار ميانگين آن خوشه به عنوان معياري براي سنجش يک خوشة استفاده مي‌شود. الگوريتم زير را مي‌توان براي روش Ward در نظر گرفت.

1.

ابتدا هر داده به عنوان يک خوشه در نظر گرفته مي‌شود.
2.

به ازاء تمام جفت خوشه‌هاي ممکن از مجموعة خوشه‌ها آن دو خوشه‌اي که مجموع مربعات تفاضل داده‌هاي خوشة حاصل از اجتماع آنها با بردار ميانگين خوشة حاصل کمينه باشد، انتخاب مي‌شوند.
3.

دو خوشة انتخاب شده با هم ترکيب مي‌شوند.
4.

تا زماني که تعداد خوشه‌ها به تعداد مورد نظر نرسيده است، مراحل ii، iii و iv تکرار مي‌شوند

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

Astaraki

الگوريتم خوشه‌بندي پايين به بالاي عمومي

اغلب الگوريتمهاي خوشه‌بندي سلسله مراتبي را به نحوي مي‌توان گسترش يافتة الگوريتم خوشه‌بندي Single-Link در نظر گرفت. تفاوت روشهاي مختلف در نحوة محاسبة ماتريس تشابه يا عدم تشابه (Dissimilaritye) آنها است. فرمولي بازگشتي به نام فرمول Lance-Williams تعريف شده است که عدم‌تشابه بين خوشة k و خوشة حاصل از پيوند خوشه‌هاي i و j را بيان مي‌کند:


که پارامترهاي ai، b و c بيان کنندة نوع روش خوشه‌بندي هستند و در جدول 16 مقادير مربوط به چند روش آورده شده است:

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!