خوشه بندی گراف (Clustering) شبکه های اجتماعی جهت تشخیص انجمن ها (community detection)

خوشه بندی گراف:

گراف‌ها به عنوان ساختارهای ریاضی که روابط اشیا با هم را در سطح انتزاع مناسبی نشان می‌دهند به طور گسترده در مدل‌سازی مسائل مختلف مورد استفاده قرار گرفته‌اند. به همین سبب، در اختیار داشتن ابزارهایی مناسب برای تحلیل آن‌ها به یک ضرورت مبدل شده و محققان بسیاری در زمینه های گوناگون به ارائه روش‌هایی برای این کار پرداخته‌اند.

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

یکی از کاربردی‌ترین مسائل در علم کامپیوتر و هوش مصنوعی، مسئله‌ی  خوشه‌بندی (Clustering) داده‌ها است. مسئله خوشه‌بندی گراف‌ها از مسائل مهم در بسیاری از زمینه‌ها مانند شبکه‌های اجتماعی، بیوانفورماتیک و الکترونیک می باشد. لذا محققان زیادی از رشته‌های مختلف تحقیقات متنوعی را پیرامون آن انجام داده‌اند.از طرفی امکان مدلسازی (Modeling) بسیاری از مسائل با نظریه گراف و نیاز به تحلیل این گراف‌ها موجب شده است تا توجه گسترده‌ای به خوشه‌بندی گراف‌ها شده و روش‌های متعددی برای  آن ارائه شود. به مسئله خوشه‌بندی در گراف ها، تشخیص ‌انجمن‌ها نیز گفته می‌شود.

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

• هدف خوشه بندی گراف:

تشخیص انجمنها و خوشه بندی گراف در یک شبکه اجتماعی به ساده سازی و تحلیل بهتر آن کمک می‌کند. انجمنها گروه‌هایی از نودهای شبکه هستند که ارتباط تنگاتنگی با هم دارند و با نودهای بیرون از شبکه ارتباط نسبتا کمی دارند. بعنوان مثال اگر ارتباطات اجتماعی افراد را در یک شبکه اجتماعی داشته باشیم دوستان هم کلاس در یک دانشکده از یک دانشگاه ممکن است تشکیل یک گروه با ارتباطات تنگاتنگ بدهند و در حقیقت یک انجمن در این شبکه اجتماعی باشند.

نزدیک بودن ویژگی‌ها عموما با استفاده از معیارهای شباهت / عدم شباهت سنجیده می‌شوند. معمولا از مفهوم فاصله برای تشخیص شباهت/عدم شباهت استفاده می‌شود. به این معنی که داده‌های مشابه را داده‌هایی تعریف می‌کنند که فاصله کمتری از یکدیگر دارند. در واقع می‌توان گفت که خوشه‌بندی، نوعی گروه‌بندی داده‌ها بر اساس شباهت آن‌ها به یکدیگر می‌باشد و هدف از خوشه‌بندی کشف ساختار داده‌ها و یافتن داده‌های مشابه می‌باشد. این مسئله در کاربرد‌های زیادی مثل ساده‌سازی داده‌ها، شباهت‌سنجی داده‌ها و یافتن االگو‌ها کاربرد دارد.

• تفاوت خوشه بندی با دسته بندی:

خوشه‌بندی برای جدا کردن مجموعه‌ای از اشیا یا داده‌ها به بخش‌های جداگانه (خوشه) است. نتیجه کار بدین صورت است که داده‌های مشابه در یک خوشه قرار می‌گیرند و اشیای متعلق به خوشه‌های مختلف به هم شبیه نیستند. خوشه‌بندی در حیطه‌های گوناگون علم کاربرد دارد و برای موارد مختلف، الگوریتم‌های خوشه‌بندی گوناگونی وجود دارد.مساله خوشه بندی یکی از مسائل پایه‌ای داده کاوی است که زیربنای بسیاری از تحقیقات در زمینه‌های مختلف بوده و راه‌حل‌های بسیاری برای آن ارائه شده است. هدف خوشه‌بندی شناسایی بخش‌هایی از داده‌ها است که شباهت زیادی به هم داشته و به بقیه‌ی داده‌ها کمتر شبیه‌اند.

خوشه‌بندی یک مسئله یادگیری بدون ناظر (Unsupervised) است و نتیجه آن منحصرا مبتنی بر تشابه بین اشیا (همراه با نمایش داده‌ها) و الگوریتم خوشه‌بندی به کار رفته است. اگر این نتیجه با منطق کاربر قابل درک باشد، می‌توان گفت که خوشه‌بندی انجام شده قابل ملاحظه و مفید است.

