Jan 082014
 
On Wednesday, January 8, 2014 12:19 AM, Hamid Kashani <clustering_1391@yahoo.com> wrote:
با سلام
مهلت تمرین آخر دوشنبه ۷ بهمن ۱۳۹۲ تمدید شد.
ضمنا تاریخ فوق هرگز قابل تمدید نمی باشد و هیچ تمرینی پس از آن قابل قبول نخواهد بود.
موفق باشید
برادران

 

Jan 012014
 

با سلام

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

البته این فایلها در روی سایت درس نیز قرار خواهد گرفت.

در مورد درخواست برخی از دوستان در مورد‌ سری نهایی تمرین‌ها، تمرین همان تمرین قبلی است،

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

clustering project instructions


Hadi Zare, Ph.D
Assistant Professor,
Faculty of New Sciences and Technologies,
University of Tehran, Iran

clustering-exs-Coverletter clustering-exs-note1 clustering-exs-note2

Dec 162013
 

خلاصه جلسه جبرانی خوشه بندی ساعت ۵ تا ۶:۳۰ دکتر زارع ۹۲/۰۹/۲۵

Classification
فیشر :
با استفاده از توزیع گوسی روش فیشر را بدست آورد در بحث Pattern Recognition

داده ها را به دو دسته train و test تقسیم می کنیم
اگر بتوانیم یک جدا ساز ساده تعیین کنیم برای داده های تست عملکرد خوبی داشته باشیم

nearest Neighbor در صورت اضافه شدن داده جدید ،
یک پیش پردازش برای کاهش بعد انجام می دهیم
و معمولا از Feature Selection برای بیرون انداختن داده های نامربوط استفاده می کنیم

برای تشخیص پارامتر های موثر
از یکی از این سه روش می توانیم استفاده کنیم
-Forward Selection
– Backward Elimination
– Bi-Directional search

در بحث Distanse های مختلفی می توانیم استفاده کنیم ( اقلیدسی – منهتن – ماهالونوبیس )
دو تا اسم داریم Peter , Piotr
از اسم اول با ۳ عملگر می توانیم به اسم دوم برسیم
————————————
فایلهای زیر آپلود شد
Clustering Final exam
sharifi test
intro_SVM_new
classification – part 4

———————————-

920925-clustring-naive-bayes
———————————-
Naive Bayes رو معمولا بر اساس گراف می کشند

نایو بیز نسبت به Future های نامربوط حساس نیست
چون در واقع ویژگی ها از هم مستقلند اثر یک ویژگی از بین می رود
آیا می شود روش Naive Bayes را بهتر کرد ؟ بله

مزایا و معایب روش Naive Bayes:

————————————–
در امتحان نمی آید
SVM : Support Vector Machine
ماشین بردار پشتیبان
آقای vladimir vapnik مطرح کرد ۱۹۸۰
Statistical Learning Theory
Dataset – MNIC
error rate بسیار کمی داشت
اولین بار روش Kernel را با SVM مطرح کردند

اگر دو کلاس داشته باشیم و بتوانیم با یک خط جدا کنیم پس بی نهایت خط دیگر می توانیم رسم کنیم
بهترین خط را کدام در نظر بگیریم
دو خط مرزی را در نظر می گیریم و مرز تصمیم گیری را در میانگین این دو خط مرزی در نظر می گیریم

Margin را باید Maximize کنیم

KKT Conditions

 

 

سر امتحان
ماشین حساب بیارید
دندوگرام باید بکشید
K-means
GMM
PCA
Fisher

روشهای classification
Naive Bayes و K-nearest Neighbor را باید بلد باشد
h.zare@ut.ac.ir
مقاله ها را به این ایمیل بفرستید

تا ۱۵ بهمن تاریخ نحویل پروژه هست

 

 

Dec 142013
 

نوشته های تدریس یار درس خوشه بندی استاد حمیدرضا برادران کاشانی

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

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

