– (75)

Please enter banners and links.

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 الگوریتم AdaBoost66
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 به کلاس Edible38
جدول 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] یکی از وظایف اساسی در داده کاوی[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] استخراج می کنیم و سپس، بر اساس آنها، کلاسه بندی را انجام می دهیم.
مفهوم الگوهای نوظهور
مفهوم الگوهای نوظهور برای استخراج دانش از پایگاه داده ها توسط 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] مسئله خواهد بود، در صورتی که ابعاد ویژگی ها بالا باشد، در نتیجه شمار الگوهای نوظهور سیر صعودی خواهد داشت که شمار زیاد از این الگوها هم برای آنالیز داده ها بصورت برخط مشکل ساز است و هم این که روال یادگیری و کلاسه بند را زمانبر و هزینه بر می کند که مناسب نیست. لذا با بیان این مسائل بایستی بتوان مجموعه کوچک و در عین حال قوی از الگوهای نوظهور را تشکیل داد که این موضوع خود موضوعی چالش برانگیز است، و اینکه کدامیک از الگوهای جدید مفید و موثر هستند ؟
کدامیک از این الگوها برای هدف کلاسه بند مفید هستند؟ و چگونه این الگوها یک کلاسه بند مفید و موثر و در عین حال دقیق را می سازند؟
3. طریقه استفاده از این الگوها و یا همان مدل است که بتواند از الگوها بخوبی بهره گرفته و کلاسه بندی دقیقی را انجام دهد بطوری که دقت کلاسه بند بالا باشد.
وقتی که ابعاد ویژگی ها بالا باشد، استخراج الگوهای نوظهور مشکل تر خواهد شد؛ چرا که ذخیره، بازیابی، هرس و مرتب کردن آنها برای کلاسه بند با تعداد کاندیداهای بسیار زیاد الگوها، سخت و یا غیرممکن خواهد شد. با ظهور داده های حجیم و بزرگ که شامل صدها هزار ویژگی هستند مانند پردازش تصویر ، داده های ژنی و داده های متنی و … ، فضای جستجوی این الگوها نسبتاً بزرگ، هزینه بر و گاهی اوقات حتی غیرممکن است [19].
ایجاد یک مدل بر اساس الگوهای نوظهور با داده های با ابعاد بالا و نمونه های حجیم یک موضوع چالش برانگیز است. مشکل حتی سخت تر می شود اگر همه فضای ویژگی ها، قبل از عملیات یادگیری در دسترس نباشد و یا نامتناهی باشد [19].
از طرفی روش های یادگیری مرسوم [37، 38، 40] قادر هستند که بحث چند کلاسه[51] را از طریق روش های دو به دو مثل یکی در مقابل یکی[52] و یکی در مقابل همه[53] مدیریت کنند. بلاوه، بسیاری از روش های موجود استخراج الگوهای نوظهور مانند روش های مبتنی بر مرز[54] [1، 3، 13] و روش های مبتنی بر محدودیت[55] [2]، الگوهای مربوط به هر کلاس را در فرآیند جداگانه ای استخراج می کنند که این امر مطلوب نیست و منجر به تکرار محاسبات سنگین می شود. لذا بایستی بتوان روش استخراجی ارائه داد که این قابلیت را دارا باشد که تمامی الگوهای کلاس های مختلف را بصورت همزمان استخراج کند.
بنابراین در این حوزه با موضوعات چالش برانگیزی بدین شرح روبرو هستیم:
1. چگونه بصورت موثر، مجموعه کوچکی از الگوهای نوظهور قوی را از داده های با ابعاد بالا استخراج کنیم؟
2. چگونگی استخراج کردن الگوهای نوظهور وقتی که کل ویژگی ها قبل از فرآیند یادگیری در دسترس نیستند؟
3. چگونگی ارائه مدل افزایشی و دینامیک در پاسخ به ویژگی های جریانی؟
4. چگونگی استخراج الگوهای نوظهور از کلاس های مختلف بصورت همزمان؟
الگوریتمهای استخراج الگوهای نوظهور
زمانی که ابعاد داده ها بالا باشد، شمار الگوهای نوظهور بسیار زیاد و در واقع نمایی و گاهاً غیرممکن خواهد بود. لذا استخراج الگوهای نوظهور از داده ها، نیاز به روالی جداگانه دارد که در این راستا روش هایی ارائه شده است. روش هایی که تلاش می کنند الگوهایی با مشخصات بیان شده، استخراج کنند؛ بدین شرح هستند: روش مبتنی بر مرز[56]، روش مبتنی بر محدودیت[57]، الگوریتم های سریع برای استخراج الگوهای نوظهور[58]، روش دیاگرام تصمیم گیری دودویی مانع صفر[59].
این روش ها کمک بسزایی در کاهش تعداد الگوهای نوظهور می کنند بدون اینکه اثری بر قدرت تشخیص کلاسه بند داشته باشد.
1.استخراج الگوها بر اساس روش مبتنی بر مرز
برای روش های مبتنی بر مرز، سه الگوریتم؛ استخراج افقی[60] ، اختلاف مرز[61] ، تولید الگوهای نوظهور جهشی[62] وجود دارد. این روش ها با الهام از الگوریتم Max_Miner طراحی شده اند.
مرز، ساختاری است که مجموعه بزرگی از آیتم ها را بصورت مختصر نمایش می دهد. مرز برای نمایش الگوهای نوظهور کاندید بکار می رود. عملیات تفکیک مرز، برای استخراج الگوها استفاده می شود. مرز افقی از داده ها، نشان دهنده همه آیتم ها با فراوانی نسبی با آستانه خاصی، در داده ها است. الگوریتم استخراج افقی، مرز افقی هم برای داده های کلاس مثبت و هم برای داده های کلاس منفی ایجاد می کند. در واقع این الگوریتم، سعی می کند مرزی برای هر یک از کلاس ها بیابد. ایده اصلی این الگوریتم، استخراج مجموعه آیتم های با فراوانی نسبی ماکزیمال است [1، 3].
الگوهای نوظهور جهشی ، الگوهای نوظهوری هستند که در داده های یک کلاس، حضور ندارند، در نتیجه نسبت فراوانی نسبی داده های کلاس های دیگر به کلاسی که این مقدار داده در آن حضور ندارد، بی نهایت می شود. به الگوهای نوظهور با نرخ رشد بی نهایت، الگوی نوظهور جهشی گفته می شود. استخراج چنین الگوهایی، کمک بسزایی به کلاسه بند می کند. به این دلیل که تفاوت بین کلاس ها توسط این الگوها، بیش از پیش قابل لمس است. لذا در این راستا، روش هایی برای استخراج الگوهای نوظهور جهشی [3، 13] ارائه شده است.
2.استخراج الگوها بر اساس روش مبتنی بر محدودیت
این روش از دو نوع محدودیت برای هرس فضای جستجو استفاده می کند که محدودیت های داخلی و خارجی را شامل می شود [2].
محدودیت هایی است که کاربر اعمال می کند، محدودیت های خارجی روش مبتنی بر محدودیت استخراج الگوهای نوظهور را ایجاد می کند. این محدودیت ها شامل تعیین حداقل مقدار برای فراوانی نسبی، نرخ رشد و بهبود نرخ رشد می باشد. از آنجا که ممکن است بعضی از الگوها زیر مجموعه دیگر الگوها باشند، چنین الگوهایی، در حکم الگوهای تکراری هستند که کمکی به کلاسه بند نمی کنند. چنین الگوهای تکراری از مجموعه الگوها باید حذف شوند که البته شمار الگوها بدین ترتیب کاهش می یابد [2].
محدودیت هایی که به صورت انطباقی در روال استخراج، بر اساس مشخصات داده ها اعمال می شود، محدودیت داخلی را تشکیل می دهند. الگوریتم مبتنی بر محدودیت استخراج الگوهای نوظهور، می تواند بصورت موثر همه الگوها را که این محدودیت ها را ارضاء می کنند، استخراج کند. این روش از جستجوی اول عرض بر روی (SE-Tree) اعمال می کند و الگوهای مفید را استخراج می کند. برای بالا بردن کارایی این روش، الگوریتم هایی ارائه شده است که هر دو دسته محدودیت ها را در یک فاز اجرایی اعمال می کنند [2].
این الگوریتم بصورت مرحله ای انجام می شود که در هر مرحله، یکسری کاندید تولید می کند و سپس آنها را تست می کند. بدین ترتیب با اعمال محدودیت ها در هر مرحله و البته تغییر بعضی محدودیت ها در هر مرحله، الگوهای نوظهور را استخراج می کند.
همچنین این موضوع قابل بیان است که روش دیاگرام تصمیم گیری دودویی مانع صفر، در مقایسه با دیگر روش ها بیشتر در زمینه داده ها با ابعاد بالا کاربرد دارد و قویتر از دیگر روش های گفته شده در این زمینه عمل می کند.
ایدهی اصلی تحقیقبرای حل موضوعات چالش برانگیز مطرح شده، ما روش درخت الگوی مکرر دینامیک[63] جهت استخراج الگوهای نوظهور قوی در ویژگی های جریانی، DFP-SEPSF را پیشنهاد می دهیم. در این روش، درخت الگوی مکرر[64] مرسوم در پاسخ به ویژگی های جریانی ساخته می شود. ایده اصلی روش پیشنهادی بدین شرح هستند:
1. با چارچوب پیشنهادی، یک تکنیک جدید، درخت الگوی مکرر دینامیک، DFP-tree، در جواب ویژگی های جریانی ارائه شده است. ما دو روش از درخت الگوی مکرر دینامیک معرفی می کنیم: درخت الگوی مکرر دینامیک نامرتب[65]، UDFP-tree، و درخت الگوی مکرر دینامیک مرتب[66]، ODFP-tree. این روش ها درخت الگوی مکرر را بصورت افزایشی به محض ورود ویژگی های جدید بصورت پایین به بالا می سازند.
2. زیر مجموعه جدیدی از الگوهای نوظهور با نام الگوهای نوظهور قوی[67]، SEPs، ارائه می دهیم. این الگوها، الگوها با کیفیت بالا[68] هستند که محدودیت فراوانی دینامیک[69] را ارضا می کنند و بسیاری از نمونه های آموزشی را پوشش می دهند. کلاسه بند بر پایه SEPs بسیار بهتر از دیگر الگوریتم های شناخته شده عمل می کند. بعلاوه، روش استخراج الگوهای نوظهور[70]، SEP-Miner، بطور چشمگیری فضای جستجوی الگوها را کاهش می دهد و الگوهای نوظهور قوی را بصورت کارایی استخراج می کند.
3. DFP-SEPSF قادر است تا به محض ورود مقادیر ویژگی های جدید، آنها را در ساختار DFP-tree وارد نماید و الگوهای نوظهور قوی جدید مربوط به این مقادیر جدید وارد شده را استخراج کند. سپس روش پیشنهادی، این الگوها را به مجموعه الگوهای استخراج شده اضافه نماید.
2. روش استخراج، الگوهای نوظهور با قابلیت پیش بینی قوی را با حذف الگوهای بی ربط و تکراری از ساختاری استخراج می کند. روش استخراج، فضای جستجوی الگوها را بصورت قابل توجهی کاهش می دهد و فرآیند کشف الگوهای نوظهور را بصورت موثری با کمک تست آماری کای مربع[71] هدایت می کند.
3. برای اینکه استخراج الگوهای نوظهور بصورت کارایی انجام پذیرد، الگوهای نوظهور از هر کلاس در زمان یکسانی بصورت موازی استخراج می شوند. DFP-SEPSF قادر است تا فرآیند استخراج الگوها از کلاس های مختلف را بدون انجام محاسبات تکراری مدیریت کند.
4. این مطالعه کارایی الگوریتم پیشنهادی را بطور کامل بررسی می کند. آزمایشات گسترده ای بر روی داده های وسیعی که شامل 24 مجموعه داده از مجموعه داده های UCI [52] و 6 مجموعه داده با ابعاد بسیار بالا صورت گرفته است. در این آزمایشات، روش پیشنهادی با دیگر روش های شناخته شده در رابطه با دقت کلاسه بندی، شمار الگوها، و زمان یادگیری مقایسه شده اند.
5. حداقل آستانه فراوانی نسبی در طول فرآیند استخراج بر اساس طول الگوهای کاندید برای هر مجموعه داده بصورت جداگانه تنظیم می شود تا کارایی DFP-SEPSF به نرخ آستانه خاصی وابستگی نداشته باشد. بعلاوه، تحلیل حساسیت آزمایشات بر روی آستانه های مختلف نرخ رشد نشان می دهد که کارایی روش پیشنهادی به نرخ رشد خاصی وابسته نیست.
در فرآیند ساخت درخت الگوی مکرر دینامیک، تعدادی محدودیت مانند حداقل آستانه فراوانی نسبی، الگوی نوظهور کمینه، و الگوی نوظهور بی ربط اعمال می شود تا فضای جستجوی الگوهای نوظهور به محض ورود ویژگی جدید هرس شود. اگر یک مقدار ویژگی محدودیت های ذکر شده را ارضا نکند، در ساختار درخت قرار داده می شود. درخت الگوی مکرر با دریافت یکی به یک ویژگی ها بتدریج ساخته می شود. برای ساخت درخت الگوی مکرر مرتب، موقعیت گره ها در درخت تغییر داده می شود تا درخت بازسازی شود. بعد از پردازش همه ویژگی ها، روش استخراج الگوها، SEP-Miner، الگوهای نوظهور با قابلیت پیش بینی قوی را از درخت الگوی مکرر استخراج می کند. روش پیشنهادی ما، در دو مرحله قابل اجرا است، اول،پایگاه داده شرطی[72] با کمک اعمال محدودیت هایی هرس می شود، دوم، پایگاه داده شرطی کاهش یافته به چندین پایگاه داده کوچکتر با کمک تست کای مربع[73]، تجزیه می شود. سپس به ازای هر زیر پایگاه داده شرطی[74] یک درخت الگوی مکرر شرطی[75] ایجاد می شود. این فرآیند مکرر اجرا می شود تا ضابطه توقف ارضا شود.
نگاهی کلی به فصول رسالهاین رساله به شش فصل تقسیم شده است. در فصل دوم، به بررسی روشها و الگوریتمهای مرسوم در استخراج الگوهای نوظهور و کلاسه بندی آنها می پردازد. در فصل سوم، دانش اولیه درباره الگوهای نوظهور و درخت های الگوی مکرر در قالب تعاریف بیان می شود. در فصل چهارم، جزئیات روشهای پیشنهادی به تفصیل ارائه میشوند. در فصل پنجم، کلاسهبندها، معیارهای ارزیابی عملکرد، مجموعه دادههای مورد آزمایش و همچنین تست آماری مورد استفاده برای مقایسه نتایج الگوریتمهای پیشنهادی با سایر روشها به تفصیل توضیح داده میشوند. در فصل ششم، نتایج حاصل از بررسی و مقایسه الگوریتمهای پیشنهادی و پاسخ سؤال‌های مطرح‌شده در فصل قبل، گردآوری‌شده است. همچنین در فصل آخر نتیجهگیری و کارهای آینده این رساله آمده است.
فصل دومپیشینهی تحقیق
پیشینهی تحقیقمقدمهدر این فصل در ابتدا به روش هایی که از الگوهای مکرر[76] در راستای کلاسه بندی بهره می گیرند، می پردازیم و سپس روش های استخراج الگوهای نوظهور و کلاسه بندهای مرتبط با این الگوها بازنگری می کنیم.
روش های مبتنی بر قانون[77]
هدف از کلاسه بندی قوانین استخراجی، استخراج کردن مجموعه کوچکی از قوانین است تا یک کلاسه بند دقیق ساخته شود. الگوریتم های استخراج قانون مانند Apriori [61] و FPgrowth [15، 16] بکار گرفته می شوند تا مجموعه کاملی از الگوها استخراج شوند. سپس مجموعه کوچکی از قوانین با کیفیت بالا انتخاب می شوند که برای کلاسه بندی بکار می روند. الگوریتم های شناخته شده برای کلاسه بند های انجمنی[78] شامل CBA، CMAR و CPAR می شوند که جزئیات این الگوریتم ها در ادامه بیان خواهند شد.
روش Classification Based on Association (CBA) [27]
روش CBA در دو فاز اجرا می شود: تولید کننده قانون[79] و سازنده کلاسه بند[80]. تولید کننده قانون، الگوریتم Appriori را بکار می گیرد تا همه قوانینی با حداقل آستانه[81] فراوانی نسبی[82] و درجه اطمینان[83] را استخراج کند. برای کلاسه بندی کردن یک نمونه تست، سازنده کلاسه بند، قوانین را بر اساس مقادیر فراوانی نسبی و درجه اطمینانشان مرتب می کند. سپس، سازنده کلاس، اولین قانون را بعنوان بهترین قانون انتخاب می کند تا بر چسب کلاس را به نمونه تست اختصاص دهد. بدلیل اینکه CBA کلاسه بندی را بر اساس فقط یک قانون برای یک نمونه تست انجام می دهد، ممکن است باعث بروز مشکل بیش یادگیر[84] شود.
روش کلاسه بندی Classification based on Multiple-class Association Rule (CMAR) [28]
با توجه به اینکه CBA فقط بر اساس یک قانون با درجه اطمینان و فراوانی بالا کلاسه بندی را انجام می دهد، مشکل بیش یادگیری صورت می گیرد و لذا دقت کلاسه بند برای نمونه های تست کم خواهد شد. برای حل این مشکل، CMAR کلاسه بندی را بر اساس چندین قانون انجام می دهد. CMAR، درخت الگوی مکرر[85] را توسعه می دهد بطوری که بتواند الگوهای مکرر[86] را بصورت کارایی استخراج کند. CMAR چندین قانون را با استفاده از وزن دهی بر اساس χ برای کلاسه بندی بکار می گیرد.
روش کلاسه بندیClassification based on Predictive Association Rule (CPAR) [29]
CPAR با الهام از الگوریتم FOIL [62] قوانین را تولید می کند. CPAR، مجموعه بسیار کوچکی از قوانین با قابلیت پیش بینی را با استفاده از الگوریتم حریصانه بطور مستقیم از مجموعه آموزشی استخراج می کند. برای جلوگیری از بیش یادگیری، CPAR بهترین k قانون را جهت کلاسه بندی کردن نمونه تست بکار می گیرد. CPAR در مقایسه با دیگر الگوریتم های استخراج قوانین دارای مزایایی بدین شرح است: 1) مجوعه خیلی کوچکتری از قوانین با کیفیت بالا بطور مستقیم از نمونه های آموزشی[87] استخراج می کند. 2) برای پرهیز از تولید قوانین تکراری، CPAR هر قانون را با توجه به مجموعه قوانینی که از قبل استخراج کرده است، تولید می کند. 3) برای کلاسه بندی، بهترین k قانون بکار گرفته می شود.
روشهای استخراج الگوها
در مقایسه با قوانین انجمنی، الگوهای نوظهور قادر هستند که تمایلات نوظهور[88] در مجموعه داده های با محدودیت زمانی[89] را استخراج کنند و یا تمایزات مفید بین کلاس های مختلف را کشف نمایند [1]. مطالعه و پژوهش در رابطه با الگوهای نوظهور اساسا به دو دسته قابل تقسیم است؛ الگوریتم های استخراج الگوهای نوظهور و الگوریتم های کلاسه بندی بر پایه این الگوها. ما در ابتدا الگوریتم های مرتبط با استخراج الگوهای نوظهور را شرح می دهیم و سپس الگوریتم های مشهور کلاسه بندی را ارائه می دهیم.
روش مبتنی بر مرز[90]
روش های مبتنی بر مرز با الهام از الگوریتم Max-miner [14] پیشنهاد شده اند. این روش ها، مفهوم مرز[91] [1] را بکار می گیرد تا ساختار مناسبی را برای نمایش مختصری برای الگوهای کاندید ارائه دهند. در هر مرز، کوچکترین و بزرگترین عضو هر مجموعه کاندید قابل نمایش است. الگوریتم اختلاف مرز[92]، الگوهای نوظهور کمینه و بیشینه[93] را استخراج می کند و بدین ترتیب مرز الگوهای استخراجی را تنظیم می کند. الگوریتم های مبتنی بر مرز قادر نیستند که الگوهای نوظهور را بصورت همزمان از کلاس های مختلف استخراج کنند. این الگوریتم ها، برای هر کلاس طی فرآیند جداگانه ای الگوها را استخراج می کنند و لذا به ازای هر کلاس، جداگانه اجرا می شود.
روش مبتنی بر محدودیت (ConsEPMiner[94]) [2]
الگوریتم مبتنی بر محدودیت در دو سطح اجرا می شود؛ تولید الگوهای کاندید و هرس الگوهای اکتشافی. الگوریتم ConsEPMiner از دو نوع محدودیت استفاده می کند تا بتواند بطور موثری فضای جستجو الگوهای نوظهور را هرس کند و محاسبات را ذخیره نماید. محدودیت های ذاتی[95] و خارجی[96] عنوان محدودیت هایی است که در فرآیند استخراج اعمال می شود. محدودیت های خارجی شامل محدودیت حداقل آستانه فراوانی نسبی، نرخ رشد و پیشرفت نرخ رشد[97] است که توسط کاربر قابل تنظیم است. محدودیت ذاتی شامل مجوعه یکسانی از فراوانی نسبی[98]، نرخ رشد بالا[99] و مبدا یکسان[100] است.
الگوریتم استخراج درخت الگوی تقابل[101] (CP-Tree) [17، 25]
الگوریتم استخراج الگوهای متمایز، با الهام از FP-tree، ساختار گسترش یافته ای ساختار درختی پیشوندی ارائه می دهد. این ساختار به خلاف الگوریتم درخت الگوی مکرر، نیازی به پیوند بین نودها ندارد. الگوریتم توسط جستجوی اول عمقی[102]، CP-tree را از ریشه پیمایش می کند تا الگوهای نوظهور جهشی قوی[103] را استخراج کند. الگوی نوظهور جهشی قوی، یک نوع خاص از الگوهای نوظهور جهشی[104] است که بایستی دارای حداقل فراونی نسبی باشد. این نوع درخت، کارایی استخراج الگوهای نوظهور را با استفاده از الگوهای نوظهور جهشی قوی بهبود می بخشد و همچنین قادر است که مجموعه داده های چند کلاسه را مدیریت نماید.
روش استخراج با کمک دیاگرام دودیی صفر[105] ZBDD Miner [18]
از آنجایی اینکه روش های ذکر شده، قادر نیستند که داده ها با ابعاد بیشتر از شصت را مدیریت کنند، بعداً، ZBDD EP-Miner شد. این روش از Zero-Suppressed Binary Decision Diagrams (ZBDDs) استفاده می کند تا الگوهای نوظهور را از داده ها با ابعاد بالا استخراج کند. با این وجود، ZBDD EP-miner هنوز شمار زیادی از الگوهای نوظهور را استخراج می کند حتی با اعمال محدودیت های آلفا و بتا [18].
این محدودیت ها استفاده می شوند تا فضای جستجوی الگوهای نوظهور را بیشتر هرس کند. محدودیت آلفا بر اساس مفهوم a-priori است. در نمونه های مثبت[106]، هر آیتم که فراوانی نسبی اش[107] کمتر از مقدار آلفا باشد، هم از نمونه های مثبت و هم از نمونه های منفی حذف می شود. محدودیت بتا بیشترین مقدار فراوانی[108] برای یک الگوریتم در نمونه های منفی مشخص می کند؛ اگر فراوانی الگوی کاندید بیشتر از بتا باشد، آن الگو از نمونه های آموزشی حذف می شود.
روش استخراج الگوی نوظهور متمایز [109]DP Miner
بر اساس مفهوم مجموعه آیتم بسته[110]، یک کلاس هم ارزی[111] مجموعه ای از آیتم های مکرر[112] است که همیشه در نمونه های یکسانی از نمونه های آموزشی اتفاق می افتند. مشابه با مفهوم مرز در الگوریتم های مبتنی بر مرز، یک کلاس هم ارزی بوسیله الگوهای بسته[113] و تولیدکننده ها[114] تعیین می شود. الگوهای بسته، همان مجموعه آیتم های ماکزیمال هستند و تولیدکننده ها، همان مجموعه آیتم های کمینه در یک کلاس هم ارزی هستند که همه این آیتم ها دارای فراوانی یکسانی هستند. الگوریتم DPMiner، Discriminative Pattern Miner، الگوهای بسته و تولیدکننده ها را که برای نمایش یک کلاس هم ارزی کافی هستند، بصورت همزمان استخراج می کند. بعلاوه، قادر است که الگوهای با قدرت تمایز دلتا[115] را استخراج کند. الگوهای نوظهور با قدرت تمایز دلتا دارای حداکثر فراوانی در کلاس های مقابل است. با توجه به اینکه الگوریتم های ZBDD EP-miner و DPMiner، محدودیت های آلفا و بتا را بکار می گیرند تا فضای جستجوی الگوها را کاهش دهند؛ ممکن است بعضی از الگوهای نوظهور مفید در نظر گرفته نشوند و تاثیر نامطلوبی در کلاسه بندی داشته باشد.

