آخرين ارسالهاي تالار

خطا: mod_kunenalatest:كيوننا نسخه 1.7 (يا بالاتر) بر روي سيستم شما نصب نيست!
پیغام
  • Kunena is not installed or the installed Kunena version is not supported. The plug-in has now been disabled. Please install/upgrade Kunena to version 1.7 for the Kunena Discuss Plug-in to function properly.
اعمال تبديل بر ويژگيها با استفاده از خطاي كلاس­بندي كمينه مبتني بر هسته برای بازشناسي الگو مشاهده در قالب PDF چاپ فرستادن به ایمیل
نوشته شده توسط admin   
سه شنبه, 10 تیر 1393 ساعت 23:43

اعمال تبديل بر ويژگيها  با استفاده از خطاي كلاس­بندي كمينه مبتني بر هسته برای بازشناسي الگو

 

چكيده

روشهاي اعمال تبديل بر وي‍‍ژگي را مي­توان به دو دسته خطي و غيرخطي تقسيم كرد. روشهاي تبديل و استخراج وي‍ژگي مبتني بر هسته از جمله روش­هاي غيرخطي هستند كه اخيراً مورد توجه بيشتري قرار گرفته­اند. در اين روشها، ايده اصلي نگاشت غيرخطي ويژگيها به فضايي با ابعاد بالاتر است. اين نگاشت با هدفها و معيارهاي متفاوتي صورت مي­گيرد. در آناليز متمايزساز خطي مبتني بر هسته (KLDA)، معيار تفكيك­پذيري بيشتر ويژگيها در فضاي جديد است، حال آنكه در آناليز مولفه­هاي اصلي مبتني بر هسته (KPCA)، معيار استقلال بيشتر ويژگيها در فضاي حاصل است. در مقاله حاضر يك روش جديد مبتني بر هسته پيشنهاد و فرموله مي شود كه بر كمينه كردن خطاي كلاس­بندي در فضاي ايجاد شده توسط هسته (KMCE) تكيه دارد. معیارهای بهینه­سازی در روشهای KLDA و KPCA مستقل از خطای کلاس­بندی می­باشند در صورتیکه در روش پیشنهادی علاوه بر بهره برداری از ایده­ی نگاشت غیرخطی هسته­، معیار کمینه­سازی خطای کلاس بندی نیز مورد نظر قرار می­گیرد. نتايج حاصل بر روي دادگان UCI و كلاس­بندهاي مختلف، نشان مي­دهند كه روش پيشنهادي در مقايسه با روشهاي تبديل ويژگي خطي و روشهاي شناخته شده تبديل ويژگي مبتني بر هسته، در مورد كلاس­بندهای مبتنی بر فاصله، نرخ بازشناسی بهتری دارد و در مورد کلاس­بندهای آماری و مبتنی بر درخت تصمیم نیز کارآیی قابل قبولی دارد.

کلمات کلیدی: تبدیل ویژگی،  آنالیز تفکیک­پذیری خطی، روش آنالیز مولفه اصلی، خطای کلاس­بند کمینه، تابع هسته

 

 

 

1. مقدمه

تبدیل ویژگی[1] اصل مهمی در شناسائی الگو[2]ست. هدف اصلی آن انتقال دادگان با ابعاد زیاد به فضای جدید با ابعاد کمتر می­باشد، که در این فضا توصیف ساختار داده­ها بهتر انجام گیرد. به عنوان مثال اگر ساختار کلاسهایی که تفکیک­پذیری غیرخطی­اند با تبدیلی به خطی تبدیل شود، عملاً کلاس­بندی آسانتر می­شود و تفکیک­پذیری خطی کلاسها افزایش می­یابد. تبدیل ویژگی خود می­تواند مراحل استخراج ویژگی[3]، کاهش ویژگی[4] و تبدیل ویژگی را در برداشته باشد، که برای هر بخش روشهای مختلفی ارائه شده است. از سویی تبدیل ویژگی می تواند بصورت تبدیل خطی مانند آنالیز تفکیک­پذیری خطی[5] (LDA)یا تبدیل غیرخطی مانند آنالیز تفکیک­پذیری مبتنی بر هسته[6] انجام گیرد.

تبديل ويژگي فرايندي است كه در طي آن مجموعه ويژگي جديدي ايجاد مي­شود. از ديدگاهي مي­توان تولید ويژگي[7] و استخراج ويژگي را از انواع تبديل ويژگي دانست. كه معمولاً به هر دو روش كشف ويژگي[8] گفته مي­شود. در ايجاد ويژگي فرايند با توليد ويژگي­هاي جديد همراه است كه به اين ترتيب علاوه بر ويژگي­هاي اوليه، ويژگي­هاي توليد شده نيز به مجموعه ويژگي­ها اضافه مي­شود. فرايند استخراج ويژگي به صورت يك تابع نگاشت از فضاي ويژگي­هاي اصلي به فضاي ويژگي­هاي جديد مي­باشد. ايجاد ويژگي تعداد ويژگي­ها را زياد مي­كند، در مقابل استخراج ويژگي تعداد ويژگي­ها را كاهش مي­دهد. انتخاب ويژگي[9] زيرمجموعه­اي از ويژگي­هاي اصلي را بدون تغيير آن­ها انتخاب مي­كند و به نوعي كاهش ويژگي را نيز در بردارد.

مطالعات زیادی در زمینه روشهای تبدیل داده و ویژگی انجام شده است [1-5]. روش آنالیز مولفه­ اصلی[10](PCA) بر اساس مقادیر ویژه[11] و بردارهای ویژه[12] عمل می­کند و بردارهای ویژه­ای را بر می­گرداند که دارای مقدار ویژه­ بزرگتری باشند [1]. روش PCA بر اساس وابستگی داده­ها عمل می­کند. این تبدیل خطی و بدون ناظر بوده و تضمین می­کند که داده­های تبدیل یافته دارای وابستگی نباشند [1]. از روشهای خطی دیگر می­توان به روش MDS[13] اشاره کرد که در آن از ماتریس ضرب داخلی داده­ها استفاده می­شود و نشان داده شده است که هم­ارز PCA می­باشد [9].

روش آنالیز تفکیک­پذیری خطی بر اساس معیار Fisher عمل می­کند. این روش باناظر سعی در بدست آوردن تبدیلی دارد که فاصله درون کلاسی را کاهش و فاصله برون کلاسی را افزایش دهد [2]. عدم همبستگی دادگان در کلاسبندی مطلوب بوده، از اینرو روش آنالیز تفکیک­پذیری خطی غیر همبسته[14] مطرح گردیده است. روش ULDA تبدیلی بدست می­آورد که علاوه بر افزایش معیار Fisher، مولفه­های ویژگی تبدیل یافته  بطور آماری همبستگی کمتری داشته باشند [3]. روش LDA برای مسائلی که فاصله کلاسها در آن کم می­باشد عملکرد ضعیفی دارد که به همین جهت روش آنالیز تفکیک­پذیری خطی وزن­دهی[15] (WLDA) شده مطرح گردیده است[4]. عملکرد روش WLDA به نحوه انتخاب تابع وزن­دهی کلاس­ها وابسته است که Loog و همکارانش در [5] روش [16]aPAC را برای حل این مشکل پیشنهاد کردند. فرض یکسان بودن واریانس کلاس­ها در روش LDA، عملکرد این روش را زمانی که واریانس کلاسها مشابه نیست، ضعیف می­­کند. روشهای HDA[17] [6]، HLDA[18] [2]، [19]UHLDA [7] و PLDA[20] [8] این فرض را از LDA حذف کرده­اند.