بنابراین دوستانی که در تمرین های گذشته کارشان به نظرشان اشکالات یا کاستی های داشته می توانند در این مینی پروژه جبران نمایند.
باز هم تاکید می کنم که بهترین فردی که در هر گروه بهترین و کاملترین گزارش در آن
گروه را ارائه دهد معیاز ارزیابی آن گروه می باشد.
ضمنا تمرین فیشر را نیازی نیست کسی نجام دهد
این تمرین را به عنوان آخرین تمرین درس در نظر گرفته ایم.
لطفا تمرین را دانلود کنید همه چیز اعلام شده
پیاده سازی نمی خواهد فقط گزارش کامل
روش هایی که هدفشان تمایز بین داده های دو یا چند کلاس است مثل فیشر دیگر چه روش هایی داریم
در مورد تمرین سوالی نیست؟
روش VQ
, Kmeans
چه روش های مشابهی وجود دارند

در تمامی گروه ها هدف بیان توابع cost function جدید است
اسم تمرین در سایت shw2 است

دوستان اگر با تمرین کمی کار کنند
بعد می توانند سوالاتشات را از طریق ایمیل clustering_1391 – yahoo بپرسند

tamrin-ta-Clustering

Dec 122013
 

دانلود رکود کلاس حضوری 

 

پروژه ها را شروع کنید
تا آخر بهمن احتمالا وقت هست برای تحویل پروژه
جواب نمونه سوالات ترم گذشته
سوال ۱ :
a) درست است
b) نادرست است (تحلیل مولفه های اصلی نیست – اصلا به تعداد کلاسها توجهی ندارد )
c) نادرست ( EM در GMM بود و در سلسه مراتبی نیست )
d) درست است
e) درست است
f) اشتباه است

سوال ۲ :
a) در PCA مولفه های موثر در را مشخص می کند
b ) فیشر – خطی بودن
c) رسم نقاط – با روش فیشر حل می کنیم
SW^1(mu1-mu2)

سوال ۳ :
a) برچسب داشته باشد بهتر است
b) تعداد داده های اشتباه تقسیم بر تعداد کل مشاهدات
برای بهتر شدن و جلوگیری از Overfitting از CrossValidation میشه استفاده کرد

c) هزینه محاسباتی زیاد است – برای کاهش بعد

ابتدا باید similarity را باید حساب کنیم ( بجای محاسبه distance )
نمونه جدید را داریم

نونه سوال ترم پیش : نمونه سوال خوشه بندی – دکتر زارع

 

 

exam-response4

 

————-

 

 

 

ارائه خانم مهندس شیخیان

 

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

سلسله مراتبی ها
خوشه ها از بالا به پایین خوشه ها مشخص تر هستند ولی انباشتگیشون بیشتر است

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

مزیت Cure نسبت به سایر روشهای سلسله مراتبی تشخیص خوشه های کروی و غیر کروی را می تواند
انجام دهد

مزایای Cure حساس نبودن به شکل هست
وبه Outlier حساس نیستند چون خوشه بندی را بر اساس میانگین انجام می دهند و نه بر اساس فاصه
نقطه ها

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

در هر خوشه که تعدای نقاط را داریم
بر اساس Merge شدن نقاط هست

بقیه نقاط در مراحل بعدی با هم Merge می شوند

این روش ار random Sample استفاده می کند
خوشه بندی در دو مرحله صورت می گیرد
دیتا های ورودی پارتشین می شود
خوشه بندی ناقص انجام می شود
outlier های حذف می شود

خیلی مهم است که اندازه random Sample درست محاسبه شود.
چون ممکن است حجم محاسبات زیاد شود و یا اینکه خیلی داده ها دیده نشوند

شرط خاتمه این الگوریتم نسبت n به q هست

در سرعت این الگوریتم (Sample size و تعداد Partition ها ) بسیار مهم است

مهمترین خاصیت »: خوشه های غیر کروی هم می تواند انجام دهد
قابلیت محاسبه big data دارد
استفاده از Partitioning

———————————————————

ارائه خانم مهندس قربانی

