پایان نامه بررسی الگوریتم های خوشه بندی جریان های داده متنی

چکیده

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

تعریف داده کاوی

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

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

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

داده کاوی علم استخراج اطلاعات مفید از پایگاه های داده یا مجموعه دادهای می باشد

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

فصل اول. 1

1- 1 مقدمه. 2

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

1-3 کاربردهای داده کاوی.. 4

1-4 مراحل داده کاوی.. 5

1- 5 تکنیکها و روشهای داده کاوی.. 6

1-6 مقدمه‌ای بر خوشه‌بندی.. 7

1-7 کلاستر چیست؟. 10

1-8 انواع کلاسترها 10

1-9 خوشه‌بندی در مقابل طبقه‌‌بندی.. 10

1-10 یادگیری با نظارت در مقابل یادگیری بدون‌نظارت.. 11

1-11 کاربردها 12

1-12 مسائل درگیر با روش‌های خوشه‌بندی موجود 13

1-13 خوشه‌بندی در مقابل چندی‌سازی برداری.. 13

1-14 ویژگی های الگوریتم های خوشه بندی.. 14

1-15 روش‌های خوشه‌بندی.. 14

1-15-1 خوشه‌بندی انحصاری و خوشه‌بندی با هم‌پوشی. 15

1-15-1-1 خوشه بندی فازی.. 15

1-15-2 خوشه‌بندی سلسله مراتبی و خوشه‌بندی مسطح. 16

1-15-3 روشهای خوشه‌بندی سلسله مراتبی. 17

1-15-3-1 خوشه‌بندی با روش Single-Link. 18

1-15-3-2 خوشه‌بندی با روش Complete-Link. 19

1-15-3-3 خوشه‌بندی با روش Average-Link. 20

1-15-3-4 خوشه‌بندی با روش Group Average Link. 21

1-15-3-5 خوشه‌بندی با روش Median Distance. 22

1-15-3-6 خوشه‌بندی با روش Ward. 23

1-15-3-7 الگوریتم خوشه‌بندی پایین به بالای عمومی. 23

1-15-4 روش خوشه‌بندی K-Means (C-Means یا C-Centeriod) 24

1-15-4-1 مشکلات روش خوشه‌بندی K-Means. 26

1-15-5 الگوریتم خوشه‌بندی LBG.. 26

1-15-6 خوشه‌بندی بر اساس چگالی. 28

1-16 خوشه بندی متن. 34

1-16-1 الگوریتم خوشه بندی Bi-Section-K Means. 35

1-16-2 خوشه بندی مستندات متنی به کمک انتولوژی.. 36

1-16-3 کامپایل کردن دانش پس زمینه درون متن. 37

1-16-4 استراتژی های استفاده از کلمه در مقابل مفهوم 38

1-17 خوشه بندی جریانهای داده 38

1-17-1 الگوریتم های خوشه بندی جریان داده 39

1-17-2  مقایسه الگوریتم های خوشه بندی جریان داده 42

1-18 جریان داده متنی. 43

فصل دوم 45

( بررسی الگوریتم های خوشه بندی جریان های داده متنی) 45

2-1 مقدمه. 46

2-1-1TF-ICF. 47

2-2-2 الگوریتم STREAMING OSKM.. 49

2-2-2-1 K-means کروی انلاین. 49

2-2-2-2 پیاده سازی کارامد oskm.. 50

2-2-2-3 خوشه بندی مقیاس پذیر. 51

2-2-2-4STREAMING OSKM.. 53

2-2-2-5 ارزیابی و مقایسه. 53

2-2-3 الگوریتم OCTS. 53

2-2-3-1 تعاریف اولیه. 54

2-2-3-3 الگوریتم خوشه بندی انلاین OCTS. 59

2-2-3-4 الگوریتم OCTS. 62

2-2-4 ویژگی های Bursty. 66

2-2-4-1 ارائه ویژگی bursty. 69

تعریف6  ویژگی bursty. 69

2-2-5 الگوریتم خوشه بندی جریان متن بر اساس انتخاب ویژگی انطباقی. 71

2- طراحی پردازش جریان. 73

1 معایب الگوریتم TSC-AFS. 76

2-3 معیارهای ارزیابی کیفیت خوشه بندی.. 76

