۴. If then STOP; otherwice returen to step 2.

شکل ۲-۱۰. الگوریتم فازی خوشه‌بندی
۲-۲-۱-۲-۳. الگوریتم طیفی
روش خوشه‌بندی طیفی^[۴۹] که بر اساس مفهوم گراف طیفی [۱۱] مطرح شده است، از ماتریس شباهت برای کاهش بعد داده‌ها در خوشه‌بندی استفاده می‌کند. در این روش یک گراف وزن‌دار بدون جهت به نحوی تولید می‌شود که رئوس گراف نشان‌دهنده‌ی مجموعه نقاط و هر یال وزن‌دار نشان‌دهنده‌ی میزان شباهت جفت داده‌های متناظر باشد. بر خلاف روش‌های کلاسیک، این روش، روی‌ داده‌ای پراکنده‌ در فضایی با شکل‌ هندسی غیر محدب، نتایج مطلوبی تولید می‌کند [۶۳]. کاربرد این روش در محاسبات موازی^[۵۰] [۶۹, ۷۰]، تنظیم بار^[۵۱] [۱۵]، طراحی VLSI^[52] [۲۸]، طبقه‌بندی تصاویر^[۵۳] [۳۵] و بیوانفورماتیک^[۵۴] [۳۱, ۵۹] می‌باشد.

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

در خوشه‌بندی طیفی از بردارهای ویژگی در ماتریس شباهت برای افراز مجموعه‌ داده استفاده می‌شود. در اغلب این روش‌ها، مقدار ویژه اولویت بردارها را تعیین می‌کند. ولی این نحوه‌ی انتخاب، انتخاب بهترین بردارها را تضمین نمی‌دهد. در اولین تحقیقی که در این زمینه توسط ژیانگ و گنگ [۶۱] انجام شد، مسئله‌ی انتخاب بردارهای ویژگی مناسب جهت بهبود نتایج خوشه‌بندی پیشنهاد گردید. در روش پیشنهادی آن‌ ها شایستگی هر یک از بردارهای با بهره گرفتن از تابع چگالی احتمال هر بردار تخمین زده می‌شود. وزنی به بردارهایی که امتیاز لازم را به دست آورندگ، اختصاص یافته و برای خوشه‌بندی از آن‌ ها استفاده می‌شود. در کاری دیگر که توسط ژائو [۶۴] انجام شده است، هر یک از بردارهای ویژه به ترتیب حذف می‌شوند و مقدار آنتروپی مجموعه بردارهای باقی‌مانده محاسبه می‌شود. برداری که حذف آن منجر به افزایش آنتروپی و ایجاد بی‌نظمی بیشتر در مجموعه داده شود، اهمیت بیشتری داشته و در رتبه بالاتری قرار می‌گیرد. سپس زیرمجموعه‌ای از مناسب‌ترین بردارها برای خوشه‌بندی مورد استفاده قرار می‌گیرند. الگوریتم خوشه‌بندی طیفی دارای متدهای متفاوتی جهت پیاده‌سازی است، که الگوریتم‌های برش نرمال، NJW، SLH وPF از آن جمله می‌باشد. در تمامی این روش‌ها، بخش اول، یعنی تولید گراف، مشترک می‌باشد. ما در ادامه ابتدا به بررسی بخش مشترک این روش‌ها می‌پردازیم. سپس به تشریح دو روش پر کاربرد برش نرمال و NJW می‌پردازیم.
در الگوریتم خوشه‌بندی طیفی، افراز داده‌ها بر اساس تجزیه‌ی ماتریس شباهت و به دست آوردن بردارها و مقادیر ویژه‌ی آن صورت می‌گیرد. مجموعه‌ی با داده‌ی بعدی را در نظر بگیرید، می‌توان برای این مجموعه گراف وزن‌دار و بدون جهت را ساخت به صورتی که رئوس گراف نشان‌دهنده داده و یال‌ها که ماتریس شباهت را تشکیل می‌دهند بیانگر میزان شباهت بین هر جفت داده متناظر باشند. ماتریس شباهت به صورت رابطه ۲-۹ تعریف می‌شود:
(۲-۹)
تابع میزان شباهت بین دو داده را اندازه می‌گیرد. می‌تواند یک تابع گوسی به صورت باشد. که در آن فاصله‌ی بین دو نمونه را نشان می‌دهد و پارامتر مقیاس سرعت کاهش تابع با افزایش فاصله بین دو نمونه را مشخص می‌کند. در ادامه به بررسی دو الگوریتم خوشه‌بندی طیفی برش نرمال و NJW می‌پردازیم.
۲-۲-۱-۲-۳-۱. الگوریتم برش نرمال
الگوریتم برش نرمال^[۵۵] توسط شی و ملیک [۳۵] برای قطعه‌بندی تصاویر ارائه شده است. در این روش، میزان تفاوت بین خوشه‌های مختلف و شباهت بین اعضا یک خوشه، بر اساس فاصله‌ی داده‌ها محاسبه می‌کند. رابطه ۲-۱۰ اشاره به مفهوم شباهت داده دارد که با بهره گرفتن از آن اقدام به ساخت گراف وزن‌دار می‌نماییم:
(۲-۱۰)
موقعیت i-امین داده (پیکسل در تصاویر) و بردار ویژگی از صفات داده (مانند روشنایی در تصاویر) می‌باشد. با کمک حد آستانه می‌توان میزان تنکی ماتریس شباهت را با توجه به تعداد اثرگذار داده‌های همسایه تعیین کرد. گام‌های این الگوریتم به صورت زیر می‌باشد:

