Artificial Intelligence - هوش مصنوعی  
انجمن را در گوگل محبوب کنيد :

بازگشت   Artificial Intelligence - هوش مصنوعی > یادگیری (Learning) > خوشه بندی(Clustering)


 
تبليغات سايت
Iranian Association for the Advancement of Artificial Intelligence
ارسال تاپيک جديد  پاسخ
 
LinkBack ابزارهاي تاپيک نحوه نمايش
قديمي ۱۲-۴-۱۳۸۸, ۱۰:۱۲ بعد از ظهر   #1 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink مباني خوشه بندي!

مقدمه‌اي بر خوشه‌بندي

خوشه‌بندي را مي‌توان به عنوان مهمترين مسئله در يادگيري بدون نظارت در نظر گرفت. خوشه‌بندي با يافتن يک ساختار درون يک مجموعه از داده‌هاي بدون برچسب درگير است. خوشه‌ به مجموعه‌اي از داده‌ها گفته مي‌شود که به هم شباهت داشته باشند. در خوشه‌بندي سعي مي‌شود تا دادهها به خوشه‌هايي تقسيم شوند که شباهت بين داده‌هاي درون هر خوشه حداکثر و شباهت بين داده‌هاي درون خوشه‌هاي متفاوت حداقل شود.


شکل 1: در اين شکل نمونه‌اي از اعمال خوشه‌بندي روي يک مجموعه از داده‌ها مشخص شده است که از معيار فاصله(Distance) به عنوان عدم شباهت(Dissimilarity) بين داده‌ها استفاده شده است.

خوشه‌بندي در مقابل طبقه‌‌بندي

در طبقه‌بندي هر داده به يک طبقه (کلاس) از پيشين مشخص شده تخصيص مي‌يابد ولي در خوشه‌بندي هيچ اطلاعي از کلاسهاي موجود درون داده‌ها وجود ندارد و به عبارتي خود خوشه‌ها نيز از داده‌ها استخراج مي‌شوند. در شکل زير تفاوت بين خوشه‌بندي و طبقه‌بندي بهتر نشان داده شده است.


a


b

شکل 2: a) در طبقه‌بندي با استفاده يک سري اطلاعات اوليه داده‌ها به دسته‌هاي معلومي نسبت داده‌ مي‌شوند. در خوشه‌بندي داده‌ها با توجه به الگوريتم انتخاب شده به خوشه‌هايي نسبت داده‌ مي‌شوند
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
3ngineer (۰۴-۱۴-۱۳۹۴), dr_bijan (۰۹-۲۳-۱۳۹۲), engineer_yasin (۰۴-۲۹-۱۳۸۹), Faa916 (۰۸-۶-۱۳۹۶), farshad1362 (۰۹-۱۰-۱۳۹۰), hamedmehdihamed (۱۲-۲۶-۱۳۹۰), hamidrezas (۰۲-۲۴-۱۳۹۰), ITman2010 (۰۳-۱۹-۱۳۹۱), mozhdeh65 (۰۸-۱۹-۱۳۹۰), redeemer (۱۰-۲-۱۳۹۲), reza_kh (۰۸-۱۰-۱۳۹۰), samane_89 (۰۲-۲۵-۱۳۹۰)

  #ADS
نشان دهنده تبلیغات
تبليغگر
 
 
 
تاريخ عضويت: -
محل سكونت: -
سن: 2010
پست ها: -
 

نشان دهنده تبلیغات is online  
قديمي ۱۲-۴-۱۳۸۸, ۱۰:۱۷ بعد از ظهر   #2 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Smile

يادگيري با نظارت در مقابل يادگيري بدون‌نظارت

در يادگيري با نظارت از ابتدا دسته‌ها مشخص هستند و هر يک از داده‌هاي آموزشي به دسته‌اي خاص نسبت داده شده است و اصطلاحأ گفته مي‌شود ناظري وجود دارد که در هنگام آموزش اطلاعاتي علاوه بر داده‌هاي آموزش در اختيار يادگيرنده (Learner) قرار مي‌دهد. ولي در يادگيري بدون نظارت هيچ اطلاعاتي بجز داده‌هاي آموزشي در اختيار يادگيرنده قرار ندارد و اين يادگيرنده است که بايستي در داده‌ها به دنبال ساختاري خاص بگردد.
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
dr_bijan (۰۹-۲۳-۱۳۹۲), Faa916 (۰۸-۶-۱۳۹۶), farshad1362 (۰۹-۱۰-۱۳۹۰), hamidrezas (۰۲-۲۴-۱۳۹۰), mozhdeh65 (۰۸-۱۹-۱۳۹۰), redeemer (۱۰-۲-۱۳۹۲), reza_kh (۰۸-۱۰-۱۳۹۰)
قديمي ۱۲-۴-۱۳۸۸, ۱۰:۱۸ بعد از ظهر   #3 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Question

