جواب های میان ترم داده کاوی

جوابها رو خودم نوشتم ممکنه درست نباشن! :)

دریافت

عنوان: جواب میان ترم داده کاوی
حجم: 39.3 کیلوبایت

شبکه های جهان کوچک؟ small world networks

خب اینها یه شبکه هایی مثل شبکه های اجتماعی (ارتباط انسانها با هم) اند که با وجود اینکه حتی تصادفی هم نیست تعداد گام هایی که برای رسیدن از یه جا (نفر) به یه جای دیگه هست کمه. اگه تصادفی بود و 6 گام می رفتیم و هر آدمی 10 نفر دیگه رو می شناخت، یه میلیون نفر آدم می شناختیم. یعنی خودش خود به خود خوشه بندی شده است. (خوشه بندی = یه سری چیز رو توی یه سری مجموعه بذاریم بدون اینکه از قبل بدونیم چی اند).

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

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

روشهایی که برای ساختن یه شبکه ی جهان کوچک (طبیعی) دادن:

یک گراف منظم رو تصادفی لینک هاش رو عوض کنیم...Watts and Strogatz   FreeNet 

ادامه دارد!

simrank

یادآوری می کنم من منبع غیر موثق ام و مسئولیت غلط بودن حرفهام هم به عهده نمی گیرم.

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

توی یه روش دیگه (شباهت مقاله ها) میان تعداد اونهایی که به هر دو تا لینک دارن رو حساب می کنن (شبیه جاکارده اینجا) و یکی دیگه هم تعداد اونهاییه که هر دوی اینها بهش لینک دادن. حالا simrank می خواد اینها رو تعمیم بده، یعنی به جای اینکه فقط یک قدم قبل رو ببینه، چند قدم قبل رو ببینه.

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

بعد بازگشتی میان حسابش می کنن:

شباهت هر کس با خودش یکه.

در بقیه موارد شباهتش جمع فاصله ی گره های ورودی به اون گره ها تقسیم بر تعدادشونه. تعدادشون که میشه حاصل ضرب تعداد گره های ورودی به x در تعداد گره های ورودی به y. یه ضریب هم توش ضرب می کنن.

شباهتش به random walk هم احتمالا توی اینه که اون گره ای که می خوایم شباهتش رو با x حساب کنیم (مثلا y) یه جایی توی گرافه و باید به مقصد x برسیم. خب توی random walk که می دونیم با بینهایت تا گام حتما میرسیم، میانگین هم کمتر از دو برابر تعداد یالها ضربدر (n-1) میشه (n تعداد راسها). (این آخری رو از رو نگاه کردم. - زندگی سخت شده دیگه میانگین ها هم اون میانگین های قبلی نیستن.)

برای نامتقارن کردنش هم توان 2 ی تعداد یالهای ورودیش رو توش ضرب می کنن.

الآن به اونجایی رسیدم که از random walk بودنش حرف زده، گفته که از گره های x و y شروع می کنیم و گراف رو یالهاش رو خلاف جهت میریم تا به هم برسیم. (توی random walk احتمال رفتن به هر همسایه ای مساویه).

دیگه اینکه برای خروجی هم میشه تعریفش کرد. زمانش هم O(n^2*d^2) میشه که n تعداد راسهاست و d درجه ورودی راسهاست. برای اینکه بهتر کار کنه خودش پیشنهاد کرده که راسهایی از این گراف دومیه رو که خیلی دورند در نظر نگیریم اصلا! (خودش یه شعاع فرض کرده) بعد این باعث شده بشه O(n*d^2).

مشکلی که بر می خورده این بوده که تاثیر صفحات محبوب و نامحبوب رو حذف می کرده. برای این اومدن اون نسخه ی نامتقارنش رو تعریف کردن. (توی فرمول اصلی به جای اینکه به تعداد تقسیم کنه توی تعداد صفحه دومیه ضرب کرده)

اشکالهایی که هنوز داره اینه که فقط لینک ها رو در نظر گرفته، مقیاس پذیری و کارایی اش مشکل داره (چرا؟ اینکه شعاع r گرفته بود؟) و نمیشه شباهت های دیگه رو باهاش به کار گرفت.

شباهت

برای تعریف شباهت یا همون یک منهای فاصله (در اکثر موارد) یه سری معیار هست که توشون یه سری خصوصیت ها باید باشه تا بشه با الگوریتم های مختلف ازشون استفاده کرد.

خصوصیت هایی که باید داشته باشند:

• تقارن: فاصله ی x تا y با فاصله ی y تا x برابر باشه. مثالی از یه فاصله ی نامتقارن n امین نزدیک ترین نقطه به یه نقطه ی دیگه است.
• نامساوی مثلث: (همون قضیه حمار!) یعنی مجموع فاصله x تا y و y تا z از فاصله ی x تا z بیشتر باشه. (این در واقع اصلی ترین شرطه)
• فاصله ی هر نقطه تا خودش صفر باشه.

خب معیارهایی که هست هم بعضی هاشو میگم:

• فاصله های خیلی متداول:
• فاصله ی اقلیدسی (فاصله ی مستقیم دو تا نقطه)
• فاصله ی منهتن (که روی صفحه ی چهارخونه تعداد یالهاییه که با هم فاصله دارن = جمع اختلاف xها و yهای دو نقطه)
• نُرم ها (مینکفسکی):
• برای بینهایتش میشه ماکسیمم قدر مطلق اختلاف مولفه ها (xها با هم، yها با هم، ...)
• نرم 1 = قدر مطلق = مجموع قدر مطلق اختلاف مولفه ها
• نرم های دیگه! (p-norm) = مجموع اختلاف مولفه ها رو به توان p برسونیم ریشه p-ام بگیریم.
• فاصله های گسسته
• فاصله ی n-امین نقطه یا رنک (چندمین دورترین نقطه از این نقطه است) = روی فاصله های دیگه می تونه تعریف بشه
• فاصله ی جاکارد: شباهتش رو تعریف می کنم چون آسون تره (فاصله میشه یک منهای شباهت): تعداد اعضای اشتراک به تعداد اعضای اجتماع. شکل برداری اش رو هم میگن تانیموتو.
• فاصله های جالب
• یه فاصله ی دیگه که توی الگوریتم خوشه بندی doubling ازش استفاده میشه و اسمش رو درست نمی دونم: تعداد نقطه هایی که توی دایره به شعاع r هستند به تعداد نقطه هایی که توی شعاع 2r از یه نقطه هستند.
• یه فاصله که یکی از روی این فاصله قبلیه تعریف کرده و توش یه احتمال هم توی صورت ضرب کرده.
• simrank: یه فاصله ی برداری بر مبنای random walk

این داستان ادامه دارد!

اسلاید خلاصه مقالات داده کاوی

لینک دانلود پاورپوینت خلاصه مقالات: www.di.uniba.it/~malerba/courses/bcdm/2012-13/SMOTI.pps

برای به دست آوردن خط رگرسیون هم با رگرسیون خطی میشه درآورد که اون هم میشه این طوری حساب کرد:

y-miangin(y) = (covariance(x,y)/var(x))*(x-miangin(x))

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

راستی این هم توی امتحان نیومد.

سوالات میان ترم داده کاوی شریف