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

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)

یک روش افزایشی که در آن یک درخت ویژگی خوشه بندی (CF-tree) را به صورت افزایشی می سازیم.

1- از روی داده های حافظه یک CF-tree اولیه بساز.

2- یک روش خوشه بندی را به کار ببر تا برگهای CF-tree را خوشه بندی کنی.

Clustering Feature (CF):  CF = (N, LS, SS)

که در آن LS جمع خطی داده ها و N تعداد داده ها و SS جمع توان دوم آنهاست. در هر گره میانی جمع CF گره های فرزند آن است.

تنها برای داده های عددی قابل استفاده است.

در الگوریتم BIRCH، درخت ویژگی (CF-Tree) دو پارامتر تعداد فرزندان (branching factor) و threshold ( حداکثر قطر زیرخوشه های برگهای آن زیر درخت) را دارد.

پایین ترین سطح درخت (برگها) بینشان لیست پیوندی دو طرفه است.

قطر خوشه:

الگوریتم:

هر داده را به نزدیک ترین برگ درخت اختصاص بده و CF آن را به روز کن. اگر قطر داده های آن برگ از مقدار آستانه بیشتر شد آن را به دو درخت تقسیم کن.

ایرادها:

به ترتیب وابسته است.

چون حداکثر تعداد در هر برگ داریم، خوشه هایی که می سازد طبیعی نیستند.

خوشه های محدب می سازد که به قطر و شعاع بستگی دارند.

CHAMELEON ( Hierarchical Clustering using dynamic modeling)

تعریف inter connectivity: جمع وزن یالهای بین دو خوشه

تعریف فاصله ی بین خوشه ای: min cut (وزن یالهایی که باید قطع کنیم تا دو خوشه جدا شوند)

ادغام: آنهایی که فاصله شان از یک حد آستانه کمتر باشد ادغام می کند.

ملاک فاصله: وزن یالهای بین دو خوشه تقسیم بر میانگین (وزن یالهای درون هر خوشه) برای دو خوشه

(برای فاصله بین دو خوشه وزن mincut را به جای مجموع بذارید.)