کاربردها

از آنجا که خوشه‌بندي يک روش يادگيري بدون نظارت محسوب مي‌گردد، در موارد بسياري مي‌تواند کاربرد داشته‌ باشد

*

در بازاريابي (Marketing): دسته‌‌بندي مشتري‌ها به دسته‌هايي بر حسب رفتارها و نيازهاي آنها از طريق مجموعه زيادي از ويژگي‌ها و آخرين خريد‌هاي آنها.
*

زيست‌‌‌شناسي (Biology): دسته‌بندي حيوانات و گياهان از روي ويژگي‌هاي آنها
*

کتابداري : دسته‌بندي کتابها
*

نقشه‌برداري شهري (City-Planning): دسته‌بندي خانه‌ها بر اساس نوع و موقعيت جغرافيايي آنها.
*

مطالعات زلزله‌نگاري (Earthquake studies): تشخيص مناطق حادثه‌خيز بر اساس مشاهدات قبلي.
*

وب (WWW): دسته‌بندي اسناد و يا دسته‌بندي مشتريان به سايتها و ....
*

داده کاوي (Data Mining): کشف اطلاعات و ساختار جديد از داده‌هاي موجود
*

در تشخيص گفتار (Speech Recognition): در ساخت کتاب کد از بردارهاي ويژگي، در تقسيم کردن گفتار بر حسب گويندگان آن و يا فشرده‌سازي گفتار
*

در تقسيم‌بندي تصاوير(Image Segmentation): تقسيم‌بندي تصاوير پزشکي و يا ماهواره‌اي
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
3ngineer (۰۴-۱۴-۱۳۹۴), dr_bijan (۰۹-۲۳-۱۳۹۲), Faa916 (۰۸-۶-۱۳۹۶), farshad1362 (۰۹-۱۰-۱۳۹۰), hamidrezas (۰۲-۲۴-۱۳۹۰), redeemer (۱۰-۲-۱۳۹۲), reza_kh (۰۸-۱۰-۱۳۹۰)
قديمي ۱۲-۴-۱۳۸۸, ۱۰:۲۰ بعد از ظهر   #4 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Cool

مسائل درگير با روش‌هاي خوشه‌بندي موجود

متأسفانه چندين مسئاله در خصوص روش‌هاي خوشه‌بندي مطرح است که هنوز به شکل کامل پاسخ داده نشده‌اند. و همچنان تلاش‌هاي بسياري به منظور حل آنها انجام مي‌گيرد.

· روش‌هاي خوشه‌بندي قادر نيستند تمامي نيازهاي مسائل را به طور هم‌زمان برآورده‌کنند.

· به دليل پيچيدگي‌ محاسباتي زياد در برخورد با مجموعه داده‌هاي بزرگ با تعداد داده ‌زياد و تعداد ويژگي‌هاي زياد براي هر داده عملي نيستند.

· به دليل وابستگي‌ شديد به تعريف معيار شباهت بين داده‌ها در مسائلي که تعريف معيار شباهت مشکل باشد نتايج مطلوبي توليد نمي‌کنند.(در داده‌ها با تعداد ويژگي‌ زياد)

· براي نتايج آنها مي‌توان تفسيرهاي مختلفي بيان کرد.


خوشه‌بندي در مقابل چندي‌سازي برداري

همان‌گونه که بحث شد، خوشه‌بندي نوعي سازماندهي داده‌ها است، بر اساس شباهتي که بين آنها تعريف مي‌شود به گونه‌اي که شباهت بين داده‌هايي که درون يک خوشه قرار مي‌گيرند، نسبت به داده‌هايي که درون خوشه‌هاي متفاوت قرار مي‌گيرند، بيشتر باشد.

در کاربردهاي ارتباطي و فشرده‌سازي داده‌ها از روشهايي به نام چندي‌سازي برداري استفاده مي‌شود که از بعضي جنبه‌ها مي‌توان آنها را معادل خوشه‌بندي در نظر گرفت. در چندي‌سازي برداري نيز داده‌ها بر اساس ميزان شباهت بين آنها به دسته‌هايي تقسيم مي شوند و هر دسته بوسيله يک بردار که به آن کلمه کد (CodeWord) گفته مي‌شود جايگزين مي‌گردد. به مجموعة اين کلماتِ کد اصطلاحأ کتابِ کد(CodeBook) گفته مي‌شود.

