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

منبع: http://www.cs.uu.nl/docs/vakken/ga/homew1-2013-her.pdf

منبع: http://www.cs.uu.nl/docs/vakken/ga/homew2-2013.pdf

منبع: http://www.cs.uu.nl/docs/vakken/ga/homew2-2013-her.pdf

جواب تکلیف 2:

1- ham sandwich cut : دوگان نقاط را حساب می کنیم. خط جدا کننده خطی است که مثلا نقاط قرمز بالای آن و نقاط آبی زیر آن هستند. در فضای دوگان می شود نقطه ای که بین LE نقاط قرمز UE نقاط آبی باشد. (اگر همدیگر را قطع کنند.)

 *الآن به این نتیجه رسیدم که باید سوالهای حل کردنی (نه اثباتی) رو بخونم چون احتمالا تو امتحان از اینها میاد.

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

سوالهای کتاب:

4.11 Give an example of a 2-dimensional linear program that is bounded, but where there is no lexicographically smallest solution.

هر LP که جواب نداشته باشد.

4.9 Suppose we want to find all optimal solutions to a 3-dimensional linear program with n constraints. Argue that Ω(nlogn) is a lower bound for the worst-case time complexity of any algorithm solving this problem.

تصویر آن روی دو بعد CH است که بهتر از nlogn نمی توان حل کرد. (reduction)

6.1 Draw the graph of the search structure D for the set of segments depicted in the margin, for some insertion order of the segments.

6.2 Give an example of a set of n line segments with an order on them that makes the algorithm create a search structure of size Θ(n2) and worst-case query time Θ(n).

همان شکل سوال بالا.

SVM

maximize margine

max(2/||w||)

اگر خطی جداناپذیر باشد، به ابعاد بالاتر می بریم.

validation of clusters of data

http://en.wikipedia.org/wiki/Silhouette_(clustering)

نمونه سوالات داده کاوی

http://4c.ucc.ie/~ymalitsky/DataMining/SampleExam_sol.pdf

2008 Midterm Exam
2007 Final Exam
2009 Midterm Exam with Solution Sketches 
2009 Final Exam with Solution Sketches 
2010 Midterm Exam with Solution Sketches 
2011 Midterm Exam with Solution Sketches
2012 Midterm Exam with Solution Sketches 
2013 Midterm Exam with Solution Sketches 
2010 Final Exam with Solution Sketches
2011 Final Exam with Solution Sketches

شبکه بیز

مثال: بر اساس داده ی جدید x وزن یالها را به روز کنید. (ضریب یادگیری 0.9)

روابط:

جواب:

در خطا Oi(1-Oi) مشتق تابع سیگموئید است.

داده های پرت

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

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

تفاوت آن با داده نوظهور: داده ی نوظهور در ابتدا داده ی پرت است اما بعدا به مدل اضافه می شود.

انواع داده ی پرت:

1- global outlier: (نقطه نامتعارف) نقطه ای که نسبت به همه ی داده ها داده ی پرت باشد.

2- contextual outlier: (داده پرت مشروط) بر اساس context مشخص شده داده ی پرت باشند. مثلا دمای هوای 10 درجه در تابستان در تهران

contextual attributes: صفت هایی که به context مربوط اند. (در این مثال فصل و شهر)

behavioral attributes: صفت هایی که مشخصات شی را معلوم می کنند و برای تشخیص داده ی پرت بودن به کار می روند. (در این مثال دما)

می شود این نوع داده پرت را تعمیم داده پرت محلی دانست که چگالی آن به نسبت اطراف آن متفاوت است.

3- collective outlier: دسته ای از داده ها که با هم نسبت به کل داده ها نامتعارف هستند نه تک تک. مثل: intrusion detection

برای تشخیص این دسته باید دسته های داده را چک کرد.

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

روشهای تشخیص داده پرت:

روشهای آماری: احتمال اینکه یک نقطه وجود داشته باشد با استفاده از توزیع نرمال حساب کنید و اگر کم بود داده ی پرت است. (پارامتری و غیرپارامتری)

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

روشهای مبتنی بر خوشه بندی: خوشه های با تعداد کم

روشهای مبتنی بر دسته بندی: داده ها را به دو دسته ی پرت و نرمال تقسیم کنید.

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

