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

سپس به تشريح دو روش پر كاربرد برش نرمال و NJW مي‌پردازيم.
در الگوريتم خوشه‌بندي طيفي، افراز داده‌ها بر اساس تجزيه‌ي ماتريس شباهت و به دست آوردن بردارها و مقادير ويژه‌ي آن صورت می‌گيرد. مجموعه‌ي با داده‌يبعدي را در نظر بگيريد، مي‌توان براي اين مجموعه گراف وزن‌دار و بدون جهت را ساخت به صورتي که رئوس گراف نشان‌دهنده داده و يال‌ها كه ماتريس شباهت را تشكيل مي‌دهند بيانگر ميزان شباهت بين هر جفت داده متناظر باشند. ماتريس شباهت به صورت رابطه 2-9 تعريف مي‌شود:
(2-9)
تابع ميزان شباهت بين دو داده را اندازه مي‌گيرد. مي‌تواند يك تابع گوسي به صورت باشد. كه در آن فاصله‌ي بين دو نمونه را نشان مي‌دهد و پارامتر مقياس سرعت كاهش تابع با افزايش فاصله بين دو نمونه را مشخص مي‌کند. در ادامه به بررسي دو الگوريتم خوشه‌بندي طيفي برش نرمال و NJW مي‌پردازيم.
2-2-1-2-3-1. الگوريتم برش نرمال
الگوريتم برش نرمال55 توسط شي و مليك [35] براي قطعه‌بندي تصاوير ارائه شده است. در اين روش، ميزان تفاوت بين خوشه‌هاي مختلف و شباهت بين اعضا يك خوشه، بر اساس فاصله‌ي داده‌ها محاسبه مي‌کند. رابطه 2-10 اشاره به مفهوم شباهت داده دارد که با استفاده از آن اقدام به ساخت گراف وزن‌دار مي‌نماييم:
(2-10)
موقعيت i-امين داده (پيكسل در تصاوير) و بردار ويژگي از صفات داده (مانند روشنايي در تصاوير) مي‌باشد. با كمك حد آستانه مي‌توان ميزان تنكي ماتريس شباهت را با توجه به تعداد اثرگذار داده‌هاي همسايه تعيين کرد. گام‌هاي اين الگوريتم به صورت زير مي‌باشد:
1- محاسبه ماتريس درجه.
2- محاسبه ماتريس لاپلاسين.
3- محاسبه دومين بردار ويژگي متناظر با دومين کوچک‌ترين مقدار ويژه.
4- استفاده از براي خوشه‌بندي (قطعه‌بندي در تصاوير) گراف.
روش برش نرمال بيشتر در قطعه‌بندي تصاوير كاربرد دارد و معمولاً در خوشه‌بندي داده از ساير الگوريتم‌هاي خوشه‌بندي طيفي استفاده مي‌کنند.
2-2-1-2-3-2. الگوريتم NJW
ايده الگوريتم استفاده از اولين بردار ويژه متناظر با بزرگ‌ترين مقدار ويژه ماتريس لاپلاسين است. مراحل اين الگوريتم به صورت زير مي‌باشد: [51]
1- ساخت ماتريس شباهت با استفاده از رابطه 2-9.
2- محاسبه ماتريس درجه، و ماتريس لاپلاسين.
3- به دست آوردن اولين بردار ويژه متناظر با اولين بزرگ‌ترين مقدار ماتريسو تشكيل ماتريس ستوني.
4- نرمال سازي مجدد و تشكيل به طوري که همه سطرهاي آن طول واحد داشته باشد.
5- خوشه‌بندي مجموعه داده بازنمايي شده با استفاده از.