دربعضي از بخث‌هاي علمي بين خوشه‌بندي و چندي‌سازي برداري تفاوتهايي قائل مي‌شوند. زيرا خوشه‌بندي را يک رهيافت بدون نظارت براي تحليل داده‌ها در نظر مي‌گيرند ولي چندي‌سازي برداري را روشي براي کشف خوشه‌ها نمي‌شناسند بلکه آن را راهي براي نمايش داده‌ها با تعداد عناصر کمتر به گونه‌اي که اطلاعات از دست رفته حداقل شود، مي‌شناسند. علي‌رغم تفاوت بيان شده مي‌توان روشهاي بکار رفته در هر يک آنها را در ديگر نيز بکار برد در اينجا بين خوشه‌بندي و چندي‌سازي برداري تفاوتي قائل نمي‌شويم.
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
dr_bijan (۰۹-۲۳-۱۳۹۲), Faa916 (۰۸-۶-۱۳۹۶), hamidrezas (۰۲-۲۴-۱۳۹۰), redeemer (۱۰-۲-۱۳۹۲), reza_kh (۰۸-۱۰-۱۳۹۰)
قديمي ۱۲-۴-۱۳۸۸, ۱۰:۲۱ بعد از ظهر   #5 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Cool

روش‌هاي خوشه‌بندي

روش‌هاي خوشه‌بندي را مي‌توان از چندين جنبه تقسيم‌بندي کرد:



1- خوشه‌بندي انحصاري (Exclusive or Hard Clustering) و خوشه‌بندي با هم‌پوشي (Overlapping or Soft Clustering)

در روش خوشه‌بندي انحصاري پس از خوشه‌بندي هر داده دقيقأ به يک خوشه تعلق مي‌گيرد مانند روش خوشه‌بندي K-Means. ولي در خوشه‌بندي با همپوشي پس از خوشه‌بندي به هر داده يک درجه تعلق بازاء هر خوشه نسبت داده مي‌شود. به عبارتي يک داده مي‌تواند با نسبتهاي متفاوتي به چندين خوشه تعلق داشته باشد. نمونه‌اي از آن خوشه‌بندي فازي است.



2- خوشه‌بندي سلسله مراتبي (Hierarchical) و خوشه‌بندي مسطح(Flat)

در روش خوشه بندي سلسله مراتبي، به خوشه‌هاي نهايي بر اساس ميزان عموميت آنها ساختاري سلسله‌ مراتبي نسبت داده مي‌شود. مانند روش Single Link. ولي در خوشه‌بندي مسطح تمامي خوشه‌هاي نهايي داراي يک ميزان عموميت هستند مانند K-Means. به ساختار سلسله مراتبي حاصل از روشهاي خوشه‌بندي سلسله مراتبي دندوگرام (Dendogram) گفته مي‌شود.

با توجه با اينکه روش‌هاي خوشه‌بندي سلسله مراتبي اطلاعات بيشتر و دقيق‌تري توليد مي‌کنند براي تحليل داده‌هاي با جزئيات پيشنهاد مي‌شوند ولي از طرفي چون پيچيدگي محاسباتي بالايي دارند براي مجموعه داده‌هاي بزرگ روش‌هاي خوشه‌بندي مسطح پيشنهاد مي‌شوند.

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


همان گونه که بيان شد، در روش خوشه بندي سلسله مراتبي، به خوشه‌هاي نهايي بر اساس ميزان عموميت آنها ساختاري سلسله‌ مراتبي، معمولا به صورت درختي نسبت داده مي‌شود. به ا ين درخت سلسله مراتبي دندوگرام (dendogram) مي‌گويند. روش کار تکنيکهاي خوشه‌بندي سلسله‌مراتبي معمولا بر اساس الگوريتمهاي حريصانه (Greedy Algorithms) و بهينگي مرحله‌اي (stepwise-optimal) است. روشهاي خوشه‌بندي بر اساس ساختار سلسله مراتبي توليدي توسط آنها معمولا به دو دستة زير تقسيم مي‌شوند:



1.

بالا به پايين (Top-Down) يا تقسيم کننده (Divisive): در اين روش ابتدا تمام داده‌ها به عنوان يک خوشه در نظر گرفته مي‌شوند و سپس در طي يک فرايند تکراري در هر مرحله داده‌هايي شباهت کمتري به هم دارند به خوشه‌هاي مجزايي شکسته مي‌شوند و اين روال تا رسيدن به خوشه‌هايي که داراي يک عضو هستند ادامه پيدا مي‌کند.



2.