از دیگر روشهای تبدیل می­توان به آنالیز مولفه­های مستقل[21] اشاره نمود. در ICA وابستگی آماری مولفه­های مختلف را کاهش می­دهد [10]. از این تبدیل برای تفکیک­پذیری کور منابع[22] استفاده می­شود. عملکرد ICA متناسب با درستی فرض مستقل بودن منابع می­باشد [10]. روش خطی آنالیز تفکیک­پذیری ارتجاعی[23] با ایجاد نیروی کشش بین نمونه­های یک کلاس و نیروی رانش بین نمونه­های دو کلاس متفاوت سعی در تمایز نمونه­ها دارد [11]. تکنیک­های گفته شده با بهینه­سازی معیاری سعی در بدست آوردن تبدیل دارند. که اصولاً با معیار کلاس­بندی متفاوت است. روش خطای کلاس­بند کمینه[24] بر اساس کاهش خطای کلاس­بندی عمل می­کند. کاهش خطای کلاس­بندی می­تواند از طریق تغییر مدلها کلاس­بند در مرحله یادگیری یا تبدیل ویژگی­ها صورت پذیرد [12, 13]. روش تبدیل ویژگی MCE به صورت یک الگوریتم تکرار شونده است که در آن ماتریس تبدیل ویژگی با توجه به خطای کلاس­بند بدست آمده که این بهینه­سازی می­تواند گرادیان کاهشی [13] یا الگوریتم­های تکاملی مانند استراتژی تکاملی[25] [14] باشد.

دسته دیگری از روشهای تبدیل ویژگی، روشهای غیرخطی می­باشند. تبدیلات خطی در متمایزسازی دادگانی که کلاسهای آن ذاتاً جداسازی خطی نمی­شوند، عملکرد ضعیفی دارند. روش غیرخطی آنالیز مولفه­های اصلی(NLPCA)[26] مشابه با PCA برای تعیین و کاهش همبستگی داده­ها به کار می رود. روش PCA همبستگی خطی بین ویژگیها را مشخص می­کند اما NLPCA همبستگی خطی و غیرخطی بین ویژگیها را بدون توجه به ماهیت غیرخطی داده­ها مشخص می­کند. در روش NLPCA یک شبکه عصبی برای تعیین نگاشت غیرخطی آموزش داده می­شود. [15-17]

دیدگاه غیرخطی دیگر استفاده از تابع هسته می­باشد، به این معنی که ابتدا با تابع هسته داده­ها به فضای غیرخطی نگاشت داده می­شوند و در این فضا نگاشت خطی اعمال می­گردد. این ایده در ماشین بردار پشتیبان (SVM) غیرخطی بکار می­رود. [18, 19] روش آنالیز تفکیک­پذیری ارتجاعی مبتنی بر هسته[27] [11]، آنالیز مولفه­های اصلی مبتنی بر هسته[28] [20, 21]، آنالیز تفکیک­پذیری مبتنی بر هسته[29] [29] نمونه­هایی از روشهای مبتنی بر هسته می­باشند. Mika و همکارانش الگوریتم تفکیک­پذیری Fisher مبتنی بر هسته را بهمراه منظم­سازی ماتریس پراکندگی درون کلاسی ارائه کردند [24]. Xiong و همکارانش الگوریتم KDA موثری پیشنهاد کردند که از آنالیز دو مرحله­ای و تجزیه QR استفاده می­کند [25]. Yang و همکارانش روش KPCA بهمراه LDA را پیشنهاد کردند که متمایزسازی را دو چندان می­کند [26]. Xiong و همکارانش دو روش آنالیز تفکیک­پذیری غیرهمبسته مبتنی بر هسته[30] و آنالیز تفکیک­پذیری متعامد مبتنی بر هسته[31] ارائه داده­اند که سعی در ناهمبستگی بیشتر دادگان و تعامد آنها دارند [23].  در روش­های مبتنی بر هسته تعیین نوع هسته در عملکرد روش تبدیل ویژگی موثر است، در این راستا بررسی­هایی روی عملکرد توابع هسته مختلف در SVM صورت گرفته است [22]. انتخاب تابع هسته به روش­ تبدیل ویژگی مبتنی بر هسته و ماهیت دادگان بستگی دارد.

از منظر ديگري مي­توان روشهاي تبديل ويژگي را به دو دسته باناظر و بدون ناظر طبقه نمود. در روش­هاي باناظر اطلاعاتي از قبيل برچسب كلاس نمونه­هاي آموزشي در اختيار الگوريتم قرار دارد، اما در روش­هاي بدون ناظر هيج اطلاعاتي از كلاس دادگان در اختيار الگوريتم نمي­باشد. از روشهاي باناظر مي­توان به LDA، MCE و از روشهاي بدون ناظر مي­توان به PCA و KPCA اشاره نمود.

در این مقاله روش خطای کلاس­بند کمینه مبتنی بر هسته[32] ارائه شده است. همان گونه كه گفته شد روش­هاي تبديل ويژگي عملكرد ضعيفي بر روي دادگاني كه به طور خطي تفكيك­پذير نيستند، دارند. از اينرو روشهاي غيرخطي مطرح شدند كه شاخه­اي از آنها روش­هاي مبتني بر هسته مي­باشند. از سويي ديگر روش خطای کلاس­بند کمینه نسبت به روش­هاي ديگر تبديل ويژگي عملكرد بهتري دارد، چرا كه معيار بهينه­سازي آن نرخ خطاي كلاس­بندي است. به عبارت ديگر تبديلي را بدست مي­آورد كه سعي در كاهش خطاي كلاس­بندي داشته باشد. با توجه به خواص مكانيزم نگاشت غيرخطي و روش خطای کلاس­بند کمینه  بر آن شديم تا با تلفيق اين دو الگوريتم روش جديدي ارائه شود كه خواص هر دو مكانيزم را در بر داشته باشد. روش پیشنهادی به این صورت عمل می­کند که ابتدا با یک نگاشت غیرخطی دادگان را به فضای با ابعاد بزرگتر می­برد، سپس الگوریتم MCE در فضای جدید اعمال می­شود. روش پيشنهادي يك روش باناظر و بدون كاهش ويژگي خواهد بود. روش پیشنهادی برمبنای دو تابع خطا ارائه شده است. عملکرد روش KMCE با روش های خطی MCE، LDA و PCA و روشهای غیرخطی KLDA و KPCA مقایسه شده است. آزمایشات بر روی دادگان دو کلاسی با دو ویژگی و دادگان Iris، glass و vowel از مجموعه دادگان UCI [30] انجام شده است.

ادامه مقاله به این صورت خواهد بود که در بخش دوم روشهای تبدیل ویژگی خطی و غیرخطی بررسی می­شوند. در بخش سوم روش پیشنهادی تبدیل ویژگی غیرخطی مبتنی بر هسته ارائه می­شود. نتایج آزمایشات در بخش چهارم بیان می­شوند. در نهایت بخش پنجم به نتیجه گیری اختصاص دارد.

2. روشهای تبدیل ویژگی

مرحله استخراج ويژگي­ها در سيستم­هاي بازشناسي الگو يكي از قسمت­هاي كليدي و مؤثر در كارائي سيستم مي­باشد كه دقت سيستم بازشناسي به عملكرد استخراج ويژگي وابسته است. ویژگیها باید بتوانند میان کلاسها تمایز به وجود آورند که چون خود ویژگیها قادر به ایجاد تمایز کافی میان کلاسها نیستند، می توان از روشهای تبديل ويژگي برای ایجاد تمایز بيشتر میان کلاسها استفاده کرد. در اين بخش تعدادي از مهمترین روشهاي متمايزساز خطي و غيرخطي مورد بررسی قرار می­گيرند.

1.2. روشهاي تبديل ويژگي خطي

شاخه­اي از روشهاي تبديلات ويژگي، روشهاي خطي مي­باشند كه عملكرد قابل قبولي براي دادگان با قابليت تفكيك­پذيري خطي دارند. روش­هاي PCA و LDA از شناخته­ترين روشهايي هستند كه در اين دسته قرار مي­گيرند. روش PCA روش بدون ناظر و روش LDA روش باناظر مي­باشد. هر دو روش سعي در بهينه­سازي تابع خاصي دارند. روش MCE نيز روش تبديل وي‍ژگي ديگري است كه هم خطي و هم باناظر مي­باشد. در روش MCE برخلاف دو روش PCA و LDA ، سعي در بدست آوردن ماتريس تبديلي است كه خطاي كلاس­بندي را كاهش دهد. در اين زيربخش سه روش PCA، LDA و MCE بررسي خواهند شد.

1.1.2. آنالیز مولفه­های اصلی

