CD: Community Detection

مقاله ای کامل در خصوص تشخیص جامع در گراف

مقاله ای کامل در خصوص  تشخیص جامع در گراف

http://s8.picofile.com/file/8315208184/0906_0612.pdf.html


در این مقاله  در ابتدا به علم مدرن شبکه ها می پردازیم  که  پیشرفتهای قابل توجهی در درک ما از سیستم های پیچیده ای به ارمغان آورده است. یکی از مهم ترین ویژگی های گراف ها هستند که  نشان دهنده خروجی سیستم های واقعی یا همان ساختار جامعه یا خوشه بندی است.

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

تحلیل خوشه ای چیست؟

تحلیل خوشه ای چیست؟

اصطلاح تحلیل خوشه ای (کلاستر) که اولین بار توسط تریون در سال 1939 استفاده شد، در بردارنده الگوریتم‌ها و روش‌هایی برای گروه‌بندی موردهای مشابه (شامل افراد، اشیاء، رویدادها و ...) درون طبقات مختلف می‌باشد. سؤالی که معمولاً محققان با آن روبرو می‌شوند این است که "چگونه داده‌های مشاهده شده را درون ساختاری بامعنی سازماندهی کنند؟". تحلیل کلاستر موارد را بر اساس میزان ارتباطشان دسته‌بندی می‌کند. بنابراین افراد یک کلاستر دارای بیشترین میزان ارتباط با یکدیگر و کمترین میزان ارتباط با اعضای دیگر کلاسترها می‌باشند. از آنچه گفته شد می‌توان فهمید که تحلیل کلاستر بدون آن‌که به تشریح چرایی وجود داده‌ها بپردازد، برای کشف ساختار داده‌ها بکار می‌رود.بنابراین تحلیل کلاستر ابزاری اکتشافی است که می‌تواند ارتباطات و ساختار بین داده‌ها را که قبلاً مشهود و محسوس نبودند را آشکار نماید.در این روش هیچ فرضی در مورد تعداد گروه‌ها یا ساختمان آن‌ها در نظر گرفته نمی‌شود. دسته‌بندی کردن بر اساس مشابهت‌ها و یا فواصل انجام می‌شود.

چرا تحلیل خوشه‌ای ارزشمند است؟

اما ممکن استگروه‌های غیرقابل انتظاری ایجاد کند که احتمالاً بیانگر روابط جدیدی خواهد بود و باید مورد بررسی دقیق‌تری قرار گیرند.

 

انواع تحلیل خوشه‌ای

  1. تحلیل خوشه‌ای دو مرحله‌ای Two-Step Cluster Analysis))
  2. تحلیل خوشه‌ای –KمیانگینK-Means Cluster Analysis))
  3. تحلیل خوشه‌ای سلسله مراتبی(Hierarchical Cluster Analysis)

 

تحلیل خوشهای دو مرحله‌ای

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

وجه تمایز الگوریتم موجود در این رویه با فنون سنتی خوشه‌بندی بصورت زیر بیان می شود: 

  1. قابلیت خوشه‌بندی بر اساس متغیرهای گسسته (رسته‌ای) و پیوسته
  2. انتخاب خودکار تعداد خوشه‌ها
  3. قابلیت تحلیل کارآمد فایل داده‌های بسیار بزرگ

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

 

تحلیل خوشه‌ای Kمیانگین

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

 

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

اگر تعداد مشاهدات کم باشد و انتخاب بین چندین روش مختلف سازماندهی خوشه‌ها، تبدیل متغیرها و اندازه‌گیری عدم شباهت بین خوشه‌ها مطرح باشد، معمولاً این رویه پیشنهاد می‌شود.

