پایان ترم هندسه محاسباتی

(مال یه دانشگاه دیگه است)

خودش: http://www.cs.iastate.edu/~cs518/exams/final.pdf

جوابش: http://www.cs.iastate.edu/~cs518/exams/final-soln.pdf

خب به سبک همیشه اول من حل می کنم بعد چک می کنم.

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

http://www.cs.wustl.edu/~pless/546/lectures/l6.html

خب حالا برگردیم به حل سوالا. (آخرش نفهمیدم این مثلث بندی دوگانش اون وجه بیرونی رو میخواد یا نه!+چقدر دردناکه آدم جواب تمرینهایی که با بدبختی حل کرده بعدا پیدا کنه تو اینترنت! :|)

1- الف) هر چند ضلعی با y یکنوا رو میشه تو زمان خطی مثلث بندی کرد. درسته، چون همه اش رو میشه به اون راس اولیه وصل کرد مثلث ساخت.

ب) هر گره داخلی به جز ریشه توی kd-tree یک ناحیه مستطیلی موازی یک محور رو مشخص می کنه.

kd-tree یه درخته که هر عمقش یکی از محورهای مختصات در فضای d بعدی رو نصف می کنه. (به درد پیدا کردن نقطه ای می خوره که اول داشتیم بعد گم کردیم! :)) ) یعنی هر عمقی که میگذره یه بار نصف میشه، حالا بعد از بار اولی که نصف شد یه چیزی شبیه مستطیل میشه دیگه. (بیشتر مکعب مستطیل) چون کلا بازه اش محدوده. فکر کنم درسته. (ما که نخوندیم!) -غلطه انگار بازه اش محدود نیست اونی که بازه اش محدوده درخت بازه است.. :))

ج) درسته. یال غیر مجاز یعنی چی؟ :))

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

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

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

ز) حساب کردن تقاطع n تا نیم صفحه، از نظر محاسبه معادل ساختن CH نقاط دوگان خطوط مرزی این صفحه هاست. درسته،

2- یه درخت بازه برای مجموعه ی n تا بازه ... حافظه می گیره و می تونه بازه ی شامل یه نقطه رو در زمان ... بده. فقط دومی رو میدونم که logn میشه. دومی هم logn+k میشه! اولی n میشه.

3- با چه شرایطی arrangement مربوط به n تا خط ماکسیمم تعداد راس، یال و فیس رو داره؟

احتمالا وقتی همه خطها همدیگه رو قطع کنن! (این کافی نیست انگار: باید هیچ سه تایی هم توی یه نقطه قطع نکنند!)

4- نمی دونم منظورش اینه که جایی که می بینه بکشم یا جایی که میتونه ازش رد بشه. (منظورش این بوده که اگه حرکت کنه چه جاهایی رو نمیبینه!)

5- خوشبختانه/بدبختانه نخوندیم!

6- الف) CH نقاط S رو کشیدم بعد از رو مرزش رد شدم. (مرز بالایی نزدیک تر بود!)

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

7-دوگان: مجموعه خطوط دوگان نقطه های خط l: y=mx+b چی میشه؟

میشه یه دسته خط به مرکز m,-b که اشتراکشون یه نقطه m,-b است. (یعنی اگه کل خط رو بخوایم میشه اشتراک اونها میشه یه نقطه، اگه تک تک نقطه ها رو بخوایم میشه یه سری خط که از یه نقطه میگذرن) -- خودش که ثابت کرده گذاشته توی رابطه اش در آورده، ولی قضیه اینه که این دسته خطی که گفتم یه خط (خط عمودی) رو کم داره!

8- مثلث بندی دلانی (دقت کنید شماره سوالا رو دارم اشتباه می زنم :)) نمی دونم از کجا اشتباه شده ولی دیگه دیره!)

