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

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

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

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

شرط خاتمه: در صورتي که M برابر تعداد خوشة مورد نظر الگوريتم LBG بود الگوريتم خاتمه مي‌يابد و در غير اين صورت به مرحلة ii رفته و الگوريتم تکرار مي‌شود
1-8-2 روش های سلسله مراتبی
یک روش سلسله مراتبی یک تجزیه سلسله مراتبی از اشیاء داده­ای یک مجموعه معلوم ایجاد می­ کند. این روش کلاسبندی را یا به صورت ترکیبی (تراکمی)و یا به صورت تقسیمی(تفرقی) انجام دهد. یعنی در دو قالب بالا به پایین و پایین به بالا عمل می­ کنند از یک خوشه بزرگ در بالا (در روش های بالا به پایین) و یا تعداد زیادی خوشه­های کوچک در پایین ( برای روش های پایین به بالا) شروع کرده و به بهترین شکل یک خوشه را به خوشه­های کوچکتر بشکنند و یا خوشه­های کوچک را با یکدیگر ترکیب کنند تا تعداد مورد نظر خوشه بدست بیایند. به رویکرد ترکیبی ، رویکرد پایین به بالا(bottom up) نیز گفته می­ شود که با شکل­دهی گروه ­های مجزا و هر یک شامل یک شیء شروع شده. سپس اشیاء یا گروه ­های نزدیک بهم را یکی می­ کند. تا اینکه در نهایت همه گروه­ ها یکی شوند و یا ( بالاترین سطح سلسله مراتبی ) یا تا هنگامیکه شرط پایانی بدست آید در واقع خوشه ها مکررا با هم یکی میشوند تا اینکه همه اشیاء در یک خوشه قرار گیرند و یا به شرط پایان برسند. در رویکرد تقسیم یا بالا به پایین روش سلسله مراتبی با خوشه ای شامل همه اشیاء شروع می­ کند خوشه ها مکررا تقسیم میشوند وخوشه ها را به خوشه های کوچک وکوچکتر تجزیه میکندتا اینکه هر شئ در یک خوشه قرار گیرد. این روش معمولا مناسب نیست زیرا پیچیدگی محاسباتش بالاست توجه داشته باشید که در تقسیم خوشه ها باید بهترین حالت انتخاب شود. روش های سلسله مراتبی این واقعیت را دارند که در هر گامی ( یکی کردن یا تقسیم کردن) که انجام می­ شود آن گام هرگز نباید ناتمام بماند. این سختی گاهی نیز مفید می­باشد. با این وجود مشکل اصلی این تکنیکها این است که آنها نمی ­توانند تصمیمات اشتباه را تصحیح کنند.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

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

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

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

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

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

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

شکل1-4 : شباهت بين دو خوشه در روش Single-Link برابر است با کمترين فاصلة بين داده‌هاي دو خوشه
1-8-2-2 خوشه‌بندي با روش Complete-Link
اين روش همانند Single-Link جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. به اين روش خوشه‌بندي، تکنيک دورترين همسايه (furthest Neighbour) نيز گفته مي‌شود. در اين روش براي محاسبة شباهت بين دو خوشة A و B از معيار زير استفاده مي‌شود:

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

شکل1-5 : شباهت بين دو خوشه در روش Complete-Link برابر است با بيشترين فاصلة بين داده‌هاي دو خوشه.
1-8-2-3 خوشه‌بندي با روش Average-Link
اين روش همانند Single-Link جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. از آنجا که هر دو روش خوشه‌بندي Single-link و Complete-link بشدت به نويز حساس مي‌باشد، اين روش که محاسبات بيشتري دارد، پيشنهاد شد. در اين روش براي محاسبة شباهت بين دو خوشة A و B از معيار زير استفاده مي‌شود:

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

شکل1-6 : شباهت بين دو خوشه در روش Average-Link برابر است با ميانگين فاصلة بين داده‌هاي دو خوشه
1-8-2-4 ديگر روشهاي خوشه بندي سلسله مراتبي

• • خوشه‌بندي با روش Group Average Link:

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

که X_i يک نمونه داده متعلق به خوشة A، X_j يک نمونه دادة متعلق به خوشة B، N_A تعداد اعضاء خوشةA و N_B تعداد اعضاء خوشة B است. در واقع در اين روش، شباهت بين دو خوشه فاصلة بين بردار ميانگينِ تمام اعضاء يکي با بردارِ ميانگينِ تمام اعضاء ديگري است. در شکل 1-7 اين مفهوم بهتر نشان‌ داده شده است.
خوشه‌بندي با روش Median Distance:
اين روش نيز همانند Single-Link جزء روشهاي خوشه‌بندي سلسله مراتبي و انحصاري محسوب مي‌شود. در روش Group Average Link اگر يک خوشة کوچک با يک خوشة بزرگ ترکيب شود نقطة ميانگين خوشة حاصل نقطه‌اي نزديک ميانگين خوشة بزرگتر خواهد بود که در بعضي از کاربردها چندان مطلوب نيست. بدين منظور اين روش خوشه‌بندي پيشنهاد شده است که مشکل مذکور را ندارد. در اين روش از ميانة نقاط يک خوشه به‌ عنوان مرکز ثقل آن خوشه استفاده مي‌شود.[7]
شکل1-7 : شباهت بين دو خوشه در روش Group Average Link برابر است با فاصله بين ميانگين نقاط دو خوشه

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