در روش خوشه‌بندی سلسله مراتبی، به خوشه‌های نهایی بر اساس میزان عمومیت آن‌ها  ساختاری سلسله‌ مراتبی، معمولاً به صورت درختی نسبت داده می‌شود. به این درخت سلسله مراتبی دندوگرام می‌گویند. روش‌های خوشه‌بندی بر اساس ساختار سلسله مراتبی تولیدی توسط آن‌ها معمولاً به دو دسته زیر تقسیم می‌شوند:

 

  1. تقسیم کننده: در این روش ابتدا تمام داده‌ها به عنوان یک خوشه در نظر گرفته می‌شوند و سپس در طی یک فرایند تکراری در هر مرحله داده‌هاییکه شباهت کمتری به هم دارند به خوشه‌های مجزایی شکسته می‌شوند و این روال تا رسیدن به خوشه‌هایی که دارای یک عضو هستند ادامه پیدا می‌کند.

 

  1. متراکم شونده: در این روش ابتدا هر داده‌ به عنوان خوشه‌ای مجزا در نظر گرفته می‌شود و در طی فرایندی تکراری در هر مرحله خوشه‌هایی که شباهت بیشتری با یکدیگر دارند، ترکیب می‌شوند تا در نهایت یک خوشه و یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتم‌های خوشه‌بندی سلسله مراتبی متراکم شونده رایج می‌‌توان از الگوریتم‌هایSingle Linkage، Average Linkage و Complete Linkage نام برد. تفاوت اصلی در بین تمام این روش‌ها به نحوه محاسبه شباهت بین خوشه‌ها مربوط می‌شود.

معرفی اولیه DATASET

1-واحد داده‌کاوی سایت دانشگاه UCI

ده‌ها دیتاست رایگان در زمینه‌های مختلف در این آدرس قابل دسترسی است:

https://archive.ics.uci.edu/ml/datasets.html

2- دیتاست‌های عمومی سایت گوگل:

http://www.google.com/publicdata/directory



تفاوت Dataset و دیتا View

DataSet‌ در واقع یک منبع منفصل از داده هاست به این معنی که به محل اصلی داده ها دائم وصل نیست و در هنگام بارگذاری داده ها را از منبع آنها مثل SqlServer یا Access خوانده و در خود ذخیره می کند و دیگر نیازی به اتصالات و فراخوانی های پی در پی و زائد به منبع اصلی داده ها ندارد.

اما DataView چیست و فرق آن با DataSet ؟
یک DataSet در اصل می تواند View های مختلفی داشته باشد.DataView ها زیرمجموعهء DataSet ها هستند.
یک DataView میتواند دقیقا همان اطلاعات یا مقدار کمتر از اطلاعات یک DataSet را نمایش دهد.
هر DataSet یک DataView دارد که اگر آنرا تعریف نکنیم (۰)DataView است.
وقتی چیزی را به DataSet بایند (Bind) می کنیم یعنی به(۰)dataset.dataview بایند کرده ایم.

DataView دیدگاه خاصی از داده ها هستند که قابلیت سفارشی سازی دارند یعنی می توانیم آنرا فیلتر کنیم یا مرتب سازی کنیم و … ولی داده ای اصلی همچنان بدون تغییر در DataTable قرار دارند.

معیار و شاخص های ارزیابی

« شاخص های شباهت توپولوژیک »

 به طور کلی به سه گروه طبقه بندی داریم : استراتژی های مبتنی بر شباهت ، الگوریتم‌های احتمال حداکثر و مدل های احتمالی. دو روش آخر می‌توانند برای شبکه‌های بزرگ با بیش از 10000 گره وقت گیر باشند. با توجه به منافع  ما در شبکه‌های بزرگ و پراکنده با 10 گره ، تمرکز ما ابتدا بر روی اطلاعات محلی و استفاده از شاخص‌های شباهت برای مشخص نمودن احتمال تعاملات در آینده است. ما دو طبقه‌ی عمده‌ی شاخص‌های شباهت را در نظر می‌گیریم.1- مبتنی بر توپولوژیک 2- ویژگی گره.

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

جدول شماره 1 شاخص‌های انتخاب شده در پیشگویی لینک را نشان میدهد . ما مجاور گره‌ی u را به صورت (u)={v ∈ V|eu.v ∈ E} تعریف می‌کنیم، که در آن G=(V , E) شبکه‌ای است شامل راس‌های (V) و لبه‌های (E) . درجه‌ی گره‌ی u با ku  نشان داده می‌شود ، ماتریس مجاورت با A و مسیری با طول n  میان u, v ∈ V  با Pn (u, v) نشان داده می‌شود.