تبدیل خطی­ PCA  دادگان را به فضایی نگاشت می کند که  دراآن داده ها بیشترین واریانس را  داشته باشند. فرض کنید دادگان شامل N مشاهده، Xk ، k=1,…,N و  باشد. ماتریس کوواریانس مجموعه دادگان از رابطه زیر بدست می­آید: [37]

(1)

با قطری­سازی C مولفه­های اصلی بدست می­آیند که این مولفه­ها تصویر متعامد روی بردارهای ویژه هستند که با حل معادله مقادیر ویژه محاسبه می­شوند. [37]

(2)

که  مقادیر ویژه و  (به معنی  به استثنای ) بردارهای ویژه می­باشند. از طرفی ، همه پاسخها برای V بایستی ترکیب خطی از مشاهدات باشند، داریم: [37]

(3)

که ها ضرایبی هستند که مقادیر آنها به گونه­ای انتخاب می­شوند که رابطه بالا برقرار باشد. [37]

2.1.2. آنالیز تفکیک­پذیری خطی

LDA يكي از روش­هاي شناخته شده براي ایجاد تمایز میان ویژگیها و كاهش خطي ابعاد وي‍ژگي[33] باناظر مي­باشد. در LDA كلاسيك، ماتريس كوواريانس درون كلاسي و برون كلاسي بفرم زير محاسبه مي­شوند. [38]

(4)

(5)

كه N تعداد كل نمونه­ها، Ni تعداد نمونه­هاي كلاس iام، µi ميانگين كلاس iام، I تعداد كلاسها و   نمونه niام از كلاس iام مي­باشند. trace(SW) همبستگي درون كلاسي و trace(Sb) تمايز بين كلاسي را اندازه­گيري مي­كنند. تابع trace مقادير روي قطر اصلي ماتريس مربعي وروديش را بر مي­گرداند. [39] هدف LDA بدست آوردن ماتريس تبديل، W است به نحوي كه رابطه Fisher را ماكزيمم كند. [38]

(6)

2.1.3. خطاي کلاس­بند کمينه

روش کمينه نمودن خطاي کلاس‌بندي (MCE) ، روش متمايزسازي است كه هم در گروه تبديل ويژگي و هم در گروه آموزش دسته­بند بكار گرفته مي­شود [31, 32]. هنگامي‌که روش MCE براي آموزش HMM (به عنوان يک دسته‌بند) استفاده مي‌شود، MCE پارامترهاي مدل را بگونه­اي تغيير مي­دهد كه خطاي كل كلاس‌­بندي كاهش يابد [36]. در روش آموزش به کمک MCE، ابتدا تابع هدف (که براي يافتن پارامترهاي HMM بکار مي‌رود) با استفاده از يک تابع پيوسته مدل مي‌شود. سپس، کمينه اين تابع با يک روش ، مانند Gradient Probabilistic Descent، بدست مي‌آيد [33].

ايده اصلي الگوريتم MCE، بهينه‌سازي نرخ خطاي تجربي با استفاده از يک مجموعه داده آموزشي، جهت بهبود نرخ خطاي بازشناسي مي‌باشد. پس از آنکه نرخ خطاي تجربي، بوسيله يک بازشناس يا دسته‌بند، کمينه شد، تخميني باياس شده از نرخ خطاي واقعي بدست مي‌آيد. يک راه مؤثر جهت کاهش اين نرخ و بهبود کارآيي کلي سيستم، افزايش مرز ميان کلاس‌ها در داده‌هاي آموزشي است. به اين منظور از گراديان کاهشي [33] يا ترکيب امتيازهاي حاشيه و نرخ خطاي تجربي استفاده شده است.

روش MCE براي بدست آوردن تبديل‌ فضاي ويژگي نيز استفاده مي‌شود. در [34]، MCE براي يافتن ماتريس تبديل ويژگي‌ها، که بتواند خطاي کلاس‌بندي را کمينه کند، استفاده شده است. Wang و Paliwal  اين روش را براي بازشناسي واکه‌ها بهبود بخشيدند [35]. در اين رويکردها از تابع هزينه‌ بصورت رابطه (7) استفاده شده است.

(7)

 

که در آن M تعداد کلاس‌ها، η مقداري مثبت (ارائه شده در [36])، و لگاريتم احتمال تعلق O به کلاس iλ که بصورت رابطه (8) تعريف مي‌شود:

(8)

 

که F مجموعه پارامترهاي مرتبط با ويژگيها و کلاس­بندها مي­باشد. در روش MCE ، هدف کمينه نمودن تابع هزينه(7) است. اما از آنجا که اين توابع مشتق­پذير نيستند، از يک تابع پيوسته نرم مانند تابع سيگمويد بعنوان تابع هزينه استفاده مي­کنيم. بنابراين خواهيم داشت:

(9)

 

که  تابع هزينه (7) مي­باشد و  پارامتر تنظيم بزرگتر از يک است. بنابراين اگر خيلي کوچکتر از صفر باشد، در واقع يک دسته‌بندي درست رخ داده و  به صفر نزديک مي­شود. از طرفي مقدار مثبت براي  نشان دهنده جريمه براي دسته‌بندي نادرست است و در اينصورت  به 1 متمايل مي­شود. کل خطاي کلاس‌بند براي مشاهده O از رابطه (10) بدست مي­آيد:

(10)

 

با استفاده از ماتريس تبديل، بردارهاي ويژگي از فضاي ويژگي اصلي به فضاي جديد برده مي‌شود تا تمايز کلاس‌ها بيشتر گردد. تمايز بيشتر باعث کاهش خطا مي­شود. از اينرو با استفاده از معيار تابع هزينه سعي مي‌شود ماتريس تبديل بهينه بدست آيد. مقادير درايه‌هاي ماتريس تبديل بروش تکراري با استفاده از گراديان كاهشي براي تابع L، با رابطه (11) قابل محاسبه خواهد بود.

(11)

 

رابطه فوق را مي­توان بصورت ماتريسي بيان کرد:

(12)

 

کهW ماتريس تبديل؛ r شاخص rامين درايه ماتريس تبديل W؛ iter انديس تکرار الگوريتم، و پارامتر يادگيري مي­باشد. رابطه (12) نشان‌دهنده يک رويه تکراري است. اين رويه زماني متوقف مي‌شود که مقدار تابع هزينه از يک حد آستانه کمتر شود.

فرض کنيد ماتريس تبديل W بردار ويژگي‌هاي n بُعدي x را به بردار y با بُعد (d≤ n) d تبديل مي‌کند. هدف، بدست آوردن ماتريس تبديل W است که تابع هزينه را کمينه نمايد. براي كمينه كردن خطا از رابطه (9) نسبت به W مشتق گرفته مي­شود، مي‌توان نوشت:

(13)

 

تابع هزينه  همان رابطه (9) مي‌باشد. بردار O رشته مشاهده يا رشته بردار ويژگي‌هاي تبديل‌يافته است و بصورت مي‌باشد. همچنين بردار ويژگي‌هاي اصلي بصورت  نشان داده شده است. با توجه به رابطه (9) خواهيم داشت [8]:

(14)

 

براي محاسبه بخش دومِ رابطه (13)،  ، از رابطه (7) بر حسب W مشتق­گيري مي­شود:

(15)

 

در اين رابطه  با توجه به نوع کلاس­بند محاسبه مي­شود. به عنوان مثال نحوه محاسبه براي کلاس­بند مبتني بر فاصله بصورت زير است.

(16)

که  درايه dام مرکز کلاس iام مي­باشد. با جايگذاري (16) در رابطه (15) مقدار  بدست مي­آيد. با جایگزین کردن  رابطه محاسبه شده  و رابطه (14) در (13) مقدار  بدست مي­آيد. با بكارگيري مقادير  در رابطه (12) ماتريس بهينه بدست مي­آيد.

2.2. روشهاي تبديل وي‍ژگي غيرخطي

