clustering
 

سلام من دانشجوي كارشناسي ارشد هستم يه پروزه مربوط به كلاستر ينگ دارم به اين صورت هستش كه داده ها رو گرفته و بدون اينكه تعيين كنيم داده ها بايد به چند شاخه تقسيم شوند الگوريتم كلاسترين را به وسيله k-means انجام دهيم
و دسته آخر مشخص كنيم چند كلاس تشكيل مي شود مشكل من اينه كه نمي دونم چطور بايد بدون اينكه بدونم چند دسته هست الگوريتم رو پياده كنم و شرط توقف چي هستش
اگه كسي ميتونه به من كمك كنه متشكر مي شوم

سلام
طبیعت الگوریتم k-means این طور است که دسته ها را خودش مشخص می کند نه اینکه از ورودی بگیرد.شرط های توقفش هم در خود الگوریتم اعمال می شود تا آنجایی که یادم می آید روی similarityوdisimilarity خوشه ها و بین خوشه ها مانور می دهد.

1) امکان نداره بتونید بدون تعریف تعداد خوشه های مد نظر این کار رو انجام دهید. اصولا خوشه بندی روش بدون نظارت هست و خودش نمی تونه چیزی یاد بگیره

2) قانون توقف:
الگوریتم وقتی پایان می پذیرد که مرکز هندسی تغییر زیادی نکند. به عبارت دیگر، الگوریتم زمانی پایان می یابد که برای همه خوشه ها، همه رکوردهایی که در آن خوشه قرار دارند در همان خوشه باقی بمانند. همچنین هرگاه الگوریتم به معیارهای خاصی نیز برسد الگوریتم پایان پیدا می کند، مانند کاهش یافتن مقدار مجموع مربعات خطا یا sse.

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

دوست خوبم اصولا تمامی روش های خوشه بندی روی similarityوdisimilarity درون و بین خوشه ای مانور می دهند. همه روش های خوشه بندی می خواهند similarity(شباهت) درون خوشه ای را افزایش دهد و disimilarity(عدم شباهت) بین خوشه ای را نیز افزایش دهند.
به عبارت دیگه اعضای داخل خوشه با هم بیشترین شباهت رو داشته باشند و این اعضا با اعضای خوشه های دیگر کمترین شباهت را داشته باشند.

اولا در الگوریتم kmeans خومان تعداد کلاستر ها را مشخص می کنیم
برای شرط پایان می توان هم تعداد تکرار مثلا 100 بار تکرار و هم می توان مجموع فاصله داده ها از مرکز کلاستر مربوط به خود را در نظر گرفت مثلا بگوییم باید کمتر از 2 بشود و یا شرطی مبنی بر این که داده ها در تکرار الگوریتم در کلاستر ها جابه جا نشوند و از همه بهتر ترکیبی از آنهاست چون امکان توی لوپ افتادن وجود دارد

clustering
 

با تشكر از توجه تمامي دوستان عزيز
تمام مطالبي كه شما فرمودين به نوعي درست هستش
حناب astudio من كدم مشكلي كه داره در شرط توقف هتستش
اول داده ها به دو دسته تقسيم مي شوند بعد بايد يه معيار انتخاب كنيم تا يكي از كلاستر ها شكسته بشه(مثلا هر دسته كه تعداد اعضايش بيشتر بود شكسته بشه) بعد از شكستن دسته اول يه مقدار كوچك را از سنترويد دسته كه شكسته شده كم يا زياد مي كينم و آنقدر ادامه مي دهيم تا الگوريتمن متوقف بشه و.....
در پايان ما بايد به اين نتيجه برسيم كه اين داده ها چند دسته هستند
ho_gh_722@yahoo.com
اين ايميل منه كسي از دوستان اگه مي تونه كمكم كنه بهم ايمل بزنه خوشحال مي شم

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

سلام