الگوریتم Birch
برای Big Data – استفاده از الگوریتم های ساده امکان پذیر نیست
قبلا بر اساس احتمال ( یادگیری ماشین ) و یا بر اساس آمار ( روش های فاصله ) کار می کنند.

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

ولی روش Birch مشکلات روش های قدیم را ندارد

تراکم خوشه ها حول جرم را نشان می دهد

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

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

یک درخت به نام CF Tree می سازد
تا بتواند خوشه ها را با هم ادغام کند

در مثال آخر LS و SS مشخص شده اند
LS : مجموع خطی داده ها ست
SS : جمع مربعات n داده هست

هر کدام از پارامتر ها یک ارتفاعی دارند
که درخت CF انها را بالانس می کند

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

Birch

منبع : کتاب Mining of Massive  Dataset
ایده کلی : تفاوت مهم Random Sampling بود
ولی birch نقاط را تبدیل به Future می کرد

Dec 092013
 

روش فیشر

پراکنش داده ها
داده ها را از دو بعد به یک بعئ می خواهیم map کنیم

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

نام این مساله : مساله مقدار ویژه تعمیم یافته

این نمونه معمولا در امتحان می آید
یا مفهوم این که Fisher با PCA جه فرقی می کند

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

معمولا دوستان در اینورس کردن ماتریس اشتباه می کنند
جهتش هم می خواهیم که رسم کنید
——————————–

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

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

اولین قدم data Gathering هست – طبقه بندی اطلاعات اولیه جمع آوری شده

خیلی از مسایل خوشه بندی تعبیر Geo metric دارند
اگر بتوانیم Rule برایش تعریف کنیم

آقای فیشر اولین بار مساله pattern Recognition را حل کرد و داده های IRIS رو مطرح کرد

fisher

قانون که می گذاریم باید برای داده های بعدی هم خوب کار کند
هر چه مدل ساده تر باشد احتمال اینکه برای داده های بعدی هم کار کند محتمل تر است

clustering-fisher-leanear-Discriminant-Example

over fitting
به صورت simple از هم جدا کنیم

Predictive Accuracy
صحت پیش بینی
Accuracy صحت : تعداد صحیح ها تقسیم بر تعداد کل نمونه ها
خطا : تعداد اشتباهات تقسیم بر تعداد کل نمونه ها

روش k-fold :

داده ها را به دو قسمت تقسیم می کنیم
داده های train و داده های test
یک مدل را بر اساس داده های Train می سازیم و test را با آن آزمایش می کنیم
داده ها را به k قسمت مساوی تقسیم می کنیم
قدم اول : مدل را می سازم و با قسمت k ام خطای مدل را بدست می آوریم
قدم دوم : k-1 را Train در نظر می گیریم و باز خطا را بدست می آوریم

یک مقاله به صورت تجربی (imperical ) بخش ها را به ۱۰ قسمت تقسیم کردند
و ما هم اکثر مسایل رو ۱۰-fold می گوییم
Nearest Neighbor Classifier
هر داده جدیدی که آمد فاصله اش را با کل داده های قبلی حساب کن ، سپس sort کن

کمترین فاصله ها اکثریت را پیدا می کنیم
جزء روش های Lazy محسوب می شود چون خیلی هزینه بر هست ( با محاسباتی زیاد
هست )

جلسه بعد nearest neghbor را می گوییم

 

Dec 072013
 

خلاصه درس تدریس یار خوشه بندی – ۹۲/۰۹/۱۶
فیشر دو کلاسه را جلسه قبل گفتیم

هم واریانس بین کلاسی و هم واریانس درون کلاسی را محاسبه می کردیم

از لاگرانژ استفاده نکردیم و مستقیم مشتق گرفتیم ( چون صورت و مخرج با هم ساده می شد)
که رابطه ۴٫۲۹ بدست آمد

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

——————————————
فیشر چند کلاسه :

مثلا روی داده های IRIS که چهار بعدی هست که می خواهیم به دو یا سه بعد کاهش می دهیم

