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

مقدمه

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

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

فهرست

مقدمه. 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

پـــایــان نــامه روش های خوشه بندی جریان داده

چکیده

 حجم بزرگ داده ها به تنهایی به مدیران سازمان ها در تصمیم سازی و تصمیم گیری هیچ کمکی نمی کند، بلکه باعث سردرگمی مدیران سازمان ها نیز می شود.بنابراین مدیریت داده های خام و تبدیل داده های خارجی و داخلی سازمان به اطلاعات و دانش با استفاده از تکنیک های گوناگون،نقش اساسی و محوری دارد.از تکنیک های معروف در این زمینه داده کاوی است،که می تواند بر روی بانک اطلاعاتی انجام شود و دانش مورد نیاز را بدست آورد.در فصل اول به بررسی این مفهوم پرداختیم. کاوش خوشه ها نیز یکی از تکنیک های حائز اهمیت در زمینه رو به رشد،معروف به داده کاوی اکتشافی می باشد که در رشته های گوناگون مهندسی و علمی از قبیل زیست شناسی،روان شناسی،پزشکی،بازاریابی،کامپیوتر و نقشه برداری ماهواره ای به کار گرفته شده است. این مفهوم در فصل های سوم و چهارم دنبال شده است.در فصل سوم به یکی از الگوریتم های خوشه بندی به نام CStree پرداخته شده و نقاط ضعف این الگوریتم نیز مطرح شده است .تحلیل خوشه ها،اطلاعات را بوسیله یک ساختار اساسی مختصر بدو شکل گروه بندی تنها یا گروه بندی سلسله مراتبی سازماندهی می نماید.خوشه بندی ،ابزاری برای اکتشاف ساختارهایی از درون داده هاست که نیاز به هیچ فرضی از آنها نیست.این روش در هوش مصنوعی و شناسایی الگو،یادگیری بدون ناظر نامیده می شود.الگوریتم های خوشه بندی گوناگونی برای استخراج دانش از درون مجموعه اطلاعات مختلف وجود دارد.اما عموما این الگوریتم ها حساس به داده های مورد آزمایش و برخی پارامترهای اولیه می باشند،لذا نتایج حاصل از آنها وابسته به ساختار داده ها می باشد.تاکنون الگوریتمی ارائه نشده است که بتواند هر گونه ساختار داده ای را استخراج نماید. یکی دیگر از پدیده های نوظهور در دنیای اطلاعات،داده های جریانی می باشند.این پدیده که در فصل چهارم مطرح شده است،اشاره به حجم وسیعی از اطلاعات انباشته شده دارد که محدودیت های فراوانی برای پردازش ایجاد کرده اند.اندازه این داده ها بیش از حافظه اصلی،یکی از این موانع می باشد.لذا می بایست الگوریتم های جدیدی برای برخورد با این گونه داده ها توسعه یابند.

کلمات کلیدی: داده کاوی، دسته بندی، خوشه بندی، جریان داده

فهرست مطالب

تقدیم به: 3

تقدیر و تشکر. 4

فصل اول مقدمه ای بر داده کاوی. 1

1-1 مقدمه 2

1-2عامل مسبب پیدایش داده کاوی. 2

1-3داده کاوی و مفهوم اکتشاف دانش (K.D.D) 3

1-3-1 تعریف داده کاوی. 5

2-3-1 فرایند داده‌کاوی. 6

1-3-3 قابلیتهای داده کاوی. 7

4-3-1 چه نوع داده‌هایی مورد کاوش قرار می گیرند؟ 8

4-1 وظایف داده کاوی. 9

1-4-1 کلاس بندی. 10

2-4-1 مراحل یک الگوریتم کلاس‌بندی. 11

3-4-1 انواع روش‌های کلاس‌بندی. 11

1-3-4-1 درخت تصمیم. 12

1-1-3-4-1 کشف تقسیمات.. 13

2-1-3-4-1 دسته بندی با درخت تصمیم. 15

3-1-3-4-1 انواع درخت‌های تصمیم. 17

4-1-3-4-1 نحوه‌ی هرس کردن درخت.. 17

2-3-4-1 بیزی. 18

1-2-3-4-1 تئوری بیز. 20

2-2-3-4-1 دسته بندی ساده بیزی. 22

4-4-1 ارزیابی روش‌های کلاس‌بندی. 28