2-2-1-2-4. الگوريتم خوشه‌بندي کاهشي
الگوريتم خوشه‌بندي کاهشي56 يکي از سريع‌ترين الگوريتم‌هاي تک گذر، براي تخمين تعداد خوشه و مراکز آن‌ها در مجموعه‌ي داده مي‌باشد. اين مفهوم يعني به جاي تحت تأثير قرار گرفتن محاسبات از ابعاد مسئله، متناسب با اندازه مسئله آن را انجام دهيم. با اين وجود، مراکز واقعي خوشه الزاماً يکي از نقاط داده موجود در مجموعه داده نيست ولي در بيشتر موارد اين انتخاب تخمين خوبي است که به صورت ويژه از اين رويکرد در محاسبات کاهشي استفاده مي‌شود. اگر هر نقطه از مجموعه داده به عنوان گزينه‌اي براي مرکز خوشه در نظر گرفته شود، معيار تراکم هر نقطه به صورت زير تعريف مي‌شود [79].
(2-11)
در رابطه بالا يک ثابت مثبت است، که نشان‌دهنده‌ي شعاع همسايگي57 (ساير نقاط داده که نزديک‌ترين نقاط به اين داده خاص هستند) مي‌باشد، و نشان‌دهنده‌ي ساير داده‌هاي مجموعه، و نشان‌دهنده‌ي تعداد اين داده‌ها است. از اين روي، داده‌اي داراي بيش‌ترين مقدار تراکم مي‌باشد که بيش‌ترين نقاط داده در همسايگي آن است. اولين مرکز خوشه بر اساس بزرگ‌ترين مقدار تراکم انتخاب مي‌شود. بعد از اين انتخاب ميزان تراکم هر يک از نقاط داده به صورت زير به‌روز مي‌شود [79].
(2-12)
در رابطه بالا ثابت مثبت همسايگي را تعريف مي‌کند که ميزان کاهش تراکم قابل اندازه‌گيري را نشان مي‌دهد. از آنجايي که نقاط داده در نزديکي مرکز خوشه اول به طور قابل‌توجهي مقادير چگالي را کاهش مي‌دهند بعد از به‌روز کردن مقادير تابع چگالي توسط رابطه بالا مرکز خوشه بعدي بر اساس داده‌اي که بزرگ‌ترين مقدار چگالي را دارد انتخاب مي‌شود. اين فرآيند آن قدر تکرار مي‌شود تا به تعداد کافي مرکز خوشه ايجاد شود. پس از اتمام اين فرآيند مي‌توان توسط الگوريتم که مراکز داده در آن توسط فرآيند بالا به صورت دستي داده شده است (نه به صورت تصادفي)، داده‌ها را خوشه‌بندي کرد. شبه کد شکل زير روند فرآيند بالا را نشان مي‌دهد که در آن ابتدا مقادير ثابت‌ها () و مجموعه داده به عنوان ورودي گرفته مي‌شود و پس از ساخت مراکز داده مطابق با تعاريف بالا، اين مراکز براي خوشه‌بندي در الگوريتم استفاده مي‌شود [79].
Inputs Dataset, Constants
Output Clusters

Steps
1. Initialize constants and density values
2. Make a new cluster center.
3. Update density values
4. If the sufficient number of clusters are not obtained, go to 2.
3. Clustering the dataset by k-means, using fix centers.
شکل 2-11. خوشه‌بندي کاهشي
2-2-1-2-5. الگوريتم خوشه‌بندي Median K-Flat
الگوريتم Median K-Flat يا به اختصار MKF مجموعه داده‌يرا به K خوشه‌ي افراز مي‌کند که هر خوشه يک شبه فضاي58 d-بُعدي تقريباً خطي مي‌باشد. پارامتر‌ با فرض ماتريسي با ابعاد مي‌باشد، که هر يک از خانه‌هاي آن تخمين شبه فضاي خطي متعامد59 مي‌باشد. قابل به ذکر است که مي‌باشد. در اين جا تخمين شبه فضاي خوشه‌هاي را نام‌گذاري مي‌کنيم. مطابق تعاريف بالا تابع انرژي براي افرازهاي ‌ بر اساس شبه فضاي به شکل زير تعريف مي‌شود [77].
(2-13)
اين الگوريتم سعي مي‌کند تا مجموعه داده را به خوشه‌هاي ‌تبديل کند به نحوي که تابع انرژي کمينه باشد. تا وقتي که سطوح تخت اساسي60 به شکل شبه فضاي خطي هستند ما مي‌توانيم به صورت فرضي المان‌هاي X را در يک حوضه واحد نرمال کنيم به طوري که براي و تابع انرژي را به شکل زير بيان کنيم: [77]
(2-14)
اين الگوريتم براي کمينه‌سازي تابع انرژي الگوريتمMKF از روش کاهش گراديان تصادفي استفاده مي‌کند. مشتق تابع انرژي بر اساس ماتريس به شرح زير است:
(2-15)
اين الگوريتم نياز به تطبيق بر اساس مؤلفه‌ي متعامد مشتق دارد. بخشي از مشتق که با شبه فضاي موازي است به شرح زير مي‌باشد.
(2-16)
از اين روي مؤلفه متعامد برابر است با رابطه 2-17 مي‌باشد.
(2-17)
در رابطه بالا برابر با رابطه 2-18 است.
(2-18)
با در نظر گرفتن محاسبات بالا، الگوريتم MKF تصميم مي‌گيرد که داده تصادفي از مجموعه داده، عضو کدام باشد، و از اين طريق شروع به چيدن داده‌ها مي‌کند. آن گاه، الگوريتم تابع را به‌روز کند که در آن (مرحله زماني) پارامتري است که توسط کاربر تعيين مي‌شود. اين فرآيند آن قدر تکرار مي‌شود تا ضابطه همگرايي ديده شود. آنگاه هر نقطه از مجموعه داده به نزديک‌ترين شبه فضاي که تعيين‌کننده خوشه‌هاست اختصاص داده مي‌شود. شبه کد زير فرآيند الگوريتم MKF را نشان مي‌دهد [77].
Input:
: Data, normalized onto the unit sphere, d: dimension of subspaces K: number of subspaces, the initialized subspaces. : step parameter.
Output: A partition of X into K disjoint clusters