فیشر حالت چند کلاسه – تعداد ابعاد از D بعد به به بیشتر از یک بعد و کمتر از D بعد هست

می خواهیم ‘D ویژگی خطی بدست بیاوریم

اگر ۴ بعد داریم می خواهیم به دو بعد کاهش بدهیم یعنی ‘D مساوی ۲ هست دوبردار باید داشته باشیم w1 و w2 داریم

رابطه ۴٫۳۹

clustering-fisher-multi





S Within جمع روی k کلاس واریانس درون کلاسی

clustering-fisher-multi-solution

یک ماتریس نسبت به دو کلاسه بیشتر داریم به اسم :
S total ماتریس کواریانس کل نمونه ها ( پراکندگی کل داده ها صرف نظر از کلاسشون )

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

متوسط هر کلاس با متوسط همه کلاس ها S Bitween

Trace : اعضای قطر اصلی را با هم جمع کنیم

برای اینکه مساله فیشر را حل کنیم Sw , Sb را باید محاسبه کنیم
S^-1w*Sb

y1 , y2 در کنار هم بردار دو بعدی کاهش یافته می شود

clustering-fisher-multi2

نکته : Rank ماتریس ( درجه ماتریس )
می خواهیم ببینیم که حداکثر به چند بعد می توانیم کاهش بدهیم

هر ماتریس درون کلاسی Rank آن ۱ است
و k تا ماتریس را که با هم جمع می کنیم Rank آن K می شود

چون تمام متوسط ها به m ربط پبدا کردند Rank k-1 می شود

پس برای IRIS به دو بعد می توانیم کاهش دهیم چون ۳ تا کلاس دارد

clustering-fisher-multi-note

——————————–
تمرین : فیشر ۳ کلاسه IRIS را انجام دهید
——————————–

تمرین مهم :
موضوع اول : K-means
Search کنید در موضوعات k-means که به آن VQ یا LBG هم می گویند
می خواهیم انواع حالت های آنرا بگویید ( weighted VQ )
مقاله های جدید را پیدا کنید
۱- انواع روش های VQ را بگویند
۲- روش دوم VQ را بهبود دادند
۳- روشهای VQ را Weighted را گفته اند
Wave Distance – چه تابع هایی را می توان به جای Distance اقلیدسی ، معیار فاصله جدید استفاده کرده

به جای تابع نرم اقلیدسی چه تابع های دیگری را گذاشته است
ترجیحا مقالاتی را پیدا کنید که Cost Function های جدید ارائه کرده اند

————————————
موضوع GMM

————————————
موضوع Kernel

————————————
موضوع Fisher

Nov 302013
 

خلاصه درس تدریس یار خوشه بندی – آقای برادران – ۹۲/۰۹/۰۹
تمرین که تا پنج شنبه ۱۴/۰۹/۹۲ تمدید شد

Fisher Linear Discriminant
جدا ساز خطی فیشر

فیشر ۲ کلاسه (C1 , C2) داریم
D بعدی هستند و می خواهیم به فضای ۱ بعدی کاهش دهیم

y=W’*X
w محور خروجی فیشر هست
y داده های تصویر شده

در جدا سازی خطی به روش فیشر، نگاشت با دید کلاسه بندی انجام می شود و شامل ۲ مرحله است :
مرحله ۱ : نگاشت در فضای D بعدی به یک بعدی یا چند بعدی
مرحله ۲ : طبقه بندی بر اساس محور های جدید

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

