داده های پرت

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

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

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

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

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) است.

روش های خوشه بندی بر مبنای چگالی

DBSCAN مخفف density based spatial clustering of applications with noise یعنی خوشه بندی مکانی بر مبنای چگالی در کاربردهای دارای نویز.

زمان الگوریتمش nlogn است اگر با اندیس گذاری مکانی پیاده سازی بشه وگرنه n2. (فکر کنم یعنی اگه بشه تو logn همسایه های یک نقطه رو پیدا کرد.)

الگوریتم:

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

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

در غیر این صورت p یک نقطه ی مرزی است و هیچ نقطه ای از طریق p به یک خوشه تعلق نمی گیره، پس به سراغ نقطه ی بعدی برو.

این کار را برای همه ی نقطه ها تکرار کن.

OPTICS(Ordering Points to Identify the Clustering Structure) یعنی مرتب کردن نقاط برای تشخیص ساختار خوشه

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

هسته: همسایه های یک نقطه که حداقل minpts نقطه دارند که در فاصله ی کمتر از epsilon هستند.

فاصله (دسترسی) هسته p با نقطه q: اگر q هسته نباشد تعریف نشده است. اگر q هسته باشد، اگر p درون همسایگی q باشد شعاع آن همسایگی و در غیر این صورت فاصله ی pq است.

توی مثال شکل سمت چپ فاصله ی هسته رو نشون میده سمت راست فاصله ی هسته ی p تا نقطه های q1 و q2 رو که هر کدوم از اونها هسته اند (فرض کنید minpts که توی شکل ننوشته طوری باشه که اینها هسته بشن مثلا 3) و q1 حالتیه که توی همسایگی اش p افتاده، q2 حالتیه که خارج همسایگی اش افتاده و فاصله ی pq شده.

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

DENCLUE: using statistical density function

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

CLARA (clustering large applications)

الگوریتم PAM را روی چند نمونه از داده ها اجرا می کند.

PAM(partition around medoids)

فکر کنم همان الگوریتم local search است. میگه k تا نقطه ی دلخواه را نماینده بگیر، اگر جای نماینده و یک نقطه عادی رو عوض کردی و وضع بهتر شد این کار رو بکن. انقدر ادامه بده که دیگه تغییری نکنه.

CLARANCE(Randomized Clara)

ایده: جستجوی تصادفی

نمونه های تصادفی از همسایه ها می سازد.

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

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

ROCK(RObust Clustering using linKs)

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

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

ملاک شباهت در ROCK: می دانیم ملاکی مثل فاصله جاکارد (تعداد اعضای اشتراک به اجتماع) کار نمی کند. (این الگوریتم مال داده های غیر عددی است. مجموعه در نظر بگیرید.)

ملاک همسایگی: اگر تعداد اعضای اشتراک آنها (با فاصله جاکارد) از یک حد آستانه بیشتر باشد همسایه اند.

ملاک لینک: تعداد همسایه های مشترک دو گره

الگوریتم: ماتریس شباهت را بر اساس ملاک لینک حساب کن.

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

وقتی داده ها زیاد باشند، از آنها نمونه برداری می کند و نمونه ها را خوشه بندی می کند.

*یک اشتباهی که در ترجمه های قبلی کردم این است که Robust رو غلط ترجمه کردم، معنی اش اینه که به خطا و نویز حساس نباشه.

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

probabilistic hierarchical clustering

احتمال maximum likelihood مربوط به هر خوشه را حساب می کنیم. اگر دو خوشه را با هم ادغام کردیم و هزینه کمتر شد این کار را انجام می دهیم.

خوشه ها از هم مستقل اند و هزینه را احتمال آنها تعریف می کنیم که می شود ضرب احتمال خوشه ها در هم.

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

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

پیشنهاد می کنم شکل بکشید چون این طوری اصلا نمیشه جواب داد! :)

7-15- روشهای خوشه بندی: شکل خوشه، پارامتر الگوریتم، محدودیت ها

روشهای ارزیابی دقت دسته بندها

hold out:

به صورت تصادفی به دو قسمت با اندازه 1/3 برای تخمین دقت و 2/3 برای ساخت مدل تقسیم می شود.

random sampling:

روش hold out را k بار تکرار کنیم و دقت را میانگین دقت دسته بندهای ساخته شده قرار دهیم.

cross validation: (k-fold)

به k زیرمجموعه افراز کنیم. k مرحله به این صورت انجام دهیم که با زیرمجموعه i-ام تست کنیم و با بقیه مدل بسازیم.

leave one out:

روش cross validation که k تعداد نمونه ها باشد. (کاربرد در داده های کم)

stratified cross validation:

روش k-fold که در آن فاصله ی داده ها در هر fold مشابه فاصله ی داده های مجموعه اصلی باشد.

Bootstrap:

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

.632 Bootstrap

pr(d unique samples) = (1-1/d)^d = 1/e = 0.368

1-0.368=0.632

که در آن d تعداد نمونه های انتخاب شده است. در این صورت دقت به صورت زیر محاسبه می شود:

accuracy(D) = 1/k*sum_i_1_k(accuracy(Ti)*0.368+accuracy(D-Ti)*0.632)

Ti = training set in i-th step (1<=i<=k)

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

می توانیم از توزیع نرمال یا از توزیع t استفاده کنیم.

Null Hypothesis: دسته بندهای M1 و M2 مثل هم عمل می کنند. (باید این فرض را رد کنیم)

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

significance level/2= confidence limit

(به دلیل تقارن توزیع)