همانطور كه گفته شد مي­توان روش­هاي تبديل وي‍ژگي را به دو دسته روشهاي خطي و غيرخطي تقسيم نمود. علت پيدايش روشهاي غيرخطي عملكرد ضعيف روشهاي تبديل ويژگي خطي براي دادگاني است كه به طور خطي تفكيك­پذير نيستند. روشهاي غيرخطي به اين صورت عمل مي­كنند كه به كمك يك نگاشت غيرخطي داده­ها را به فضاي جديد با ابعاد زياد برده كه در اين فضا دادگان به طور خطي تفكيك­پذير مي­شوند. بعضي از روشهاي غيرخطي با كمك شبكه عصبي نگاشت غيرخطي ايجاد مي­كنند و سپس تبديلي خطي بكار مي­برند از قبيل NLPCA. دسته ديگر از روشهاي غيرخطي روشهاي مبتني بر هسته مي­باشند. در روش­هاي تبديل غيرخطي، نگاشت غيرخطي در دست نمي­باشد و با روشهايي آن را تخمين مي­زنند. روش­هاي مبتني بر هسته بر اين ايده استوارند كه ضرب داخلي دادگان نگاشت يافته با يك تابع غيرخطي نامعلوم را مي­توان با تابع هسته تخمين زد، كه به آن ايده هسته[34] گفته مي­شود. در ادامه ابتدا ايده هسته و سپس دو روش KLDA و KPCA بررسي خواهند شد.

2.2.1. ايده تابع هسته

مجموعه X را در نظر بگيريد تابع هسته k به صورت زير تعريف مي شود.

(17)

 

از ويژگيهاي تابع هسته مي­توان متقارن بودن و مثبت بودن را نام برد، كه در روابط (18) و (19) اين مطلب بيان شده است.

(18)

 

(19)

 

مي­توان نشان داد که براي يک تابع هسته، k، فضاي هيلبرت H و يک تبديل  وجود دارد که رابطه زیر برقرار باشد:

(20)

 

2.2.2. آنالیز مولفه­های اصلی مبتنی بر هسته

تکنیک اصلی KPCA محاسبه تبدیل PCA در فضای نگاشت یافته توسط یک تابع نگاشت غیر خطی است که از ایده  هسته برای  تخمین این نگاشت استفاده می شود. داده­های نگاشت یافته  را در نظر بگیرید که میانگین آنها صفر نباشد. ابتدا با رابطه زیر میانگین داده­های نگاشت یافته صفر می­شود:

(21)

ماتریس کوواریانس از رابطه (22) محاسبه می­شود:

(22)

 

معادله مقادیر ویژه برای ماتریس کوواریانس فوق بفرم  می­باشد. که  مقادیر ویژه و  (به معنی  به استثنای ) بردارهای ویژه می­باشند. معادل معادله مقادیر ویژه را می­توان به صورت رابطه (23) نوشت:

(23)

 

که ها ضرایبی هستند که مقادیر آنها به گونه­ای انتخاب می­شوند که رابطه (26) برقرار باشد.

(24)

 

كه با جايگذاري رابطه (24) در  رابطه (23) خواهيم داشت:

(25)

که K ماتريس هسته بوده و به فرم ماتريس مربعي  با عناصر  مي­باشد . براي نرمال­سازي راه­حل­هاي ، بايستي رابطه  در فضاي نگاشت يافته اعمال شود. همچنين، همانند هر الگوريتم PCA ديگري، دادگان در فضاي نگاشت يافته بايد متمركز[35] شوند. براي اين كار ماتريس هسته با رابطه زير جايگزين مي­شود،

(26)

که  مي­باشد. [20]

2.2.3. آنالیز تفکیک­پذیری خطی مبتني بر هسته

در مورد  داده­هایی که به صورت طبيعي تفكيك­پذيرخطي نيستند،   روش­هاي متمايزساز ويژگي خطي از قبيل LDA كارائي لازم را نخواهند داشت. از اينرو روش­هاي مبتني بر هسته ارائه شده­اند كه اين روش­هاي بار محاسباتي كمي نسبت به روشهای غیرخطی مبتنی بر شبکه عصبی به سيستم تحميل مي­كنند. فرض كنيد مشاهدات، X از طريق تابع  به فضاي جديد نگاشت داده شوند، ماتريس كوواريانس درون كلاسي و برون كلاسي در فضاي نگاشت يافته بفرم زير محاسبه مي­شوند. [40]

(27)

(28)

که N تعداد كل نمونه­ها، Ni تعداد نمونه­هاي كلاس iام،  ميانگين كلاس iام در فضاي نگاشت يافته، I تعداد كلاسها و   نمونه niام از كلاس iام در فضاي نگاشت يافته مي­باشند. هدف KFDA ماكزيمم كردن رابطه زير مي­باشد:

(29)

اما ماتريس تبديل W را مي­توان به صورت ميانگين وزني داده­هاي آموزشي نگاشت يافته نوشت،

(30)

بنابراين رابطه Fisher به صورت زير خواهد شد:

(31)

كه P و Q از طريق توابع هسته قابل محاسبه مي­باشند. روابط زير نحوه محاسبه P و Q را نشان مي­دهند. [40]

(32)

(33)

كه K ماتريس هسته،  و تابع k(.)، تابع هسته مي­باشد. و I ماتريس هماني،  كه در آن N تعداد كل مشاهدات مي­باشد. و ماتريس R بفرم زير محاسبه مي­شود.

(34)

كه Nj تعداد مشاهدات مربوط به كلاس jام است.

در این بخش دو دسته روشهای تبدیل ویژگی خطی و غیرخطی مورد بررسی قرار گرفتند. روشهای تبدیل ویژگی خطی مانند LDA، PCA و MCE با اعمال یک تبدیل خطی روی ویژگی­ها، بردارهای ویژگی را به فضای جدید نگاشت می­دهند. در روش LDA تبدیل بر اساس معیار Fisher بدست می­آید. در این معیار ماتریس تبدیلی به منظور افزایش کوواریانس بین کلاسی به کوواریانس درون کلاسی بدست می آورد. و در PCA سعی دارد که دادگان در فضای ویژگی جدید بیشترین واریانس ممکن را دارا باشند. در هر دو این روشها علاوه بر فرضیاتی که روی دادگان دارند، ماتریس تبدیل بر مبنای ماکزیمم کردن معیاری بدست می آید که به کلاس­بند توجهی ندارد. روش MCE نیز یکی دیگر از روشهای تبدیل ویژگی خطی است. در این روش ماتریس تبدیل بر اساس کاهش خطای کلاس بند بدست می آید بنابراین انتظار عملکرد بهتری برای این روش نسبت به دو روش LDA و PCA در کلاس بندی می­رود.

روشهای تبدیل ویژگی خطی برای دادگانی که ذاتاً تفکیک­پذیر خطی نیستند عملکرد ضعیفی دارند، از اینرو محققان روشهایی تبدیل ویژگی غیرخطی را ابداع نمودند. زیر شاخه­ای از روشهای غیرخطی، روشهای مبتنی بر هسته هستند. این روشها ابتدا با یک نگاشت غیرخطی دادگان را به فضای با ابعاد بزرگتر می­برند. فرض بر این است که دادگان در این فضای به اندازه کافی بزرگ، تفکیک پذیر خطی هستند. سپس با اعمال یکی از روشهای تبدیل خطی روی دادگان نگاشت یافته، فضای ویژگیها را تغییر می­دهند. اما تابع غیرخطی برای نگاشت به فضای با ابعاد بزرگ در دسترس نمی­باشد بنابراین روابط را به گونه­ای بازنویسی و فرموله می­کنند که ضرب نقطه­ای نمونه­های نگاشت یافته حاصل شود و بعد ضربهای نقطه­ای را با تابع هسته جایگزین می­کنند.

روشهای KLDA و KPCA دو روش تبدیل ویژگی مبتنی بر هسته می­باشند که روابط آنها در این بخش آورده شده است. این روشها عملکرد بهتری نسبت به روشهای تبدیل ویژگی خطی دارند. این برتری برای دادگانی که ذاتاً تفکیک­پذیر خطی نیستند مشهودتر است. اما از آنجائی که معیار بدست آوردن این تبدیلات همان رابطه Fisher و واریانس ویژگیها می­باشند بنابراین انتظار بهتر بودن برای این روشها در کاربرد کلاس­بندی نمی­رود. در ادامه برای رفع این نقیصه یعنی عدم انطباق معیار بدست آوردن تبدیل ویژگی با خطای کلاس­بندی روش خطای کلاس­بند کمینه مبتنی بر هسته (KMCE) پیشنهاد گردیده است.