(m2-m1=w'(m2-m1

m2-m1 سمت چپ میانگین داده های تصویر شده هستند
m2-m1 سمت راست میانگین داده های اصلی هستند

چون نمی توانیم m2-m1 سمت راست را تغییر دهیم بایستی w را تغییر دهیم تا m2-m1 زیاد شود

برای اینکه فاصله بین کلاس ها بیشتر باشد
fisher2class1
اگر واریاس را لحاظ کنیم :

fisher2class2

پراکندکی بین دو کلاس زیاد شده
ولی پرکندگی داخل کلاس ها کم شده
که این از اهداف فیشر است

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

—————————–
– Bitween – Inter Class – ماتریس بین کلاسی Sb=(m2-m1)-(m2-m1)transpose
– Within – Intra Class ماتریس درون کلاسی

clustering-fisher2class3
برای محاسبه w این را لحاظ می کنیم که با جهت w سر و کار داریم و نه اندازه اش

clustering-fisher2class-formula

 

 

 

 

 

Nov 252013
 

خلاصه مباحث درس خوشه بندی – دکتر زارع – ۹۲/۰۹/۰۴

مبحث Kernel
و روش فیشر

نکته : یک فایل ورد یک صفحه ای Topic مقاله به همراه سال Journal بفرستید
که در موضوع کلاس باشید

تغییرات را با ماتریس کواریانس نشان می دادیم
با استفاده از تابع لاگرانژ انجام می دادیم

خلاصه PCA: اول ماتریس را Centralize می کردیم ماتریس S را می سازیم ، مقدار
ویژه و بردار ویژه را بدست می آوریم

میشه ثابت کرد اگر بخواهیم کمترین میزان Reconstruction را داشته باشیم
نگاشت تولید شده توسط PCA کمترین خطای بازیابی را می دهد
PCA یک روش Unsupervised هست
ولی روش های جدید Supervised آن هم آمده است
دقیقترین نمایش داده ها در فضای با بعد کمتر (مثل مپ کردن تصویر )
————————————–
Kernel Trick
افزایش بعد برای جدا سازی خطی

PCA را بر اساس Dot Product می خواهیم بنویسیم

کتاب Principal Component Analysis
—————————————–
بحث بعدی : fisher LDA کاهش بعد با در نظر گرفتن کلاس ها است

اشکال PCA در کاهش بعد این بود که کلاس ها با هم ترکیب می شوند

PCA-DataRepresentation-VS-DataClassification

 

روش فیشر :

 
Fisher-Linear-Discriminant

Nov 232013
 

فرمولاسیون ماکزیمم واریانس

بحث PCA
و بحث Kernel

ورودی مساله : N تا داد ها ی D بعدی
یک زیر فضا را می خواهیم بدست بیاوریم که بعد داده های جدید از بعد داده های اصلی
کمتر باشد.

پراکندگی داده های تصویر شده حداگثر شود
Max ( Variance )
بردار U فقط جهتش مهم بود

برای تصویر داده روی بردار ، داده را در بردار ضرب می کنیم
اگر اندازه یک برداری بزرگ باشد ، داده را که ضرب میکنیم مقدار بزرگتری بدست می آید

اگر فضای تصویر M بعدی را در نظر بگیریم
تصویر خطی بهینه ای که برای آن واریانس داده های تصویر شده بیشینه شود.
————————————————
Kernel Method
ابزار خیلی پر کاربرد در مسایل غیر خطی
در مساله که داده ها در فضا قرار گرفته اند که با یک خط نمی توانیم جدا کنیم
مثل دو تا شکل ماه که ترکیب شده اند

از یک سری منحنی های غیر خطی باید استفاده کنیم که Kernel این امکان را فراهم
میکند

Kernel داده ها را به فضایی با بعد بالاتر تصویر می کند (فضای وِیژگی)

Motivations – Kernet Definiation – Mercer’s Theorem – Kernel Matrix – Kernel
Construction

یکسری Classifier خطی داریم ، یکسری Label داریم
کلاس ضربدر و کلاس دایره
شکل سمت چپ کلاس اولیه است

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

داده ها را از فضای ۲ بعدی به فضای ۳ بعدی تبدیل می کنیم

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

فضای توسعه یافته را فی می گوییم

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

جلسه حضوری پنج شنبه ۷ آذر
مهلت تمرین تا جمعه ۸ آذر

 

 

Nov 182013
 

 

می خواهیم بیشترین تغییرات را حفظ کنیم
تغییرات را با واریانس نمایش می دهیم

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

مقادیر ویژه
بردار ویژه
eig(A) در متلب eigenVector و eigenValue
را به ما خواهد داد

یا SVD(A) برای هر ماتریسی یک تجزیه می
دهد
باید possitive definite باشد

از ضرایب لاگرانژ استفاده کنیم
از یک فضای p بعدی به فضای ۱ بعدی
کاهش دادیم
—————————————–
Reconstruction بازیابی

تبدیل زدیم برای کاهش بعد
ولی باید برگردانیم به فضای اولیه

PCA
برای حذف نویز در تصویر

 

Nov 162013
 

تمرین مهلت : ۴ آذر
GMM
پیاده سازی k-means
جواب خروجی های k-means بردار وزن ، کواریانس ، را به GMM می دهیم

 

روش PCA ( Pricipal Component Analysis)
یکی از روش های کاهش بعد هست

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

یا اینکه به صورت رندوم چند مولفه را حذف کنیم !!!

یا اینکه مولفه هایی را نگه داریم که بیشترین تاثیر گذاری را دارد

پس PCA روشی است که کاربرد های ( کاهش بعد ، فشرده سازی ، استخراج ویژگی ،تصویر سازی ) دارد

دو تعریف رایج برای PCA که الگوریتم یکسانی دارد :

تعریف ۱ : داده ها را در یک زیر فضا تصویر کنیم به طوری که هدفی آن واریانس داده های تصویر شده بیشینه باشد

تعریف ۲ : تصویر خطی که فاصله تصویر میانگین فاصله های مجذور شده بین نقاط داده های و تصویرهایشان ، کمینه شود.

Clustering-pca
داده های اصلی داده های قرمز رنگ هستند
از این داده های قرمز رنگ تصویری رسم می کنیم که نقاط سبز بدست می آید

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

Clustering-pca-formula-maximum-variance

فرمولاسیون ماکزیمم واریانس :

این فرمولاسیون مطابق با تعریف اول است .
مثلا ما ۱۰۰ تا داده ۴ بعدی داریم
N=100
D=4
می خواهیم واریانس تصویر داده ها حداکثر شود
در ابتدا فرض می کنیم که داده ها را در یک بعد بهینه می خواهیم تصویر کنیم

اندازه بردار اهمیتی ندارد ، جهت بردار مهم است
پس قیدی می گذاریم : Norm بردار u1 باید ۱ شود
یا اول از کل داد ه ها میانگین بگیریم بعد تصویر کنیم
میانگین داده ها ی تصویر شده را بدست آوردیم

S ماتریس کواریانس
u هم بردار
حتما این اسلاید ها را مطالعه کنید

Nov 112013
 

Data matrix
N record
each record has p features

N is very large
p is very large
both of them
N no problem, p is very large
p no peoblem, N is very large

کاهش ویژگی Feature Reduction
فرض کنیم در فضای ۱۰ بعدی کار می کنیم می خواهیم بعد ها را کاهش دهیم

بر اساس مساله کار می کنند

supervised , unsupervised
minimum Information Loss

فاصله بین کلاس ها را هم بهتر است که بیشتر کنیم

x1 تا xn مشاهدات ما هستند
که فضای p بعدی ما هستند
G ماتریس تبدیل هست

داده های با حجم زیاد Hign Dimentional را باید حجمش را کم کنیم

دسته بندی

Feature Selection : اگر p تا بعد دارم فقط با فیوچر های موثر کار کنیم

Visualization
Data Compression
Noise Removal
—————-
Application of feature reduction
Face recognition
Handwrittien digit recognition
textmining
Image retrieval
Microarray Data Analysis
Protein classification

——————
Feature Reduction Algorithms :
Unsupervised :
-latent Semantinc Indexing ( LSI) : truncated SVD
– Independent Component Analysis (ICA)
PCA
CCA

Supervised :
LDA

Semi-supervised :
Research Topics
——————–
Linear
LSI
PCA
LDA
CCA : cononical Correclation
—————————–

PCA : principal Component Analysis

 

http://www.sas.com/data-visualization/overview.html

 

 

Nov 092013
 

۹۲/۰۸/۱۸
ادامه GMM

روش EM برای مخلوط های گوسی

ضرایب مولفه های گوسی
بردار میانگین
و ماتریس های کواریانس گوسی

قلب هر الگوریتم خوشه بندی cost function آن است
که به پارامتر های الگوریتم خوشه بندی می رسیم
به ما N تا بردار ویژگی میدهند یک GMM را باید به آن Fit کنیم

تشخیص تعداد خوشه ها
۱-خروجی روش k-means را به عنوان ورودی GMM ( که بردار هستند )

ضرایب مخلوط pk را چجوری می تونیم از k-means بدست بیاریم ؟
k-means یک الگوریتم هارد هست و هر نقطه را فقط به یک خوشه اختصاص می دهد
ماتریس کواریانس = بردار ویژگی منهای متوسط ضرب در ماتریس ترانهاده
وزن ها : تعداد اعضای هر خوشه تقسیم بر تعداد کل
——————–
ورودی و خروجی GMM چه چیز هایی هستند ؟
ورودی : N تا بردار ویژگی
خروجی : پارامتر های مخلوط گوسی

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

نکته : پارامتر های GMM را نمی توانیم در اول کار محاسبه کنیم ( فرم بسته ندارد )
پس یک سری فرمول غیر بسته ای که بدست آوردیم تابع درست نمایی را محاسبه می کنیم و مداوما تکرار می کنیم تا دیگر تغییر نکند

clustering-gmm-EM-kmeans

clustering-gmm-EM-kmeans2clustering-gmm-EM-kmeans3

clustering-gmm-EM-kmeans4
ماتریس قطری ایزوتوپریک
a) خوشه بندی بر اساس رندوم گرفته
b ) در مرحله دوم : مقدار احتمال پسین را پیدا کرده
c) قسمت maximation را انجام دادیم ( متوسط ها، وزن ها ، … )
d) دوباره احتمال پسین انتخاب کردیم
e) دوباره پارامتر های توزیع پسین را انتخاب کردیم ( در مرحله پنجم )
f) مرحله بیست که تابع درستنمایی تغییر نمی کند

 