4-1-6 انواع روش‌های پیش بینی. 29

1-4-6-1 رگرسیون. 29

1-4-6-1-1 رگرسیون خطی. 29

1-4-6-1-2 رگرسیون منطقی. 31

1-4-7 تخمین. 32

فصل دوم خوشه بندی. 34

2 1-تعریف فرایند خوشه‌بندی. 35

2-2 روش ها و الگوریتم‌های خوشه‌بندی. 36

2-3 روش و الگوریتم سلسله مراتبی. 37

2 3-1-روش های سلسله‌مراتبی. 37

2 3-2-الگوریتم های سلسله مراتبی. 38

2-3-3- الگوریتم خوشه بندی single-linkage. 39

2 3-4-الگوریتم‌های تفکیک... 45

3-5-2روش‌های متکی برچگالی. 46

3-7-2 روش‌‌های متکی بر مدل. 47

فصل سوم خوشه بندی CS tree. 48

3-1مقدمه 49

3-2 مروری بر روش های خوشه بندی جریان داده 50

3-3 خوشه بندی توری جریان داده 52

3-1-3 مروری بر روش خوشه بندی توری CS tree. 53

3-2- 3 بررسی نقاط ضعف الگوریتم CS tree. 56

3-4 الگوریتم پیشنهادی. 60

3-1-4 بازتعریف مفهوم همسایگی و رفع مشکل تقسیم بی معنی خوشه ها 63

3-5 اصلاح روند بروز رسانی خوشه ها 66

3-6 اصلاح ساختار نمایش خوشه ها 67

فصل چهارم جریان داده و مدل های ان. 69

4-1 مقدمه 70

4-2 کاربردهای داده های جریانی. 71

4-2-1 شبکه های حسگر. 71

4-2-2 تحلیل ترافیک شبکه 72

4-2-3 محرک های مالی. 73

4-2-4 تحلیل تراکنش ها 73

4-3 مدل داده های جریانی. 74

4-4 زیربنای نظری. 75

4-4-1 تکنیک های مبتنی بر داده 76

4-4-1-1 نمونه برداری. 76

4-4-1-2 پراکنده ساختن بار 77

4-4-1-3 طراحی اولیه 77

4-4-1-4 ساختمان داده خلاصه 78

4-4-1-5 انبوه سازی. 78

4-4-2 تکنیک های مبتنی بر وظیفه 78

4-4-2-1 الگوریتم های تخمین. 79

4-4-2-2 الگوریتم های مبتنی بر پنجره 79

4-4-2-3 الگوریتم های دانه دانه سازی نتایج. 80

4-5 خوشه بندی داده های جریانی. 80

4-5-1 بهبود روش های سنتی. 81

4-5-1-1 الگوریتم CLARANS. 82

4-5-1-2 الگوریتم BIRCH.. 84

4-5-2 ظهور تکنیک های جدید. 87

4-5-2-1 الگوریتم مبتنی بر چگالی DBSCAN.. 87

4-5-2-2 الگوریتم مبتنی بر گریدSTING.. 90

4-6 بحث در مورد الگوریتم ها 93

4-6-1 ایا توسعه روش های سنتی درست است؟ 93

4-6-2 روش های جدید چه پیشنهاداتی دارند؟ 94

منابع. 96

فهرست اشکال

شکل 1-1 فرآینده داده کاوی.. 7

شکل1-2 نمونه یک درخت تصمیم.. 13

شکل 1-3 یک تقسیم بندی خوب ، درجه خلوص را برای فرزندان افزایش می دهد. 15

شکل 3-1 تقسیم خوشه های با معنی به زیر خوشه های بی معنی.. 58

شکل3-2 خطاهای روش Cs tree در ترکیب خوشه های یک بعدی و ایجاد خوشه های چند بعدی- قسمت A خطا در تعداد خوشه ها ، قسمت B خطا در شکل خوشه ها، قسمت C خطا در مرز خوشه ها 59

شکل3 -3  روی هم افتادگی خوشه ها در بروز رسانی به روش Cs tree. 60

شکل 4-2  الگوریتم خوشه بندی CLARA.. 82

شکل 4-3  الگوریتم خوشه بندی CLARANS . 84

شکل 4-4  الگوریتم خوشه بندی BIRCH.. 86