3. روش پیشنهادی - خطای کلاس­بند کمینه مبتنی بر هسته (KMCE)

روش پیشنهادی، KMCE، غیرخطی سازی روش MCE از طریق ایده هسته است. این روش از سویی دارای خاصیت MCE یعنی انطباق معیار تخمین تبدیل با کلاس­بندی می­باشد. و از سوی دیگر دارای خاصیت نگاشت غیرخطی روشهای مبتنی بر هسته است. در این راستا فرض می­شود که دادگان با یک تابع غیرخطی به فضای با ابعاد بزرگتر نگاشت داده می­شوند سپس الگوریتم MCE روی دادگان نگاشت یافته اعمال می­شود. با توجه به نامعلوم بودن تابع نگاشت بایستی تمامی روابط بگونه­ای بازنویسی شوند که بتوان ضربهای نقطه­ای نمونه­های نگاشت یافته را با تابع هسته جایگزین نمود. در ادامه الگوریتم پیشنهادی فرموله می­شود.

فرض كنيد مشاهده X از طريق تابع  به فضاي جديد نگاشت داده شود كه بفرم زير نمايش داده مي­شود:

(35)

 

همچنین فرض کنید که با ماتریس تبدیل W داده های نگاشت یافته به  تبدیل شوند.

(36)

 

از طرفی W بفرم  تعریف می شود که N تعداد کل نمونه های آموزشی و  نمونه iام داده آموزشی نگاشت یافته می باشد. بنابراین رابطه (36) به صورت زیر در می­آید:

(37)

 

روش خطای کلاس­بندی کمینه سعی در بدست آوردن تبدیلی دارد که خطای کلاس­بندی را کاهش دهد. دو تابع هزینه برای این روش در مقالات ارائه شده است كه آنها در فضاي نگاشت يافته بازنويسي شده­اند.

(38)

 

که I تعداد کلاسها،  ηعدد مثبتی است. همچنین  مشاهده­ی نگاشت یافته و تبدیل یافته  از کلاس kام می­باشد.  برابر با مربع فاصله با نماينده كلاس iام در فضاي نگاشت شده و تبدیل یافته يعني می باشد که به صورت رابطه زير بیان می­گردد.

(39)

 

با توجه به استفاده نرم اقلیدوسی و رابطه (39) داریم:

(40)

 

با بسط ضرب ماتریسی فوق بفرم عددی خواهیم داشت:

(41)

 

هدف روش خطای کلاس­بندی کمینه اين است كه توابع هزینه مینیمم شوند. ولی این توابع مشتق­پذیر نیستند، از اینرو از تابع پیوسته نرم مانند تابع سیگموید بعنوان تابع هزینه استفاده می­گردد، خواهیم داشت:

(42)

 

که  تابع هزینه (38) می­باشد و  پارامتر تنظیم بزرگتر از یک است. بنابراین اگر  خیلی کوچکتر از صفر باشد، در واقع یک کلاس­بندی درست داریم و  به صفر نزدیک می­شود. از طرفی مقدار مثبت برای  نشان دهنده جریمه برای کلاس­بندی نادرست است که در اینصورت  به یک متمایل می­شود. کل خطای کلاس­بندی برای مشاهده از رابطه (43) بدست می­آید:

(43)

 

که I تعداد کلاسها،  تعداد مشاهدات کلاس kام و  کل مشاهدات است. با استفاده از ماتریس تبدیل بردارهای ویژگی را از فضای ویژگی اصلی به فضای جدید برده تا تمایز کلاسها بیشتر شود. تمایز بیشتر باعث کاهش خطا می­شود. از همینرو با استفاده از معیار تابع هزینه سعی در بدست آوردن ماتریس تبدیل بهینه داریم. مقادير درايه‌هاي ماتريس تبدیل بروش تکراري با استفاده از گراديان كاهشي با رابطه زير محاسبه مي‌شود:

(44)

 

هدف بدست آوردن ماتریس تبدیل بهینه­ای است که تابع هزینه را کاهش دهد. از اینرو از تابع هزینه بر اساس α مشتق می­گیریم.

(45)

 

با توجه به رابطه (42) داریم:

(46)

 

برای محاسبه ترم دوم در رابطه (45)، ، از رابطه (38) استفاده می­شود. بعد از مشتق­گیری از روابط فوق می­توان نوشت:

(47)

 

مقدار  از رابطه زير محاسبه مي­گردد.

(48)

 

با جايگذاري (48) در رابطه (47) مقدار  بدست مي­آيد. با جانشيني رابطه محاسبه شده  و رابطه (46) در (45) مقدار  بدست مي­آيد. با بكارگيري مقادير  در رابطه (44) ماتريس بهينه بدست مي­آيد.

به این ترتیب ماتریس بهینه­ای بدست می­آید که پس از اعمال بر روی دادگان و کلاس­بندی دادگان تبدیل یافته خطای کلاس­بندی کاهش می­یابد. در بخش بعدی روش پیشنهادی با دیگر روشهای تبدیل ویژگی از دو منظر بصری و تاثیر روی عملکرد کلاس­بندها مورد ارزیابی قرار می­گیرد.

4. ارزیابی روش پیشنهادی KMCE

در اين بخش به مقايسه و ارزيابي روش پيشنهادي با روش­هاي MCE، LDA، PCA، KLDA و KPCA پرداخته خواهد شد. نتايج آزمايشات در دو زير بخش ارائه مي­شود. در زيربخش اول عملكرد روشها در فضاي دو بعدي بررسي مي­شود. و در زیربخش دوم نتایج کلاس بندی پس از اعمال هر یک از روشهای پیش پردازش مطرح شده در مقاله روی دادگان UCI گزارش می گردد.

1.4. ارزیابی روش KMCE در فضای دو بعدی

ابتدا روش­هاي تبديل ويژگي بر روي دو مجموعه داده دو بعدي تعريف شده با نام­هاي CircleLine و Chess بفرم شكل­های (1-الف) و (1-ب) اعمال می­­شوند. این مجموعه دادگان دارای ساختاری به فرم جدول (1) می­باشند. در این دو دیتابیس میانگین و واریانس هر ویژگی برای هر دو کلاس یکسان می­باشد. همانطور که در شکل­های (1-الف) و (1-ب) مشاهده می­شود، هر دو دادگان تفکیک­پذیر خطی نیستند. از اینرو انتظار می­رود که روشهای متمایزساز خطی عملکرد ضعیفی داشته باشند.

 

 

جدول 1 – ساختار دادگان دوبعدی CircleLine و Chess

نام دادگان

تعداد کلاس

تعداد ویژگی

تعداد نمونه آموزشی

تعداد نمونه تست

CircleLine

2

2

400

200

Chess

2

2

400

200

 

 

 

الف – دادگان Chess

ب- دادگان CircleLine

شکل 1 – نمایش دوبعدی مجموعه تست دادگان Chess و CircleLine در فضای ویژگی

 

 

شکل (2) تبدیل یافته­های دادگان Chess را پس از اعمال الگوریتمهای پیش­پردازش نشان می­دهد. در تمام روشها از دادگان آموزش برای بدست آوردن ماتریس تبدیل ویژگی استفاده شده است، سپس ماتریس تبدیل ویژگی بدست آمده روی دادگان تست اعمال می­شود. شکل )2-الف) فضای دوبعدی دادگان بعد از اعمال روش LDA را نشان می­دهد. با توجه به فرض اولیه LDA مبنی بر تفکیک­پذیری خطی دادگان و عدم تطبیق این فرض با دادگان Chess این روش عملکرد مطلوبی نداشته و صرفاً باعث دوران دادگان شده است.

