پایان نامه بررسی روش های متن کاوی

 مقدمه

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

تعداد متغیرهایی که برای هر مشاهده باید اندازه­گیری شود، ابعاد داده نامیده می­شود. عبارت "متغیر" (variable) بیشتر در امار استفاده می­شود در حالی که در علوم کامپیوتر و یادگیری ماشین بیشتر از عبارات "ویژگی" (feature) و یا "صفت" (attribute) استفاده می­شود.

بسترهای داده­ای که دارای ابعاد زیادی هستند علیرغم فرصت­هایی که به وجود می­اورند، چالش­های محاسباتی زیادی را ایجاد می­کنند. یکی از مشکلات داده­های با ابعاد زیاد این است که در بیشتر مواقع تمام ویژگی­های داده­ها برای یافتن دانشی که در داده­ها نهفته است مهم و حیاتی نیستند. به همین دلیل در بسیاری از زمینه­ها کاهش ابعاد داده یکی از مباحث قابل توجه باقی مانده است.

استراتژی‌های پیشرفته‌ جستجوی ممنوعه

ساختار کلی جستجوی ممنوعه، اغلب جوابگوی مسایل بزرگ نیست. بنابراین به منظور افزایش قدرت الگوریتم، از استراتژی‌های زیر که معروف به استراتژی‌های پیشرفته جستجوی ممنوعه هستند استفاده می‌شود [Gend03]:

استراتژی لیست کاندید (Candidate List Strategy): در یک TSعادی، برای حرکت از یک جواب فعلی به یک جواب همسایه، باید مقدار تابع هدف برای هر عنصر از همسایه‌ها ارزیابی شود. این کار می‌تواند از لحاظ محاسباتی بسیار هزینه­بر باشد. روشی دیگر، این است که به جای ان که تمامی همسایه‌ها بررسی شود، تنها یک زیرمجموعه‌ تصادفی از همسایه­ها در نظر گرفته شود که در نتیجه، هزینه‌ محاسباتی به طور قابل ملاحظه‌ای کاهش می‌یابد. انتخاب زیرمجموعه‌ای از جواب­های همسایه به صورت تصادفی، می‌تواند به عنوان یک مکانیزم ضد چرخه عمل کند؛ این کار اجازه می‌دهد که از لیست ممنوعه کوچکتری نسبت به کل همسایگی، استفاده شود. البته باید در نظر داشت که این کار یک عیب مهم دارد و ان احتمال از دست دادن جواب­های خوب است، بنابراین احتمال‌هایی را نیز می‌توان به کار برد تا معیارهای ممنوعه فعال شود.استراتژی تقویت (Intensification Strategy): استراتژی تقویت به معنای یافتن حرکت‌های خوب و افزایش انجام ان حرکت‌ها در الگوریتم است. تقویت، در بسیاری از پیاده‌سازی‌هایTSاستفاده می‌شود، اما همیشه ضروری نیست، زیرا حالت‌های بسیاری وجود دارد که در انها جستجوی معمولی کفایت می‌کند.استراتژی تنوع بخشی (Diversification Strategy): روش‌های مبتنی بر جستجوی محلی، ان‌قدر محلی هستند که زمان زیادی و یا تمامی زمان خود را در بخش محدودی از فضای جستجو صرف می‌کنند. نتیجه‌ای که از این واقعیت می‌توان گرفت، این است که هر چند جواب‌های خوبی به وسیله این روش­ها به دست می‌اید، اما ممکن است جستجو از اکتشاف مناطق بهتر باز بماند و بنابراین به جواب‌هایی برسد که از جواب بهینه، بسیار دور هستند. تنوع‌بخشی، یک مکانیزم الگوریتمیک است که برای حل این مشکل تلاش می‌کند. برای انجام این کار، تنوع‌بخشی جستجو را مجبور می‌کند به سوی مناطقی که تاکنون کشف نشده، حرکت کند.

تعداد صفحات 102 word

فهرست

مقدمه. 2

روش های مبتنی بر استخراج ویژگی.. 4

روش های انتخاب ویژگی.. 5

تعاریف.. 6

بررسی توابع مختلف ارزیابی و تولید کننده 10

توابع تولید کننده 11

جستجوی کامل.. 11

جستجوی مکاشفه ای.. 12

جستجوی تصادفی.. 12

توابع ارزیابی.. 12