یکی یکی باید نقطه اضافه کنیم و با اون locally Delaney درستش کنیم. از p به سه تا راس مثلثی که توش افتاده (1) وصل می کنیم بعد یال مثلثهای زیری p و 2 و بعد مثلث جدیده با 3 فلیپ میشن. -- ساختمان داده اش انگار این طوریه که تا برگ که بری اون ناحیه رو میده.. درست نفهمیدم و نخوندیم دیگه! :)

9- دیاگرام ورونوی:

الف) ثابت کنید بزرگترین دایره ی خالی که مرکزش توی CH نقاطه روی راس دیاگرام ورونوی میفته. (راهنمایی: برهان خلف)

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

ب) ثابت کنید اگر روی CH باشد (برخلاف قسمت الف) باید روی یال دیاگرام ورونوی بیفتند.

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

ج) یک الگوریتم بدهید که این بزرگترین دایره را به دست بیاورد. زمان اجرای الگوریتم =؟

خودش گفته یه sweep با الگوریتم fortune بریم و VD بسازیم.

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

البته اون قسمتی که از روی ورونوی CH ساخته نفهمیدم (گفته یه ناحیه باز پیدا کنید و ccw حرکت کنید) ولی خب در بدترین حالت میشه جدا حساب کرد.

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

امتحان هندسه محاسباتی

مال یه دانشگاه دیگه است: http://www.cs.iastate.edu/~cs518/exams/midterm.pdf

1- سه نقطه ی p1 و p2 و p3 داریم، شرط اینکه p3 روی پاره خط p1p2 باشد با ضرب برداری چیست؟

p1p2xp1p3=0

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

اصلاحیه: این کافی نیست، چون ممکنه نقطه p3 در ادامه ی نیم خط p1p2 بیفته، پس باید یه چک دیگه هم بکنیم که این طوری میشه که از p1 و p2 به p3 دو تا بردار رسم کنیم، اگر همجهت بودن یعنی p3 بیرون پاره خطه، و اگر مخالف جهت هم بودن یعنی روی پاره خط بوده. این هم با ضرب داخلی میشه چک کرد چون کسینوس همجهت ها کسینوس صفره که میشه یک و کسینوس خلاف جهت ها کسینوس 180 درجه است که میشه منفی یک.

2- کدامیک از مجموعه های زیر محدب اند؟

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

الف) یک نقطه : به انتفای مقدم هست! (چون دو تا نقطه نداره!)

ب) یک مثلث تو خالی: نیست چون دو تا نقطه که رای نیستن به هم وصل کنیم تو این مجموعه (محیط مثلث) نیست.

ج) سهمی: نیست چون اصلا تو نداره که بخواد توش بیفته!

د) بیضی تو پر: هست

3-صحیح/غلط

الف) ؟؟

ب) جواب یک سوال برنامه ریزی خطی اگر یکتا باشه باید روی یک راس ناحیه مجاز باشه = درسته!

ج) تقاطع n تا نیم صفحه (شامل مرزها) نمی تونه یه نقطه بشه! غلطه. مثال نقضش محور مختصات!

4-تعداد مثلثهای یک مثلث بندی چند ضلعی ساده با n راس چیست؟

سه تا راس که برای یه مثلث می خوایم، هر راسی اضافه بشه یه مثلث اضافه میشه. کلا میشه n-3 به علاوه یکی میشه n-2

5- نخوندیم!

6-نخوندیم!

7-نخوندیم!

-----------------

*- doubly connected edge lists

1- فرض کنید e یک نیم یال باشه که یک قسمت مسطح رو مشخص میکنه، کدوم یکی از موارد زیر همیشه درست اند؟

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

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

ب) قبلی بعدی e خود  e میشه. درسته!

ج) نیم یال e جزو فیس مجاور e هست. درسته انگار غلطه! :))

د) فیس مجاور e = فیس مجاور بعدی e. درسته دیگه تا وقتی دوباره به e برسه همه دور یه فیس اند.