شکل (2-ب) فضای دوبعدی ویژگیها را بعد از اعمال الگوریتم PCA نمایش می دهد. روش PCA بدون توجه به برچسب کلاس نمونه­های آموزشی سعی در بدست آوردن تبدیلی دارد که واریانس ویژگی ها در راستای آن ماکزیمم گردد، لذا با توجه به ساختار دادگان Chess واریانس در راستای قطر دادگان ماکزیمم است که انتظار می­رود تبدیل PCA دادگان را دوران داده به نحوی که قطرها در راستای محورهای جدید ویژگی قرار گیرند. بنابراین مشاهده می­گردد که تبدیل PCA نیز عملکرد ضعیفی دارد.

شکل (2-ج) پراکندگی نمونه­ها پس از تبدیل MCE را نشان می دهد. این تبدیل سعی در کاهش خطای کلاس بندی دارد اما یک تبدیل خطی است و همانطور که در شکل دیده می­شود عملکرد ضعیفی برای دادگان Chess دارد. شکل (2-د) تبدیل یافته از روش KLDA و شکل (2-ه) تبدیل یافته از روش KPCA را نشان می­دهند. در هر دو روش از تابع هسته گوسین با پارامتر 2 استفاده شده است. همانطور که مشاهده می­شود روش­های مبتنی بر هسته نسبت به روشهای معمولی عملکرد بهتری داشته و پراکندگی دادگان به گونه است که دو کلاس توسط یک کلاس­بند خطی تفکیک­پذیر بوده و خطای کمتری نسبت به روشهای تبدیل معمولی حاصل می­شود.

شکل (2-و) نمونه­های تبدیل یافته در فضای ویژگی­های جدید پس از اعمال روش پیشنهادی، KMCE را نشان می­دهد. تابع هسته بکار رفته در این روش نیز تابع گوسین با پارامتر 2 می­باشد. با توجه به شکل می­توان دید که عملکرد روش پیشنهادی نسبت به روش MCE بسیار بهتر بوده، همچنین نسبت به روش تبدیلات مبتنی بر هسته دیگر مثل KLDA و KPCA نیز عملکرد مناسبتری داشته است. این امر با توجه به الگوریتم روش پیشنهادی و معیاری که  تبدیل بر اساس آن بدست می­آید قابل انتظار است. از سوئی روش پیشنهادی یک روش غیرخطی بوده بنابراین برتری روشهای تبدیل ویژگی مبتنی بر هسته را در بردارد و از سوی دیگر معیاری که براساس آن ماتریس تبدیل تخمین زده می­شود مستقیماً خطای کلاس­بندی است.

 

 

 

 

الف- تبدیل LDA

ب- تبدیل PCA

ج- تبدیل MCE

 

 

 

د- تبدیل KLDA

ه- تبدیل KPCA

و- تبدیل KMCE

شکل 2 – نمایش دوبعدی مجموعه تست دادگان Chess بعد از اعمال تبدیلات ویژگی LDA، PCA، MCE، KLDA، KPCA و KMCE

 

 

شکل (3) تبدیل یافته­های دادگان CircleLine را پس از اعمال الگوریتمهای پیش­پردازش نشان می­دهد. در تمامی روشهای تبدیل ویژگی از دادگان آموزش برای بدست آوردن ماتریس تبدیل ویژگی استفاده شده است و این ماتریس روی دادگان تست اعمال گردیده است. شکل­های )3-الف)، (3-ب) و (3-ج) بترتیب فضای دوبعدی دادگان بعد از اعمال روش­های LDA، PCA و MCE را نشان می­دهند. در LDA فرض بر تفکیک­پذیر خطی بودن دادگان است و با توجه به ماهیت دادگان CircleLine یعنی تفکیک­پذیر بودن غیرخطی، این روش عملکرد خوبی ندارد. روش PCA که یک روش بدون ناظر است تبدیل ویژگی­ای بدست می­آورد که واریانس ویژگی­های جدید بیشتر شود، با توجه به پراکندگی دادگان در فضای ویژگی­ها، واریانس در تمامی جهات یکسان است لذا PCA نمی­تواند تبدیل بهینه­ای بدست آورد. روش MCE ماتریس تبدیلی را بدست می­آورد که خطای کلاس بندی را کاهش دهد. روش MCE یک تبدیل خطی بدست می­آورد و عملکرد ضعیفی برای دادگانی مانند CircleLine که تفکیک پذیر خطی نیستند، دارد.

شکل (3-د) نمونه­های تبدیل یافته از روش KLDA و شکل (3-ه) نمونه­های تبدیل یافته از روش KPCA را نشان می­دهند. همانطور که مشاهده می­شود روش­های مبتنی بر هسته نسبت به روشهای معمولی عملکرد بهتری داشته و پراکندگی دادگان به گونه است که دو کلاس توسط یک کلاس­بند خطی تفکیک­پذیر بوده و خطای کمتری نسبت به روشهای تبدیل معمولی حاصل می­شود.

 

 

 

 

الف- تبدیل LDA

ب- تبدیل PCA

ج- تبدیل MCE

 

 

 

د- تبدیل KLDA

ه- تبدیل KPCA

و- تبدیل KMCE

شکل 3 – نمایش دوبعدی مجموعه تست دادگان CircleLine بعد از اعمال تبدیلات ویژگی LDA، PCA، MCE، KLDA، KPCA و KMCE

 

 

2.4. ارزیابی روش KMCE جهت پیش پردازش در کلاس­بندی

جهت بررسی بهتر عملکرد روش پیشنهادی نسبت به دیگر روش­های تبدیل ویژگی، این تبدیلات را بعنوان پیش پردازش در کلاس­بندی دادگان نگاشت یافته با هر یک از روشهای فوق بکار برده و نتایج کلاس­بندی مورد ارزیابی قرار خواهد گرفت. برای انجام آزمایشات علاوه بر دو مجموعه دادگان Chess و CircleLine از مجموعه دادگان Iris، Glass و Vowel مربوط به دادگان UCI [30] نیز استفاده شده است. مشخصات مجموعه دادگان در جدول (2) آورده شده است. برای کلاس­بندی از ابزار Weka استفاده شده است. کلاس­بندهای مورد استفاده در این بخش در سه گروه طبقه بندی می­شوند: گروه کلاس­بندهای مبتنی بر فاصله مانند IB1، IBK و KStar، گروه کلاس­بندهای آماری مانند BayesNet، گروه کلاس­بندهای مبتنی بر درخت تصمیم­گیری مانند NBTree و Random Forest. در ادامه نتایج کلاس بندی حاصل از هر یک از گروه­ها آورده شده است.

جدول (3) نتایج کلاس بندی را روی کلاس­بندهای مختلف و دادگان مختلف نشان می­دهد. ستون­های جدول نشان­دهنده روش تبدیل ویژگی و سطرها نشان­دهنده متد کلاس­بند می­باشد. روش پیشنهادی یعنی KMCE در کنار روشهای LDA، PCA و MCE به عنوان روشهای تبدیل ویژگی خطی و KLDA و KPCA بعنوان روشهای تبدیل ویژگی غیرخطی مورد ارزیابی قرار گرفته است. ستون Normal نتایج کلاس­بندی را برای دادگانی که هیچ تبدیلی روی آنها انجام نگرفته است را نشان می­دهد. اعداد مندرج در جدول نتایج کلاس­بندی دادگان نگاشت یافته را به درصد نشان می­دهد. در هر سطر بیشترین مقدار بفرم ضخیم بهمراه خط زیر و مقدار دوم بفرم فقط ضخیم نمایش داده شده است.

 

 

جدول 2 – مشخصات مجموعه دادگان UCI [30]

نام دادگان

تعداد کلاس

تعداد ویژگی

تعداد نمونه آموزشی

تعداد نمونه تست

Iris

3

4

90

60

Vowel

11

10

528

462

Glass

6

9

127

87

 

جدول 3 – نتایج کلاس بندهای مختلف روی دادگان نگاشت یافته با تبدیلات مختلف

KMCE

KPCA

KLDA

MCE

PCA

LDA

Normal

 

 

 

 

97.00

71.50

92.50

93.00

92.00

93.00

93.00

Chess

IB1

کلاس بند مبتنی بر فاصله

100.00

96.50

97.00

98.00

97.50

98.00

98.00

CircleLine

98.33

96.67

96.67

95.00

95.00

93.33

95.00

Iris

58.44

57.58

53.27