روش های کلاسه بندی مبتنی بر الگوهای نوظهور
روش کلاسه بندی بر اساس مجموع الگوهای نوظهور CAEP[116][21]
از آنجایی که الگوهای نوظهور، دانش تمایز بین کلاس های مختلف را نشان می دهد، آنها در ایجاد کلاسه بندی دقیق بسیار موثر هستند. کلاسه بند های بر پایه الگوهای نوظهور قدرت مجموع الگوهای نوظهور را برای کلاسه بندی یک نمونه تست بکار می گیرد. Dong [21] اولین کلاسه بند بر پایه الگوهای نوظهور را ارائه داد که CAEP، Classification by Aggregating Emerging Patterns، نامیده شد. CAEP همه الگوهای نوظهور قوی را بوسیله الگوریتم های مبتنی بر مرز استخراج می کند. برای کلاسه بندی کردن یک نمونه تست، برای هر کلاس یک امتیاز[117] محاسبه می شود. کلاس با بالاترین امتیاز بعنوان برچسب نمونه تست در نظر گرفته می شود. اگر تعداد الگوهای کاندید کلاس های مختلف نامتوازن[118] باشد، کلاس با الگوهای بیشتر تمایل در بدست آوردن امتیاز بیشتر دارد. برای حل این مشکل، یک امتیاز پایه[119] برای هر کلاس از نمونه های آموزشی بدست می آید [21].
الگوریتم کلاسه بندی بر پایه تئوری اطلاعات[120] iCAEP
بعداً، Zhang et al. [26]، یک نوع از CAEP را که iCAEP، Information based Classification by Aggregating Emerging Patterns، نامیده شد، معرفی کرد. iCAEP، از تئوری اطلاعات[121] استفاده می کند تا نیازی به محاسبه base score برای هر کلاس نباشد.
برای کلاسه بندی یک نمونه تست، کوچکترین امتیاز بعنوان برچسب کلاس نمونه تست در نظر گرفته می شود. در مقایسه با CAEP، iCAEP دقت را بهبود می دهد و زمان را برای کلاسه بندی کاهش می دهد.
روش کلاسه بندی برپایه الگوهای نوظهور جهشیJEPs-Classifier [3]
بر اساس CAEP، الگوریتم کلاسه بند بر پایه الگوهای نوظهور جهشی توسط Li et al. ارائه شد. JEPs-classifier محنصراً از الگوهای نوظهور جهشی[122] با فراوانی نسبی بالا برای کلاسه بندی استفاده می کند. این نوع الگوها، رساترین الگوهای نوظهور جهشی[123] نامیده می شوند چرا که این الگوها همان محموعه آیتم های کمینه در مرز[124] هستند که دارای فراوان نسبی بالایی نسبت به دیگر آیتم ها در مرز هستند. JEPs-classifier از الگوریتم های مبتنی بر مرز بهره گرفته و الگوهای نوظهور جهشی را در قالب مرز فضای الگوها استخراج می کند. رساترین الگوهای نوظهور جهشی لزوما حداقل آستانه برای فراوانی نسبی ارضا نمی کند.
روش کلاسه بندی بر پایه الگوهای نوظهور جهشی قوی[125] [25]
این کلاسه بندی بر پایه قدرت مجموع الگوهای نوظهور جهشی قوی است و تلاش می کند تا با استفاده از الگوهای نوظهوری جهشی که حداقل آستانه را برای فراوانی نسبی دارا هستند، به دقت قابل توجهی دست یابد.
روش تصمیم گیری مبتنی بر نمونه[126] DeEPs [20]
بعداً، بر پایه روش های مبتنی بر نمونه[127]، کلاسه بند تنبل[128] به نام DeEPs، Decision-making by Emerging Patterns، ارائه شد [20]. جهت کاهش فضای جستجو الگوها، DeEPs یک نمونه تست را بعنوان یک فیلتر بکار می گیرد تا مقادیر آموزشی بی ربط را در نظر نگیرد. برای هر نمونه تست، DeEPs الگوهای نوظهور کاندید را استخراج می کند و مقادیر ویژگی هایی که در نمونه تست دیده نشده اند را نادیده می گیرد. این تکنیک، کارایی و دقت کلاسه بندی هایی مثل کلاسه بندی بر پایه مجموع الگوهای نوظهور CAEP و کلاسه بندی بر پایه الگوهای نوظهور جهشی JEP-classifier را بهبود می بخشد. اما، این روش منجر به تکرار محاسبات سنگین می شود بخصوص وقتی که نمونه های تست مشابه باشند.
روش پیش بینی توسط مجموعه راست نمایی (PCL[129]) [5]
PCL پیش بینی را توسط مجموعه ای از درست نمایی ها[130] انجام می دهد. PCL از K بالاترین الگوهای نوظهور که در نمونه تست شامل می شوند، برای کلاسه بندی استفاده می کند. برای هر کلاس، PCL یک امتیاز با استفاده از اجتماع درست نمایی حاصل از K بالاترین الگوهای نوظهور که نمونه تست را پوشش می دهند، بدست می آورد. PCL برای مجموعه داده ها با ابعاد بالا مناسب است بخصوص برای داده های بیان ژن.
بدلیل محدودیت های روش های استخراج الگوهای نوظهور، روش های سابق قادر نیستند تا مجموعه داده ها با ابعاد بالا را مدیریت کنند. روش پیشنهادی ما، DFP-SEPSF، فضای جستجوی الگوهای نوظهور را با استفاده از فرایند هرس در روال ساخت درخت الگوی مکرر دینامیک و استخراج الگوها، بطور قابل توجهی کاهش می دهد. همچنین روش پیشنهادی، الگوهای نوظهور هر کلاس را در زمان یکسانی و بطور موازی از کلاس ها استخراج می کند.
فصل سوم
دانش اولیه