توضیحات و عملکرد شاخص

شاخص‌های شباهت توپولوژیک (علامت اختصار)

 

 فرمول و نحوه محاسبه شاخص

احتمال این که یک مجاور از u یاv مجاور، مجاور هر دوی آنهاست را اندازه‌گیری می‌کند.این سنجش روشی است برای شناسایی محتوای مشترک که در بازیابی اطلاعات معنی دار است.

شاخص جاکارد(J)

 

کمیت ویژگی‌های مشترک گره‌های u و v را تعیین می‌کند و ویژگی های نادر را بیشتر می‌کند. با توجه به این مورد در مجاورها، ضریب آدم-ادار می‌تواند برای مشخص کردن هم پوشانی مجاور میان گره‌های u وv که باعث افزایش هم پوشانی مجاورها می‌شود .

ضریب آدم-ادار(A)

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

مجاوران مشترک (c)

مجموع وزن حداقل را در مسیر های مستقیم میان u و v تقسیم می‌کند که با تعداد مسیرهای میان u وv تقسیم می‌شود و در آن تنها مسیرهایی با طول 2 و 3 به علت اندازه‌ی بزرگ این شبکه در نظر گرفته می‌شوند. ما wp را به عنوان وزن حداقل لبه ها در مسیر در نظر می‌گیریم .

وزن متوسط مسیر(p)

به گونه‌ای محاسبه می‌شود که کاتز یک شاخص جهانی در نظر گرفته شود. زمانی که   این مجموعه، همگرا با  می‌باشد.زمانی که ، سپس k تعداد مجاوران مشترک را تخمین می‌زند. با توجه به اندازه‌ی این شبکه و هزینه‌ی محاسباتی این شاخص، به n=3 بسنده می‌کنیم. ما  قرار می‌دهیم زیرا  همگرایی و تاکید بر تعداد مسیرها با طول بیش از دو، برای ما حائز اهمیت نیست. مشاهدات قبلی نشان می‌دهند که افرادی که به نظر می‌رسد مرتبط با طول مسیر n در RRN های توییتر هستند ممکن است در واقع به علت نقش داده‌های از دست رفته ، با یک مسیر کوتاه تر مرتبط شوند.

کاتز(k)

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

پیوست ترجیحی (Pr)

 

مقدار منبع ارائه شده برای یک گره را در نظر می‌گیرد و فرض می‌کند که هر گره منبع خود را در میان مجاورها به طور برابر توزیع می‌کند.

تخصیص منبع (R)

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

شاخص ترویج هاب (Hp)

زمانی که یکی از گره‌ها درجه‌ی بزرگی داشته باشد، مقسوم الیه بزرگتر خواهد بود و بنابراین Hd در حالتی که یکی از کاربران هاب باشد، کوچکتر خواهد بود.

شاخص منزوی هاب (Hd)

 

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

شاخص لیتچ هولم نیومن (Leicht–Holme–Newman) (L)

تعداد مجاورهای مشترک مربوط میانگین هندسی را اندازه‌گیری می‌کند.

شاخص سالتون (Sa)

 

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

شاخص سورنسن (So)

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

"شاخص‌های شباهت ویژگی های فردی"

شباهت Id(I)

T(u) تعداد توییت‌هایی را که برای گره‌ی u در یک هفته جمع شده‌اند، اندازه‌گیری می‌کند. این شاخص، کمیت شباهت شمارش توییت‌های دو فرد را اندازه‌گیری می‌کنند، که 1 نشان دهنده‌ی شمار‌های توییت یکسان و0نشان دهنده‌ی شمارهای توییت غیر مشابه می‌باشد.

شباهت شمار توییت (T)


در پژوهش قبلی امتیازهای(H)به عنوان میانگین امتیازهایHبرای کلمات تالیفی کاربران u وv  در طول هفته‌ی تجزیه و تحلیل، محاسبه شدند.

شباهت شادی (H)

