روشهاي خوشهبندي
روشهاي خوشهبندي را ميتوان از چندين جنبه تقسيمبندي کرد:
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: تفاوت بين روشهاي بالا به پايين با روشهاي پايين به بالا