دانش اولیه
الگوهای نوظهور
فرض کنید مجموعه داده D دارای N ویژگی (F1,F2, . . . ,FN) و برچسب کلاس C است. هر کدام از ویژگی ها در صورتی که ویژگی پیوسته باشد در فواصلی مجزا می شوند.I را بعنوان مجموعه ای از همه آیتم ها تعریف می کنیم. یک مجموعه آیتم[131] X یک زیر مجموعه از I است که مقدار فراوانی نسبی[132] آن

که |X| تعداد نمونه های شامل X را بیان می کند و |D| تعداد کل نمونه های را در مجموعه داده D را بیان می کند. مجموعه برچسب کلاس C شامل M برچسب کلاس مختلف است؛ C = {C1, C2, . . ., CM}. مجموعه داده D در M مجموعه داده D1, D2, . . ., DM تجزیه می شود که هر مجموعه داده Dk شامل نمونه ها با برچسب کلاس Ck است. به طور خاص، مجموعه داده D به دو مجموعه داده مثبت Dp و مجموعه داده منفی Dn قابل تقسیم است. Dp شامل نمونه مثبت و Dn شامل نمونه های منفی می شود. نرخ رشد[133] (GR) مجموعه آیتم X از مجموعه داده Ds به مجموعه داده Dt ( s,t =1, . . . , M) در ادامه شرح داده خواهد شد.
تعریف 1: (نرخ رشد GR) نرخ رشد یک مجموعه آیتم X از Ds به Dt،