پايين به بالا (Bottom-Up) يا متراکم شونده (Agglomerative): در اين روش ابتدا هر داده‌ها به عنوان خوشه‌اي مجزا در نظر گرفته مي‌شود و در طي فرايندي تکراري در هر مرحله خوشه‌هايي که شباهت بيشتري با يکديگر با يکديگر ترکيب مي‌شوند تا در نهايت يک خوشه و يا تعداد مشخصي خوشه حاصل شود. از انواع الگوريتمهاي خوشه‌بندي سلسله مراتبي متراکم شونده رايج مي‌توان از الگوريتمهاي Single-Link، Average-Link و Complete-Link نام برد. تفاوت اصلي در بين تمام اين روشها به نحوة محاسبة شباهت بين خوشه‌ها مربوط مي‌شود. که در بخشهاي بعد به تشريح هر يک پرداخته خواهد شد.



نمونه‌اي از روش خوشه‌بندي سلسله مراتبي و تفاوت بين روشهاي بالا به پايين و پايين به بالا در شکل زير مشاهده مي‌شود.

شکل 3: تفاوت بين روشهاي بالا به پايين با روشهاي پايين به بالا
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
3ngineer (۰۴-۱۴-۱۳۹۴), 83202200 (۰۴-۱۶-۱۳۸۹), Amirmasoud1365 (۰۸-۲۷-۱۳۹۰), dr_bijan (۰۹-۲۳-۱۳۹۲), Faa916 (۰۸-۶-۱۳۹۶), farshad1362 (۰۹-۱۰-۱۳۹۰), hamedmehdihamed (۱۲-۲۶-۱۳۹۰), hamidrezas (۰۲-۲۴-۱۳۹۰), mahlla (۰۹-۵-۱۳۹۰), mozhdeh65 (۰۸-۱۹-۱۳۹۰), redeemer (۱۰-۲-۱۳۹۲), reza_kh (۰۸-۱۰-۱۳۹۰)
قديمي ۱۲-۴-۱۳۸۸, ۱۰:۳۳ بعد از ظهر   #6 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Lightbulb

خوشه‌بندي با روش Single-Link

اين روش يکي از قديمي‌ترين و ساده‌ترين روشهاي خوشه‌بندي است و جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. به اين روش خوشه‌بندي، تکنيک نزديکترين همسايه (Nearest Neighbour) نيز گفته مي‌شود. در اين روش براي محاسبة شباهت بين دو خوشة A و B از معيار زير استفاده مي‌شود:



که i يک نمونه داده متعلق به خوشة A و j يک نمونه دادة متعلق به خوشة B مي‌باشد. در واقع در اين روش شباهت بين دو خوشه، کمترين فاصلة بين يک عضو از يکي با يک عضو از ديگري است. در شکل زير اين مفهوم بهتر نشان‌ داده شده است


شکل 4: شباهت بين دو خوشه در روش Single-Link برابر است با کمترين فاصلة بين داده‌هاي دو خوشه


1-1-1- مثال: در اين قسمت سعي شده است تا در مثالي با فرض داشتن 6 نمونه داده و ماتريس فاصلة بين آنها که در جدول 1 نشان‌داده شده است، نحوة اعمال روش خوشه‌بندي Single-Link بهتر تشريح شود

جدول 1: ماتريس فاصلة بين 6 نمونة داده


در ابتدا هر داده به عنوان يک خوشه در نظر گرفته مي‌شود و يافتن نزديکترين خوشه در واقع يافتن کمترين فاصلة بين داده‌هاي بالا خواهد بود. با توجه به جدول 1 مشخص است که داده‌هاي 3 و 5 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با کمترين فاصلة بين 3 و يا 5 از ساير خوشه‌ها. نتيجه در جدول 2 نشان ‌داده شده است.



با توجه به جدول 2 مشخص است که داده‌هاي 1 و 2 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با کمترين فاصلة بين 1 و يا 2 از ساير خوشه‌ها. نتيجه در جدول 3 نشان ‌داده شده است.


با توجه به جدول 3 مشخص است که خوشه‌هاي (3 و 5) و 4 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با کمترين فاصلة بين (3 و 5) و يا 4 از ساير خوشه‌ها. نتيجه در جدول 4 نشان ‌داده شده است.



با توجه به جدول 4 مشخص است که خوشه‌هاي (1 و 2) و 6 کمترين فاصله را دارا هستند. و در نتيجه آنها را با هم ترکيب کرده و خوشة جديدي حاصل مي‌شود که فاصلة آن از ساير خوشه‌ها برابر است با کمترين فاصلة بين (1 و 2) و يا 6 از ساير خوشه‌ها. نتيجه در جدول 5 نشان ‌داده شده است.

در نهايت اين دو خو‌شة حاصل ا هم ترکيب مي‌شوند. نتيجه در دندوگرام شکل 5 نشان داده شده است.


