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

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

برای رعایت حریم خصوصی نام نگارنده پایان نامه درج نمی گردد

(در فایل دانلودی نام نویسنده موجود می باشد)

تکه هایی از متن پایان نامه به عنوان نمونه :

(ممکن می باشد هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود اما در فایل دانلودی همه چیز مرتب و کامل می باشد)

چکیده

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

در این مطالعه، ما ساختار دینامیک از درخت الگوی مکرر پیشنهاد می دهیم تا درخت به محض ورود ویژگی های جدید ساخته گردد و استخراج الگوهای نوظهور بصورت برخط صورت گیرد. 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 دانلود متن کامل در سایت sabzfile.com

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

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

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

 چالش­های موجود در استخراج الگوهای نوظهور

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

 در سیاق استخراج این الگوها سه مساله اساسی هست:

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

وقتی که ابعاد ویژگی ها بالا باشد، استخراج الگوهای نوظهور مشکل تر خواهد گردید؛ زیرا که ذخیره، بازیابی، هرس و مرتب کردن آنها برای کلاسه بند با تعداد کاندیداهای بسیار زیاد الگوها، سخت و یا غیرممکن خواهد گردید. با ظهور داده های حجیم و بزرگ که شامل صدها هزار ویژگی هستند مانند پردازش تصویر ، داده های ژنی و داده های متنی و … ، فضای جستجوی این الگوها نسبتاً بزرگ، هزینه بر و گاهی اوقات حتی غیرممکن می باشد [19].

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

از طرفی روش های یادگیری مرسوم [37، 38، 40] قادر هستند که بحث چند کلاسه[51] را از طریق روش های دو به دو مثل یکی پیش روی یکی[52] و یکی پیش روی همه[53] مدیریت کنند. بلاوه، بسیاری از روش های موجود استخراج الگوهای نوظهور مانند روش های مبتنی بر مرز[54] [1، 3، 13] و روش های مبتنی بر محدودیت[55] [2]، الگوهای مربوط به هر کلاس را در فرآیند جداگانه ای استخراج می کنند که این امر مطلوب نیست و منجر به تکرار محاسبات سنگین می گردد. پس بایستی بتوان روش استخراجی ارائه داد که این قابلیت را دارا باشد که تمامی الگوهای کلاس های مختلف را بصورت همزمان استخراج کند.

پس در این حوزه با موضوعات چالش برانگیزی بدین تبیین روبرو هستیم:

  1. چگونه بصورت موثر، مجموعه کوچکی از الگوهای نوظهور قوی را از داده های با ابعاد بالا استخراج کنیم؟
  2. چگونگی استخراج کردن الگوهای نوظهور وقتی که کل ویژگی ها قبل از فرآیند یادگیری در دسترس نیستند؟
  3. چگونگی ارائه مدل افزایشی و دینامیک در پاسخ به ویژگی های جریانی؟
  4. چگونگی استخراج الگوهای نوظهور از کلاس های مختلف بصورت همزمان؟

تعداد صفحه :138

قیمت : 14700 تومان

بلافاصله پس از پرداخت لینک دانلود فایل در اختیار شما قرار می گیرد

و در ضمن فایل خریداری شده به ایمیل شما ارسال می گردد.

پشتیبانی سایت :        ****       serderehi@gmail.com

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

***  *** ***