بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
بهبود انتخاب ویژگی با الگوریتم های تکاملی بهینه سازی ازدحام ذرات و ژنتیک برای طبقه بندی متن
چکیده
پیدا کردن زیرمجموعه ای بهینه از یک مجموعه بزرگ ویژگی، مسئلهای است که در اغلب زمینهها با آن مواجه هستیم. از آنجایی که بالا بودن تعداد ویژگیها بار محاسباتی سیستم را بالا میبرد، نیاز به ارائه ی سیستمی با کمترین تعداد ویژگی و کارایی قابل قبول ضروری به نظر میرسد. در اینمقاله ما با استفاده از دو الگوریتم تکاملی بهینه سازی ازدحام ذرات (PSO ) والگوریتم ژنتیک (GA) انتخابویژگی را بر روی مجموعه دادههای متنی انجام دادهایم و سپس ویژگیهای انتخا ب شده را به دستهبند SVMدادیم تا دقت دستهبند را محاسبه کنیم. این الگوریتمها بر روی مجموعه داد ههای Spambase،Ionosphere،German شبیه سازی شدهاند. سپس نتایج به دست آمده توسط هر دو الگوریتم را مورد مقایسه قرار دادهایم که نتایج نشانده نده برتری الگوریتم ژنتیک میباشد.
کلمات کلیدی
متنکاوی، انتخابویژگی،الگوریتم ژنتیک (GA)، الگوریتم بهینهسازی ازدحام ذرات (PSO)،طبقه بندی.
-1 مقدمه
امروزه بخش قابل توجهی از اطلاعات موجود در پایگاه دادههای متنیذخیره میشود که از مجموعه بزرگی از اسناد و منابع مختلف، از قبیل اخبار، مقالات علمی، کتاب، کتابخانههای دیجیتالی، پیامهای ایمیل و صفحات وب تشکیل شده است. پایگاه دادههای متنی با توجه به افزایش میزان اطلاعات موجود در فرم الکترونیکی، مانند نشریات الکترونیکی، انواع مختلف مدارک الکترونیکی، پست الکترونیکی و شبکه جهانی وب به سرعت در حال رشد میباشند. دادههای ذخیرهشده در پایگاه دادههای متنی به صورت نیمه ساختیافته1 هستند بدین معنی که نه کاملا بدون ساختار2 هستند و نه به طور کامل ساختیافته. برای مثال، یک سند متنی ممکن است شامل چند زمینه ساختاری، مانند عنوان، نویسندگان، تاریخ انتشار و دسته باشد، اما برخی از اجزای آن مانند چکیده و یا محتوای متن، بدون ساختار باشد. تحقیقات زیادی در زمینه مدلسازی و پیادهسازی در خصوص دادههای نیمه ساختیافته صورت گرفته است. علاوه بر این، تکنیکهای بازیابی اطلاعات، از جمله روشهای نمایهسازی متن3، برای رسیدگی به اسناد بدون ساختار توسعه یافته هستند. تکنیکهای سنتی بازیابی اطلاعات با توجه به رشد فزاینده دادههای متنی جوابگو نیستند. بنابراین کاربران نیاز به ابزارهایی برای مقایسه اسناد مختلف، رتبهبندی اهمیت و ارتباط اسناد و یا پیدا کردن الگوها و روندها در اسناد متعدد هستند. بنابراین، متنکاوی به موضوعی محبوب و ضروری در داده کاوی تبدیل شده است.
مساله انتخاب ویژگی، یکی از مسائلی است که در مبحث یادگیری ماشین و در بررسی مسائل شناخت الگو از دیدگاه امار مطرح است. این مساله در بسیاری از کاربردها (مانند طبقه بندی) اهمیت به سزایی دارد، زیرا در این کاربردها تعداد زیادی ویژگی وجود دارد، که بسیاری از ان-ها یا بلااستفاده هستند و یا اینکه بار اطلاعاتی چندانی ندارند. حذف کردن این ویژگیها مشکلی از لحاظ اطلاعاتی ایجاد نمیکند، ولی حذف ویژگیهای نامرتبط و اضافی بار محاسباتی را کاهش میدهد. علاوه بر این باعث میشود که اطلاعات غیرمفید زیادی را به همراه دادههای مفید ذخیره کنیم.
روشهای بسیاری برای بهبود انتخاب ویژگی ارائه شدهاست.در مرجع[1] یک روش انتخاب ویژگی دو مرحلهای برای طبقه بندی متن ارائه دادند که درمرحله اول، یک روش انتخاب ویژگی جدید برای کاهش اصطلاحات کم اهمیت اعمالمیکند و در مرحله دوم یک فضای معنایی جدید، بین واژگان، براساس روشن مایهسازی، معنایی نهان ایجاد میکند. در مرجع [2]یک الگوریتم انتخاب ویژگی ناهموار موثر با دید دانهبندی برای مجموعه دادهها در مقیاس بزرگارئه دادند که در آن یک مجموعه داده در مقیاس بزرگ داده شدهاست، این الگوریتم ابتدا دانههای کوچک مختلف را انتخاب میکند و سپس بر روی هر دانه کوچک، میزان کاهش را از مجموعه داده اصلی براورد میکند. در مرجع [3]یک نمونه جدید به طور همزمان تکاملی و الگوریتم انتخاب ویژگی ارائه داده اند که برای میلیونها مورد از هزاران ویژگی مقیاسپذیر است. این پیشنهاد براساس اصل تقسیم و غلبه همراه باساماندهی است,اصل تقسیم وغلبه موجب اجرای الگوریتم در زمان خطی میشود. همچنین این روش درمحیط های موازی به راحتی قابل اجرا است ومیتواند بدون بارگذاری کل مجموعه داده در حافظه کارکند. در مرجع[4]یک تابع معیارکلیدرمورداطلاعات متقابل در انتخاب ویژگی ارائه شدهاست، که میتواند بسیاری از اندازهگیریهای اطلاعاتی در الگوریتمهای پیشین را به یکدیگر نزدیک کند. در انتخابگرهای سنتی، اطلاعات متقابل در کل فضای نمونه برآورد میشوند که نمیتواند دقیقا نشان دهنده ارتباط میان ویژگیها باشد. برای مقابله با این مشکل ،هدف دوم این مقاله پیشنهاد یک الگوریتم انتخاب ویژگی جدید براساس اطلاعات متقابل پویا است، که تنها در موارد بدون بر چسب تخمین زده شده است. در مرجع [5]یک روشنی مه نظارت بیزی برای انتخاب ویژگی طبقه بندی شده را ارائه داده اند. با توجه به اینکه دربرنامههای کاربردی دنیای واقعی ،دریافت کردن نمونه های بدون برچسب معمولا آسان است،اما به دست آوردن برچسبهای دقیق، مربوط به نمونه ها گران است، این امر منجر به زباله های بالقوه از اطلاعات طبقه بندی شده ارزشمند، درنمونه های بدون برچسب میشود که دور ریخته می شوند. در نتیجه این روش نمونه های فاقد برچسب را در مشکل انتخاب ویژگیهای طبقه بندی شده، حل میکند.
در این تحقیق از الگوریتم های تکاملی PSO و GA برای انتخاب ویژگی استفاده شده است، الگوریتم های تکاملی فضای مسئله را در مدت زمان کمتری جستجو می کنند و سریعتر به جواب میرسند در نتیجه برای مجموعه داده های با ابعاد بالا کارایی مناسبی دارند. در نهایت برای ارزیابی کارایی، این دو الگوریتم با یکدیگر مورد مقایسه قرار گرفته اند که نتایج شبیه سازی برتری الگوریتم ژنتیک را نشان میدهد.
-2 متن کاوی
متنکاوی دانش استخراج اطلاعات از متن بدون ساختار است. به عبارتی میتوان متن کاوی را به عنوان روشها و الگوریتمهایی از فیلدهای یادگیری ماشین و تکنیکهای آماری با هدف پیدا کردن الگوهای مفید در متن درنظرگرفت. برای این هدف پیشپردازش متون ضروریاست. در بسیاری از روشها،متدهای استخراج اطلاعات،پردازش زبان طبیعی یا برخی پیش پردازشهای ساده برای استخراج داده از متن استفاده میشوند.سپس میتوان الگوریتمهای دادهکاوی را بررویدادههایاستخراجشده اعمال کرد. شکل (1) فرایند کلی استخراج دانش از متن را نشان میدهد.[6]
شکل(:(1 فرایند استخراج دانش از متن
آماده سازی متون (پیش پردازش)
در این مرحله داده های ورودی باید به صورتی تبدیل شوند که قابل پردازش توسط مراحل بعد باشند. در مرحله پیشپردازش معمولا بر رویدادههای ورودی عملیات زیر صورت میگیرد:
· جداسازی کلمات:4 در این مرحله تمام متن به صورت کلمات متمایز تبدیل میشود و همچنین علائم نگارشی، تگها و ... حذف میشوند.
· حذف کلمات زائد:5 در این مرحله کلمات زائد نظیر for , not, and the , … (در متون لاتین) حذف میشوند
· ریشهیابی کلمات:6 در این مرحله کلمات به فرم ریشهشان تبدیل میشوند و کلماتی که به خاطر پیشوندها و پسوندهایشان از یکدیگر متمایز شدهاند ولی ریشه یکسانی دارند، در یک گروه قرار داده میشوند (اصطلاحا کلماتی که هم خانواده هستند).
· وزن دهی کلمات7 (ویژگیها): پس از انجام مراحل فوق متن به صورت برداری از کلمات که ویژگیهای متن هستند میتواند نمایش داده شود. حال میتواند این ویژگیها را با توجه به میزان اهمیت آنها نسبت به سند متنی و دسته آن وزن دهی کرد.
-2-2 استخراج ویژگی8
روشهای مبتنی بر استخراج ویژگی، یک فضای چند بعدی را به یک فضای با ابعاد کمتر نگاشت میدهند.. در این تحقیق از روش وزندهی tfidf استفادهشده است که عملکرد دستهبندها با استفاده از این روش وزندهی مورد ارزیابی قرار میگیرند.[7]
-3-2 انتخاب ویژگی
این مرحله به انتخاب زیرمجموعهای از ویژگیهای متن اشاره دارد. با توجه به اینکه پس از مراحل فوق تعداد ویژگیها در متن بسیار زیاد خواهد شد و این امر در کاهش کارایی دستهبندی تاثیر زیادی خواهد داشت. در مرحله انتخاب ویژگی سعی بر این است که از بین ویژگیهای موجود مهمترین و اساسیترین ویژگیها انتخاب شوند. با حذف ویژگیهای غیرمرتبط و غیرقابل تمایز، کارایی دستهبندی میتواند افزایش یابد.در این تحقیق از الگوریتم PSO و GA برای انتخاب ویژگی استفاده شده است و کارایی آنها با هم مورد مقایسه قرار گرفته است.
-1-3-2 الگوریتم ژنتیک برای انتخاب ویژگی
ایده اولیه این روش از نظریه تکاملی داروین الهام گرفته شده است و کارکرد ان براساس ژنتیک طبیعی استوارمیباشد.[8] در واقع الگوریتمهای ژنتیک از اصول انتخاب طبیعی داروین برای یافتن فرمول بهینه جهت پیشبینی یا تطبیق الگو استفاده میکنند . قانون انتخاب طبیعی بدین صورت است که تنها گونههایی از یک جمعیت ادامه نسل میدهند که بهترین خصوصیات را داشته باشند و انهایی که این خصوصیات را نداشته باشند ،به تدریج و در طی زمان از بین میروند .
در حالت کلی وقتی یک الگوریتم ژنتیکی اعمال میشود چرخه زیر را طی میکند:
ابتدا یک جمعیت اولیه از افراد به طور اتفاقی و بدون در نظرگرفتن معیار خاصی انتخاب میشود. برای تمامی کروموزومهای(افراد) نسل صفر مقدار برازش با توجه به تابع پردازش که ممکن است بسیار ساده یا پیچیده باشد تعیین میشود. سپس با مکانیزمهای مختلف تعریف شده برای عملگر انتخاب زیرمجموعهای از جمعیت اولیه انتخاب خواهد شد. سپس روی این افراد انتخاب شده عملیات برش و جهش در صورت لزوم با توجه به صورت مسأله اعمال خواهد شد.
حا ل باید این افراد که مکانیزم الگوریتم ژنتیک در موردشان اعمال شده است با افراد جمعیت اولیه (نسل صفر) از لحاظ مقدار برازش مقایسه شوند. (قطعاً توقّع داریم که افراد نسل اول با توجه به یکبار اعمال الگوریتم های ژنتیک روی آنان از شایستگی بیشتری برخوردار باشند، اما الزاماً چنین نخواهد بود.) به هرحال افرادی باقی خواهند ماند که بیشترین مقدار برازش را داشته باشند. چنین افرادی در مقام یک مجموعه به عنوان جمعیت اولیه برای مرحله بعدی الگوریتم عمل خواهد کرد.
هر مرحله تکرار الگوریتم یک نسل جدید را ایجاد می کند که با توجه به اصلاحاتی که در آن صورت پذیرفته است رو به سوی تکامل خواهد داشت. تذکر این نکته خالی از لطف نیست که هر چند الگوریتمهای ژنتیک دارای پایه ریاضی متقن و مشخصی نیستند اما به عنوان یک مدل اجرایی و مطمئن که به خوبی نیز پیادهسازی میشود کارایی خود را نشان داده اند.
طرح کلی یک الگوریتم به شرح زیر می باشد:
آغاز: جمعیت n کروموزومی به صورت تصادفی ایجاد کنید (راه حلهای مناسب مسأله). ارزش گذاری: برازندگی f(x) هر کروموزوم X در جمعیت را ارزیابی کنید.
جمعیت جدید: جمعیت جدیدی را تشکیل دهید. مراحل زیر را تکرار کنید تا جمعیت جدید کامل شود:
انتخاب: دو کروموزوم (والدین) را با توجه به برازندگی آنها از میان جمعیت انتخاب کنید(هر چه برازندگی بیشتر باشد شانس انتخاب بیبشتر است.) ترکیب: با توجه به احتمال ترکیب شدن9 والدین را برای تشکیل فرزندان10 جدید با هم ترکیب کنید.
جهش: با توجه به احتمال جهش11 فرزندان را در هر لوکاس(موقعیت در کروموزوم)12 مورد جهش قرار دهید. پذیرفتن: فرزندان جدید را در جمعیت جدید بگنجانید.
جایگزینی: جمعیت جدید ایجاد شده را برای روند الگوریتم بکار ببرید.
-2-3-2 الگوریتم بهینهسازی انبوه ذرات13
ایده PSO، برای اولین بار توسط کندی و ابرهارت در سال 1995مطرح شد. PSO یک الگوریتم محاسبهای تکاملی الهام گرفته از طبیعت و براساس تکرارمیباشد. منبع الهام این الگوریتم، رفتار اجتماعی حیوانات، همانند حرکت دسته جمعیپرندگان و ماهیها است.[9]هرعضوازجامعه،مطابق منطق خود ،عملی را که فکر میکند درست است ،انجام میدهد،اما برای تصمیمگیری،نتیجه تصمیمگیریهای قبلی خود و دیگران را نیز در نظر میگیرد. به این ترتیب، یک جریان اطلاعاتی بین اعضای جامعه به وجود میایدکه درکل باعث میشود تصمیمهای معقولتری ازطرف اعضای جامعه اتخاذ شود.[10]
در PSOهرجواب،یک پرنده در فضای جستجو است که انرا "فرد یا جزء" 14مینامند. هر جزء موقعیت خود را دارد و یک مقدار برازندگی که توسط تابع برازندگی بهینه میشود. ذرات در میان فضای جستجو پرواز میکنند و دو توانایی ضروری دارند،
(1 حافظهای برای ذخیرهسازی بهترین مکان خود
(2 اگاهی در مورد بهترین موقعیت در همسایگی خود یا در کل فضای پاسخها
برای هر ذره دو مقدار موقعیت و سرعت، تعریف میشود که به ترتیب با یک بردار مکان ویک بردار سرعت، مدل میشوند. اجزا در هر تکرار (پرواز) خود، بنابر جدیدترین بردار سرعت، از موقعیتی به موقعیتهای دیگر میروند. بردار سرعت، در نتیجه تجربه هر جزء که از دیگر اجزا به دست میاورد و همچنین با استفاده از بهترین موقعیت در گروه، تعیین میشود. اعضای گروه، مکانهای خوب را به یکدیگر از طریق ارتباط، انتقال میدهند و موقعیت و سرعتشان را با مکانهای خوبتنظیم میکنند.
به روز رسانی بهترین خاطره محلی در رابطه (1) نشان داده شده است:
به روز رسانی بهترین خاطره عمومی در رابطه (2) نشان داده شدهاست:
در PSO هر راه حل تنهایک پرنده در فضای جستجو است و عضو نامیده می شود. تمام پرندگان یک مقدار شایستگی دارند که توسط تابع شایستگی که باید بهینه شود ارزیابی میگردد. علاوه براین هر پرنده i، دارای یک موقعیت در فضای D بعدی مسئله است که در تکرار tام، با یک بردار با رابطه (3) نمایش داده میشود:
همچنین این پرنده سرعتی دارد که پروازش را هدایت میکند و در تکرار t ام با بردار در رابطه((4 نشان داده میشود:
و این پرنده نیز در هر تکرار یک حافظه از بهترین موقعیت قبلی خودش را دارد که با بردار در رابطه (5) نشان داده میشود:
در هر تکرار جستجو، هر عضو با در نظر داشتن دو مقدار بهترین به روزرسانی میشود. اولی مربوط به بهترین راه حلی است که پرنده تا کنون آن را تجربه کرده است. (مقدار شایستگی این بهترین راه حل نیز ذخیره میگردد.) این مقدار را بهترین p یا اصطلاحا Pbest مینامند. دومین بهترین که توسط PSO دنبال میشود بهترین موقعیتی است که تا کنون در جمعیت به دست آمده است. این مقدار بهینه عمومی است و اصطلاحا Gbest نامیده میشود. زمانیکه یک عضو، بخشی از جمعیت را به عنوان توپولوژی همسایگانش در نظر میگیرد، بهترین مقدار یک بهترین محلی است و Lbest نامیده میشود. بعد از اینکه دو بهترین مقدار پیدا شدند سرعت و موقعیت هر عضو به ترتیب توسط فرمولهای شماره (6)و (7) به روزرسانی میشوند:
در فرمولهای فوق i بیانگر شماره تکرار، و متغیرهای c1, c2 فاکتورهای یادگیری هستند. اغلب 2 c1 c2 است که میزان جابجایی یک پرنده را در یکبار تکرار کنترل میکند. r1, r2 دو عدد تصادفی یکنواخت در رنج [0,1] هستند. w یک وزن جبری است که به صورت نوعی در رنج [0,1] مقداردهی اولیه میگردد. یک وزن جبری بزرگتر یک استکشاف عمومی و وزن جبری کوچکتر استکشاف محلی را تسهیل مینماید. در الگوریتم PSO استاندارد جمعیت با راه حلهای تصادفی مقدار دهی اولیه میشود. و تا رسیدن به شرط خاتمه به صورت تکراری شایستگی جمعیت محاسبه، مقادیر Pbest و Gbest ست، سرعت و موقعیت نیز به ترتیب به روزرسانی میشوند. در آخر هم Gbest و مقدار شایستگیاش به عنوان خروجی بیان میشوند.
-4-2 الگوریتم یادگیری
پس از انجام مراحل فوق، اکنون متن به صورت برداری از ویژگیها با وزنهای متفاوت درآمده است که به الگوریتم یادگیری داده میشود تا مدل دستهبندی تولید شود. پس از تولید مدل دستهبندی میتوان دسته مربوط به متنهای جدید را تشخیص داد.[11]
در واقع میتوان گفت که در این مرحله دستهبندها از روی متنهای پیشپردازش شده اقدام به یادگیری میکنند. مسئله یادگیری در دستهبندی متون با استفاده از تکنیکهای یادگیری ماشین به دو دسته با ناظر15 و بدون ناظر16 تقسیمبندی میشود. در یادگیری