تعریف 2: (الگوی نوظهور EP [1]) حداقل آستانه نرخ رشد داده شده است. مجموعه آیتم X گفته می شود الگوی نوظهور است اگر

تعریف 3: ( الگوی نوظهور جهشی JEP [1]) اگر ، مجموعه آیتم X الگوی نوظهور جهشی از مجموعه داده از Ds به Dt نامیده می شود.
برای اینکه تفاوت الگوهای مکرر و الگوهای نوظهور مشخص شود، در ادامه تعریف الگوهای نوظهور را بر اساس confidence ارائه می دهیم. اطمینان[134]، تخمین ماکزیمم درست نمایی مربوط به احتمال شرطی است:

کلاسه بند مبتنی بر الگوهای مکرر، استخراج قوانین انجمنی و کلاسه بندی را با یکدیگر ترکیب می کند. در این راستا، نتیجه[135] قانون انجمنی برچسب کلاس در نظر گرفته می شود و کلاسه بند بر اساس چنین الگوهای ساخته می شود. در شکل زیر
100012516446500-6457951137285شکل 3-1. یک مثال از الگوهای مکرر استخراج شده از مجموعه داده Balloon
00شکل 3-1. یک مثال از الگوهای مکرر استخراج شده از مجموعه داده Balloon

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