49.57

41.13

44.16

49.57

Vowel

74.71

71.26

68.97

66.67

72.41

67.82

66.67

Glass

97.50

71.50

92.50

92.50

93.00

93.00

92.50

Chess

IBK,3

100.00

96.50

97.00

97.00

96.50

97.00

96.50

CircleLine

98.33

98.33

96.67

95.00

95.00

95.00

95.00

Iris

59.74

58.23

54.33

49.13

39.39

42.86

49.13

Vowel

77.01

65.52

74.71

65.52

71.26

65.52

65.52

Glass

99.00

75.50

92.00

94.00

90.00

92.50

94.00

Chess

KStar

99.50

94.50

97.50

97.00

95.50

95.50

97.00

CircleLine

98.33

96.67

96.67

95.00

93.33

96.67

95.00

Iris

57.80

53.03

50.64

50.22

38.10

36.58

45.24

Vowel

77.01

72.41

66.67

77.01

68.97

63.22

77.01

Glass

94.50

68.50

90.50

50.00

82.50

73.50

50.00

Chess

BayesNet

کلاس بند آماری

88.50

81.00

97.00

78.00

88.00

88.00

76.00

CircleLine

96.67

95.00

95.00

96.67

96.67

95.00

91.67

Iris

42.86

39.61

44.81

36.36

37.01

41.56

36.58

Vowel

66.67

51.72

66.67

68.97

64.37

43.68

68.97

Glass

94.50

68.50

90.50

97.50

82.00

88.50

97.50

Chess

NBTree

کلاس بند مبتنی بر درخت تصمیم

99.00

81.00

97.00

95.00

89.00

92.00

95.00

CircleLine

95.00

91.67

96.67

96.67

91.67

95.00

96.67

Iris

42.64

35.50

35.04

35.71

33.55

29.44

33.33

Vowel

65.52

67.82

58.62

60.92

77.01

65.52

60.92

Glass

 

 

در ابتدای جدول (3) نتایج کلاس­بندهای مبتنی بر فاصله بیان شده است. در اینجا سه روش کلاس­بندی KStar، k نزدیکترین همسایه با شعاع همسایگی، k، برابر یک (IB1) و سه (IBK,3) مد نظر قرار گرفته است. با توجه به نتایج، روشهای تبدیل ویژگی غیرخطی عملکرد بهتری نسبت به روشهای تبدیل ویژگی خطی دارند و این تفاوت در دادگان با تعداد ویژگی و تعداد کلاس بیشتر مانند Glass و Vowel مشهودتر است. روش پیشنهادی، KMCE، نسبت به روش MCE دارای نرخ کلاس بندی بالاتری است، این امر به دلیل ویژگی مبتنی بر هسته بودن روش پیشنهادی است. همان­گونه که قبلاً گفته شد روش MCE یک روش تبدیل ویژگی خطی است و در دادگان با تعداد ویژگی و تعداد کلاس بیشتر عملکرد ضعیفی دارد. با بکارگیری MCE در قالب روش­های مبتنی بر هسته این نقیصه برطرف گردید. روش پیشنهادی بر اساس کاهش خطای کلاس بندی عمل می­کند، برای بدست آوردن خطا از کلاس­بند فاصله استفاده شده است. بنابراین انتظار می­رود که در کلاس بندهای مبتنی بر فاصله عملکرد بهتری داشته باشد و همانطور که در جدول (3) مشاهده می شود در تمامی دادگان و روشهای کلاس­بندی مبتنی بر فاصله، روش KMCE نرخ کلاس­بندی بالاتری دارد.

باید توجه داشت که روش KMCE براساس کاهش خطای کلاس بند مبتنی بر فاصله عمل می­کند و کارائی برتر این روش نسبت به دیگر روشهای تبدیل ویژگی در کلاس­بندهای مبتنی بر فاصله مشاهده شد. در ادامه عملکرد این روش در کلاس­بندهایی که از معیار فاصله استفاده نمی­کنند نیز ارزیابی خواهد شد. برای این منظور ابتدا روش پیشنهادی در کلاس­بندهای آماری و سپس در کلاس­بندهای مبتنی بر درخت تصمیم مورد بررسی قرار می­گیرد.

بخشی از جدول (3) نتایج کلاس­بندی را روی کلاس­بند آماری BayesNet نشان می­دهد. چنانچه مشاهده می­شود برای کلاس­بند BayesNet روش KMCE نسبت به روشهای تبدیل ویژگی خطی و بطور خاص نسبت به روش MCE نتایج بالاتری در کلاس بندی دارد. درضمن روش KMCE نسبت به روش KPCA عملکرد بالاتری داشته است، به عنوان مثال این بهبود در دادگان Glass از 51.72 درصد برای روش تبدیل ویژگی PCA به 66.67 درصد برای روش تبدیل ویژگی KMCE رسیده است. در این کلاس­بند روش KLDA و روش پیشنهادی نتایج نزدیک به هم دارند.

نتایج کلاس­بندهای مبتنی بر درخت تصمیم NBTree در انتهای جدول (3) نشان داده شده است. با توجه به نتایج مندرج در جدول، روش KMCE در اغلب موارد بیشترین نتیجه بازشناسی را دارد و یا رتبه دوم را در بین روشهای تبدیل ویژگی به خود اختصاص داده است.

5. نتيجه گيري

در این مقاله روش خطاي كلاس­بندي كمينه مبتني بر هسته (KMCE) برای بازشناسی الگو پیشنهاد و فرموله گردیده است. این روش بر مبنای معیار كمينه كردن خطاي كلاس­بند در فضاي ايجاد شده توسط هسته می­باشد. معیار پیشنهادی با مستقل کردن ویژگی­های در فضای هسته (مانند KPCA) و تفکیک­پذیری بیشتر کلاس­ها در فضای هسته (مانند KLDA) و دیگر تبدیلات خطی ویژگی­ها مانند LDA، PCA و MCE  مقایسه شده است. از سه گروه کلاس­بند مبتنی بر فاصله، آماری و مبتنی بر درخت تصمیم جهت ارزیابی تاثیر روش پیشنهادی نسبت به دیگر روشها بر نرخ بازشناسی استفاده شده است. نتایج نشان می­دهند که روش KMCE برای تمامی دادگان و تمامی کلاس­بندهای مبتنی بر فاصله عملکرد بهتری داشته است. این امر به معیار بدست آوردن تبدیل در روش پیشنهادی کاهش خطای کلاس­بندی بر می­گردد که روش برای کلاس­بند فاصله فرموله شده است. بنابراین انتظار کارائی بهتر در کلاس­بندهای مبتنی بر فاصله می­رود. به علاوه عملکرد KMCE در کلاس­بندهای آماری و مبتنی بر درخت تصمیم­گیری نیز قابل قبول است.

منابع

[1] I. T. Jolliffe, Principal Component Analysis, Springer-Verlag, New York, 1986.

[2] M. Loog, R.P.W. Duin, Linear dimensionality reduction via a heteroscedastic extension of LDA: the Chernoff criterion, IEEE Transaction Pattern Analysis and Machine Intelligence 26 (6), (2004) 732–739.

[3] Z. Jin, J.Y. Yang, Z.S. Hu, Z. Lou, Face recognition based on the uncorrelated discriminant transformation, Pattern Recognition 34 (7) (2001) 1405–1416.

[4] Z. Jin, J.Y. Yang, Z.S. Hu, Z. Lou, Face recognition based on the uncorrelated discriminant transformation, Pattern Recognition 34 (7) (2001) 1405–1416.

[5] M. Loog, R.P.W. Duin,  R. Haeb-Umbach, Multiclass Linear Dimension Reduction by Weighted Pairwise Fisher Criteria, IEEE Transactions On Pattern Analysis And Machine Intelligence, Vol. 23, No. 7, July 2001.

[6] I. Alphonso, “Heteroscedastic Discriminant Analysis”, Critical Review Paper, ECE 8990 - Special Topics in ECE - Pattern Recognition, Institute for Signal and Information Processing, Mississippi State University, 2001.

[7] A.K. Qin, P.N. Suganthan, M. Loog, Uncorrelated heteroscedastic LDA based on the weighted pairwise Chernoff criterion, Pattern Recognition 38 (2005) 613 – 616.