Steps:
1. Pick a random point in X
2. Find its closest subspace , where
3. Compute by
4. Update
5. Orthogonalize
6. Repeat steps 1-5 until convergence
7. Assign each xi to the nearest subspace
شکل 2-12. شبه‌کد الگوريتم MKF [77]
2-2-1-2-6. الگوريتم خوشه‌بندي مخلوط گوسي
يک مخلوط گوسي61 يا همان را مي‌توان ترکيب محدبي62 از چگالي‌هاي گوسي دانست. يک چگالي گوسي در فضاي d-بُعدي به ازاي ميانگين، توسط ماتريس هم‌وردايي63 با ابعاد به صورت زير تعريف مي‌شود: [83]
(2-19)

در رابطه بالا پارامتر‌هاي و را تعريف مي‌کند. از اين روي مؤلفه به صورت زير تعريف مي‌شود:
(2-20)
در رابطه (2-20) پارامتر وزن مخلوط کردن64 و مؤلفه مخلوط مي‌باشد. از آنجا که در مقايسه با تخمين چگالي غير پارامتري، تعداد کمتري از توابع چگالي در تخمين چگالي مخلوط بايد ارزيابي شود، از اين روي ارزيابي چگالي کارآمدتر خواهد بود. علاوه بر آن، استفاده از اجراي محدوديت هموار کردن65 بر روي برخي از مؤلفه‌هاي مخلوط در نتيجه‌ي چگالي به ما اجازه مي‌دهد تا چگالي مستحکم‌تري را تخمين بزنيم. الگوريتم حداکثر-انتظار66 يا همان به ما اجازه به‌روز کردن پارامتر‌هاي مؤلفه‌ي مخلوط را مطابق با مجموعه داده به ازاي هر مي‌دهد، به طوري که احتمال هرگز کوچک‌تر از مخلوط جديد نشود. به‌روز کردن الگوريتم مي‌تواند در يک فرآيند تکراري براي تمامي مؤلفه‌هاي مطابق با رابطه‌هاي زير انجام شود: [83]
(2-21)
(2-22)
(2-23)
(2-24)
در اين تحقيق از روش پيشنهادي بومن و همکاران67 براي پياده‌سازي الگوريتم مخلوط گوسي استفاده شده است. از آنجايي که روش پياده‌سازي و توضيحات مربوط به الگوريتم مخلوط گوسي در روش ترکيب مبتني بر مخلوط استفاده مي‌شود از اين روي در بخش روش‌هاي ترکيب نتايج با تابع توافقي آن را بررسي خواهيم کرد.

2-2-2. معيارهاي ارزيابي
در يادگيري با ناظر68 ارزيابي راحت تر از يادگيري بدون ناظر است. براي مثال آن چيز كه ما در رده‌بندي69 بايد ارزيابي كنيم مدلي است كه ما توسط داده‌هاي70 يادگيري به الگوريتم هوش مصنوعي71 آموزش72 داده‌ايم. در روش‌هاي با ناظر ورودي و خروجي داده معلوم است و ما بخشي از كل داده را براي آزمون جدا كرده و بخش ديگر را به عنوان داده يادگيري استفاده مي‌کنيم و پس از توليد مدل مطلوب ورودي داده آزمون73 را در مدل وارد كرده و خروجي مدل را با خروجي واقعي مي‌سنجيم74. از اين روي معيارهاي بسياري براي ارزيابي روش‌هاي با ناظر ارائه‌شده‌اند.
در يادگيري بدون ناظر روش متفاوت است. در اين روش هيچ شاخص معيني در داده جهت ارزيابي وجود ندارد و ما به دنبال دسته‌بندي كردن داده‌ها بر اساس شباهت‌ها و تفاوت‌ها هستيم. از اين روي برخلاف تلاش‌هاي خيلي از محققان، ارزيابي خوشه‌بندي خيلي توسعه داده نشده است و به عنوان بخشي از تحليل خوشه‌بندي رايج نشده است. در واقع، ارزيابي خوشه‌بندي يكي از سخت‌ترين بخش‌هاي تحليل خوشه‌بندي است [33]. معيارهاي عددي، يا شاخص‌هايي كه براي قضاوت جنبه‌هاي مختلف اعتبار يك خوشه به كار مي روند، به سه دسته كلي تقسيم مي‌شوند:
1- شاخص خارجي75 كه مشخص مي‌کند كه كدام خوشه‌هاي پيداشده به وسيله الگوريتم خوشه‌بندي با ساختارهاي خارجي تطبيق دارند. در اين روش نياز به اطلاعات اضافي مثل برچسب نقاط داده، داريم. آنتروپي يك مثالي از شاخص خارجي است.
2- شاخص داخلي76 كه براي اندازه‌گيري ميزان خوبي77 يك ساختار خوشه‌بندي بدون توجه به اطلاعات خارجي به كار مي‌‌رود. 78 يك نمونه از شاخص داخلي است.
3- شاخص نسبي79 كه براي مقايسه دو خوشه‌بندي مختلف يا دو خوشه مختلف به كار مي‌رود. اغلب يك شاخص خارجي يا داخلي براي اين تابع استفاده مي‌شود. براي