2- یه قسمت دادن بهتون که 7 تا یال e1,..,e7 داره، و سه تا فیس f1,..,f3. هر یال ei به صورت ei,a و ei,b به دو تا نیم یال تقسیم میشه. جدولها رو با توجه به شکل پر کنید.

face -- outer component -- inner component

f1 -- e3a, e1a, e2a -- e2b, e1b, e3b 

f2 -- e61, e4a, e5a --  e5b, e4b, e6b

f3 -- e7a, e7b -- e7b, e7a

half-edge -- twin -- incident face -- next -- prev

e1a -- e1b -- f2 -- e2a -- e3a

e1b -- e1a -- f1 -- e3b -- e2b

e3a -- e3b -- f2 -- e1a -- e2a

e3b -- e3a -- f1 -- e2b--e1b

e5a -- e5b -- f3-- e6a -- e4a

e5b -- e5a -- f2 -- e4b--e6b

e7a--e7b--f3--e7b--e7b

e7b--e7a--f3--e7a--e7a

3- مساله موزه هنری!

الف) گراف دوگان مثلث بندی بالا رو بکشید.

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

ب) با سه تا رنگ (اعداد 1 و 2 و3) راسهای گراف رو رنگ کنید. (دو تا از قبل رنگ شده) - این کار رو با دی اف اس انجام بدید.

این دی اف اس ای که میگه باید روی فیس ها بزنید. (راسهای گراف دوگان!)

** در این لحظه ی خاص کشف کردم که حل سوالها روی همون سایت بود! (نمی دونم چرا قبلش ندیده بودم! :دی)

این لینک: http://www.cs.iastate.edu/~cs518/exams/midterm-soln.pdf

4- الف) از رو جواب ببینید دیگه! شبیه آپدیت کردن لینک لیست میمونه فقط باید قبلی رو از روی ccw روی فیس اش تشخیص بدید!

چیزهایی که باید درست کنید: next و prev و origin و twin هستند. (حواستون باشه مثلا prev راس بعدی رو هم تغییر بدید!)

ب) گفته برای تقاطع دو یال چند تا آپدیت باید انجام بشه؟ کلا 4 تا فیس هست، هر کدوم طبق قسمت الف 12 تا آپدیت داره میشه 48 تا.

5-الف) با n تا نقطه ی داده شده یه چند ضلعی (ساده = نه لزوما محدب) بسازید که راسهاش اینها باشند. (با فرض اینکه هیچ سه نقطه ای همخط نیستند)و n>=3

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

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

ب) زمان الگوریتمتون چقدره؟ زمانش میشه زمان مرتب کردن نقاط میشه O(nlogn) چون بعدش فقط یه وصل کردنه که O(n) زمان می بره.

(زمان مال من میشه O(n3) چون باید همه ی ضلع ها رو با همه ی نقاط باقیمونده حساب کنه تا هر راسی رو اضافه کنه!)

ج) چرا این زمان بهینه است؟

( مال من که بهینه نبود! :)) )

خب من ایده ای نداشتم دیدم خودش reduce کرده sort کردن n تا عدد (x) رو به ساختن این چند ضلعی برای نقاط (x,x^2). خب اگه این چند ضلعی رو برای این نقطه ها بسازیم، چرا x ها مرتب میشن؟؟ (کسی ایده ای داره؟ :)) ) خب اگه بیایم زاویه رو حساب کنیم با یه نقطه ی گوشه میشه انتقال مبدا مختصات میشه (x-x0, x^2-x0^2) بعد زاویه اش میشه arctan(x^2-x0^2)/(x-x0) که میشه arctan(x+x0) که خب x0 که ثابته، تانژانت هم که صعودیه، پس اگه این مرتب بشه اون هم مرتب میشه! (پس ایده ای اش همون حساب کردن زاویه بود)

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

*** چه عجب تموم شد!

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

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

دریافت

عنوان: جواب میان ترم داده کاوی
حجم: 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 بر اساس سایز باید در نظر می گرفتم یا نه.

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

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