clustering-gmm-EM-kmeans-example

Nov 042013
 

خلاصه درس خوشه بندی ۹۲/۰۸/۱۳ دکتر زارع

ادامه بحث social Network

یک سری Object داریم که به هم متصل هستند

بزرگترین گراف همبند = Giant Component

Network crowd and marketing

kleinburg , jon

Community Structure یا Community detection
مفهومی هست به نام Clustering Coefficent ضریب خوشه بندی

Zacharay Karate Club
شبکه ای به عنوان Bench mark شناسایی جوامع پنهان هست
این شبکه دو بخش است
یک باشگاه – یک مربی و تعدادی هنر آموز
مربی به یک باشگاه دیگر می رود

Scientometric :به دنبال این است که شاخه مختلف علم چه ارتباطی می توان داشته باشد
و پیش بینی اینکه یک دانش جدید کجا بوجود می آید.
: information retreival

Determining Weights

Edge independent path

 

Nov 022013
 

خلاصه درس تدریس یار خوشه بندی – مهندس برادران
پارامتر گاما z k
متغیر تصادفی است که نسبت داده می شود به خوشه k ام
احتمال پیشین : پیش از اینکه x وجود داشته باشد ، فقط احتمال پیشین می دهیم

تابع توزیع نرمال

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

خوشه بندی با GMM
فرض کنیم یک GMM 3 مولفه ای را برای خوشه ها کافی است