مثال:

حل: اگر حریصانه اختصاص بدهیم (maximum likelihood) و m میانگین و s انحراف معیار نمونه باشد:

m= 28.61

var = 2.29

s = 1.51

می دانیم m+3s و m-3s دارای 99.7% داده ها به شرط نرمال بودن توزیع هستند.

m+3s = 28.61+3*1.51=33.14

m-3s=28.61-3*1.51=24.08

پس داده های خارج این بازه به احتمال کمتر از 0.15% دارای توزیع نرمال هستند پس داده ی پرت هستند. داده های پرت: 24.0

حل 2: ملاک IQR: ابتدا Q1 و Q2 و Q3 را به دست می آوریم (چارکها). بعد بازه ی زیر را در نظر می گیریم و هر داده خارج آن را پرت اعلام می کنیم:

IQR = Q3-Q1

interval = [Q1-1.5IQR, Q3+1.5IQR]

در این بازه 99.3% داده ها قرار دارند.

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

روشهای غیرپارامتری

مثال: هیستوگرام: 

کل بازه ی 0 تا 5 روی محور x را که جمع کنیم 99.8 می شود یعنی 0.02% داده ها خارج این بازه و پرت هستند. چون داده ها نامنفی اند پس مربوط به بیشتر از 5 است (یعنی 5000$) = داده های پرت

یعنی داده های پرت داده هایی هستند که در نمودار ناچیز بوده اند.

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

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

بر مبنای grid : قبل از محاسبه ی فاصله ی دو به دو هرس می کنیم، به این صورت که فقط خانه های اطراف را چک می کنیم:

یک grid می سازیم و از هر نقطه یک دایره به شعاع r/2 می زنیم اگر نقطه ی دیگری درون این دایره بود همچنان آن خانه grid سطح یک است در غیر این صورت سطح 2 می شود. همه ی نقاط سطح 2 داده ی پرت هستند و همه ی نقاط سطح 1 داده ی پرت نیستند.

بر مبنای چگالی: همان روش k نزدیک ترین همسایه که در ابتدای همین نوشته گفته شد.

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

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies)

یک روش افزایشی که در آن یک درخت ویژگی خوشه بندی (CF-tree) را به صورت افزایشی می سازیم.

1- از روی داده های حافظه یک CF-tree اولیه بساز.

2- یک روش خوشه بندی را به کار ببر تا برگهای CF-tree را خوشه بندی کنی.

Clustering Feature (CF):  CF = (N, LS, SS)

که در آن LS جمع خطی داده ها و N تعداد داده ها و SS جمع توان دوم آنهاست. در هر گره میانی جمع CF گره های فرزند آن است.

تنها برای داده های عددی قابل استفاده است.

در الگوریتم BIRCH، درخت ویژگی (CF-Tree) دو پارامتر تعداد فرزندان (branching factor) و threshold ( حداکثر قطر زیرخوشه های برگهای آن زیر درخت) را دارد.

پایین ترین سطح درخت (برگها) بینشان لیست پیوندی دو طرفه است.

قطر خوشه:

الگوریتم:

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

ایرادها:

به ترتیب وابسته است.

چون حداکثر تعداد در هر برگ داریم، خوشه هایی که می سازد طبیعی نیستند.

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

CHAMELEON ( Hierarchical Clustering using dynamic modeling)

تعریف inter connectivity: جمع وزن یالهای بین دو خوشه

تعریف فاصله ی بین خوشه ای: min cut (وزن یالهایی که باید قطع کنیم تا دو خوشه جدا شوند)

ادغام: آنهایی که فاصله شان از یک حد آستانه کمتر باشد ادغام می کند.

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

(برای فاصله بین دو خوشه وزن mincut را به جای مجموع بذارید.)

ارزیابی خوشه بندی

1- آزمون یکنواخت بودن: چک کنید که توزیع تصادفی نقاط همین خوشه ای که شما پیدا کردید تولید نکند.

راه انجام: n نقطه تصادفی از D (مجموعه نقاط اولیه) انتخاب کنید و فاصله شان را تا نزدیک ترین همسایه شان در D پیدا کنید (x) و یکبار دیگر n نقطه تصادفی انتخاب کنید و فاصله ی هر کس را تا نزدیک ترین همسایه شان در D پیدا کنید که جزو همین نقاط نباشد (y). شاخص Hopkin را برای آن حساب کنید:

اگر توزیع تصادفی باشد این مقدار به 0.5 نزدیک می شود چون مجموع xi ها و مجموع yi ها تقریبا مساوی می شود و اگر D خوشه بندی شده باشد این مقدار به 1 نزدیک می شود.

2- پیدا کردن تعداد خوشه ها:

روش Empirical: نصف جذر تعداد نقاط = تعداد خوشه ها

روش Elbow: جمع تعداد نقاط عطف منحنی واریانس درون خوشه ای

روش cross validation:

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

3- کیفیت خوشه ها:

#روش با نظارت: مقایسه با حالت بهینه (نوشته ground truth من به نظرم یعنی حالت بهینه) با شاخص های racall با BCube precision و مثل آنها را به کار ببر.

اصولی که در روش بانظارت (extrinsic) باید برای کیفیت بررسی شود:

homogeneity:(همگن بودن) آنهایی که شبیه تر هستند در یک خوشه بیفتند.

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

rag bag: داده ی پرت را در یک خوشه ی "other" یا کمکی بگذاریم نه اینکه به خوشه ها تخصیص بدهیم.

حفظ خوشه های کوچک: بین تقسیم کردن خوشه ی کوچک و بزرگ، بهتر است خوشه بزرگ را تقسیم کند.

#روش بدون نظارت: میزان تفکیک خوشه ها و میزان فشرده بودن خوشه ها. مثل: ضریب Silhouette

خوشه بندی مبتنی بر Grid

multi resolution grid data sturcture:

سلسله مراتبی از grid ها که هر سلول سطح بالاتر مجموعه ای از سلول های سطح پایین تر است.

روشها:

STING(STatistical Information Grid)

در هر سلول سطح پایین یک اطلاعات آماری (مثل مینیمم، ماکسیمم، میانگین، مجموع) یا پارامترهای یک توزیع آماری (مثل: میانگین و واریانس در نرمال؛ البته چون نمی توانیم از واریانس grid ریزتر، مقدار آن برای درشت تر را به دست بیاوریم، به جای آن توان دوم نقاط و میانگین آنها را نگه می داریم.) نگه داشته می شود. هر بار آن سلولهایی که در بازه ی اطمینان سطح فعلی قرار نمی گیرند را محاسبه کن و حذف کن. از بالا به پایین این عمل را انجام می دهیم. برای کوئری هم همین طور جواب می دهیم. ایراد این روش این است که خوشه های آن شکل عمودی و افقی دارند. (البته هر چه grid را ریزتر بگیریم این مرزها دقیقتر می شود.)

WaveCluster

با استفاده از روش wavelet

CLIQUE (CLustering In QUEst)

هم بر مبنای Grid هم بر مبنای خوشه بندی زیرفضا - هم بر مبنای چگالی هم بر مبنای grid

هر بعد را به بازه های مساوی تقسیم می کند. (در m بعد به واحدهای مکعبی)

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

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

(خیلی شبیه اون روش P3C است که ارائه ی من بود، فقط فرقش اینه که تستهای آماری کمتری انجام میده که نتیجه اش هم اینه که خوشه بندیشون با وجود سادگی و scalability خیلی نتیجه ی خوبی نمیده.)

مباحث امتحان

یکی از بچه ها به استاد ایمیل زده بود و لیست مباحث امتحان را داده بود.

> 8.5 - Model Evaluation and Selection
> 8.6 - Techniques to Improve Classification Accuracy
> 9.1 - Bayesian Belief Networks
> 9.2 - Classification by Backpropagation
> 9.3 - Support Vector Machines
> Regression
> 9.5 - Lazy Learners ( or Learning from Your Neighbors )
> 10.1 - Cluster Analysis
> 10.2 - Partitioning Methods
> 10.3 - Hierarchical Methods
> 10.4 - Density-Based Methods
> 10.5 - Grid-Based Methods

12- داده های پرت

قسمت هایی که مونده تا الآن سوال حل کردن از فصل 9 و روشهای چگالی و بعد از آن از خوشه بندی (10) و داده های پرت (فصل 12) است.