[8] M. Sakai, N. Kitaoka and S. Nakagawa, Power Linear Discrimant Analysis, 9th International Symposium on Signal Processing and Its Applications (ISSPA), 2007.

[9] H. Abdi, Metric multidimensional scaling, in Encyclopedia of Measurement and Statistics, Sage, Thousand Oaks, CA, (2007), pp. 598-605.

[10] A. Hyvarinen, J. Karhunen, E. Oja, Independent Component Analysis, John Wiley & Sons, 2001.

[11] A. Kocsor, K. Kovacs, Kernel Springy Discriminant Analysis and Its Application to a Phonological Awareness Teaching System, in Proceedings of Text, Speech and Dialogue (TSD):5th International conference, pp. 325-328,2002.

[12] A. de la Torre, A. M. Peinado, A. J. Rubio, V. E. SGnchez, J. E. Diaz, An application of minimum classification error to feature space transformations for speech recognition, Speech Communication 20 (1996) 273-290.

[13] B. H. Juang, W. Chou, C. H. Lee, Minimum classification error rate methods for speech recognition, IEEE Transaction Speech Audio Processing. 5 (3), 257–265, 1997.

[14] T. Rudolph, Minimum classification error optimization of word recognizers using evolution strategies, IEEE International Conference on Evolutionary Computation, 521 - 526 vol.2, 1995.

[15] E.C. Malthouse, Limitations of Nonlinear PCA as performed with generic Neural Networks, IEEE Transaction on Neural Networks, Vol. 9, No. 1, pp. 165-173, January 1998.

[16] D. Tzovaras, M. G. Strintzis, Use of Nonlinear Principal Component Analysis and Vector Quantization for Image Coding, IEEE Transactions On Image Processing, Vol. 7, No. 8, 1998.

[17] M. A. Kramer, Nonlinear principal component analysis using auto associative neural networks, AIChE J., vol. 37, pp. 233–243, 1991.

[18] V. N. Vapnik , Statistical Learning Theory, John Wiley & Sons Inc., 1998.

[19] N. Cristianini, J. Shawe-Taylor, An Introduction to Support Vector Machines and other kernel-based learning methods Cambridge University Press, 2000.

[20] B. Scholkopf, A. Smola, and K. R. Muller, Nonlinear component analysis as a kernel eigenvalue problem, Neural Comput., vol. 10, no. 5, pp. 1299–1319, 1998.

[21] C. Liu, Gabor-based kernel PCA with fractional power polynomial models for face recognition, IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no. 5, pp. 572–581, May 2004.

[22] W. Cao, L. Li, and X. Lv, Kernel function characteristic analysis based on support vector machine in face recognition, Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, Hong Kong, Vol. 5, 19-22 Aug. 2007, pp. 2869-2873.

[23] T. Xiong, J. Ye, Kernel Uncorrelated and Orthogonal Discriminant Analysis: A Unified Approach, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’06), pp. 125–131 (2006)

[24] S. Mika, G. Ratsch, J. Weston, B. Schokopf,  K. R. Muller, Fisher discriminant analysis with kernels, In IEEE Neural Networks for Signal Processing Workshop, pp. 41– 48, 1999.

[25] T. Xiong, J. Ye, Q. Li, R. Janardan, V. Cherkassky, Efficient kernel discriminant analysis via QR decomposition, In NIPS, pages 1529–1536. 2005.

[26] J.Yang, A. Frangi, J. Yang, and Z. Jin. KPCA plus LDA: A complete kernel fisher discriminant framework for feature extraction and recognition. IEEE TPAMI, 27(2):230–244, 2005.

[27] J. Ye, Charaterization of a family of algorithms for generalized discriminant analysis on undersampled problems, Journal of Machine Learning Research, 6:483–502, 2005.

[28] W. Zheng, L. Zhao, and C. Zou, Foley-Sammon optimal discriminant vectors using kernel approach, IEEE Trans Neural Networks, 16(1):1– 9, 2005.

[29] V. Roth and V. Steinhage, Nonlinear discriminant analysis using kernel functions, in Advances in Neural Information Processing Systems, pp. 568–574, 1999.

[30] C. Blake, E. Keogh, C. J. Merz, UCI Repository of Machine Learning Databases, 1998. Available: www.ics.uci.edu/ mlearn/MLRepository.html

[31] R. O. Duda, P. E. Hart and D. G. Stork, Pattern classification, 2nd edition, John Wiley & Sons, 2001.

[32] B. Zhang and S. Matsoukas, Minimum phoneme error based heteroscedastic linear discriminant analysis for speech recognition. In: Proceedings of ICASSP, vol. 1. Philadelphia, PA, pp. 925-928, 2005.

[33] M. Loog and R. P. W. Duin, Linear Dimensionality Reduction via a Heteroscedastic Extension of LDA: The Chernoff Criterion. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 6, pp. 732-739, 2004.

[34] J. Hung and L. S. Lee, Data-driven temporal filters for robust features in speech recognition obtained via minimum classification error (MCE). In: Proceedings of ICASSP, pp. 373-376, 2002.

[35] X. Wang and K. K. Paliwal, Feature extraction and dimensionality reduction algorithms and their applications in vowel recognition. Pattern Recognition, vol. 36, pp. 2429-2439, 2003.

[36] B. H. Juang, W. Chou and C. H. Lee, Minimum classification error rate methods for speech recognition. IEEE Transaction on Speech and Audio Processing, Vol. 5, No. 3, pp. 257-265, 1997.

[37] A. Lima, H. Zen, Y. Nankaku, C. Miyajima, K. Tokuda, T. Kitamura, On the Use of Kernel PCA for Feature Extraction in Speech Recognition, Proceeding of EuroSpeech, pp. 2625–2628, Sep. 2003.

[38] K. Fukunaga, Introduction to Statistical Pattern Recognition, Academic Press, San Diego, California, USA, 1990.

[39] G. H. Golub, C. F. Van Loan, Matrix Computations, The Johns Hopkins University Press, Baltimore, MD, USA, third edition, 1996.

[40] A. Kocsor, L. Toth, Kernel-Based Feature Extraction with a Speech Technology Application, IEEE Transactions On Signal Processing, Vol. 52, No. 8, pp. 2250-2263, 2004.

 


[1] Feature Transformation

[2] Pattern Recognition

[3] Feature Extraction

[4] Feature Reduction

[5] Linear Discriminant Analysis (LDA)

[6] Kernel Discriminant Analysis (KDA)

[7] Feature construction

[8] Feature discovery

[9] Feature Selection

[10] Principal Component analysis (PCA)

[11] Eigen value

[12] Eigenvector

[13] Metric Multi-Dimensional Scaling (MDS)

[14] Uncorrelated LDA (ULDA)

[15] Weighted LDA (WLDA)

[16] Approximate Pairwise Accuracy Criteria (aPAC)

[17] Heteroscedastic Discriminant Analysis (HDA)

[18] Heteroscedastic Linear Discriminant Analysis (HLDA)

[19] Uncorrelated Heteroscedastic LDA (UHLDA)

[20] Power Linear Discriminant Analysis (PLDA)

[21] Independent Component Analysis (ICA)

[22] Blind Source Separation (BSS)

[23] Springy Discriminant Analysis (SDA)

[24] Minimum Classification Error (MCE)

[25] Evolution Strategy (ES)

[26] Nonlinear Principal Component Analysis (NLPCA)

[27] Kernel Springy Discriminant Analysis (KSDA)

[28] Kernel Principal Component Analysis (KPCA)

[29] Kernel Discriminant Analysis (KDA)

[30] kernel uncorrelated discriminant analysis (KUDA)

[31] Kernel orthogonal discriminant analysis (KODA)

[32] Kernel Minimum Classification Error (KMCE)

[33] Linear Dimensionality Reduction (LDR)

[34] Kernel Trick

[35] To be centered

نظر ها (0)
تنها کاربران عضو شده می توانند نظر ارسال کنند!
آخرین بروز رسانی در سه شنبه, 10 تیر 1393 ساعت 23:47
 
logo-samandehi