در صورتی که الگویی معیار اطمینان برابر یک به ازای یک کلاس به خود اختصاص دهد، این الگو، الگوی نوظهور جهشی را نشان می دهد.
تعریف 4: ( الگوی نوظهور قوی SEP) حداقل نرخ رشد و تعداد میانگین مقادیر برای یک آیتم K داده شده است. الگوهای نوظهور قوی از مجموعه داده Ds به Dt، مجموعه آیتم X با n آیتم است که شرایط ذیل را ارضا می کند:

که شرط 1 تعریف محدودیت فراوانی دینامیک[136] است.
در الگوهای نوظهور قوی، ما محدودیت فراوانی دینامیک را بر اساس طول الگو و تعداد میانگین مقادیر K تنظیم می کنیم. ایده پشت آن اینست که الگوهای نوظهور قوی تمایل دارند تا همه ترکیبات ممکن از آیتم ها را برای یک الگو خاص در نمونه های آموزشی را پوشش دهند، از این رو، حداقل فراوانی الگو بایستی باشد. برای مثال، فرض کنید ما یک الگوی نوظهور با دو آیتم، تعداد میانگین مقادیر 3، و 20 نمونه آموزشی داریم. بنابراین، حداقل فراوانی الگو است و حداقل آستانه فراوانی نسبی است.
بعلاوه، طول الگوهای نوظهور بوسیله محدودیت فراوانی محدود می شود. طول الگو حداکثر است. فرآیند استخراج الگوهای نوظهور SEPs با طول بزرگتر از استخراج نمی کند.
کلاسه بندی بر پایه الگوهای کوتاهتر با آیتم های کمتر مطلوب است بدلیل اینکه با ویژگی های بیشتر معمولا در کلاسه بندی مشارکت نمی کنند و حتی، برای کلاسه بندی مضر است. از آنجایی که SEPs الگوهای کوتاهتر و با فراوانی بالا را نشان می دهند، برای کلاسه بندی بسیار مفید هستند.
تعریف 5: (بهبود نرخ رشد[137] Rateimp [2]) فرض کنید الگوی نوظهور e داده شده است، بهبود نرخ رشد e، Rateimp(e)، بعنوان کمترین اختلاف بین نرخ رشد e و نرخ رشد همه زیر مجموعه هایش توصیف می گردد.