شکل 5: دندوگرام مثال Single-Link
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
3ngineer (۰۴-۱۴-۱۳۹۴), dr_bijan (۰۹-۲۳-۱۳۹۲), Faa916 (۰۸-۶-۱۳۹۶), farshad1362 (۰۹-۱۰-۱۳۹۰), hamidrezas (۰۲-۲۴-۱۳۹۰), redeemer (۱۰-۲-۱۳۹۲), reza_kh (۰۸-۱۰-۱۳۹۰)
قديمي ۱۲-۴-۱۳۸۸, ۱۱:۰۸ بعد از ظهر   #7 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Exclamation

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

*خوشه‌بندي با روش Group Average Link: اين روش همانند Single-Link جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. [Webb] به اين روش Centriod Distance نيز گفته مي‌شود. در اين روش براي محاسبة شباهت بين دو خوشة A و B از معيار زير استفاده مي‌شود:


که Xi يک نمونه داده متعلق به خوشة A، Xj يک نمونه دادة متعلق به خوشة B، NA تعداد اعضاء خوشةA و NB تعداد اعضاء خوشة B است. در واقع در اين روش، شباهت بين دو خوشه فاصلة بين بردار ميانگينِ تمام اعضاء يکي با بردارِ ميانگينِ تمام اعضاء ديگري است. در شکل F4 اين مفهوم بهتر نشان‌ داده شده است.

*

خوشه‌بندي با روش Median Distance: اين روش نيز همانند Single-Link جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. در روش Group Average Link اگر يم خوشة کوچک با يک خوشة بزرگ ترکيب شود نقطة ميانگين خوشة حاصل نقطه‌اي نزديک ميانگين خوشة بزرگتر خواهد بود که در بعضي از کاربردها چندان مطلوب نيست. بدين منظور اين روش خوشه‌بندي پيشنهاد شده است که مشکل مذکور را ندارد. در اين روش از ميانة نقاط يک خوشه به‌ عنوان مرکز ثقل آن خوشه استفاده مي‌شود.


شکل 10: شباهت بين دو خوشه در روش Group Average Link برابر است با فاصله بين ميانگين نقاط دو خوشه

*

خوشه‌بندي با روش Ward:

اين روش نيز همانند Single-Link جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. در اين روش خوشه‌‌بندي براي کاهش تلفات ناشي داده‌هاي دور افتاده (Outlier) از معياري جديد براي محاسبة عدم‌شباهت بين خوشه‌ها استفاده مي‌کند. در روش Ward's از مجموع مربعات تفاضل هر داده از يک خوشه با بردار ميانگين آن خوشه به عنوان معياري براي سنجش يک خوشة استفاده مي‌شود. الگوريتم زير را مي‌توان براي روش Ward در نظر گرفت.

1.

ابتدا هر داده به عنوان يک خوشه در نظر گرفته مي‌شود.
2.

به ازاء تمام جفت خوشه‌هاي ممکن از مجموعة خوشه‌ها آن دو خوشه‌اي که مجموع مربعات تفاضل داده‌هاي خوشة حاصل از اجتماع آنها با بردار ميانگين خوشة حاصل کمينه باشد، انتخاب مي‌شوند.
3.

دو خوشة انتخاب شده با هم ترکيب مي‌شوند.
4.

تا زماني که تعداد خوشه‌ها به تعداد مورد نظر نرسيده است، مراحل ii، iii و iv تکرار مي‌شوند
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
3ngineer (۰۴-۱۴-۱۳۹۴), atefeh.esmaili (۰۹-۳-۱۳۸۹), dr_bijan (۰۹-۲۳-۱۳۹۲), Faa916 (۰۸-۶-۱۳۹۶), reza_kh (۰۸-۱۰-۱۳۹۰)
قديمي ۱۲-۴-۱۳۸۸, ۱۱:۱۲ بعد از ظهر   #8 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink

الگوريتم خوشه‌بندي پايين به بالاي عمومي

اغلب الگوريتمهاي خوشه‌بندي سلسله مراتبي را به نحوي مي‌توان گسترش يافتة الگوريتم خوشه‌بندي Single-Link در نظر گرفت. تفاوت روشهاي مختلف در نحوة محاسبة ماتريس تشابه يا عدم تشابه (Dissimilaritye) آنها است. فرمولي بازگشتي به نام فرمول Lance-Williams تعريف شده است که عدم‌تشابه بين خوشة k و خوشة حاصل از پيوند خوشه‌هاي i و j را بيان مي‌کند:


