X
تبلیغات
رایتل

CD: Community Detection

معرفی اولیه 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