فصل سوم : جمع بندی و پیشنهادات.. 78

فهرست منابع. 85

شکل1-2:a) در طبقه‌بندی با استفاده  یک سری اطلاعات اولیه داده‌ها به دسته‌های معلومی نسبت داده‌ می‌شوند.b) در خوشه‌بندی داده‌ها با توجه به الگوریتم انتخاب شده به خوشه‌هایی نسبت داده‌ می‌شوند 15

شکل 1-3  مجموعه داده پروانه ای.. 20

شکل 1-4 : شمایی از روشهای خوشه‌بندی بالا به پایین و روشهای پایین به بالا. 22

شکل1-5 : شباهت بین دو خوشه در روش.. 23

شکل 1-6: شباهت بین دو خوشه در روش Complete-Linkبرابر است با بیشترین فاصلة بین داده‌های دو خوشه. 24

شکل 1-7 : شباهت بین دو خوشه در روش Average-Linkبرابر است با میانگین فاصلة بین داده‌های دو خوشه  25

شکل1-8 :  شباهت بین دو خوشه در روش Group Average Linkبرابر است با فاصله بین میانگین نقاط دو خوشه  26

شکل (2-1) تفاوت بین خوشه بندی جریان های متنی و سنتی. 51

شکل 2-2 ایجاد مدلVSMایستا از داده خام 72

شکل 2-3 شمایی از ارائه ویژگی bursty. 73

شکل 2-4 الگوریتم TSC-AFS. 79

پاورپوینت بررسی داده کاوی و الگوهای تکرارشونده در جریان داده‌ها

فرمت فایل : power point (قابل ویرایش) تعداد اسلاید : 40 اسلاید

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

پایان نامه داده کاوی پویا با استفاده از عامل هوشمند

چکیده

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

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

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

فهرست مطالب

 فصل اول - معرفی و آشنایی با مفاهیم اولیه. 1

1-1- مقدمه­ای بر داده­کاوی.. 2 

1-1-1- خوشه­بندی.. 3

1-1-2- کشف قواعد وابستگی.. 4

1-1-3- طبقه­بندی.. 4

1-1-3-1- طبقه­بندی مبتنی بر قواعد. 5

1-2- داده­کاوی توزیع­شده 7

1-3- عاملها و سیستمهای چندعامله. 8

1-3-1- عامل. 8

1-3-1-1- مقایسه عامل با شی.. 9

1-3-1-2- معماری عاملها 11

1-3-1-3- معماری BDI. 12

1-3-2- سیستم­های چندعامله. 14

1-3-2-1- مذاکره 17

1-4- بهره­گیری از عامل برای داده­کاوی.. 19

1-4-1- سیستم­های چندعامله، بستری برای داده­کاوی توزیع شده 19

1-5- جمع­بندی.. 22

 فصل دوم - داده­کاوی پویا 23

2-1- مقدمه­ای بر داده­کاوی پویا 24

2-2- جریان داده 25

2-3- طبقه­بندی جریان داده 26

2-3-1- موضوعات پژوهشی.. 27

2-4- جمع­بندی.. 31

فصل سوم - مروری بر کارهای انجام شده 33

3-1- مقدمه. 34

3-2- داده­کاوی توزیع­شده ایستا 35

3-2-1- روشهای غیرمتمرکز. 36

3-2-2- روشهای مبتنی بر توزیع ذاتی داده­ها 37

3-3- کارهای مهم انجام شده در زمینه داده­کاوی با استفاده از عامل. 38

3-4- کارهای انجام شده در زمینه طبقه­بندی جریان داده­ها 41

3-4-1- روشهای طبقه­بندی Ensemble-based. 41

3-4-2- درختهای تصمیم بسیار سریع. 43

3-4-3- طبقه­بندی On-Demand. 46

3-4-4- OLIN.. 48

3-4-5- الگوریتمهای LWClass. 49

3-4-6- الگوریتم ANNCAD.. 51

3-4-7- الگوریتم SCALLOP. 51

3-4-8- طبقه­بندی جریان داده­ها با استفاده از یک روش Rule-based. 53

3-5- جمع­بندی.. 54

فصل چهارم - تعریف مساله. 55

4-1- مقدمه. 56

4-2- تعریف مساله برای فاز اول. 56