که پارامترهاي ai، b و c بيان کنندة نوع روش خوشه‌بندي هستند و در جدول 16 مقادير مربوط به چند روش آورده شده است:

Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
83202200 (۰۴-۱۶-۱۳۸۹), aimaryam (۰۵-۱۰-۱۳۸۹), atefeh.esmaili (۰۹-۲-۱۳۸۹), dr_bijan (۰۹-۲۳-۱۳۹۲), Faa916 (۰۸-۶-۱۳۹۶), hamedmehdihamed (۱۲-۲۶-۱۳۹۰), mardin200 (۱۲-۵-۱۳۸۸), reza_kh (۰۸-۱۰-۱۳۹۰), الههsh (۱۰-۱۲-۱۳۸۹)
قديمي ۱۲-۴-۱۳۸۸, ۱۱:۲۱ بعد از ظهر   #9 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink

روش خوشه‌بندي K-Means (C-Means يا C-Centeriod)

اين روش علي‌رغم سادگي آن يک روش پايه براي بسياري از روش‌هاي خوشه‌بندي ديگر (مانند خوشه‌بندي فازي) محسوب مي‌شود. اين روش روشي انحصاري و مسطح محسوب مي‌شود.[1] براي اين الگوريتم شکلهاي مختلفي بيان شده است. ولي همة آنها داراي روالي تکراري هستند که براي تعدادي ثابت از خوشه‌ها سعي در تخمين موارد زير دارند:

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

· نسبت دادن هر نمونه داده به يک خوشه که آن داده کمترين فاصله تا مرکز آن خوشه را دارا باشد.

در نوع ساده‌اي از اين روش ابتدا به تعداد خوشه‌‌هاي مورد نياز نقاطي به صورت تصادفي انتخاب مي‌شود. سپس در داده‌ها با توجه با ميزان نزديکي (شباهت) به يکي از اين خوشه‌ها نسبت داده‌ مي‌شوند و بدين ترتيب خوشه‌هاي جديدي حاصل مي‌شود. با تکرار همين روال مي‌توان در هر تکرار با ميانگين‌گيري از داده‌ها مراکز جديدي براي آنها محاسبه کرد و مجدادأ داده‌ها را به خوشه‌هاي جديد نسبت داد. اين روند تا زماني ادامه پيدا مي‌کند که ديگر تغييري در داده‌ها حاصل نشود. تابع زير به عنوان تابع هدف مطرح است.



که ║║ معيار فاصلة بين نقاط و cj مرکز خوشة j ام است.

الگوريتم زير الگوريتم پايه براي اين روش محسوب مي‌شود:

1.

در ابتدا K نقطه به عنوان به نقاط مراکز خوشه‌ها انتخاب مي‌شوند.
2.

هر نمونه داده به خوشه‌اي که مرکز آن خوشه کمترين فاصله تا آن داده را داراست، نسبت داده‌ مي‌شود.
3.

پس تعلق تمام داده‌ها به يکي از خوشه‌ها براي هر خوشه يک نقطه جديد به عنوان مرکز محاسبه مي‌شود. (ميانگين نقاط متعلق به هر خوشه)
4.

مراحل 2 و 3 تکرار مي‌شوند تا زماني که ديگر هيچ تغييري در مراکز خوشه‌ها حاصل نشود.



مثالي براي روش خوشه‌بندي K-Means:

در شکل زير نحوة اعمال اين الگوريتم خوشه‌بندي روي يک مجموعه داده‌ که شامل دو گروه داده است نشان داده شده است. يک گروه از داده‌ها با ستاره و گروه ديگر با دايره مشخص شده اند(a). در مرحله اول نقطه‌اي به عنوان مرکز خوشه‌ها انتخاب شده اند که با رنگ قرمز نشان‌داده شده اند(b). سپس در مرحله دوم هر يک از نمونه‌ داده‌ها به يکي از اين دو خوشه نسبت داده شده است و براي هر دسته جديد مرکزي جديد محاسبه شده سات که در قسمت c نشان داده شده اند. اين روال تا رسيدن به نقاطي که ديگر تغيير نمي‌کنند، ادامه پيدا کرده است.


a


b


c

d

e

f

شکل 11: مثالي براي روش خوشه‌بندي K-Means

مشکلات روش خوشه‌بندي K-Means

علي‌رغم اينکه خاتمه‌پذيري الگوريتم بالا تضمين شده است ولي جواب نهايي آن واحد نبوده و همواره جوابي بهينه نمي‌باشد. به طور کلي روش ساده بالا داراي مشکلات زير است.

*

جواب نهايي به انتخاب خوشه‌هاي اوليه وابستگي دارد.
*

روالي مشخص براي محاسبة اولية مراکز خوشه‌ها وجود ندارد.
*

اگر در تکراري از الگوريتم تعداد داده‌هاي متعلق به خوشه‌اي صفر شد راهي براي تغيير و بهبود ادامة روش وجود ندارد.
*