برای استخراج موثر الگوهای نوظهور، Rateimp(e) فضای جستجو الگوها را هرس می کند و محاسبات اضافی را کاهش می دهد. یک آستانه مثبت از بهبود نرخ رشد،R، مجموعه مختصری از الگوها را که توسط دیگر الگوهای استخراجی قابل دستیابی نیستند، ارائه می دهد. بعلاوه، بهبود نرخ رشد می تواند در استخراج الگوهای قوی کمک کند. بنابراین، بهبود نرخ رشد ارتباط و وابستگی بین الگوهای نوظهور را نشان می دهد و الگوهای تکراری را کاهش می دهد.
یک مثال مصور در جدول 3-1 با استفاده از مجموعه داده mushroom از مجموعه داده های جمع آوری شده در UCI [52] ارائه شده است. حداقل آستانه فراوانی 0.05 و حداقل آستانه نرخ رشد است. الگوهای کاندید از دو کلاس Edible و Poisonous با 8124 نمونه و 22 ویژگی استخراج شده اند.
بر اساس تعریف 2، در جدول 3-1، آیتم های {odor = almond}، {stalk-color = white}، {odor = almond, stalk-color = white} الگوهای نوظهور از کلاس Edible هستند. بعلاوه، {odor = almond} و همچنین {odor = almond, stalk-color = white} الگوهای نوظهور جهشی هستند. بر اساس تعریف 3، آیتم ، {odor = almond} یک الگوی نوظهور است اما {odor = almond, stalk-color = white} یک الگوی نوظهور تکراری[138] است. در حقیقت، همه سوپرست های آیتم با نرخ رشد بینهایت، الگوی نوظهور جهشی هستند. واضح است که بهبود نرخ رشد صفر است.
فراوانی نسبی
(کلاس Poisonous) فراوانی نسبی
(کلاس Edible) الگوهای نوظهور کاندید
0.0951 0 {odor = almond}
1.4959 0.6540 0.4372 {stalk-color = white}
0.0951 0 {odor = almond, stalk-color = white }
جدول 3-1. الگوهای نوظهور کاندید از کلاس Poisonous به کلاس Edible
در کلاسه بندی بر پایه الگوهای نوظهور، همه الگوهای هر کلاس Ci، کلاس iام، از نمونه های آموزشی استخراج می شوند و برای تصمیم گیری در مورد برچسب کلاس نمونه های تست بکار گرفته می شوند. برای کلاسه بندی کردن یک نمونه تست t، M امتیاز محاسبه می شود، بطوری که برای هر کلاس یک امتیاز محاسبه می شود. کلاس با بالاترین امتیاز بعنوان برچسب کلاس برای t در نظر گرفته می شود، label(t) = argmaxci score (t, Ci). تعریفی که در ادامه آمده است، امتیاز مجموع[139] را بعنوان تابع امتیازدهی[140] ارائه می دهد.
تعریف 6: (جمع آوری امتیاز[141] [21]) نمونه تست t و مجموعه الگوهای نوظهور Ei که از کلاس Ci از نمونه های آموزشی استخراج شده اند، داده شده اند. مجموع امتیاز برای t به ازای کلاس Ci بدین شرح تعریف می شود:

بدلیل اینکه تعداد الگوهای نوظهور از کلاس های مختلف ممکن است نامتوازن باشد، نمونه تست t ممکن امتیاز بالاتری برای کلاس Ci با الگوهای بیشتر از دیگر کلاس Cj بدست آورد، حتی اگر برچسب کلاس t کلاس Cj باشد. بنابراین، تابع امتیاز که توسط تعریف 4 معرفی شده است، بایستی جهت کلاسه بندی نمونه تست t تغییر داده شود.
مفهوم امتیاز پایه[142] [21] می تواند کمک کند تا این مشکل حل شود. امتیاز پایه، baseScore(Ci)، از نمونه های آموزشی هر کلاس بدست می آید. با امتیاز پایه، امتیاز جدید یک نمونه تست t برای کلاس Ci که امتیاز نُرم شده، normScore(t, Ci)، نامیده می شود، بصورت نسبت امتیاز Score(t, Ci) و امتیاز پایه baseScore(Ci) تعریف می شود،

