بهبود پیچیدگی زمانی روش های خوشه بندی سلسله مراتبی با کمک دیاگرام وروئی

گروه بندی اشیا(داده ها) به صورتی کهاشیا یک گروه با یکدیگر حداکثر شباهت و با گروه دیگر حداکثر تفاوت را داشته باشند، خوشه بندی نامیده می شود. خوشه بندی داده ها یک مسئله NP-Hard می باشد. بنابراین روش های ارائه شده تاکنون روش های تقریبی هستند. یکی از مهمترین روش های خوشه بندی،روش سلسله مراتبی است. در روش سلسه مراتبی خوشه های شبیه به هم در هر گام با هم ترکیب و خوشه بزرگتری ایجاد می شود. در این روش در هر مرحله پس از ایجاد یک خوشه جدید فاصله این خوشه تا تمامی خوشه ها محاسبه می شود. پیچیدگی زمانی این کار بالا است. شبیه ترین(نزدیکترین) خوشه به یک خوشه همیشه در همسایگی خوشه قرار دارد. بنابراین تنها لازم است فاصله هر خوشه تا همسایگانش محاسبه شود. در صورتی که روی داده ها دیاگرام وروئی(Voronio Diagram) وجود داشته باشد،همسایه های یک خوشه را می توان با کمک این دیاگرام به دست آورد. در ای پژوهش با کمک دیاگرام وروئی، فضای جستجوی یافتن شبیه ترین خوشه به همسایه های یک خوشه می یابد. این موضوع سبب کاهش پیچیدگی زمانی روش ارائه شده می شود. الگوریتم ارائه شده با جاوا پیاده سازی و با کمک ابزار وکا(Weka) با روش خوشه بندی سلسله مراتبی Average-Linkage مقایسه شد. نتایج ارزیابی بهبود زمانی روش ارائه شده را در مقایسه با روش مورد مقایسه نشان می دهد

Keywords:

خوشه بندی , دیاگرام وروئی(Voronio Diagram) , روش سلسله مراتبی