4-2-1- جریان داده 57

4-2-2- مفهوم یا مدل موجود در جریان داده 57

4-2-3- مساله طبقه­بندی جریان داده­های دارای تغییر مفهوم. 57

4-3- تعریف مساله برای فاز دوم. 59

فصل پنجم - رویکردهای پیشنهادی.. 62

5-1- مقدمه. 63

5-2- رویکرد پیشنهادی برای فاز اول پروژه 63

5-2-1- عامل و ویژگیهای آن در این مساله. 64

5-2-2- عملکرد کلی عامل. 65

5-2-3- معماری عامل. 66

5-2-3-1- حسگرها 67

5-2-3-2- پایگاه دانش عامل. 68

5-2-3-3- تابع ارزیابی محیط.. 70

5-2-3-3-1- نحوه تشخیص اطلاعات و نگهداری الگوهای recur در جریان داده 70

5-2-3-3-2- نحوه استخراج الگوهای recur 70

5-2-3-3-3- نحوه بروزرسانی اطلاعات مربوط به الگوهای recur 73

5-2-3-3-4- نحوه محاسبه وقوع احتمال وقوع یک الگوی خاص... 74

5-2-3-4- تابع سودمندی.. 75

5-2-3-5- بخش تصمیم­گیری و Planning. 79

5-2-3-5-1- بخش تصمیم­گیری.. 79

5-2-3-5-2- Planning. 83

5-2-3-6- بخش Action. 86

5-3- رویکرد پیشنهادی برای فاز دوم مساله. 87

5-3-1- عاملهای مشتری.. 88

5-3-2- عامل صفحه زرد. 90

5-3-3- عاملهای داده­کاو. 91

5-3-3-1- معماری عاملهای داده­کاو. 92

5-3-3-1-1- تابع BRF. 94

5-3-3-1-2- تابع Generate Options. 95

5-3-3-1-3- تابع فیلتر. 95

5-3-3-1-4- بخش Actions. 96

5-3-3-1-5- Plan های عامل. 97

5-3-3-1-5- 1- Plan مربوط به طبقه­بندی.. 97

5-3-3-1-5-2- Plan مربوط به تطبیق طبقه­بند 98

5-3-3-1-5-3- Plan مربوط به خرید و فروش قواعد با استفاده از مذاکره 101

5-4- جمع­بندی.. 111

فصل ششم - آزمایشات و نتایج.. 113

6-1- مقدمه. 114

6-2- محیط عملیاتی.. 114

6-3- مجموعه داده­های مورد استفاده 116

6-3-1- مجموعه داده­های استاندارد. 116

6-3-2- مجموعه داده­های واقعی.. 117

6-4- معیارهای ارزیابی و روشهای مورد استفاده برای مقایسه. 117

6-5- آزمایشات انجام شده 118

6-5-1- آزمایشات مربوط به فاز اول. 119

6-5-2- آزمایشات مربوط به فاز دوم. 128

6-6- جمع­بندی.. 130

 فصل هفتم- جمع­بندی و نتیجه­گیری.. 132

فهرست مراجع. 136

فهرست اشکال