در اين روش فرض شده است که تعداد خوشه‌ها از ابتدا مشخص است. اما معمولا در کاربردهاي زيادي تعداد خوشه‌ها مشخص نمي‌باشد.



الگوريتم خوشه‌بندي LBG

همان‌گونه که ذکر شد الگوريتم خوشه‌بندي K-Means به انتخاب اولية خوشه‌ها بستگي دارد و اين باعث مي‌شود که نتايج خوشه‌بندي در تکرارهاي مختلف از الگوريتم متفاوت شود که اين در بسياري از کاربردها قابل نيست. براي رفع اين مشکل الگوريتم خوشه‌بندي LBG پيشنهاد شد که قادر است به مقدار قابل قبولي بر اين مشکل غلبه کند.[7]

در اين روش ابتدا الگوريتم تمام داده‌ها را به صورت يک خوشه‌ در نظر مي‌گيرد و سپس براي اين خوشه يک بردار مرکز محاسبه مي‌کند.(اجراي الگوريتم K-Means با تعداد خوشة 1K=). سپس اين بردار را به 2 بردار مي‌شکند و داده‌ها را با توجه به اين دو بردار خوشه‌بندي مي‌کند (اجراي الگوريتم K-Means با تعداد خوشة K=2 که مراکز اوليه خوشه‌ها همان دو بردار هستند). در مرحلة بعد اين دو نقطه به چهار نقطه شکسته مي‌شوند و الگوريتم ادامه پيدا مي‌کند تا تعداد خوشة مورد نظر توليد شوند.



الگوريتم زير را مي‌توان براي اين روش خوشه‌بندي در نظر گرفت:

1.

شروع: مقدار M(تعداد خوشه‌ها) با عدد 1 مقدار دهي اوليه مي‌شود. سپس براي تمام داده‌ها بردار مرکز محاسبه مي‌شود.
2.

شکست: هر يک از M بردار مرکز به 2 بردار جديد شکسته مي‌شوند تا 2M بردار مرکز توليد شود. هر بردار جديد بايستي درون همان خوشه قرار داشته باشد و به اندازة کافي از هم دور باشند.
3.

K-Means: با اجراي الگوريتم K-Means با تعداد خوشة 2M و مراکز اوليه خوشه‌هاي محاسبه شده در مرحلة ii خوشه‌هاي جديدي با مراکز جديد توليد مي‌شود.
4.

شرط خاتمه: در صورتي که M برابر تعداد خوشة مورد نظر الگوريتم LBG بود الگوريتم خاتمه مي‌يابد و در غير اين صورت به مرحلة ii رفته و الگوريتم تکرار مي‌شود.
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
dr_bijan (۰۹-۲۳-۱۳۹۲), hmlk67 (۰۳-۱۱-۱۳۹۴), neda2 (۱۲-۴-۱۳۸۸), shadi.mahmoudi (۰۵-۳-۱۳۹۱), shahak (۱۲-۱۷-۱۳۸۸), sinakhaki (۱۲-۵-۱۳۸۸)
قديمي ۱۲-۴-۱۳۸۸, ۱۱:۴۳ بعد از ظهر   #10 (لینک دائم)
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Wink

خوشه‌بندي بر اساس چگالي

اين روشهاي خوشه‌بندي بر اين اصل استوارند که خوشه‌ها‌، ناحيه‌هايي از فضاي داده با چگالي زيادي هستند که توسط نواحي با چگالي کمتر از همديگر جدا شده‌اند. براي پياده‌سازي اين روشهاي خوشه‌بندي لازم است تا ابتدا اصطلاحاتي تعريف شوند:

چگالي نقاط محلي در نقطة P (Local Point Density) : اگر P را نقطة هستة يک همسايگي و ε شعاع همسايگي براي نقطة P در نظر گرفته شود آنگاه همسايگي به شعاع ε براي نقطة P به صورت زير تعريف مي‌شود:


به تعداد نقاط قرار گرفته شده درون يک همسايگيِ داده شده چگالي نقاط آن همسايگي گفته مي‌شود.

شکل 12: يک همسايگي براي P داراي چگالي نقاط 5

در دسترسِ مستقيمِ چگالي (Directly Density-Reachable): دادة p را در دسترسِ مستقيمِ چگاليِ q گويند اگر p درون يک همسايگي به شعاع ε با هستة q باشد. در شکل زير بهتر مي‌توان اين مفهوم را درک کرد.


شکل 13: p در دسترسِ مستقيمِ چگاليِ q قرار دارد.

