new5 free

جستجوی الگوهای نوظهور با ویژگی های جریانی

59.000تومان

توضیحات

دانلود و مشاهده قسمتی از متن کامل پایان نامه :

 

 

دانشکده­ مهندسی

 

پایان­نامه کارشناسی ارشد در رشته­ مهندسی کامپیوتر (هوش مصنوعی)

جستجوی الگوهای نوظهور با ویژگی های جریانی

توسط:

………………..

استاد راهنما:

دکتر ستار هاشمی

بهمن 1392

 

 

 

چکیده

 

 

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

در این مطالعه، ما ساختار دینامیک از درخت الگوی مکرر پیشنهاد می دهیم تا درخت به محض ورود ویژگی های جدید ساخته شود و استخراج الگوهای نوظهور بصورت برخط صورت گیرد. DFP-SEPSF، یک روش موثر پایین به بالا ارائه می دهد تا یک درخت الگوی مکرر دینامیک نامرتب UDFP-tree و یک درخت الگوی مکرر دینامیک مرتب ODFP-tree بسازد. اولین روش ترتیب آیتم ها را در نظر نمی گیرد، در حالیکه دومین روش ترتیب آیتم ها را اعمال می کند.

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

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

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

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

واژه­های کلیدی:

الگوهای نوظهور، درخت الگوی مکرر دینامیک، ترتیب آیتم ها، ویژگی های جریانی

 

 

 

 

 

 

 

 

 

 

فهرست مطالب

فصل اول ………………………………………………………………………………………………………………………………..  1

1- مقدمه ………………………………………………………………………………………………………………………………..  2

1-1 مقدمه ……………………………………………………………………………………………………………………  2

1-2 مفهوم الگوهای نوظهور ………………………………………………………………………………………….  3

1-3 مفهوم ویژگی های جریانی ……………………………………………………………………………………..  5

1-4 چالش های موجود در استخراج الگوهای نوظهور …………………………………………………….  6

1-5 الگوریتم های استخراج الگوهای نوظهور ………………………………………………………………..  8

1-6 ایده اصلی تحقیق ………………………………………………………………………………………………….  11

1-7 نگاهی کلی به فصول رساله ……………………………………………………………………………………  13

فصل دوم ………………………………………………………………………………………………………………………………..  14

2- پیشینه تحقیق …………………………………………………………………………………………………………………..  15

2-1 مقدمه …………………………………………………………………………………………………………………..  15

2-2 روش های مبتنی بر قانون ………………………………………………………………………………………  15

2-2-1 روش Classification Based on Association (CBA) ………………………………  15

2-2-2 روش کلاسه بندی Classification based on Multiple-class Association Rule (CMAR)                 16

2-2-3 روش کلاسه بندی Classification based on Prediction Association Rule (CPAR)        16

2-3 روش های استخراج الگوها ……………………………………………………………………………………  17

2-3-1 روش مبتنی بر مرز ………………………………………………………………………………………….  17

2-3-2 روش مبتنی بر محدودیت ……………………………………………………………………………….  17

2-3-3 الگوریتم استخراج درخت الگوی تقابل CP-tree …………………………………………….  18

2-3-4 روش استخراج با کمک دیاگرام دودویی صفر ZBDD Miner …………………………  18

2-3-5 روش استخراج الگوهای نوظهور متمایز DP-Miner ……………………………………….  18

2-4 روش های کلاسه بندی مبتنی بر الگوهای نوظهور ………………………………………………………………  20

2-4-1 روش کلاسه بندی مبتنی بر اساس مجموع الگوهای نوظهور CAEP ………………………………..  20

2-4-2 الگوریتم کلاسه بندی بر پایه تئوری اطلاعات iCAEP ……………………………………………………  20

2-4-3 روش کلاسه بندی بر پایه الگوهای نوظهور جهشی JEPs-classifier …………………………….  21

2-4-4 روش کلاسه بندی بر پایه الگوهای نوظهور جهشی قوی …………………………………………………  21

2-4-5 روش تصمیم گیری مبتنی بر نمونه DeEPs …………………………………………………………………..  21

2-4-6 روش کلاسه بندی توسط مجموعه راست نمایی PCL …………………………………………………….  22

فصل سوم ……………………………………………………………………………………………………………………………….  23

3- دانش اولیه ………………………………………………………………………………………………………………………..  24

3-1 الگوهای نوظهور …………………………………………………………………………………………………… 24

3-2 درخت الگوی مکرر دینامیک DFP-tree ………………………………………………………………  30

فصل چهارم …………………………………………………………………………………………………………………………….  33