• محاسبه ماتریس درجه .

• محاسبه ماتریس لاپلاسین .

• محاسبه دومین بردار ویژگی متناظر با دومین کوچک‌ترین مقدار ویژه .

• استفاده از برای خوشه‌بندی (قطعه‌بندی در تصاویر) گراف .

روش برش نرمال بیشتر در قطعه‌بندی تصاویر کاربرد دارد و معمولاً در خوشه‌بندی داده از سایر الگوریتم‌های خوشه‌بندی طیفی استفاده می‌کنند.
۲-۲-۱-۲-۳-۲. الگوریتم NJW
ایده الگوریتم استفاده از اولین بردار ویژه متناظر با بزرگ‌ترین مقدار ویژه ماتریس لاپلاسین است. مراحل این الگوریتم به صورت زیر می‌باشد: [۵۱]

• ساخت ماتریس شباهت با بهره گرفتن از رابطه ۲-۹.

• محاسبه ماتریس درجه ، و ماتریس لاپلاسین .

• به دست آوردن اولین بردار ویژه متناظر با اولین بزرگ‌ترین مقدار ماتریس و تشکیل ماتریس ستونی .

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

• خوشه‌بندی مجموعه داده بازنمایی شده با بهره گرفتن از .

۲-۲-۱-۲-۴. الگوریتم خوشه‌بندی کاهشی
الگوریتم خوشه‌بندی کاهشی^[۵۶] یکی از سریع‌ترین الگوریتم‌های تک گذر، برای تخمین تعداد خوشه و مراکز آن‌ ها در مجموعه‌ی داده می‌باشد. این مفهوم یعنی به جای تحت تأثیر قرار گرفتن محاسبات از ابعاد مسئله، متناسب با اندازه مسئله آن را انجام دهیم. با این وجود، مراکز واقعی خوشه الزاماً یکی از نقاط داده موجود در مجموعه داده نیست ولی در بیشتر موارد این انتخاب تخمین خوبی است که به صورت ویژه از این رویکرد در محاسبات کاهشی استفاده می‌شود. اگر هر نقطه از مجموعه داده به عنوان گزینه‌ای برای مرکز خوشه در نظر گرفته شود، معیار تراکم هر نقطه به صورت زیر تعریف می‌شود [۷۹].
(۲-۱۱)
در رابطه بالا یک ثابت مثبت است، که نشان‌دهنده‌ی شعاع همسایگی^[۵۷] (سایر نقاط داده که نزدیک‌ترین نقاط به این داده خاص هستند) می‌باشد، و نشان‌دهنده‌ی سایر داده‌های مجموعه، و نشان‌دهنده‌ی تعداد این داده‌ها است. از این روی، داده‌ای دارای بیش‌ترین مقدار تراکم می‌باشد که بیش‌ترین نقاط داده در همسایگی آن است. اولین مرکز خوشه بر اساس بزرگ‌ترین مقدار تراکم انتخاب می‌شود. بعد از این انتخاب میزان تراکم هر یک از نقاط داده به صورت زیر به‌روز می‌شود [۷۹].
(۲-۱۲)
در رابطه بالا ثابت مثبت همسایگی را تعریف می‌کند که میزان کاهش تراکم قابل اندازه‌گیری را نشان می‌دهد. از آنجایی که نقاط داده در نزدیکی مرکز خوشه اول به طور قابل‌توجهی مقادیر چگالی را کاهش می‌دهند بعد از به‌روز کردن مقادیر تابع چگالی توسط رابطه بالا مرکز خوشه بعدی بر اساس داده‌ای که بزرگ‌ترین مقدار چگالی را دارد انتخاب می‌شود. این فرایند آن قدر تکرار می‌شود تا به تعداد کافی مرکز خوشه ایجاد شود. پس از اتمام این فرایند می‌توان توسط الگوریتم که مراکز داده در آن توسط فرایند بالا به صورت دستی داده شده است (نه به صورت تصادفی)، داده‌ها را خوشه‌بندی کرد. شبه کد شکل زیر روند فرایند بالا را نشان می‌دهد که در آن ابتدا مقادیر ثابت‌ها ( ) و مجموعه داده به عنوان ورودی گرفته می‌شود و پس از ساخت مراکز داده مطابق با تعاریف بالا، این مراکز برای خوشه‌بندی در الگوریتم استفاده می‌شود [۷۹].

Inputs Dataset, Constants
Output Clusters
Steps
۱. Initialize constants and density values
۲. Make a new cluster center.
۳. Update density values
۴. If the sufficient number of clusters are not obtained, go to 2.
۳. Clustering the dataset by k-means, using fix centers.