باشگاه دانشجویی کارشناسی ارشد دانشگاه امیرکبیر

خلاصه درس خوشه بندی جلسه ۹۲/۰۷/۲۹

GMM assumption
فرض می کنیم هر کلاستر تابع توزیع نرمال هست

اگر بخواهیم یک مدل آمیخته را نمایش دهیم
اگر Latent Variable ها را بدانیم
Latent Varible ها Parent های کلاستار ها هستند

aic : Akaike information Criteria
BIC :Bayesian Information Criteriaumber of cluster

می توانیم از فرمول قانون بیز استفاده کنیم

اگر تعداد داده ها زیاد باشد و شکل نمایشی آن gaussian مانند باشد استفاده از روش GMM بسیار خوب است
ولی اگر داده ها کم است از GMM استفاده نکنید

الگوریتم EM – یک فرض می گذارد
اساس کار این است که به صورت پیش فرض اطلاعات کافی نیست
و مشاهدات ناقص هست
یک متغیر zk به مساله اضافه می کند
و بر اساس متغیر پنهان (Latent variable )

هدف : با استفاده از الگوریتم EM، پارامتر های توزیع آمیخه(Mixture Model ) را بدست بیاوریم

قدم اول : مقدار دهی اولیه : Log Lokely hood را حساب می کنیم
قدم دوم : expectarion امید را حساب می کنیم
قدم سوم : مجددا پارامتر های استفاده شده را در وضعیت حاضر بدست میاریم
قدم آخر : فرض میکنیم Stop کردیم
موی کا ، سیگما کا و پای کا را بدست آوردیم
احتمال پسین هر کلاس به شرط مشاهده xi را حساب می کنیم
از قاعده بیز هر کدام که احتمالش بیشتر بود
داده کلاستر ۲ می شود
عمل انتصاب را انجام می دهیم

جلسه بعد AIC , BIC و همچنین Evaluation را می گوییم

پروژه :
برای پروژه درس از داده های شغلی تان استفاده کنید
مقاله از jornal international استفاده نکنید
از ۲۰۱۱ یا ۲۰۱۲ به بعد باشد

۹۲/۰۷/۲۰
این جلسه باقی K-means را می گوییم و در جلسه بعدی درس بعدی GMM هست

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

در LMS بفرستید
و اگر نتونسید به ایمیل clustering_1391@yahoo.com
تا روز جمعه بفرستید
محدودیت اصلی روش k-means مبنایی
چنانچه مقادیر اولیه بردار های میانگین خوشه درست و مناسب انتخاب نشود.
ممکن است J در مینیمم محلی متوقف شود.

۳ روش برای مقدار دهی اولیه الگوریتم خوشه بندی K میانگین
۱- تصادفی
۲- تقسیم باینری
۳- آماده سازی حساس به هیستوگرام

روش آماده سازی رندوم : Random Selection
در این روش الگوریتم خوشه بندی k میانگین چندین بار با مراکز اولیه رندوم اجرا شده ، مراکزی که اولین مقدار تابع هدف اعوجاج به عنوان مراکز اولیه الگوریتم خوشه بندی در نظر گرفته می شوند.

روش تقسیم باینری :Binary Splitting
۱- از کل بردار ها یک مقدار متوسط و یک مقدار انحراف استاندارد می گیرد
۲- از مقدار متوسط یک ضریبی از انحراف استاندارد مقدار با کم و به اندازه همان زیاد می کند
۳- هر خوشه را بر اساس متوسط و انحراف استاندارد به دو گروه دیگر تقسیم می کند
درنهایت به k مرکز میرسیم
مثلا به ۷ تا خوشه که رسیدیم خوشه ها را ۸ تا در نظر میگیریم

این روش نسبت به روش رندوم سریعتر و موفق تر هست

روش حساس به هیستوگرام Histogram Sensitive
این روش یک هیستوگرام را بدست می آورد( نمودار فراوانی داده ها ) Hist در متلب را تست کنید.

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

نمونه سوم را فاصله اش را با این یک نمونه پیدا می کنیم
نمونه سوم را حذف نمی کنیم بلکه به عنوان نمونه جدید در X_ref می گذاریم