در دسترسِ چگالي (Density-Reachable): دادة p را در دسترسِ چگاليِ q گويند اگر داده‌اي وجود داشته باشد که هم درون يک همسايگي به شعاع ε با هستة p و هم درون يک همسايگي به شعاع ε با هستة q باشد. در شکل زير بهتر مي‌توان اين مفهوم را درک کرد

شکل 14: p در دسترسِ چگاليِ q قرار دارد.

متصلِ چگالي (Density-Connected): دادة p را متصلِ چگاليِ q گويند اگر داده‌اي مانند o وجود داشته باشد که هم در دسترسِ چگاليِ p و هم در دسترسِ چگاليِ q باشد. در شکل زير بهتر مي‌توان اين مفهوم را درک کرد.

شکل 15: p متصلِ چگاليِ q است

خوشة مبتني بر چگالي (Density-Based Cluster): زير مجموعه‌اي غيرتهي(S) از مجموعة داده‌ها (D) که داراي دو شرط زير باشد:

§ حداکثر: اگر p درون S باشد و q در دسترسِ چگاليِ p باشد آنگاه q نيز متعلق به S باشد.

§ اتصال: هر دادة درون S متصلِ چگاليِ ساير داده‌هاي درون S باشد.



o خوشه‌بندي بر اساس چگالي (Density-Based Clustering): خوشه‌بندي بر اساس چگالي بر روي مجموعة دادة D مجموعه‌اي به صورت {S1, …, Sn, N} است که :

§ S1, …, Sn تمام خوشه‌هاي مبتني چگاليِ درون D است.

§ N=D\{ S1, …, Sn } مجموعة نويز خوانده مي‌شود.



شکل 16: خوشه‌بندي بر اساس چگالي

الگوريتم خوشه‌بندي براساس چگالي DBSCAN: در اين روش خوشه‌بندي هر دادة متعلق به خوشة C در دسترس چگالي ساير داده‌هاي متعلق به آن خوشه‌ است و در دسترس چگالي هيچ دادة ديگري قرار ندارد. شبه کد اين الگوريتم را زير مشاهده مي‌کنيد.



1-1-1- مثالي از الگوريتم خوشه‌بندي براساس چگالي DBSCAN: در شکل زير سعي شده است تا نحوة اعمال الگوريتم خوشه‌بندي DBSCAN را بر روي يک مجموعه داده نشان داده شود. همان‌گونه که مشاهده مي‌شود، اين الگوريتم نوانسته ‌است به خوبي داده‌ها را خوشه‌بندي کند.
a

b

c:

d:

f :

شکل 17: مثالي از روش خوشه‌بندي DBSCAN


الگوريتم سلسله مراتبي خوشه‌بندي براساس چگالي OPTICS:

در اين روش سعي مي‌شود تا با تکنيکي سلسله مراتبي خوشه‌هاي بزرگتري را از ترکيب خوشه‌اي داراي چگالي زياد ولي کوچک‌تر محاسبه کرد. در شکل زير با يک بار اعمال الگوريتم خوشه‌بندي DBSCAN خوشه‌هاي C1 و C2 حاصل گشته‌اند که در مرحلة ديگري با هم ترکيب شده و خوشة بزرگتر C را ساخته‌اند. در اين روش با افزايش تعداد تکرار مقدار پارامتر ε افزايش مي‌يابد.


شکل 18: در روش سلسله مراتبي خوشه‌بندي براساس چگالي OPTICS از ترکيب خوشه‌هاي با چگالي زياد و کوچک خوشه‌هاي بزرگتري حاصل مي‌شود.

مزاياي خوشه‌بندي بر اساس چگالي

a. خوشه‌ها مي‌توانند داراي اشکال دلخواه باشند.

b. تعداد خوشه‌ها به صورت اتوماتيک همزمان با عمل خوشه‌بندي تعيين مي‌شود.

c. در تشخيص نويزها بسيار کارا هستند.
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
dr_bijan (۰۹-۲۵-۱۳۹۲), shadi.mahmoudi (۰۵-۳-۱۳۹۱)
پاسخ



كاربران در حال ديدن تاپيک: 1 (0 عضو و 1 مهمان)
 
ابزارهاي تاپيک
نحوه نمايش

قوانين ارسال
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is فعال
شکلکها فعال است
كد [IMG] فعال است
كدهاي HTML غير فعال است
Trackbacks are فعال
Pingbacks are فعال
Refbacks are فعال




زمان محلي شما با تنظيم GMT +3.5 هم اکنون ۰۱:۱۷ بعد از ظهر ميباشد.


Powered by vBulletin® Version 3.8.3
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Search Engine Friendly URLs by vBSEO 3.1.0 ©2007, Crawlability, Inc.

Teach and Learn at Hexib | Sponsored by www.Syavash.com and Product In Review

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

Inactive Reminders By Icora Web Design