4- راهکارهای ارائه شده برای استخراج الگوهای نوظهور قوی مبتنی بر ویژگی های جریانی ………..  34

4-1 مقدمه …………………………………………………………………………………………………………………..  34

4-2- درخت الگوی مکرر دینامیک نامرتب Unordered Dynamic FP-tree ……………..  35

4-3 درخت الگوی مکرر دینامیک مرتب Ordered Dynamic FP-tree ……………………..  44

4-4 روش استخراج الگوها SEP-Miner ……………………………………………………………………..  56

فصل پنجم ………………………………………………………………………………………………………………………………  62

5- آزمایشات تجربی ……………………………………………………………………………………………………………….  63

5-1 مقدمه …………………………………………………………………………………………………………………..  63

5-2 کلاسه بندها …………………………………………………………………………………………………………  63

5-2-1 کلاسه بند درخت تصمیم C4.5 ……………………………………………………………………  63

5-2-2 کلاسه بند SVM …………………………………………………………………………………………  64

5-2-3 کلاسه بند بیزین ساده ………………………………………………………………………………..  65

5-2-4 کلاسه بند نزدیکترین همسایه …………………………………………………………………….  66

5-2-5 الگوریتم AdaBoost…………………………………………………………………………………. 66

5-3 تست های آماری ………………………………………………………………………………………………….  68

5-3-1 تست آماری جفت شده t-tets …………………………………………………………………………  68

5-3-2 تست آماری Wilcoxon ………………………………………………………………………………..  68

5-3-3 تست آماری فردمن ……………………………………………………………………………………….  69

5-4 تنظیمات تجربی ……………………………………………………………………………………………………  71

5-5 مقایسه دقت پیش بینی ………………………………………………………………………………………..  73

5-6 مقایسه تعداد الگوها …………………………………………………………………………………………….  81

5-7 مقایسه زمان اجرا …………………………………………………………………………………………………  83

5-8 تحلیل اثر ترتیب در ساخت درخت الگوی مکرر دینامیک ………………………………………  86

5-9 چگونگی تعیین کردن حداقل آستانه فراوانی نسبی ………………………………………………..  88

5-10 تحلیل حساسیت روی حداقل آستانه های نرخ رشد ……………………………………………….  89

5-11 مقایسه کارایی DFP-SEPSF بدون دانستن کل فضای ویژگی ها ………………………….  90

5-12 خلاصه نتایج تجربی …………………………………………………………………………………………….  94

فصل ششم ……………………………………………………………………………………………………………………………..  96

6- نتیجه گیری و کارهای آینده ……………………………………………………………………………………………….  97

اختصارات ……………………………………………………………………………………………………………………………….  99

واژه نامه فارسی به انگلیسی …………………………………………………………………………………………………….  100

واژه نامه انگلیسی به فارسی …………………………………………………………………………………………………….  108

فهرست منابع ………………………………………………………………………………………………………………………….  116

 

 

 

فهرست جدول­ها

جدول 3-1 الگوهای نوظهور کاندید از کلاس Poisonous به کلاس Edible……………………………….. 38

جدول 5-1 توصیف مجموعه داده ها؛ #Features تعداد ویژگی ها، #Instances تعداد نمونه ها، #Classes تعداد کلاس ها  71

جدول 5-2 مقایسه دقت پیش بینی (%): کلاسه بندهای DFP-SEPSF، EPSF، SJEP، CAEP ..             75

جدول 5-3 مقایسه دقت پیش بینی (%): کلاسه بندهای DFP-SEPSF، CBA، CMAR، CPAR . 77

جدول 5-4 مقایسه دقت پیش بینی (%): کلاسه بندهای DFP-SEPSF، NB، Knn، J48، SVM، AdaBoost           78

جدول 5-5 تعداد دفعات win/tie/loss کلاسه بند DFP-SEPSF در مقابل یازده کلاسه بند دیگر ………..  80

جدول 5-6 تعداد دفعات win/tie/loss کلاسه بند DFP-SEPSF در مقابل یازده کلاسه بند دیگر؛ با استفاده از تست جفت شده t-test در سطح معنادار 95% …………………………………………………………………………………………………………………..  80

جدول 5-7 تعداد دفعات win/tie/loss کلاسه بند DFP-SEPSF در مقابل یازده کلاسه بند دیگر؛ با استفاده از تست Wilcoxon در سطح معنادار 95% ……………………………………………………………………………………………………………………………  80

جدول 5-8 تست فردمن در سطح معنادار 95% با میانگین رتبه کلاسها ……………………………………..  81

جدول 5-9 تست Bonferroni-Dunn ……………………………………………………………………………………  81

جدول 5-10 مقایسه تعداد الگوهای استخراجی: کلاسه بندهای DFP-SEPSF، CAEP، CBA، CMAR    83

جدول 5-11 زمان اجرا: کلاسه بندهای DFP-SEPSF، CAEP ………………………………………………….  86

جدول 5-12 مقایسه درخت الگوی مکرر مرتب با درخت الگوی مکرر نامرتب ………………………………  88

 

 

 

 

 

فهرست شکل­ها

شکل 3-1. یک مثال از الگوهای مکرر از مجموعه داده Balloon ………………………………………………  25

شکل  3-2. یک مثال از درخت الگوی مکرر دینامیک ……………………………………………………………….  32

شکل 4-1. مرحله به مرحله ساخت دینامیک درخت الگوی مکرر بدون در نظر گرفتن ترتیب آیتم ها                          35

شکل 4-2. ساخت درخت الگوی مکرر دینامیک بدون در نظر گرفتن ترتیب آیتم ها ……………………  40

شکل 4-3. مقایسه ساختار درخت الگوی مکرر با و بدون در نظر گرفتن ترتیب آیتم ها ……………….  45

شکل 4-4. ساختن درخت الگوی مکرر بر پایه ویژگی های جریانی …………………………………………….  45

شکل 4-5. درخت الگوی مکرر پایه ………………………………………………………………………………………….  47

شکل 4-6. اضافه کردن گره های جدید به درخت الگوی مکرر و تغییر موقعیت آنان ……………………  48

شکل 4-7. فرآیند ترکیب مرحله  به مرحله ………………………………………………………………………………  51

شکل 4-8. استخراج الگوهای نوظهور با استفاده از FP-tree بصورت مرحله به مرحله ……………….  57

شکل 5-1 بردار پشتیبان و صفحه جداکننده خطی…………………………………………………………………….. 65

شکل 5-2 تاثیر آستانه های نرخ رشد بر روی DFP-SEPSF: دقت روش پیشنهادی بر روی سی مجموعه داده تحت آستانه های 20، 30، 40، 50 و 60 گزارش داده شده است. ……………………………………………………………………………………………….  90

شکل 5-3 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 50، 50، 60، 60، و 60 هستند.  91

شکل 5-4 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 70، 80، 100، 70، و 80 هستند              92

شکل 5-5 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 70، 90، 70، 100، و 70 هستند  92

شکل 5-6 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 50، 60، 70، 50، و 40 هستند .  93

شکل 5-7 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 80، 80، 100، 100، و 90 هستند             93

شکل 5-8 دقت های J48، Knn، NB، SVM، AdaBoost به ترتیب 90، 80، 60، 80، و 90 هستند 94

 

 


 

 

فصل اول

 

 

                                                مقدمه

 

 

 

 

 

 

 

 

 

 

1-          مقدمه

 

1-1-    مقدمه

 کلاسه بندی[1] یکی از وظایف اساسی در داده کاوی[2] است که بطور وسیعی در زمینه یادگیری ماشین[3]، شبکه های عصبی[4] و تشخیص الگو[5] مورد مطالعه واقع شده است. ورودی، مجموعه ای از نمونه های آموزشی[6] است که شامل چندین ویژگی[7] است. ویژگی ها با توجه به دامنه مقادیرشان به دو دسته ویژگی های گسسته[8] و ویژگی های پیوسته[9] قابل تفکیک هستند. در حالت کلی، یک کلاسه بند[10]، توصیف مختصر و معنادار (مدل[11]) برای هر برچسب کلاس[12] در رابطه با ویژگی ها تولید می کند. سپس، مدل برای پیش بینی برچسب کلاس نمونه های ناشناخته[13] بکار می رود. کلاسه بندی همچنین بعنوان یادگیری با ناظر[14] نیز شناخته می شود که در آن هر نمونه آموزشی دارای برچسب کلاس است. در حالی که، یادگیری بدون ناظر[15] یا خوشه بندی[16] جستجو می کند و گروه های همگن از اشیا را بر اساس مقادیر ویژگی هایشان دسته بندی می کند؛ در واقع، نمونه ها دارای برچسب کلاس نیستند. کلاسه بندی در محدوده وسیعی از کاربردها از جمله آزمایشات علمی[17]، تشخیص دارو[18]، پیش بینی آب و هوا[19]، تایید اعتبار[20]، تقسیم بندی مشتری[21]، بازاریابی هدف[22] و تشخیص تقلب[23] بطور موفقیت آمیزی بکار می رود.

کلاسه بندی بر پایه الگوها[24]، یک متدلوژی جدید محسوب می شود. کشف الگوهایی که نشاندهنده تمایز بین کلاس های مختلف هستند، یکی از موضوعات مهم در داده کاوی محسوب می شود. در این تحقیق، ما کلاسه بندی را بر اساس الگوهایی به نام الگوهای نوظهور[25] (Emerging Patterns) که تمایز بین کلاس ها را بصورت بارزی نشان می دهند، از مجموعه داده ها[26] استخراج می کنیم و سپس، بر اساس آنها، کلاسه بندی را انجام می دهیم.

1-2-   مفهوم الگوهای نوظهور

مفهوم الگوهای نوظهور برای استخراج دانش از پایگاه داده ها توسط Dong و Li پیشنهاد شده است تا تغییرات قابل توجه بین کلاس ها را به تصویر بکشند [1]. یک الگوی نوظهور، ترکیب عطفی بین ویژگی هایی است که میزان احتمال حضور آن در یک کلاس نسبت به دیگر کلاس ها بطور قابل توجهی تغییر می کند [1،2]. این الگوها مفید هستند به این دلیل که قادر هستند تا وجه تمایز بین کلاس ها را بیان کنند. در صورتی که میزان فراوانی[27] هر الگو که در یک کلاس نسبت به دیگر کلاس ها قابل توجه باشد، نشاندهنده آن است که این الگو، بطور خاص به این کلاس اختصاص دارد و از طرفی این نوع الگوها برای پایگاه داده هایی که بحث محدودیت زمانی برای استخراج دانش از آنها مطرح است، اهمیت ویژه ای می یابند.

استخراج الگوهای نوظهور بدین صورت مطرح می شود: « پیدا کردن آیتم هایی که نرخ رشد[28]  آن (که بصورت نسبت احتمال آن آیتم بین کلاس های مختلف تعریف می شود) از مقدار آستانه ای بیشتر باشد.» این مقدار آستانه باید بگونه ای انتخاب شود که الگوهای استخراجی ، تفاوت و تمایز بین کلاس های مختلف را نشان دهند. این الگوها در واقع مجموعه ای از آیتم ها هستند که بیان کننده ترکیب عطفی  بین مقادیر ویژگی ها هستند [2].

نوعاً، تعداد الگوهای استخراجی بسیار زیاد است اما فقط شمار کمی از این الگوها برای تحلیل داده ها و کلاسه بندی مطلوب و مفید هستند. از آن جایی که مقدار زیادی از این الگوها بی ربط[29] و تکراری[30] هستند، دانش جدیدی را فراهم نمی کنند و لذا تاثیر نامطلوبی بر روی دقت  کلاسه بند دارند که موجب کاهش دقت پیش بینی[31] می شوند. برای افزایش کارایی[32]  و دقت، بایستی روالی را توسعه داد که الگوهای وابسته و غیر مفید حذف شوند تا شمار این الگوها کاهش یابد.

یک الگوی نوظهور با احتمال بالا در کلاس خودش و احتمال پایین در کلاس مقابلش می تواند برای تعیین یک نمونه تست بکار رود. قدرت این الگو توسط معیارهایی مثل فراوانی نسبی[33] و نرخ رشد ( نسبت احتمال الگو در یک کلاس نسبت به دیگر کلاس ها) آن بیان می شود.

در بسیاری از زمینه های کاربردی مانند کشف دانش از داده های ژنی[34] ، پردازش تصویر[35]، کشف نفوذ[36] ، کشف برون هشته[37]، کشف کلاهبرداری[38] ، داده های نامتوازن[39] ، جریان داده ها[40] ، بیوانفورماتیک[41] ، سیستم های پیشنهاد دهنده[42] ، نیاز است که تغییر ناگهانی در داده ها تشخیص داده شود. الگوهای نوظهور تغییرات ناگهانی و تفاوت های قابل توجه را از داده ها استخراج می کنند. الگوهای نوظهور، در زمینه پردازش تصویر برای قطعه بندی  بدین گونه عمل می کند که سعی می کند در پیکسل هایی که تغییر ناگهانی شدت[43] بوجود می آید را بعنوان یک قطعه جدید معرفی کند. در زمینه کشف نفوذ و کلاهبرداری، رفتار داده ها پیگیری می شود، زمانی که رفتار داده ها بصورت ناگهانی تغییر کند، بعنوان نفوذ تشخیص داده می شود. در سیستم های پیشنهاد دهنده، سیستم به دنبال رفتارهای خاص و مختص هر کاربر است تا با کشف ویژگی های خاص هر کاربر، به او محصولات مطابق با علایق و استعدادهای او را پیشنهاد دهد. لذا الگوهای نوظهور در این راستا نقش بسزایی دارند.

  • مفهوم ویژگی های جریانی[44]

در داده های جریانی[45]، نمونه ها به مرور زمان دریافت می شوند در حالیکه تعداد ویژگی ها ثابت می باشد. اما در ویژگی های جریانی، تعداد داده های یادگیری ثابت می باشد ولی ویژگی ها بصورت دینامیک تولید می شوند و الگوریتم یادگیری به مرور زمان ویژگی ها را دریافت می دارد [31، 32]. در ویژگی های جریانی روال بدین صورت است ویژگی های توسط روش های تولید ویژگی مانند روش های یادگیری رابطه ای آماری[46] و تعاملات بین ویژگی ها[47]، تولید می شوند. مشکلاتی که در پی تولید ویژگی ها توسط این روش ها بروز می کند بدین شرح است که: 1) میلیون ها و یا حتی بیلیون ها ویژگی تولید می شوند که بدلیل محدودیت های حافظه امکان نگهداری این حجم از ویژگی وجود دارد و از طرفی زمان بسیار زیادی بایستی صرف شود تا فرآیند یادگیری شروع شود. 2) ویژگی ها توسط کوئری های موجود در SQL تولید می شوند که اجرای این کوئری ها محدود به زمان پروسسور[48] است تقریبا پروسسور هر صدهزار کوئری را در 24 ساعت اجرا می کند. از طرفی بسیاری از ویژگی ها تولیدی بی ربط و تکراری هستند[49]. این موضوع نشان می دهد که شمار کمی از این ویژگی های تولیدی در عمل در فرآیند یادگیری موثر است و لذا تولید ویژگی ها هزینه بر است [32]. بر این اساس برای فائق آمدن بر این مشکلات، مفهوم ویژگی های جریانی شکل گرفت و تلاش شد تا با تولید دینامیک ویژگی ها و بررسی این ویژگی ها در زمان تولید و تاثیر آن بر روال یادگیری فرآیند تولید ویژگی ها را هدایت کنند.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  • چالش­های موجود در استخراج الگوهای نوظهور
Total frequency فراوانی کل
Two-class دوکلاسه
Target marketing بازاریابی هدف
Training data داده­های آموزشی
Training instances نمونه های آموزشی
Training phase مرحله آموزشی
Unbalanced نامتوازن
Unknown ناشناخته
  Unordered tree درخت نامرتب
Unordered dynamic FP-tree درخت الگوی مکرر دینامیک نامرتب
Unpruned هرس نشده
Unseen data داده دیده نشده
Unsupervised learning یادگیری بدون ناظر
Variance واریانس
Weather prediction پیش بینی آب و هوا
Zero-suppressed binary decision diagram دیاگرام تصمیم دودیی مانع صفر
Zero suppressed binary decision diagram miner استخراج کننده دیاگرام تصمیم دودوی مانع صفر

 

 

فهرست منابع

 

  • [1] Dong, Guozhu, and Jinyan Li. “Efficient mining of emerging patterns: Discovering trends and differences.” In Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 43-52. ACM, 1999.
  • [2] Zhang, Xiuzhen, Guozu Dong, and Ramamohanarao Kotagiri. “Exploring constraints to efficiently mine emerging patterns from large high-dimensional datasets.” In Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 310-314. ACM, 2000.
  • [3] Li, Jinyan, Guozhu Dong, and Kotagiri Ramamohanarao. “Making use of the most expressive jumping emerging patterns for classification.” Knowledge and Information systems 3, no. 2 (2001): 131-145.
  • [4] Lo, David, Hong Cheng, Jiawei Han, Siau-Cheng Khoo, and Chengnian Sun. “Classification of software behaviors for failure detection: a discriminative pattern mining approach.” In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 557-566. ACM, 2009.
  • [5] Li, Jinyan, Huiqing Liu, James R. Downing, Allen Eng-Juh Yeoh, and Limsoon Wong. “Simple rules underlying gene expression profiles of more than six subtypes of acute lymphoblastic leukemia (ALL) patients.” Bioinformatics 19, no. 1 (2003): 71-78.
  • [6] Fang, Gang, Gaurav Pandey, Wen Wang, Manish Gupta, Michael Steinbach, and Vipin Kumar. “Mining low-support discriminative patterns from dense and high-dimensional data.” Knowledge and Data Engineering, IEEE Transactions on 24, no. 2 (2012): 279-294.
  • [7] Mao, Shihong, and Guozhu Dong. “Discovery of highly differentiative gene groups from microarray gene expression data using the gene club approach.” Journal of Bioinformatics and Computational Biology 3, no. 06 (2005): 1263-1280.
  • [8] Boulesteix, Anne-Laure, Gerhard Tutz, and Korbinian Strimmer. “A CART-based approach to discover emerging patterns in microarray data.” Bioinformatics 19, no. 18 (2003): 2465-2472.
  • [9] Li, Jinyan, and Limsoon Wong. “Identifying good diagnostic gene groups from gene expression profiles using the concept of emerging patterns.” Bioinformatics 18, no. 5 (2002): 725-734.
  • Wu, Xindong, Kui Yu, Hao Wang, and Wei Ding. “Online streaming feature selection.” In Proceedings of the 27th international conference on machine learning (ICML-10), pp. 1159-1166. 2010.
  • Zhou, Jing, Dean P. Foster, Robert A. Stine, and Lyle H. Ungar. “Streamwise feature selection.” The Journal of Machine Learning Research 7 (2006): 1861-1885.
  • Dong, Guozhu, and Jinyan Li. “Mining border descriptions of emerging patterns from dataset pairs.” Knowledge and Information Systems 8, no. 2 (2005): 178-202.
  • Li, Jinyan, Kotagiri Ramamohanarao, and Guozhu Dong. “The Space of Jumping Emerging Patterns and Its Incremental Maintenance Algorithms.” In ICML, pp. 551-558. 2000.
  • Bayardo Jr, Roberto J. “Efficiently mining long patterns from databases.” In ACM Sigmod Record, vol. 27, no. 2, pp. 85-93. ACM, 1998.
  • Han, Jiawei, Jian Pei, and Yiwen Yin. “Mining frequent patterns without candidate generation.” In ACM SIGMOD Record, vol. 29, no. 2, pp. 1-12. ACM, 2000.
  • Han, Jiawei, Jian Pei, Yiwen Yin, and Runying Mao. “Mining frequent patterns without candidate generation: A frequent-pattern tree approach.” Data mining and knowledge discovery 8, no. 1 (2004): 53-87.
  • Fan, Hongjian, and Ramamohanarao Kotagiri. “An efficient single-scan algorithm for mining essential jumping emerging patterns for classification.” In Advances in Knowledge Discovery and Data Mining, pp. 456-462. Springer Berlin Heidelberg, 2002.
  • Loekito, Elsa, and James Bailey. “Fast mining of high dimensional expressive contrast patterns using zero-suppressed binary decision diagrams.” In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 307-316. ACM, 2006.
  • Yu, Kui, Wei Ding, Dan A. Simovici, and Xindong Wu. “Mining emerging patterns by streaming feature selection.” In Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 60-68. ACM, 2012.
  • Li, Jinyan, Guozhu Dong, and Kotagiri Ramamohanarao. “Instance-based classification by emerging patterns.” In Principles of Data Mining and Knowledge Discovery, pp. 191-200. Springer Berlin Heidelberg, 2000.
  • Dong, Guozhu, Xiuzhen Zhang, Limsoon Wong, and Jinyan Li. “CAEP: Classification by aggregating emerging patterns.” In Discovery Science, pp. 30-42. Springer Berlin Heidelberg, 1999.
  • Quinlan, John Ross. C4. 5: programs for machine learning. Vol. 1. Morgan kaufmann, 1993.
  • Cortes, Corinna, and Vladimir Vapnik. “Support vector machine.” Machine learning 20, no. 3 (1995): 273-297.
  • Freund, Yoav, and Robert E. Schapire. “A desicion-theoretic generalization of on-line learning and an application to boosting.” In Computational learning theory, pp. 23-37. Springer Berlin Heidelberg, 1995.
  • Fan, Hongjian, and Kotagiri Ramamohanarao. “Fast discovery and the generalization of strong jumping emerging patterns for building compact and accurate classifiers.” Knowledge and Data Engineering, IEEE Transactions on 18, no. 6 (2006): 721-737.
  • Zhang, Xiuzhen, and Guozhu Dong. “Information-based classification by aggregating emerging patterns.” In Intelligent Data Engineering and Automated Learning—IDEAL 2000. Data Mining, Financial Engineering, and Intelligent Agents, pp. 48-53. Springer Berlin Heidelberg, 2000.
  • Ma, Bing Liu Wynne Hsu Yiming. “Integrating classification and association rule mining.” In Proceedings of the 4th. 1998.
  • Li, Wenmin, Jiawei Han, and Jian Pei. “CMAR: Accurate and efficient classification based on multiple class-association rules.” In Data Mining, 2001. ICDM 2001, Proceedings IEEE International Conference on, pp. 369-376. IEEE, 2001.
  • Han, J. “CPAR: Classification based on predictive association rules.” In Proceedings of the third SIAM international conference on data mining, vol. 3, pp. 331-335. 2003.
  • Li, Jinyan, Guimei Liu, and Limsoon Wong. “Mining statistically important equivalence classes and delta-discriminative emerging patterns.” In Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 430-439. ACM, 2007.
  • Perkins, Simon, and James Theiler. “Online feature selection using grafting.” In ICML, pp. 592-599. 2003.
  • Perkins, Simon, Kevin Lacker, and James Theiler. “Grafting: Fast, incremental feature selection by gradient descent in function space.” The Journal of Machine Learning Research 3 (2003): 1333-1356.
  • García-Borroto, Milton, José Fco Martínez-Trinidad, and Jesús Ariel Carrasco-Ochoa. “Fuzzy emerging patterns for classifying hard domains.” Knowledge and information systems 28, no. 2 (2011): 473-489.
  • Pasquier, Nicolas, Yves Bastide, Rafik Taouil, and Lotfi Lakhal. “Efficient mining of association rules using closed itemset lattices.” Information systems 24, no. 1 (1999): 25-46.
  • Novak, Petra Kralj, Nada Lavrač, and Geoffrey I. Webb. “Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining.” The Journal of Machine Learning Research 10 (2009): 377-403.
  • Fayyad, Usama, and Keki Irani. “Multi-interval discretization of continuous-valued attributes for classification learning.” (1993).
  • Allwein, Erin L., Robert E. Schapire, and Yoram Singer. “Reducing multiclass to binary: A unifying approach for margin classifiers.” The Journal of Machine Learning Research 1 (2001): 113-141.
  • Hastie, Trevor, and Robert Tibshirani. “Classification by pairwise coupling.” The annals of statistics 26, no. 2 (1998): 451-471.
  • Rifkin, Ryan, and Aldebaro Klautau. “In defense of one-vs-all classification.” The Journal of Machine Learning Research 5 (2004): 101-141.
  • Wu, Ting-Fan, Chih-Jen Lin, and Ruby C. Weng. “Probability estimates for multi-class classification by pairwise coupling.” The Journal of Machine Learning Research 5 (2004): 975-1005.
  • Pasquier, Nicolas, Yves Bastide, Rafik Taouil, and Lotfi Lakhal. “Discovering frequent closed itemsets for association rules.” In Database Theory—ICDT’99, pp. 398-416. Springer Berlin Heidelberg, 1999.
  • Bastide, Yves, Rafik Taouil, Nicolas Pasquier, Gerd Stumme, and Lotfi Lakhal. “Mining frequent patterns with counting inference.” ACM SIGKDD Explorations Newsletter 2, no. 2 (2000): 66-75.
  • Song, Hee Seok, and Soung Hie Kim. “Mining the change of customer behavior in an internet shopping mall.” Expert Systems with Applications 21, no. 3 (2001): 157-168.
  • Ungar, Lyle H., Jing Zhou, Dean P. Foster, and R. A. Stine. “Streaming feature selection using iic.” AI&STAT’05 (2005).
  • Zhou, Jing, Dean Foster, Robert Stine, and Lyle Ungar. “Streaming feature selection using alpha-investing.” In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pp. 384-393. ACM, 2005.
  • Wu, Xindong, Kui Yu, Wei Ding, Hao Wang, and Xingquan Zhu. “Online feature selection with streaming features.” (2012): 1-1.
  • Foster, Dean P., and Robert A. Stine. “Variable selection in data mining: Building a predictive model for bankruptcy.” Journal of the American Statistical Association 99, no. 466 (2004): 303-313.
  • Džeroski, Sašo. “Multi-relational data mining: an introduction.” ACM SIGKDD Explorations Newsletter 5, no. 1 (2003): 1-16.
  • Džeroski, Sašo. Relational data mining. Springer US, 2010.
  • Hall, Mark, Eibe Frank, Geoffrey Holmes, Bernhard Pfahringer, Peter Reutemann, and Ian H. Witten. “The WEKA data mining software: an update.” ACM SIGKDD Explorations Newsletter 11, no. 1 (2009): 10-18.
  • LUCS KDD Software Library. (2012) http://cgi.csc.liv.ac.uk/~frans/KDD/Software.
  • Frank and A. Asuncion, UCI machine learning repository: http:// archive.ics.uci.edu/ml.
  • Aczel and J. Daroczy, “On Measures of Information and Their Characterizations,” New York: Academic, 1975.
  • Mitchell, Tom M. “Machine learning and data mining.” Communications of the ACM 42, no. 11 (1999): 30-36.
  • Bishop, Christopher M. “Pattern recognition and machine learning (information science and statistics).” (2007).
  • Opitz and R. Maclin, “Popular ensemble methods: An empirical study,” Journal of Artificial Intelligence Research, vol. 11, 1999, pp. 169-198.
  • Bauer, Eric, and Ron Kohavi. “An empirical comparison of voting classification algorithms: Bagging, boosting, and variants.” Machine learning 36, no. 1-2 (1999): 105-139.
  • Demsar, “Statistical comparisons of classifiers over multiple data sets”, The Journal of Machine Learning Research, vol. 7, pp. 1-30, 2006.
  • L. Iman and J. M. Davenport, “Approximations of the critical region of the Friedman statistic”, Communications in statistics, vol. 9, no. 6, pp. 571-595, 1980.
  • J. Dunn, “Multiple comparisons among means”, Journal of the American Statistical Association, vol. 56, no. 293, pp. 52-64, 1961.
  • Agrawal, Rakesh, and Ramakrishnan Srikant. “Fast algorithms for mining association rules.” Proc. 20th int. conf. very large data bases, VLDB. Vol. 1215. 1994.
  • Quinlan, J. Ross, and R. Mike Cameron-Jones. “FOIL: A midterm report.” Machine Learning: ECML-93. Springer Berlin Heidelberg, 1993.

 

 

 

 

 


Abstract

Exploring Emerging Patterns with Streaming Features

By

………………

 

Mining a minimal set of strongly predictive emerging patterns from a high dimensional dataset is a challenging issue for making an accurate emerging pattern classifier. The problem becomes even more sever when features are not available as a whole; rather they show up over time. In this scheme, features are emerged one by one instead of having all features at hand before learning process gets started.

In this study, we propose a novel dynamic structure to construct the frequent pattern tree on arrival of new features and to mine emerging patterns online.

DFP-SEPSF, a Dynamic Frequent Pattern tree to mine Strong Emerging Patterns in Streamwise Features, offers an efficient bottom up approach to construct an Unordered Dynamic Frequent Pattern tree (UDFP-tree) and an Ordered Dynamic Frequent Pattern tree (ODFP-tree). The first one does not consider the item’s order whereas the second one applies item ordering.

Moreover, the proposed framework extracts Strong Emerging Patterns (SEPs) to build an accurate and fast classifier that can deal with noise.

The proposed framework reduces the pattern space of emerging pattern mining significantly and mines strong discriminating power of emerging patterns by removing useless candidate patterns.

The presented mining method discovers emerging patterns of each class simultaneously and conducts the generation process of the frequent pattern trees efficiently for saving computations.

Our experimental evaluations indicate the effectiveness of the proposed approach in comparison with other state-of-the-art methods, in terms of predictive accuracy, emerging pattern numbers, and running time.

Keywords. Emerging Patterns, Feature Streams, Dynamic Frequent Pattern Tree, Item Ordering.

 

 

 

 

 

 

 

 

 

 

 

[1] Classification

[2] Data mining

[3] Machine learning

[4] Neural networks

[5] Pattern recognition

[6] Training instances

[7] Features

[8] Nominal

[9] Numerical

[10] Classifier

[11] Model

[12] Class label

[13] Unknown

[14] Supervised learning

[15] Unsupervised learning

[16] Clustering

[17] Scientific experiments

[18] Medical diagnosis

[19] Weather prediction

[20] Credit approval

[21] Customer segmentation

[22] Target marketing

[23] Fraud detection

[24] Patterns

[25] Emerging patterns

[26] Datasets

[27] Frequency

[28] Growth rate

[29] Irrelevant patterns

[30] Redundant patterns

[31] Predictive accuracy

[32] Performance

[33] Support

[34] Gene expression data

[35] Image processing

[36] Intrusion detection

[37] Outlier detection

[38] Fraud detection

[39] Imbalanced datasets

[40] Data streams

[41] BioInformatics

[42] Recommender systems

[43] Intensity

[44] Streaming features

[45] Data Streams

[46] Statistical Relational Learning

[47] Feature interaction

[48] CPU time

[49] Irrelevant Features

دیدگاهها

هیچ دیدگاهی برای این محصول نوشته نشده است.

اولین نفری باشید که دیدگاهی را ارسال می کنید برای “جستجوی الگوهای نوظهور با ویژگی های جریانی”

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

6 + = 13