این روشی که شما مطرح کردین همانطور که دوستمان گفتند روش k-means نیست البته روشی با همان نوع ساختار است بنام splitting LBG است شرط توقف عمومی این الگوریتم هم یک حالت سلسه مراتبی داره و تا پایان یعنی به تعداد همه موارد ادامه پیدا می کنه البته در روش بهبود نیافته این مدل یعنی LBG شرط خاتمه رسیدن به یک اعوجاج کلی که محاسبه نوعی فاصله است ادامه پیدا می کنه.
در کل اگر بخواهید باروشی مانند k-means که باید تعداد خوشه ها مشخص باشه با هر روشی مانند آن که باید تعداد را تعیین کنیم در کاربرد خاصی اطلاع از حدود آن هم نداشته باشید باید مثلا در یک بازه (از 2 تا 10) خوشه بندی را انجام دهید بعد یک معیار عمومی برای کیفیت خوشه حساب کنید و تعیین کنید که کدام خوشه مناسب تر است توجه کنید روش های عمومی محاسبه similarity و disimilarity مناسب نیست و مثلا معیار silhouette coefficient مناسب است و تعیین می کند که چه تعداد خوشه مناسب است.

خطاب به همه دوستان:

به نظر من نظرات خوب بود البته بعضی جاها من ابهام داشتم.
اولا اینکه ما اصلا مسئله مطرحه رو که اقای hossein722 مطرج کردند رو نمی دونیم. پس نظر دادن در این رابطه غیر ممکنه.
در خصوص معیارها من موافقم که معیاری مثل تکرار و یا حتی عدم جابه جایی که خودم اشاره کردم اصلا شرط قوی یا robust نمی باشد. من پیشنهادم SSE یا silhouette coefficient یا امثال اینها برای ارزیابی خوشه ها هست.
ضمنا فکر کنم آقای hossein722 باید درباره مسئله بیشتر توضیح دهند تا بشه درباره شرایط توقف یا چیزهای دیگه اظهار نظر کرد.

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

با سلام
می شود در مورد silhouette coefficient کمی توضیح دهید ممنون می شوم.

سلام

احتراما این مساله که گفتید صحیح نیست چون روش هایی وجود داره که نیاز به تعیین تعداد خوشه در ابتدا نیست مانند DBSCAN و OPTICS (این روش ها فقط دو مقدار در ابتدا نیاز داره که تصادفی تعیین میشه و یا تخمین آن راهکارهایی ساده دارد و روش OPTICS که بهبود یافته آن است و بطور خودکار مقادیر را بهبود می دهد و outlier detection را هم انجام می دهد که خیلی مزیت مناسبی است)
غیر از این روش ها روش هایی هم مانند (buble و dencule اگر درست یادم بیاد) هم وجود داره میتونه ایده هایی برای تخمین تعداد خوشه بده.

سلام:

ممنون از اطلاعات خوبتون. فکر نمی کردم کسی اینجا از روش های تراکمی خوشه بندی اطلاعات داشته باشه. کاملا درست می گید. من برای روش های ابتدایی و سادا این موضوع رو مطرح کردم. مثل k-mean, kohonen و انواع سلسله مراتبی ها. می تونیم یه تاپیک درست کنیم برای هر روش و توضیحاتی مختصر درباره هرروش بدیم. اگه موافق باشید. من مایلم هرکی هرچی بلده بیاد توی این تاپیک ها بنویسه. اینجوری خیلی عالی می شه. موافقید؟

الگوریتم silhouette coefficient
 

این روش یک روش برای ارزیابی الگوریتم های خوشه بندی بدون نظارت هست. که یه الگوریتم ساده داره. صفحه 541 منبعی که توی پیوست گذاشتم رو نگاه کنید.
این الگوریتم فاصله درون خوشه ای و برون خوشه ای را برای هر نمونه حساب می کنه و با فرمول خاص خودش میزان همبستگی هر نمونه در هر خوشه را مشخص می کنه. یه عدد بین -1 تا 1. که 1 خیلی خوب و -1 خیلی بده. یعنی اگر عضوی میزان ضریب سیلوهتش مثلا 0.9- باشه قرار گرفتن این نمونه در خوشه ای که تو اون قرار داره خیلی مناسب نیست.