مقایسه می کنیم ، با هر کدام که کمترین بود

پس سه روش K-means
RSI
BSI
HSI
هست

قلب الگوریتم خوشه بندی تابع هدف آن است.

سوال : در توزیع نرمال اینکه بردار داریم در این صورت توزیع نرمال چطور محاسبه می شود؟ منظورم در قسمت ایکس منهای میو است

۹۲/۰۷/۱۳
تدریس یار خوشه بندی

تمرین تا ۲۴ مهر فرصت داده شده

الگوریتم K-means

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

یک سری بردار ویژگی داده می شود که باید تقسیم بندی کنیم که چند دسته نقسیم می شوند.

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

تعداد پارامتر های مدل را باید بیشتر کرد

باید یک پارامتر جریمه باید گذاشت که تعداد خوشه ها خیلی زیاد نشوند

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

این برچسب ها می گویند هر داده مربوط به چه خوشه ای است
در K meas
n اندیس نمونه k هست
k بین ۱ تا ۳ تغییر پیدا می کند

برای هر نمونه X(n)
نمونه یکم در مرحله اول به چه خوشه ای تعلق دارد
توسط تابع j مجموع مجذورات بردار نمونه را حساب میکنیم

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

هدف k-means حداقل سازی
به روش تکرار شونده انجام می دهد .
اول از همه شروع الگوریتم ۳ تا مرکز اولیه را بدهد

چند تا نقطه local min می تواند داشته باشد

اهمیت دارد که Global min داشته باشد

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

فرض می کنیم میو k ثابت هست
نسبت به rnk حداقل کنیم

تعلق داده ها به خوشه ها

برچسب نمونه
ولی j را در فاز دوم نسبت که میو k حداقل کنیم

در هر فاز تابع j را پیدا میکنیم

فاز دوم اینکه چجوری میو k را انتخاب کنیم
مشتق میگیریم

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

روش K-means

EM : Expectation Maximization روش بیشینه سازی امید در K-means

محدودیت اصلی روش K-means مبنایی

روشهای دیگر : فازی C-means و gmm و کاهش بعد را در این درس بررسی میکنیم

۹۲/۰۶/۲۵
خوشه بندی Clustering

n تا رکورد داریم ، می خواهیم آنها را به k قسمت تقسیم کنیم

هدف اصلی کلاسترینگ ، گروه بندی اطلاعات

روشهای semi supervised

Complex Network
شبکه های اجتماعی
اجتماعات پنهان
شبکه های تکنولوژیک – مثل شبکه برق یک منطقه -یا شبکه فرودگاه های یک کشور

recommender system

text mining

term Document Matrix
High dimential Data با روش های خوشه بندی کوچک می کنیم

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

پستانداران ، پرندگان ، خزندگان ، ماهیان ، دوزیست

معیار ها مهم هستند
محیطی که حیوانات زندگی می کنند ( دریا ، خشکی )
یا نحوه تولید مثل

اگر معیار ها را عوض کنیم دسته بندی ها متفاوت می شود
خوشه بندی … نیست ؟

Supervised classification نیست
Simple Segmentation نیست
Results of query نیست
Graph Partitioning نیست
————————————-

fraud detection کشف تقلب در بانک ها

Domain expert ها بایستی نتایج اطلاعات را تایید کنند

دسته بندی را دو بخش می کنیم
۱- روشهای افرازی Partitional Clustering
۲- روشهای سلسله مراتبی Hirerachical Clustering
——————————————–

fuzzyClustering

دسته بندی در بانک ممکن است یک سری از اطلاعات بدرد نخور باشد
که ممکن است آنها را حذف کنیم
روشهای خوشه بندی :

Newarest Neigbor
Density-Based
Conceptual Clusters

یک سری نکات :
انواع Features
مراحل خوشه بندی
۱- feature selection
۲- proximity measure
۳- معیار
۴- الگوریتم
۵- اعتبار سنجی نتایج ( روشهای ارزیابی یا domain expert )
۶- تفسیر