شکل 1-1- معماری BDI در عامل. 15
شکل 3-1- درخت تحقیق مربوط به طبقه­بندی در مبحث داده­کاوی.. 34
شکل 3-2- طبقه­بندی مبتنی بر Ensemble. .44
شکل 3-3- چارچوب روش On-Demand. 47
شکل 3-4- نمایی از سیستم OLIN.. 49
شکل 3-5- پروسه SCALLOP 53
شکل 5-1- نمودار ترتیب عملکرد عامل پیشنهادی.. 66
شکل 5-2- معماری عامل پیشنهادی.. 67
شکل 5-3- پنجره نظاره بر روی جریان داده­ها 68
شکل 5-4- گراف ایجاد شده از روی رشته مفهوم­ها 71
شکل 5-5- محل تجمع الگوهای استخراج شده از رشته مفهوم­ها 73
شکل 5-6- میزان محاسبه شده احتمالها به ازای مقادیر مختلف K.. 81
شکل 5-7- شبه کد Plan کلی عامل. 83
شکل 5-8- نسبت واریانس به حاصلضرب 50 متغیر دارای مجموع ثابت.. 85
شکل 5-9- وزن دهی چند داده مختلف... 86
شکل 5-10- نمایی کلی از سیستم چندعامله ایجاد شده 88
شکل 5-11- معماری BDI عامل داده­کاو. 93
شکل 5-12- بخشی از جریان داده و قواعد استخراج شده از آن. 99
شکل 5-13- بخشی از جریان داده و قواعد استخراج شده از آن. 101
شکل 6-1- کد نمونه برای استفاده از بسته نرم افزاری weka. 115
شکل 6-2- زمان لازم بر حسب میلی ثانیه برای داده­های Stagger 120
شکل 6-3- زمان مصرف شده برای تطبیق طبقه­بند. 120
شکل 6-4- نمودار مربوط به زمان پردازش روشهای مختلف برای داده­های HyperPlan 121
شکل 6-5- زمان مصرف شده برای تطبیق طبقه­بند 121
شکل 6-6- نمودار مربوط به زمان پردازش روشهای مختلف برای داده­های Nursery 122
شکل 6-7- زمان مصرف شده برای تطبیق طبقه­بند برای داده­های Nursery 122
شکل 6-8- عملکرد روشهای مختلف بر روی مجموعه داده HyperPlan 124
شکل 6-9- نمودار عملکرد روشهای مختلف بر روی مجموعه داده HyperPlan در یک بازه کوچکتر 124
شکل 6-10- نمودار عملکرد روشهای مختلف بر روی مجموعه داده HyperPlan در یک بازه کوچکتر 125
شکل 6-11- زمان مصرف شده برای تطبیق طبقه­بند برای داده­های HyperPlan 125
شکل 6-12- عملکرد روشهای مختلف بر روی مجموعه داده Stagger 126
شکل 6-13- زمان مصرف شده برای تطبیق طبقه­بند برای داده­های Stagger 126
شکل 6-14- عملکرد روشهای مختلف بر روی مجموعه داده Nursery 127
شکل 6-15- زمان مصرف شده برای تطبیق طبقه­بند برای داده­های Nursery 127
شکل 6-16- نمودار نتایج حاصل از طبقه­بندی توزیع ­شده مجموعه داده Nursery 130

فهرست جدولها

جدول 1-1- ویژگیهای یک عامل 11
جدول 3-1- ماتریس حاصل از روش LWClass. 51
جدول 3-2- مقایسه تکنیکهای ذکر شده 54
جدول 5-1- ساختار اطلاعاتی ذخیره شده برای هر مفهوم و الگو. 69
جدول 5-2- ساختار اطلاعاتی مربوط به وقوع الگوی "CFDA". 75
جدول 5-3- نمونه ای از خروجی تابع سودمندی عامل. 81
جدول 5-4- اطلاعات مورد استفاده برای تخمین سودمندی یک قاعده 105
جدول 6-1- دقت طبقه­بندی روشهای مختلف... 128
جدول 6-2- نتایج حاصل از طبقه­بندی توزیع شده مجموعه داده Nursery در سه مفهوم مختلف... 130

 

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

چکیده

 حجم بزرگ داده ها به تنهایی به مدیران سازمان ها در تصمیم سازی و تصمیم گیری هیچ کمکی نمی کند، بلکه باعث سردرگمی مدیران سازمان ها نیز می شود.بنابراین مدیریت داده های خام و تبدیل داده های خارجی و داخلی سازمان به اطلاعات و دانش با استفاده از تکنیک های گوناگون،نقش اساسی و محوری دارد.از تکنیک های معروف در این زمینه داده کاوی است،که می تواند بر روی بانک اطلاعاتی انجام شود و دانش مورد نیاز را بدست آورد.در فصل اول به بررسی این مفهوم پرداختیم. کاوش خوشه ها نیز یکی از تکنیک های حائز اهمیت در زمینه رو به رشد،معروف به داده کاوی اکتشافی می باشد که در رشته های گوناگون مهندسی و علمی از قبیل زیست شناسی،روان شناسی،پزشکی،بازاریابی،کامپیوتر و نقشه برداری ماهواره ای به کار گرفته شده است. این مفهوم در فصل های سوم و چهارم دنبال شده است.در فصل سوم به یکی از الگوریتم های خوشه بندی به نام 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عامل مسبب پیدایش داده کاوی

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

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

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

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