شکل 4-6 الگوریتم خوشه بندی.STING.. 92

فصل اول مقدمه ای بر داده کاوی

1-1 مقدمه

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

داده کاوی یکی از مهمترین این روشها است که به وسیله ان الگوهای مفید در داده ها با حداقل دخالت کاربران شناخته می شوند و اطلاعاتی را در اختیار کاربران و تحلیل گران قرار می دهند تا براساس انها تصمیمات مهم و حیاتی در سازمانها اتخاذ شوند .

1-2عامل مسبب پیدایش داده کاوی

اصلی ترین دلیلی که باعث شده داده کاوی کانون توجهات در صنعت اطلاعات قرار بگیرد، مساله در دسترس بودن حجم وسیعی از داده ها و نیاز شدید به اینکه از این داده ها,اطلاعات و دانش سودمند استخراج کنیم. اطلاعات و دانش بدست امده در کاربردهای وسیعی مورد استفاده قرار می گیرد.

داده کاوی را می توان حاصل سیر تکاملی طبیعی تکنولوژی اطلاعات دانست، که این سیر تکاملی ناشی از یک سیر تکاملی در صنعت پایگاه داده می باشد، نظیر عملیات جمع اوری داده ها وایجاد پایگاه داده، مدیریت داده و تحلیل و فهم داده ها.

تکامل تکنولوژی پایگاه داده و استفاده فراوان ان در کاربردهای مختلف سبب جمع اوری حجم فراوانی داده شده است. این داده های فراوان باعث ایجاد نیاز برای ابزارهای قدرتمند برای تحلیل داده ها گشته، زیرا در حال حاضر به لحاظ داده ثروتمند هستیم ولی دچار کمبود اطلاعات می باشیم.

ابزارهای داده کاوی داده ها را انالیز می کنند و الگوهای داده ها را کشف می کنند که می توان از ان در کاربردهایی نظیر تعیین استراتژی برای کسب و کار، پایگاه دانش و تحقیقات علمی و پزشکی، استفاده کرد. شکاف موجود بین داده ها و اطلاعات سبب ایجاد نیاز برای ابزارهای داده کاوی شده است تا داده های بی ارزش را به دانشی ارزشمند تبدیل کنیم

پایان نامه (به زبان انگلیسی) با عنوان داده کاوی و مدیریت ارتباط با مشتری در بیش از70 صفحه پی دی اف

استفاده از داده کاوی در مدیریت ارتباط با مشتری

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

ارائه یک مدل مستمر جهت شناسایی قوانین وابستگی از داده های کمیِ وزن دار

gb(0,0,0);font-style:normal;font-variaتکنیک قوانین وابستگی یکی از رایج ترین تکنیک های علم داده کاوی است که طی سالیان اخیر، کاربرد آن در حوزه های
مختلف علمی، بسیار مورد توجه قرار گرفته است. قوانین وابستگی، الگو های پنهان میان اقلام موجود در پایگاه داده های بزرگ را
شناسایی می کند. با وجود اینکه الگوریتم های زیادی جهت شناسایی قوانین وابستگی توسط محققان ارائه گردیده است اما
همچنان یک مشکل اساسی وجود داشته، و آن فقدان چارچوبی مناسب جهت استفاده مستمر و مداوم از این الگوریتم ها در طول
زمان است. در این مقاله جهت رفع مشکل مذکور، چارچوبی جهت استفاده مستمر از الگوریتم های قوانین وابستگی مطرح شده
است. در این مدل، در هر زمان، ابتدا پایگاه داده با افزایش تراکنش های جدیدتر و حذف تراکنش های قدیمی تر به روز شده و
سپس به تراکنش ها بر اساس میزان نزدیکی به زمان فعلی، وزن اختصاص می یابد. این کار به استفاده کنندگان از الگوریتم های
قوانین وابستگی کمک می کند تا همواره در هر زمان، قوانینی معتبرتر و مناسب تر بدست آورند. در راستای این امر، یک الگوریتم
شناسایی قوانین وابستگی از داده های کمی وزندار را توسعه داده و آن را در چارچوب یک مدل مستمر ارائه کرده ایم. در پایان،
مثالی جهت شرح چگونگی استفاده از این مدل برای شناسایی قوانین وابستگی از مقادیر کمی وزندار ارائه شده است