بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
ترکيب بردارهاي ويژه در حوزه KPCA به منظور خوشه بندي داده ها
چکيده : خوشه بندي به عنوان يکي از تکنيکهاي مهم در شناسايي الگو، پردازش تصوير و داده کاوي شناخته مي شود. در فضاهايي با ابعاد بالا به علت وجود وابستگيهاي غير خطي بين ويژگيها، الگوريتمهاي خوشه بندي معمولا با شکست مواجه مي شوند. براي مقابله با اين مشکل عموما با انتقال فضا به حوزه ويژگي - با ابعاد بالا سعي در به دست آوردن ويژگيهايي مناسب تر براي توصيف داده مي شود. در اين مقاله سعي شده است تا با انتقال داده ها به فضاي Kernel PCA به توصيف مناسب تري از داده ها دست يابيم و از خصوصيات اين فضا براي خوشه بندي بهتر استفاده نماييم . براي اين منظور، پس از استخراج ويژگيهاي جديد در فضاي متعامد KPCA، به بررسي آنها پرداخته و ويژگيهاي مناسب براي خوشه بندي را با انتساب وزن مناسب به آنها، انتخاب و ترکيب مي نماييم و در انتها از روشي مبتني بر راي گيري وزندار براي خوشه بندي داده ها استفاده مي نماييم . نتايج آزمايشها بهبود مناسبي را در مقايسه با الگوريتمهاي خوشه بندي فازي C-ميانگين ١ و K-ميانگين ١ نشان ميدهد.
واژه هاي کليدي : فضاي تعامد، تحليل مولفه هاي اصلي کرنل ، خوشه بندي
١- معرفي
تحليل مولفه هاي اصلي روشي قدرتمند براي استخراج ساختار از مجموعه داده هاي با ابعاد بالا مي باشد. در اين روش با حل يک مسئله مقادير ويژه و يا با استفاده از الگوريتمهاي تکراري ، مولفه هاي اصلي استخراج مي شوند. در حقيقت ، PCA تبديلي متعامد از دستگاه مختصاتي است که داده ها را توصيف مي کند. دستگاه مختصات جديد از تصوير داده ها بر روي محورهايي که اصطلاحا محورهاي اصلي ٢ داده ها ناميده مي شوند، به دست مي آيد. اغلب تعداد کمي از اين مولفه هاي اصلي براي توصيف ساختارهاي موجود در داده ها کافي است . اما در مواقعي که بين متغيرها در فضاي ورودي وابستگيهايي با مرتبه هاي بالا وجود داشته باشد، استفاده از روش PCA کارا نخواهد بود. در اين موارد استفاده از PCA در فضاي متغيرها و يا ويژگيها که به طور غير خطي به فضاي ورودي وابسته است و از آن به عنوان Kernel PCA ياد مي شود، ترجيح داده مي شود[١].
از جمله مزيتهاي اين فضاي جديد ، استخراج ويژگيهاي بيشتر با کيفيتي مناسب تر نسبت به مولفه هاي اصلي مي باشد به صورتيکه براي دستيابي به دقتي برابر با دقت روش PCA، در KPCA به تعداد مولفه هاي کمتري نياز داريم [٢].
در اغلب کارهايي که با هدف خوشه بندي داده ها در فضاي تعامد انجام شده [٧،٦،٤،٣]، از PCA و يا KPCA براي استخراج ويژگي استفاده شده است و بعد از تصوير داده ها در فضاي ويژگي ، با استفاده از الگوريتمهاي خوشه بندي مانند K-ميانگين داده هاخوشه بندي مي شوند. در[٣] به بررسي کارايي روشهاي مختلف استخراج ويژگي در خوشه بندي پرداخته شده است . در [٦]سعي شده است تا با راهنمايي PCA خوشه بندي انجام شود. در [٧] هدف رفع مشکل گرفتار شدن الگوريتم K-ميانگين در بهينه هاي محلي با استفاده از KPCA مي باشد.
در ادامه اين مقاله ، در بخش ٢ به معرفي Kernel PCA و بررسي مقالاتي که براي خوشه بندي از بردارهاي ويژه استفاده نموده اند مي پردازيم . روش پيشنهادي براي خوشه بندي بر اساس ترکيب بردارهاي ويژه در بخش ٣ بررسي شده و در بخش ٤، با پياده سازي اين روش به روي چهار مجموعه داده سنتز شده ، کارايي آن با روشهاي ديگر خوشه بندي مانند فازي C-ميانگين و K-ميانگين مقايسه شده است و در بخش پاياني نتيجه گيري و زمينه هاي تحقيقاتي آينده بيان شده اند.
٢- بررسي مولفه هاي اصلي در حوزه کرنل و خوشه بندي در فضاي ويژگي
٢-١ بررسي Kernel PCA
ايده KPCA استفاده از PCA براي تصوير غيرخطي داده ها با استفاده از حقه کرنل مي باشد. اگر مجموعه داده اي با m نمونه داشته باشيم به صورت ماتريس کواريانس داده ها را در فضاي ورودي به صورت تعريف مي نماييم . بردارهاي ويژه نرمال C، زيرفضاي مولفه ها را در PCA تشکيل مي دهند که داده ها به طور خطي بروي اين زيرفضا تصوير خواهند شد. براي توسعه اين روش به حالت غيرخطي ، فضاي ويژگي H را که به صورت غير خطي وابسته به فضاي ورودي است در نظر مي گيريم :
فضاي H مي تواند ابعاد بزرگ دلخواه و حتي نامحدود داشته باشد.
فرض مي کنيم داده ها مرکزدار شده باشند،
ماتريس کواريانس را در فضاي H محاسبه مي تماييم :
سپس مقادير ويژه و بردارهاي ويژه غير صفر که در معادله زير صدق مي کنند را مي يابيم .
همه جوابهاي V با در فضاي قرار مي گيرد. بنابراين :
علاوه بر اين ضرايب نيز وجود دارند به صورتيکه
با مقايسه (٤) و (٥) خواهيم داشت :
براي
با تعريف ماتريس کرنل معادله (٦) به اين صورت بيان مي شود:
و بردارهاي ستوني را مشخص مي نمايد. براي حل مسئله (٧)، مسئله دوگان آن (٨) را براي مقادير ويژه مخالف صفر حل مي کنيم .
مقادير ويژه K و مجموعه کامل بردارهاي ويژه مرتبط با آنها مي باشند. فرض مي کنيم آخرين مقدار ويژه مخالف صفر باشد. با در نظر گرفتن نرمال بودن بردارهاي وابسته به در فضاي را نرمال مي کنيم .
بنابر رابطه (٥) و (٨)، رابطه فوق به صورت زير تبديل مي شود:
براي استخراج مولفه هاي اصلي ، بايد تصوير داده ها بروي بردارهاي ويژه را در فضاي H محاسبه نماييم . براي اين منظور، اگر نقطه آزمون x را داشته باشيم تصوير آن در H برابر خواهد بود با بنابراين ،
تصوير نقطه آزمون روي بردار ويژه nام را مي ناميم .
براي سادگي ، فرض شده بود که همه داده ها مرکزدار شده اند. در فضاي ورودي محاسبه مرکز دار نمودن آسان است اما در فضاي ويژگي H مشکل است و به سادگي نمي توان مرکز مشاهدات نگاشت شده به فضاي با ابعاد بالا را محاسبه نمود. اما با استفاده از فرمول اصلاح شده زير براي KPCA اين امر محقق مي گردد.
و براي همه i و j ها[١].
کرنلهاي مختلفي مانند کرنل گوسي ، چند جمله اي ، کوادراتيک ، سيگموئيد و ... مي توانند به کار گرفته شوند.
٢-٢ بررسي روشهاي خوشه بندي با استفاده از بردارهاي ويژه
ابتدا به بررسي کارهايي مي پردازيم که با انتقال فضاي ورودي به فضاي ويژگي خطي و يا غير خطي ، سعي در استخراج ويژگيهايي مناسب تر براي خوشه بندي دارند. در [٣]، ابتدا با استفاده از روشهاي PCA، KPCA،Sammon و CCA داده ها به فضاي ويژگي انتقال يافته اند و سپس عملکرد اين روشها در خوشه بندي بروي داده ها آزمايش شده است . براي مقايسه کارايي خوشه بندي اين روشهاي تصوير داده ، از الگوريتم K-ميانگين استفاده شده است ، نتايج حاصل نشان دهنده برتري KPCA براي استخراج ويژگيهاي مناسب نسبت به سه روش ديگر است . در [٤] الگوريتم خوشه بندي معمولي را در فضاي کرنل از ديدگاه جديدي انجام داده است ، به جاي اينکه الگوريتمها در فضاي ويژگي غيرخطي کرنليزه شوند، در فضاي ويژگي خطي اين کار انجام مي شود، به بيان ديگر در اين مقاله نشان داده شده است که کرنل -K- ميانگين ٣ معادل با اعمال KPCA قبل از K-ميانگين بروي داده ها مي باشد. به اين مفهوم که اگر نمونه ها را روي KPCA تصوير کنيم و بعد K-ميانگين را روي آنها اعمال نماييم ، فاصله بين نمونه ها معادل با فاصله آنها در فضاي غير خطي هيلبرت خواهد بود. در [٦] ارتباط بين PCA و روش خوشه بندي K-ميانگين بررسي شده است و با قرار دادن حد آستانه بروي بردار ويژگي استخراج شده با تحليل مولفه هاي اصلي ، خوشه بندي اوليه را انجام مي دهد و سپس سعي بر بهينه نمودن تابع هدف K-ميانگين مي نمايد. به بيان ديگر، روشي براي خوشه بندي با الگوريتم K-ميانگين و با راهنمايي تحليل مولفه هاي اصلي ارائه شده است . در [٧] الگوريتم مکاشفه اي خوشه بندي K-ميانگين مبتني بر KPCA و برنامه نويسي پويا ارائه و سعي شده است تا با استفاده از 4 KPCA يک ناحيه بهينه از نمونه هاي ورودي در جهت اصلي کرنل به عنوان ناحيه اوليه براي K-ميانگين انتخاب مي شود تا از گرفتار شدن الگوريتم K-ميانگين در بهينه هاي محلي اجتناب شود. در دسته دوم مقالاتي قرار مي گيرند که با الهام از KPCA به روشهاي ديگري براي استخراج ويژگي و خوشه بندي مي پردازند مانند [٥] که تحليل مولفه هاي انتروپي ٥ در آن به عنوان روش جديدي براي تبديل داده ها و کاهش بعد معرفي شده است . بر خلاف KPCA اين روش نيازي به مقادير ويژه بزرگتر ندارد و ممکن است مجموعه داده تبديل يافته کاملا متفاوتي نسبت به KPCA توليد کند. اين روش مي تواند جايگزين مفيدي براي حذف نويز الگوها باشد. بعد از تصوير داده ها به فضاي ويژگي با استفاده از اين روش ، داده هاي تبديل يافته با توجه به توزيع خوشه ها در جهتهاي متفاوت ، يک ساختار زاويه اي خواهند داشت که از همين خاصيت براي خوشه بندي استفاده شده است ..
٣- روش پيشنهادي خوشه بندي بر اساس ترکيب بردارهاي ويژگي
در الگوريتمهاي خوشه بندي که در فضاي ورودي اجرا مي شوند از ويژگيهايي که داده ها را توصيف مي کنند براي هدف خوشه بندي استفاده مي شود. در اين مقاله سعي شده است تا به رويکردي جديد براي خوشه بندي برسيم ، و بنابر اين هدف به بررسي خوشه بندي در فضاي تعامد يا ويژگيهاي استخراج شده از KPCA پرداخته ايم . براي خوشه بندي داده ها، از بردارهاي ويژه که محاسبه آنها در بخش قبل توضيح داده شد به عنوان روشي براي انجام اين کار استفاده مي نماييم بدين صورت که بعد از به دست آوردن اين بردارهاي ويژه در فضاي KPCA، به دنبال يافتن بهترين هاي آنها براي خوشه بندي مي گرديم .
مراحل انجام کار به صورت زير مي باشد:
١- اولويت انتخاب بردارهاي ويژه را بر مبناي مقادير ويژه قرار مي دهيم ، يعني بردارها را بر اساس ترتيب نزولي مقادير ويژه مرتب مي کنيم .
٢- تعداد مناسبي از بردارهاي ويژه را انتخاب مي نماييم (k). در انتخاب اين تعداد عواملي مانند شکل مجموعه داده تاثيرگذار است
٣- تصوير مجموعه داده ها را مطابق رابطه (١٢) بروي بردارهاي ويژه انتخاب شده محاسبه مي کنيم و آنها را بردارهاي نگاشت مي ناميم (Prj).
٤- با يافتن حد آستانه مناسب ، به طور جداگانه بر روي هريک از اين بردارهاي نگاشت عمليات خوشه بندي را انجام مي دهيم .
٥- با توجه به ميزان توانايي و موفقيت اين بردارها در خوشه بندي ، به هرکدام از آنها وزن را اختصاص مي دهيم
٦- براي محاسبه خوشه بندي نهايي ، مطابق رابطه (١٤) براي راي گيري ، ميانگين وزندار خوشه بندي بر اساس بردارهاي نگاشت را محاسبه مي نماييم .
v
هر در رابطه فوق برداري است که نشان دهنده راي بردار ويژه iام براي خوشه بندي هر يک از داده هاي مجموعه داده مي باشد. با انتخاب حد آستانه مناسب و اعمال آن بروي بردار FinalVote خوشه بندي نهايي را اعمال مي کنيم . به عنوان مثال براي خوشه بندي داده ها به دو خوشه ، حدآستانه را برابر با ١.٥ در نظر مي گيريم .
٤- نتايج آزمايشها
در اين بخش به بررسي چند آزمايش مي پردازيم . طبق الگوريتم ارائه شده در بخش ٣ بعد از مرتب نمودن نزولي بردارهاي ويژه بر اساس مقادير ويژه ، تصوير مجموعه داده را بر روي بردارهاي ويژه انتخاب شده محاسبه مي نماييم و با قرار دادن حد آستانه مناسب روي بردارها، داده ها را خوشه مي کنيم . سپس با انتساب دادن وزن مناسب به هر يک از اين بردارها که نشان دهنده تعلق داده ها به خوشه ها مي باشند، براي مشخص نمودن خوشه نهايي که داده به آن متعلق است از راي گيري استفاده مي کنيم . براي انجام آزمايشها از کرنل گوسي استفاده نموده ايم که براي هرآزمايش مقدار σ مشخص شده است . براي ارزيابي روش پيشنهاد شده ، ميزان خطا (درصد نمونه هايي که نادرست خوشه بندي شده اند) در اين روش را با الگوريتمهاي خوشه بندي فازي C- ميانگين و K-ميانگين مقايسه نموده ايم و براي مقايسه بهتر، هر يک از الگوريتمهاي فازي C-ميانگين و K-ميانگين را هم در فضاي ورودي و هم در فضاي حاصل از نگاشت داده ها بروي بردارهاي ويژه KPCA اعمال مي نماييم . در هر يک از آزمايشهاي زير، wi ها نشان دهنده وزن منتسب به بردار ويژگي iام است . σ عرض کرنل گوسي به کار رفته را نشان مي دهد و Thr حد آستانه مورد استفاده براي خوشه بندي روي بردارهاي نگاشت مي باشد.
٤-١ آزمايش ١
مجموعه داده دوبعدي نشان داده شده در شکل ١ را در نظر بگيريد.
پارامترهاي در نظر گرفته شده براي اين مجموعه داده در جدول ١ نشان داده شده است .
در شکل ٢ نگاشت مجموعه داده بر روي سه بردار ويژه اول و نتيجه حاصل از خوشه بندي داده ها بروي اين بردارها نمايش داده شده است .
همانگونه که در شکل ٢ مشهود است توانايي بردار ويژه اول براي خوشه بندي داده ها نسبت به بردار دوم و سوم بيشتر مي باشد، بنابراين با اختصاص دادن وزن ٢ به بردار اول و وزن ١ به دو بردار دوم و سوم (جدول ١)، طبق رابطه (١٤) به محاسبه ميانگين وزندار پرداخته و خوشه بندي نهايي را انجام مي دهيم . مقايسه خطا در روش پيشنهادي و الگوريتمهاي فازي C-ميانگين و K-ميانگين در جدول ٢ نشان داده شده است . نتايج نهايي خوشه بندي با اين سه روش نيز در شکل ٣ مشاهده مي شود.