دسته بندی و تشریح الگوریتم های مختلف انتخاب ویژگی.. 17

تابع ارزیابی مبتنی بر فاصله - تابع تولید کننده مکاشفه ای.. 18

روش Relief. 18

روش Jakub. 20

تابع ارزیابی مبتنی بر فاصله - تابع تولید کننده کامل.. 21

تابع ارزیابی مبتنی بر اطلاعات - تابع تولید کننده مکاشفه ای.. 23

1)     روش درخت تصمیم(DTM) 23

الگوریتم  C4.5. 23

2)     روش استفاده شده توسط Kollerو Sahami 27

پوشش مارکوف.. 27

تابع ارزیابی مبتنی بر وابستگی - تابع تولید کننده مکاشفه ای.. 30

2)     روش PreSet 31

تابع ارزیابی مبتنی بر سازگاری - تابع تولید کننده کامل.. 32

1)     روش Focus. 32

2)     روش Schlimmer 38

3)     روش MIFES1. 38

تابع ارزیابی مبتنی بر سازگاری - تابع تولید کننده تصادفی.. 39

تابع ارزیابی مبتنی بر خطای طبقه بندی کننده- تابع تولید کننده مکاشفه ای.. 41

2)     روش SBS (Sequential Backward Selection) 41

3)     روش SBS-Slash. 41

4)     روش PQSS ((p,q) Sequential Search) 42

5)     روش BDS (Bi-Directional Search) 42

6)     روش Schemata Search. 42

7)     روش RC (Relevance in Context) 43

8)     روش Queiros and Gelsema. 43

تابع ارزیابی مبتنی بر خطای طبقه بندی کننده - تابع تولید کننده کامل.. 43

تابع ارزیابی مبتنی بر خطای طبقه بندی کننده - تابع تولید کننده تصادفی.. 44

جمع بندی روش های انتخاب ویژگی.. 46

روش های فرا اکتشافی.. 49

روش های مکاشفه ای.. 50

انواع الگوریتم‌های مکاشفه‌ای.. 51

پیاده‌سازی الگوریتم های فرا اکتشافی.. 53

ویژگی های مشترک روش های فرا اکتشافی.. 54

دسته‌بندی الگوریتم‌های فرا اکتشافی.. 54

الگوریتم ژنتیک (Genetic Algorithm) 56

مراحل الگوریتم ژنتیک... 59

انواع کدینگ... 59

روشهای کدینگ... 60

روش های پیاده سازی عملگر ترکیب.. 61

ترکیب تک نقطهای : 61ترکیب دو نقطهای : 62ترکیب یکنواخت: 63ترکیب حسابی: 64

انواع روش های جهش... 65

الگوریتم ژنتیک برای انتخاب ویژگی.. 67

الگوریتم بهینه سازی جمعیت مورچگان (ACO) 68

الگوریتم ACO برای انتخاب ویژگی.. 71

الگوریتم بهینه سازی انبوه ذرات (PSO) 74

الگوریتم PSO برای انتخاب ویژگی.. 75

الگوریتم جستجوی ممنوعه (Tabu Search) 79

استراتژی‌های پیشرفته‌ جستجوی ممنوعه. 82

حافظه ها در جستجوی ممنوعه. 83

الگوریتم جستجوی ممنوعه برای انتخاب ویژگی.. 84

فهرست منابع و مراجع. 87

فهرست اشکال

شکل 1- فرایند انتخاب ویژگی.. 11

شکل 2- مقایسه توابع ارزیابی مختلف.. 20

شکل 4- الگوریتم Branch and Bound. 26

شکل 5- الگوریتم درخت تصمیم. 30

شکل 9- الگوریتم روش Focus. 36

شکل 10- الگوریتمی دیگر از روش Focus. 37

شکل 11- الگوریتم Focus-2. 38

شکل 12- کلاسهای مورد بررسی در الگوریتم Focus. 39

شکل 13- روند الگوریتم Focus. 40

شکل 14- حل ناسازگاری در الگوریتم Focus. 41

شکل 15- الگوریتم روش LVF. 43

شکل 16- طبقهبندی روشهای مختلف انتخاب ویژگی.. 50

شکل 1- بهینه محلی و بهینه کلی.. 61

شکل 7- ترکیب تک نقطهای.. 65

شکل 12- جهش باینری.. 69

شکل 17- فرایند انتخاب ویژگی در ACO.. 75