کلاس با بیشترین امتیاز نُرم شده بعنوان برچسب کلاس نمونه تست t در نظر گرفته می شود و در صورتی که امتیازات بدست آمده از کلاس های مختلف برابر شد، کلاس با بزرگترین نمونه بعنوان برچسب کلاس در نظر گرفته می شود. یک راه برای مشخص کردن امتیاز پایه این است که میانه امتیازات بدست آمده از نمونه های آموزشی کلاس Ci در نظر گرفته شود. برای مثال، فرض کنید 5 نمونه آموزشی از هر کدام از کلاس های مثبت (+) و منفی (-) وجود دارد. با همه EPs موجود از هر کلاس، فرض کنید که امتیازات حاصل از نمونه های مثبت[143] که بوسیله تعریف 4 محاسبه شده اند 17.85، 18.61، 18.76، 19.75، 20.24 هستند و امتیازات حاصل از نمونه های آموزشی منفی 7.80، 7.87، 8.20، 8.57، 8.61 هستند. در صورتی که امتیازات پایه را میانه امتیازات محاسبه شده به ازای هر کلاس در نظر بگیریم، در نتیجه، امتیاز پایه برای کلاس های مثبت و منفی به ترتیب 18.76 و 8.20 می شود. به ازای یک نمونه تست t ( می دانیم که از کلاس منفی است) با امتیازات 10.17 و 7.92 به ترتیب برای کلاس های مثبت ومنفی داده شده است؛ در صورتی که امتیاز پایه اعمال نشود، کلاس مثبت بعنوان برچسب نمونه t در نظر گرفته می شود. در حالیکه با اعمال امتیازات پایه، normScore(t, +) = 10.17/18.76 =0.54 و normScore(t,-)= 7.92/8.2 = 0.97 . بنابراین کلاس منفی بعنوان برچسب نمونه t در نظر گرفته می شود.
بعداً، Zhang et al. [26] یک تابع امتیاز ساده تر بر اساس تئوری اطلاعات[144] ارائه دادند که از محاسبه امتیاز پایه برای هر کلاس اجتناب می کند. تابع امتیاز نمونه تست t بوسیله معادله های 1 و 2 قابل محاسبه است.
فرمول 3-1 برچسب کلاس Ci به نمونه تست t اختصاص داده می شود در صورتی که L(t||Ci) کمترین مقدار به ازای کلاس Ci داشته باشد. به ازای مجموعه آیتم X، P(X|Ci) تقریبا با معادله 2 محاسبه می شود،
فرمول 3-2
در این معادله، تعداد نمونه هایی متعلق به کلاس Ci و دارای مجموعه آیتم X ، |X| تعداد کل نمونه های آموزشی شامل X ، |D| تعداد کل نمونه های آموزشی، و |Ci| تعداد نمونه های آموزشی متعلق به کلاس Ci را نشان می دهند. بعلاوه، برای اطمینان از اینکه حداقل یک EP برای کلاسه بندی نمونه تست t یافت می شود، ما همه آیتم های تکی را جدای از آن که حداقل آستانه ها را ارضا می کنند یا خیر برای کلاسه بندی نمونه تست t در نظر می گیریم.
درخت الگوی مکرر دینامیک[145] (DFP-tree)
درخت الگوی مکرر گسترش یافته ساختارهای مبتنی بر درخت های پیشوندی[146] است [15، 16]. درخت الگوی مکرر نمایش فشرده ای از داده است که اطلاعات کاملی از داده های اصلی را در خود ذخیره می کند. در FP-tree، هر مسیر مجموعه آیتم هایی را که دارای پیشوند یکسانی هستند را نشان می دهد و هر گره[147] یک آیتم و فراوانی آن را نشان می دهد. بعلاوه، همه گره هایی که آیتم یکسانی را شامل می شوند از طریق پیوند-گره[148] به هم متصل شده اند. از طریق پیوند-گره همه نمونه هایی که دارای آیتم مشابهی هستند به آسانی قابل دستیابی و شمارش هستند. راس[149] همه پیوند-گره ها برای هر آیتم در یک جدول هدر[150] ذخیره می شوند. بعلاوه، آیتم ها در جهت کاهش فراوانی شان در داده ها مرتب می شوند و در ساختار درخت ذخیره می شوند. اگر چه FP-tree به نظم خاصی وابسته نیست ولی در حالتی که مرتب شده باشد سرعت اجرای عملیات استخراج بسیار بیشتر از حالتی است که درخت نامنظم باشد. برای نمایش الگوهای نوظهور، ما ساختار FP-tree را تغییر می دهیم همانطوری که در تعریف ادامه آمده است.
تعریف 7: (درخت الگوی مکرر دینامیک DFP-tree [15]) یک درخت الگوی مکرر دارای یک ریشه تهی[151]، مجموعه ای از زیر درخت های پیشوندی بعنوان بچه های ریشه، و یک جدول هدر توصیف شده در زیر است.
هر گره در زیردرخت دارای چهار فیلد: مشخصه ID، مقدار یا آیتم value or i–، توزیع کلاس class distribution، و پیوند-گره node-link است. ID، یک گره را از مابقی گره ها متمایز می کند، value، نشاندهنده آن است که کدام مقدار ویژگی در گره جاری ذخیره شده است، class distribution، فراوانی آیتم را به ازای هر کلاس که توسط قسمتی از شاخه ای که به گره می رسد، ثبت می کند، و node-link، گره جاری را به گره بعدی که دارای آیتم مشابهی است متصل می کند و اگر گره ای وجود ندارد null می باشد. بعلاوه، تعدادی از گره ها را بعنوان گره های خارجی[152] تعریف می شوند. دو نوع از گره ها بعنوان گره های خارجی تعریف می شوند : (1) گره های برگ[153] (2) گره های پدری[154] که مقدار فراوانی شان بزرگتر از جمع فراوانی همه گره های فرزندانشان[155] باشد.
هر ورودی در جدول هدر شامل چهار فیلد است: آیتم i–، فراوانی کل total frequency، توزیع کلاس class distribution، هد پیوند-گره head of node-link است. در این مطالعه، آیتم، مقدار ویژگی را ثبت می کند، فراوانی کل، فراوانی آیتم و مقدار ویژگی را در داده ثبت می کند، توزیع کلاس، مقدار فراوانی آیتم یا مقدار ویژگی در هر کلاس را ثبت می کند، و هد پیوند-گره یک اشاره گر اشاره کننده به اولین گره حامل آیتم است.

شکل 3-2. یک مثال از درخت الگوی مکرر: هر گره دارای یک ID، یک آیتم، توزیع کلاس آیتم که نشاندهنده قسمتی از مسیر منتهی به گره است، و پیوند-گره. هر ورودی در جدول هدر دارای یک آیتم، فراوانی کل، توزیع کلاس، و هد پیوند-گره. همه گره ها به رنگ قرمز نشان داده شده اند.
مثال 1. یک مثال از درخت الگوی مکرر در شکل 3-1 نشان داده شده است. درخت دارای یک ریشه تهی و 8 گره است.هر گره دارای یک ID، یک آیتم، فراوانی آیتم در هر دو کلاس (توزیع کلاس)، و یک گره-پیوند است. همانطوری که به تصویر کشیده شده است، گره با مشخصه[156] I5 شامل آیتم c، توزیع کلاس 0 و 3 به ترتیب برای کلاس های مثبت و منفی؛ بدین معنا که آیتم c به همراه آیتم h 3 بار در کلاس منفی ظاهر شده است (ch:0:3)، و یک گره-پیوند گره I5 را به گره I3 که دارای آیتم c هست متصل می کند. در جدول هدر، هر ورودی شامل یک آیتم، فراوانی کل، توزیع کلاس، و هد آیتم است. ورودی آیتم c دارای فراوانی کل 4، توزیع کلاس 3 و 1 در کلاس های مثبت و منفی، و یک هد است که به اولین گره (I5) که دارای آیتم c است. همه گره های برگ I4، I5، I6، I7، I8 بعنوان گره های خارجی در نظر گرفته می شوند. بعلاوه، گره I1 یک گره خارجی است بدلیل اینکه فراوانی I1 که 9 است بزرگتر از جمع فراوانی بچه هایش 8 است. همه گره های خارجی به رنگ قرمز نشان داده شده اند.
فصل چهارم
راهکارهای ارائه‌شده برای استخراج الگوهای نوظهور قوی مبتنی بر ویژگی های جریانی