استفاده از فقط liklihood – بردار x را اگر در هر گوسی بگذاریم و عدد بزرگتری را بدهد می گوییم مربوط به همان خوشه است

اگر پارامتر پسین هم داشته باشیم ، ممکن است در Prior هر خوشه هم ضرب کند.

اگر صورت کسر بیشتر بود تاثیری بر مخرج کسر ندارد

مخرج در خوشه بندی تاثیر ندارد

جمع prior ها در تابع GMM مساوی ۱ است

برای اینکه نرمال سازی انجام دهیم تقسیم می کنیم
چون احتمال پسین جمعش باید ۱ باشد

آیا جمع likelihood هم باید ۱ باشد ؟ خیر ، چون ممکن است داده های پرتی داشته باشیم که احتمال آن برای مرتبط شدن به هر خوشه ای بسیار کم باشد.
مهمترین رابطه GMM

[image1]

با فرض iid بودن داده ها (مستقل و یکسان )
کل داده ها را با X نمایش می دهیم
لگاریتم
log a + log b
ضرب لگاریتم که پشت خط هستند میشه جمع لگاریتم ها شون
اگر در GMM مشتق بگیریم به رابطه بسته نمی رسیم بنابراین EM ارائه شد

تابع likelihood
مشتق نسبت به میو کا ( متوسط یک خوشه مشتق می گیریم )
برای خوشه بندی یک تابع Cost تعریف می کنیم که در اینجا تابع likelihood است