هدف از  الگوریتم‌های خوشه‌بندی و دسته‌بندی تقسیم یک سری داده در چندین گروه‌ است، به نحوی که اعضای یک گروه با هم دارای رابطه نزدیکی طبق یک معیار شباهت/عدم شباهت باشند. اما این دو دسته از الگوریتم‌ها تفاوت‌های بنیادین با هم دارند و به همین دلیل هر دسته در موقعیت به خصوصی استفاده می‌شوند.

تفاوت اصلی خوشه‌بندی و دسته‌بندی در آن است که خوشه‌بندی یک روش گروه‌بندی بدون مربی است در حالی که دسته بندی یک روش  با مربی است.در روش دسته بندی، ابتدا ماشین دسته‌بندی کننده‌ با دیدن یک سری مثال و پاسخ صحیح آن ها (پاسخ‌هایی که توسط مربی عرضه می‌شوند) آموزش داده می‌شود. سپس در نتیجه‌ی این داده‌های آموزشی گروه‌هایی شکل می‌گیرند که به هر یک از آنها یک کلاس یا دسته گفته می‌شود. سپس هر یک از نمونه‌های جدید در یکی از دسته‌های از قبل به وجود آمده قرار می‌گیرند.

در خوشه بندی، بر خلاف روش‌های با ناظر، هیچ اطلاع قبلی راجع به داده‌های ورودی وجود ندارد. بنابر این، در خوشه‌بندی، گروه‌ها -که از این پس آنها را خوشه می‌نامیم- و تعداد واقعی آنها از قبل معلوم نیستند. البته در اکثر روش‌ها، تعداد خوشه باید در ابتدای کار توسط کاربر مشخص گردد.

• خوشه بندی گراف و شبکه های اجتماعی:

با توجه به اهمیت خوشه‌بندی در تحلیل داده‌ها و گستردگی استفاده از گراف‌ در مدل‌سازی مسائل، خوشه‌بندی گراف‌ها به طور خاصی مورد توجه محققان قرار گرفته و روش‌های مختلفی برای آن ارائه شده است. از آنجایی که محققان رشته‌های مختلفی بر روی این مسئله کار کرده‌اند، رویکردهای متفاوتی نسبت به آن وجود دارد. ولی کلیت بیشتر این روش‌ها پیدا کردن زیرگراف‌هایی است که ارتباط درونی زیاد و ارتباطات بیرونی کمی دارند.

به این دلیل که مفهوم جامع و مانعی از “ارتباط درونی زیاد” و “ارتباط بیرونی کم” وجود ندارد، در هر روش تعریفی خاصی از این موضوع شده است و بر اساس آن راه‌حلی برای آن ارائه شده است. به تعبیر دیگر می‌توان گفت که خوشه‌بندی یک مسئله بهینه‌سازی است که به عنوان تابع هزینه (یا تابع هدف) آن، تعاریف متفاوتی ارائه شده است. به عنوان مثال، برخی از روش‌ها بر مبنای الگوریتم حداکثر شار-حداقل برش سعی می‌کنند خوشه‌ها را طوری پیدا کنند که شار عبوری از محل برش بیشینه شود. از طرفی برخی دیگر سعی می‌کنند با بیشینه کردن معیار پیمانگی (Modularity) خوشه‌های گراف‌ را پیدا کنند.

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

الگوریتمهای خوشه بندی به خودی خود و به صورت مستقیم قابل اعمال به مساله تشخیص انجمن در گراف نیستند. باید تبدیلاتی در این مرد صورت گیرد. از طرف دیگر اندازه‌ی بسیار بزرگ گراف‌های مورد بررسی در زمینه‌ی شبکه‌های اجتماعی و بیوانفورماتیک، محققین این حوزه‌ها را به سمت توسعه الگوریتم‌هایی که سربار محاسباتی پایینی داشته و قابلیت مقیاس‌پذیری بالایی دارند سوق داده است.

در زیر به عناوین مهمترین روش ها و الگوریتم های خوشه بندی در گراف اشاره شده است.

رو‌‌ش‌های خوشه‌بندی مبتنی بر فاصله

• روش K-Means
• روش K-Medoids.
• روش PAM
• روشCLARA
• روش OPTICS

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

• Single Linkage.
• Complete Linkage.
• Average Linkage.

روش‌های خوشه‌بندی گراف مبتنی بر پیمانگی یا ماژولاریتی (Modularity)

• روش گیروان و نیومن
• روش تیلور
• روش نیومن.
• روش Louvain

 

آدرس کانال تلگرام سایت بیگ دیتا:

t.me/bigdata_channel

آدرس کانال سروش ما:
https://sapp.ir/bigdata_channel

جهت دیدن سرفصل های دوره های آموزشی بر روی اینجا کلیک کنید.

بازدیدها: 14899