راهکارهای ارائه‌شده برای استخراج الگوهای نوظهور قوی مبتنی بر ویژگی های جریانی
مقدمهدر این فصل، ما روش های پیشنهادی را با جزییات بیان می کنیم. در روش اول DFP-SEPSF، ترتیب آیتم ها در نظر گرفته نمی شود در حالیکه در روش دوم DFP-SEPSF، درخت الگوی مکرر[157] با توجه به ترتیب آیتم ها ساخته می شود. این روش ها FP-tree را بصورت دینامیک بر اساس ویژگی های جریانی[158] بصورت پایین-بالا[159] می سازند. با ویژگی های جریانی، الگوهای غیرضرور و بی ربط[160] حذف می شوند قبل از آنکه در ساختار DFP-tree قرار گیرند. این می تواند کمک کند تا فرآیند استخراج الگو بصورت کارایی هدایت کند تا الگوهای نوظهور با قدرت پیش بینی قوی استخراج کند. ما یک روش جدید از استخراج الگوهای نوظهور را ارائه می دهیم که الگوهای نوظهور با قدرت پیش بینی بالا را از کلاس های مختلف همزمان استخراج می کند. بعلاوه، روش پیشنهادی قادر است تا داده های با ابعاد بالا[161] را با اعمال محدودیت های ذکر شده در این مطالعه اداره کند. در ویژگی های جریانی، ویژگی ها بصورت دینامیک تولید می شوند و در همان زمان پردازش می شوند. همانطوری که ویژگی ها یکی یکی می رسند، FP-tree بایستی بصورت افزایشی از دیگاه دیگری که بر اساس ویژگی های جریانی است، ساخته شود. وقتی که ویژگی جدیدی می رسد، DFP-tree از طریق گره های خارجی ساخته می شود. از آنجایی که ما هر ویژگی را به محض ورودش پردازش می کنیم، هیچ نمونه ای[162] برای ایجاد FP-tree وجود ندارد. بعبارت دیگر، درخت الگوی مکرر بر پایه ویژگی ها برای ویژگی های جریانی ساخته می شود، و لذا FP-tree بر پایه نمونه ها ساخته نمی شود. در حالیکه درخت الگوی مکرر مرسوم [15، 16] از ریشه بصورت بالا-پایین[163] بوسیله نمونه ها ساخته می شود. DFP-SEPSF یک روش جدید برای ساختن FP-tree ارائه می دهد به طوری که درخت حاصل می تواند ساخته شود وقتی که ویژگی ها یکی یکی می رسند.
درخت الگوی مکرر دینامیک نامرتب Unordered Dynamic FP-tree
در این بخش، ما ساخت نوینی از DFP-tree پیشنهاد می دهیم وقتی که ویژگی ها به مرور زمان می رسند. این تکنیک در ابتدا بدون در نظر گرفتن ترتیب آیتم ها ارائه داده می شود. شکل 4-1. فرآیند ساخت DFP-tree را به تصویر می کشد که این فرآیند با رسیدن هر ویژگی جدید تکرار می شود.

شکل 4-1. مرحله به مرحله ساخت دینامیک درخت الگوی مکرر بدون در نظر گرفتن ترتیب آیتم ها: بعد از رسیدن ویژگی Fi با مقادیر v، سه نوع محدودیت اعمال می شوند. وقتی که v الگوی نوظهور کمینه است، آن به EP-pool اضافه می شود. اگر v توسط دیگر محدودیت ها ارضا شود، v حذف می شود. در غیر اینصورت، v در ساختار DFP-tree اضافه می شود. سپس DFP-SEPSF، گره های پدر ویژگی بعدی را تعیین می کند تا موقعیت گره های بعدی یافت شود.
این روش در سه مرحله پی در پی اجرا می شود. در اولین مرحله، بعضی محدودیت ها اعمال می شوند وقتی که یک ویژگی می رسد. اگر مقدار ویژگی توسط یکی از محدودیت ها ارضا شود، آن حذف می شود. در غیر اینصورت، در مرحله دوم، مقدار ویژگی به چندین گره بعنوان گره های جدید تیدیل می شود و سپس به DFP-tree با استفاده از لیست مشخصه گره های پدر[164] اضافه می شود. در این فرآیند، گره های جدید به گره های خارجی بعنوان پدرهایشان اضافه می شوند. با اعمال محدودیت ها، فراوانی بعضی از گره های پدر بیشتر از جمع فراوانی گره های فرزندانشان است. گره های جدید حاصل از ویژگی های بعدی می توانند به این گره های پدر اضافه شوند. ما هم این گره های پدر و هم گره های برگ را بعنوان گره های خارجی. اساساً، در مرحله سوم، فرایند بروزسانی، مشخص می کند که گره های ویژگی بعدی به کدام گره های خارجی اضافه شوند. این مراحل، در بخش های ادامه به صورت جزیی شرح داده خواهد شد.
مرحله اول: اعمال محدودیت ها
فضای جستجوی الگوها، هر ترکیب ممکن از آیتم ها را برای داده های با ابعاد بالا پوشش می دهد. از این رو، بررسی فضای جستجوی الگوهای نوظهو غیر ممکن است، و لذا ما تعدادی محدودیت را اعمال می کنیم تا فضای جستجوی الگوها را کاهش دهیم. بعلاوه، این محدودیت ها آیتم های بی ربط و غیرضرور را حذف می کنند قبل از اینکه آنها در ساختار DFP-tree قرار گیرند. بنابراین، بعضی از مقادیر ویژگی در این مرحله در نظر گرفته نمی شوند. هر ویژگی ورودی بوسیله سه محدودیت پردازش می شود که بدین شرح هستند:
حداقل آستانه فراوانی نسبی[165]
هر آیتمی که مقدار فراوانی نسبی آن کمتر از حداقل آستانه فراوانی نسبی ms باشد، حذف می شود. با توجه به مفهوم مشهور غیر یکنواختی[166] یا مفهوم apriori، سوپرست های آیتم بصورت پنهانی هرس می شوند. بنابراین، اگر مقدار ویژگی محدودیت فراوانی نسبی را ارضا نکند، آن در نظر گرفته نمی شود. این محدودیت فضای جستجوی الگوهای نوظهور و زمان اجرا را کاهش می دهد.
الگوهای نوظهور کمینه[167]
هرچه طول الگوهای نوظهور بیشتر شود، مقدار فراوانی نسبی آن نیز کوچکتر می شود. بعبارت دیگر، الگوهای نوظهور کوتاه تر دارای فراوانی نسبی بالاتر اما نرخ رشد کوچکتر و الگوهای نوظهور طویلتر دارای فراوانی نسبی کوچکتر اما نرخ رشد بالاتر هستند. در صورتی که الگوهای نوظهور طویلتر استخراج شوند تا تمایز بین کلاس های مختلف را نشان دهند، ویژگی های بیشتر نمی توانند در کلاسه بندی[168] مشارکت داشته باشند. از این رو، ما تلاش می کنیم تا الگوهای نوظهور با آیتم های ( ویژگی ها) کمتر را استخراج کنیم. در این مرحله، DFP-SEPSF مجموعه آیتم های تکی را به محض ورود ویژگی جدید استخراج می کند. برای مثال، الگوی {a, b} دارای فراوانی نسبی 0.5 در Dp و فراوانی نسبی 0.02 در Dn است، از این رو نرخ رشد می شود 25. الگوی {a, b, c} دارای فراوانی نسبی به ترتیب0.01 و 0.0 در Dp و Dn است که دارای نرخ رشد است. الگوی {a, b} مفید تر از {a, b, c} است بدلیل اینکه دارای فراوانی نسبی بالاتر در Dp و همچنین نرخ رشد آن به اندازه کافی بزرگ است. در حالیکه {a, b,c} دارای نرخ رشد بی نهایت ولی فراوانی نسبی آن در Dp خیلی پایین است. بعلاوه، الگوی طویلتر {a, b, c} به احتمال کمتری در نمونه های تست دیده می شود. بر اساس معادلات 1 و 2 (تابع مجموعه امتیاز بر پایه اطلاعات[169])، الگو با فراوانی نسبی بالاتر مفیدتر است در کلاسه بند بر پایه الگوهای نوظهور[170]. در نتیجه، روش پیشنهادی ما الگوهای نوظهور کمینه را استخراج می کند.

Related posts: