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

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

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

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

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

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

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

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

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

مفهوم ویژگی های جریانی

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

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

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

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

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

• چگونه مجموعه مفید و موثری از الگوهای نوظهور، بین داده های کلاس های مختلف استخراج شود؟