خوشه بندی داده ها و یافتن نقاط پرچگال با گراف یائو و معیار ماژولاریتی

پاران مروج و اور پایان سریا خوشه بندی به مفهوم تقسیم بندی نمونه داده ها به گروه هایی مجزا بر مبنای ویژگی های مشترک به منظور کشف ویژگی های ساختاری آنها می باشد. طی مطالعات گسترده صورت گرفته، الگوریتم های متعددی در این حوزه ارائه شده اند. این راهکارها به لحاظ معیارهایی از قبیل دقت، عملکرد، هزینه محاسباتی، زمان، قدرت تشخیص خوشه ها، حساسیت نسبت به داده های پراکنده و نیاز به تنظیم پارامترها یک سری مزایا و البته چالش هایی به همراه داشته اند. مطالعات اخیر صورت گرفته در این حوزه الگوریتمی ارائه می دهد به نام الگوریتم خوشه بندی پیک که این راهکار تلفیقی از الگوریتم های خوشه بندی بر مبنای تراکم و الگوریتم های خوشه بندی بر مبنای مرکز می باشد. این روش کارآمد با بهره گیری از تلفیق مزایای این دو الگوریتم در سال های اخیر توجهات بسیاری به خود جلب کرده است. اما به دلیل عدم تشخیص صحیح مراکز خوشه در خوشه های کم چگال و همچنین تشخیص نقاط داده نرمال به عنوان نقاط داده نویز، عملکرد آن کاهش پیدا می کند. به منظور غلبه بر چالش های مطرح در الگوریتم پیک الگوریتم کارآمدی به نام خوشه بندی حداکثری ارائه شده است که نه تنها می تواند بر چالش های مطرح در الگوریتم پیک غلبه کند بلکه از مزایای آن نیز می تواند بهره مند شود. در راهکار پیشنهادی ما الگوریتمی پیشنهاد می دهیم به نام الگوریتم خوشه بندی بر گراف یائو (Y۴). در این راهکار پیشنهادی از گراف یائو به منظور تعیین نقاط پرچگالی و بهره مندی از مزایای مربوط به آن استفاده می کنیم و در ادامه به منظور تعیین مرز خوشه ها از مرز گراف یائو به منظور پوشش تمام نقاط داده و رسیدن به مرز خوشه بندی دقیق و صحیح به طوریکه با خوشه های دیگر همپوشانی نداشته باشد، بهره می گیریم. در این راهکار پیشنهادی انتظار داریم مرز خوشه ها به خصوص در مجموعه داده های نزدیک به هم و حتی تودرتو به صورت دقیق و مشخص در زمان قابل قبول و هزینه محاسباتی پایین صورت پذیرد.

کلیدواژه ها:

خوشه بندی حداکثری ، خوشه بندی ، پیک ، خوشه بندی متراکم ، گراف یائو