برای یک مجموعه‌ی متشکل از 50000 کلمه‌ی به کار رفته در توییتر از 2008 تا 2011، شباهت کلمات به کار رفته توسط u و v با فاصله‌ی همینگ اصلاح شده، محاسبه می‌شود. که در آن   نشان دهنده‌ی فراوانی نرمال کاربرد کلمه‌ی nام با کاربر u می‌باشد. مقدارw(u,v) از 0 ( کاربرد کلمات غیر مشابه ) تا1(کاربرد کلمات مشابه)می‌باشد

شباهت کلمه (w)


منبع: http://lpresearch.blogfa.com


معیارهای ارزیابی

 

شاخص کاتز

این شاخص مبتنی بر مجموعه تمام مسیرها ی اثر گذار و بیانگر مجموعه ای از مسیرهای کامل و نمایی با طول معین  که نشان دهنده ی کوتاه ترین مسیربا  بیشترین وزن است.

در فرمول این شاخص β  باید کمتر از بزرگترین مقدار ویژه ماتریس A باشد زیرا برای اطمینان از همگرایی معادله این شاخص است.

شاخص LHN2))

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

شاخص میانگین رفت و آمد زمان (ACT).

معرف (X، Y) که متوسط تعداد مراحل مورد نیاز توسط حرکت کننده تصادفی با شروع از گره x برای رسیدن به گره Y، متوسط زمان رفت و آمد بین x و y است .

شاخص کسینوس بر اساس+ L.

 این شاخص اندازه گیری مبتنی بر محتوای درونی است.

شاخص پیاده روی تصادفی با راه اندازی مجدد (RWR).

این شاخص یک برنامه مستقیم از الگوریتم PageRank است. وبیانگر یک واکر تصادفی با شروع از گره xکه به طور مکرر به همسایه تصادفی با احتمال C رفت و برگشت خواهد کرد که احتمال بازگشت به گره x برابر با احتمال 1 - C است.

شاخص SimRank شبیه به LHN2

وبدین گونه تعریف می شود با فرض اینکه که اگر دو گره مشابه با هم متصل به دوگره مشابه دیگر باشند.

شاخص ماتریس جنگل (MFI)

که در آن شباهت بین x و y می تواند به عنوان نسبت تعداد ماتریسهای جنگل پوشا متعلق به ریشه یک درخت ازگره x و y است  نسبت به یک عضو از ماتریس جنگل ریشه مربوط به گره x است.

شاخص مسیر محلی (LP)

 به ارائه یک راه حل مناسب و خوب از لحاظ دقت و پیچیدگی محاسباتی می پردازدویک شاخص با در نظر گرفتن راههای محلی با افق گسترده تر از CNاست .

شاخص تصادفی پیاده روی محلی (LRW)

 برای اندازه گیری شباهت بین گره x و y، واکر تصادفی در ابتدا در گره x قرار داده و در نتیجه تراکم اولیه با هر مرحله tافزایش می یابد.

شاخص تصادفی منطبق بر پیاده رویSRW))

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

 

شاخص شباهت شمار توییت (T)

T(u) تعداد توییت‌هایی را که برای گره‌ی u در یک هفته جمع شده‌اند، اندازه‌گیری می‌کند. این شاخص، کمیت شباهت شمارش توییت‌های دو فرد را اندازه‌گیری می‌کنند، که 1 نشان دهنده‌ی شمار‌های توییت یکسان و 0 نشان دهنده‌ی شمارهای توییت غیر مشابه می‌باشد.

شاخص شباهت شادی (H)

در پژوهش قبلی امتیازهای(H)به عنوان میانگین امتیازهایHبرای کلمات تالیفی کاربران u وv  در طول هفته‌ی تجزیه و تحلیل، محاسبه شدند.

شاخص شباهت کلمه (w) 

برای یک مجموعه‌ی متشکل از 50000 کلمه‌ی به کار رفته در توییتر از 2008 تا 2011، شباهت کلمات به کار رفته توسط u و v با فاصله‌ی همینگ اصلاح شده، محاسبه می‌شود. که در آن   نشان دهنده‌ی فراوانی نرمال کاربرد کلمه‌ی nام با کاربر u می‌باشد. مقدارw(u,v) از 0 ( کاربرد کلمات غیر مشابه ) تا1(کاربرد کلمات مشابه)می‌باشد

 

 منبع:http://lp-dahaji.blogsky.com

<< 1 2 3 >>