Nk یک عدد اعشاری است

– ماکزیمم سازی بدون قید
– ماکزیمم سازی مقید

 

 

Oct 282013
 

خلاصه درس خوشه بندی – دکتر زارع – ۹۲/۰۸/۰۶
امتحان هفته بعد میانترم   نیست
در حد روشهای سلسله مراتبی و مباحث اولیه خوشه بندی – مثل نمونه سوالی که دادیم

هفته بعد امتحان میان ترم نیست
یا اینکه یک تمرین بدهیم
بحث Model Selection

Social Network

Intruduction to Social Networks
Jure Leskoves
Stanford University
مهندسی سامانه های شبکه ای
علم جدید در قرن ۲۱ هست
Big Data
Data Science

سال ۱۹۶۴ آزمایش ارسال ۱۰۰ بسته پستی به آمریکا انجام شده که حداکثر با ۶ لینک این کار انجام شده
پدیده Small World
بخشی از این را فیزیکدانان و بعد ریاضی دانان و بعد کامپیوتری ها به دنبال نتیجه گیری از شبکه های اجتماعی هستند
۶ Degree of seperated

کتاب Networks an introduction m e j newman
یک گراف کشیده از ارتباطات اینترنت

Connection Between political blogs
http://connectedthebook.com/
Networks : Organizations
ارتباط ها را با یالها نمایش می دهیم
شبکه اقتصادی

مغز انسان
Human Brain 10 -100 billions neurons
https://www.humanbrainproject.eu/

شبکه زیستی پروتئین ppi

شبکه متابولیک

برای فهم ارتباطات شبکه :
Empirical : پرسشنامه ای
Mathematical ریاضی
Algorithms الگوریتمی

اولین مدل های شبکه ای را به روش ریاضی erdus , و reny ارائه دادند

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

اقای ves vigiani – complex network بحث بخش ویروس های کامپیوتری را تشخیص داد ، رفتار دینامیک

شبکه ها برای دسترسی پذیری به اطلاعات ، جهانی شدن
Networks : Impact

Dotnet Bilioners

معرفی شبکه
ارتباطهای بیماری ها به هم

Networks Really Matter
Network یک کلکسیونی از اشیا مختلف هست که به هم وصل شده اند

Objects : Node , Vertices
Intractions : Links , edges
System : Network , Graph

نظریه گراف : نمایش ریاضی

برای تحلیل شبکه از گراف استفاده می کنیم

نمایش صحیح برای شبکه
در برخی جاها می توان نمایش یکتا ارائه داد

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

شبکه می تواند connected باشد می تواند Disconnected هم باشد .

دوستانی که مقاله فرستاده بودند ،امشب خوانده می شود
ISI جدید باشد

 

 

با کلیک روی آگهی زیر مبلغ 400 ریال به حساب من واریز می گردد

با کلیک روی آگهی زیر مبلغ 1000 ریال به حساب من واریز می گردد