خیلی ممنون از تذکرتان اما منظور بنده از طرح مفهوم similarity یک مفهوم انتزایی از فاصله است یعنی شما معیارتان از فاصله چیست؟قطعا معیار های مختلف (یا حداقل احتمالا) در تعداد خوشه ها،طرز قرار گرفتن آنها نسبت به هم،شرط توقف و.... تاثیر گذار خواهد بود.فرض کنید شما مجموعه داده ای با 30 خصوصیت دارید خوب حالا باید روی اینکه similarity چه باشد مانور بدهید.چون شما اینجا نمی توانید فضا را درک کنید که مثلا مثل فضای دو بعدی بگویید مثلا فاصله اقلیدسی(در دو بعد) مناسب است.لذا مفاهیم similarityو disimilarity مفاهیم بنیادی خوشه بندی هستند اما از یک دید جامع مفاهیمی انتزایی هستند که بسته به الگوریتمتان،فضا تان و... قابل تعریف کردن و مانور دادن هستند.
اما در پاسخ به hossein722 تا آنجا که من متوجه شدم برای کار شما الگوریتم ISOdata مناسب تر باشد(اگر درست متوجه شده باشم)هر چند kmeans هم خوب است.
ضمیمه یک اسلاید برای kmeans پیوست شده است.

با سلام
در همان kmeans اگر attribute به صورت عددی نباشد آنها را به صورت عددی در می آوریم
یک مشکل که وجود دارد اگر میزان شباهت را فاصله اقلیدسی در نظر بگیریم
رنج یک attribute از یک تا صد باشد و attribute دیگر از یک تا دو باشد و این باعث می شود تاثیر گذاری attribute اول خیلی بیشتر شود
یک راحل برای آن map کردن تمام مقادیر attribute ها در فاصله خاص می باشد
آیا کسی را حل بهتر دارد ؟

خوب اگر قرار به map کردن باشه از self organizing map ها استفاده کنیم بهتره که. در این شرایط الگوریتم Kohonen فکر کنم خوب جواب بده چون همه داده ها رو نرمالسازی می کنه و بین بازه 0 تا1 می بره پس تاثیر متغیرها بر روی هدف یکسان می شه.

اما اگر قبل از ورود داده ها به الگوریتم k-means ، اونارو نرمال کنیم فضای مسئله کاهش داده می شه و مسئله ملموس تر می شه. حتی در این موارد در مرحله پیش پردازش می شه از کاهش داده ها برای متغیرهایی که پراکندگی داده های اونها زیاده استفاده کرد. اصولا هدف خوشه بندی خلاصه سازی هستش. پس چه بهتر قبل از ورود اطلاعات به مدل این خلاصه سازی و کاهش روی داده ها انجام بشه.

با سلام
می خواستم بدونم برای محاسبه میزان شباهت از چی استفاده می کنید؟
اگر از فاصله اقلیدسی استفاده کنیم و مثلا ورودی های ما سن افراد و جنسیت باشد ! شما باشید چکار می کنید ؟
اگر آنها را بین 1 و 0 map کنید به نظر تاثیر جنسیت بیشتر می شود و............
در کل می خواستم بدونم آیا راهی وجود داره که بازه ای که باید map کنیم را به مابدهد یا معیاری دیگری که این مشکل را نداشت باشد یعنی ورودی ها ارجحیتی بر هم نداشته باشند.

دوست عزیز دارید از اصل مطلب دور می شوید. شما برای الگوریتم هایی مثل شبکه عصبی که برای پیش بینی استفاده می شوند باید داده ها را نرمال کنید که تاثیر داده ها روی متغیر هدف یکسان شود. ولی برای الگوریتم های ساده بدون نظارت خوشه بندی که اصل قضیه شباهت ها و تفاوت ها است اصلا map کردن تاثیر شندانی بر روی نتایج نداره. چون اصل بر شباهت هاست چه مشخصه ها دارای دامنه زیادی باشند چه بین 0 و 1 باشند.

سلام دوست گرامی من هم می دونم مسئله فقط میزان شباهت است ولی وقتی شما بخواهید این الگوریتم را در متلب کد کنی متوجه می شوی که پیدا کردن میزان شباهت خیلی تاثیر پذر است از رنجی که ویژگی ها دارند چون ما فاصله اقلدسی را حساب می کنیم .
مثلا اگر جنسیت را 0 و 1 نشان دهیم و سن را 0 تا 100 در نظر بگیریم متوجه می شویم که الگوریتم به جنسیت اصلا توجهی نمی کند و خوشه بندی را بر اساس سن انجام می دهد .

می تونم دقیقا بدونم روش خوشه بندی که استفاده می کنید چه روشی هست؟ با نظارت هستش یا بدون نظارت؟

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

اولا من صنایع خوندم با اینکه بچه های صنایع متلب رو خیلی دوست دارند من اصلا دوست ندارم. و پس متلب بلد نیستم. اما قوی ترین نرم افزار داده کاوی یعنی clementine رو خیلی خوب بلدم. خیلی جالب توی رنکینگ جهانی سال 2007 KDD متلب توی رده 10هم قرار داره. لینک های زیر رو ببینید:
Data Mining - Most Popular Data Mining Software (Software) - The Data Mine Wiki
Poll: Data Mining / Analytic Software Tools

متلب اصلا نرم افزار داده کاوی نیست نرم افزارهای open source داده کاوی که بشه مثل متلب code نویسی کرد توش و تخصصشون داده کاوی باشه خیلی زیاده.
البته این موضوع به خاطر استادای ایرانی هست که به روز نیستند و هنوز با نرم افزارهای سنتی کار می کنند.
در هر حال من فکر کنم با دو متغیرجنسیت که دو مقدار داره و داده سن که 100 واحد داره فقط می شه از روش های کاهش داده ها یا نرمالسازی داده ها برای یک الگوریتم بدون نظارت مثل k-means استفاده کرد. البته از لحاظ validity این روش، این روش خیلی بد روی داده های خاص مثل داده های شما عمل می کنه.
ولی باز من فکر می کنم این داده ها با همین شکل هم خوب جواب بدند. مثلا شما برای این نوع داده ها خوشه بندی رو باید بین 2 تا 10 تا خوشه بیشتر انجام ندید. چون باید این موضوع رو هم در نظر بگیرید که تعداد خوشه ها باید به نوعی منطقی باشه. البته نه منطق خیلی دقیق و قوی.

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


age sex K-Means
12 0 cluster-1
13 0 cluster-1
14 0 cluster-1
15 0 cluster-5
16 0 cluster-5
17 0 cluster-5
18 0 cluster-5
19 0 cluster-3
20 0 cluster-3
21 0 cluster-3
12 1 cluster-4
13 1 cluster-4
14 1 cluster-4
15 1 cluster-6
16 1 cluster-6
17 1 cluster-6
18 1 cluster-6
19 1 cluster-2
20 1 cluster-2
21 1 cluster-2

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

جواب قانع کننده بود؟

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

یکم دیر اینجا رو دیدم جواب دادم.

البته 100% کلمنتیاین کارهای اضافی تری انجام می ده. اگه توی فایل pdf ای که توی پوشه نرم افزار بگردی یه فایل pdf به اسم الگوریتم هست که توش همه الگوریتم هایی کلمنتاین رو توضیح داده. معمولا در هر الگوریتم روش های برای بالا بردن دقت داره.

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

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

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

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

منظور بنده این بود که شما با اکسل هم می توانید داده کاوی انجام دهید ولی اکسل نرم افزار داده کاوی نیست همان طور که متلب نیست. البته در سراسر دنیا استفاده از متلب برای داده کاوی امری غیر بعیدی نیست و در رنکینگ جهانی متلب در رده 10هم جدول نرم افزارهای داده کاوی وجود دارد. در هر صورت اگر شما با روش ها و الگوریتم ها آشنا باشید کاملا می توانید بفهمید که چه اتفاقی داره می افته و لازم نیست خودتون کد نویسی کنید.
پیشنهاد من استفاده از نرم افزار تخصصی برای داده کاوی هست مثل کلیمنتاین و sas و یا r..

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

100% تنها راه حل برای توسعه مدلها و بهینه سازی اونها باید از متلب استفاده کرد. منم باید سعی کنم با این متلب کنار بیام و بیشتر ازش استفاده کنم.