فهرست مطالب
فصل اول

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

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

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

1- مقدمه……………………………………………………………… 2
1-1 مقدمه……………………………………………………………. 2
1-2 مفهوم الگوهای نوظهور………………………………………… 3
1-3 مفهوم ویژگی های جریانی……………………………………. 5
1-4 چالش های موجود در استخراج الگوهای نوظهور………….. 6
1-5 الگوریتم های استخراج الگوهای نوظهور…………………… 8
1-6 ایده اصلی تحقیق…………………………………………… 11
1-7 نگاهی کلی به فصول رساله………………………………. 13

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

فصل دوم

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

2-2- روش های مبتنی بر قانون
هدف از کلاسه بندی قوانین استخراجی، استخراج کردن مجموعه کوچکی از قوانین است تا یک کلاسه بند دقیق ساخته شود. الگوریتم های استخراج قانون مانند Apriori [61] و FPgrowth [15، 16] بکار گرفته می شوند تا مجموعه کاملی از الگوها استخراج شوند. سپس مجموعه کوچکی از قوانین با کیفیت بالا انتخاب می شوند که برای کلاسه بندی بکار می روند. الگوریتم های شناخته شده برای کلاسه بند های انجمنی شامل CBA، CMAR و CPAR می شوند که جزئیات این الگوریتم ها در ادامه بیان خواهند شد.

2-2-1. روش Classification Based on Association (CBA) [27]
روش CBA در دو فاز اجرا می شود: تولید کننده قانون و سازنده کلاسه بند . تولید کننده قانون، الگوریتم Appriori را بکار می گیرد تا همه قوانینی با حداقل آستانه فراوانی نسبی و درجه اطمینان را استخراج کند. برای کلاسه بندی کردن یک نمونه تست، سازنده کلاسه بند، قوانین را بر اساس مقادیر فراوانی نسبی و درجه اطمینانشان مرتب می کند. سپس، سازنده کلاس، اولین قانون را بعنوان بهترین قانون انتخاب می کند تا بر چسب کلاس را به نمونه تست اختصاص دهد. بدلیل اینکه CBA کلاسه بندی را بر اساس فقط یک قانون برای یک نمونه تست انجام می دهد، ممکن است باعث بروز مشکل بیش یادگیر شود.

2-2-2. روش کلاسه بندی Classification based on Multiple-class Association Rule (CMAR) [28]
با توجه به اینکه CBA فقط بر اساس یک قانون با درجه اطمینان و فراوانی بالا کلاسه بندی را انجام می دهد، مشکل بیش یادگیری صورت می گیرد و لذا دقت کلاسه بند برای نمونه های تست کم خواهد شد. برای حل این مشکل، CMAR کلاسه بندی را بر اساس چندین قانون انجام می دهد. CMAR، درخت الگوی مکرر را توسعه می دهد بطوری که بتواند الگوهای مکرر را بصورت کارایی استخراج کند. CMAR چندین قانون را با استفاده از وزن دهی بر اساس χ برای کلاسه بندی بکار می گیرد.

2-2-3. روش کلاسه بندیClassification based on Predictive Association Rule (CPAR) [29]
CPAR با الهام از الگوریتم FOIL [62] قوانین را تولید می کند. CPAR، مجموعه بسیار کوچکی از قوانین با قابلیت پیش بینی را با استفاده از الگوریتم حریصانه بطور مستقیم از مجموعه آموزشی استخراج می کند. برای جلوگیری از بیش یادگیری، CPAR بهترین k قانون را جهت کلاسه بندی کردن نمونه تست بکار می گیرد. CPAR در مقایسه با دیگر الگوریتم های استخراج قوانین دارای مزایایی بدین شرح است: 1) مجوعه خیلی کوچکتری از قوانین با کیفیت بالا بطور مستقیم از نمونه های آموزشی استخراج می کند. 2) برای پرهیز از تولید قوانین تکراری، CPAR هر قانون را با توجه به مجموعه قوانینی که از قبل استخراج کرده است، تولید می کند. 3) برای کلاسه بندی، بهترین k قانون بکار گرفته می شود.

2-3- روش¬های استخراج الگوها
در مقایسه با قوانین انجمنی، الگوهای نوظهور قادر هستند که تمایلات نوظهور در مجموعه داده های با محدودیت زمانی را استخراج کنند و یا تمایزات مفید بین کلاس های مختلف را کشف نمایند [1]. مطالعه و پژوهش در رابطه با الگوهای نوظهور اساسا به دو دسته قابل تقسیم است؛ الگوریتم های استخراج الگوهای نوظهور و الگوریتم های کلاسه بندی بر پایه این الگوها. ما در ابتدا الگوریتم های مرتبط با استخراج الگوهای نوظهور را شرح می دهیم و سپس الگوریتم های مشهور کلاسه بندی را ارائه می دهیم.

2-3-1. روش مبتنی بر مرز
روش های مبتنی بر مرز با الهام از الگوریتم Max-miner [14] پیشنهاد شده اند. این روش ها، مفهوم مرز [1] را بکار می گیرد تا ساختار مناسبی را برای نمایش مختصری برای الگوهای کاندید ارائه دهند. در هر مرز، کوچکترین و بزرگترین عضو هر مجموعه کاندید قابل نمایش است. الگوریتم اختلاف مرز ، الگوهای نوظهور کمینه و بیشینه را استخراج می کند و بدین ترتیب مرز الگوهای استخراجی را تنظیم می کند. الگوریتم های مبتنی بر مرز قادر نیستند که الگوهای نوظهور را بصورت همزمان از کلاس های مختلف استخراج کنند. این الگوریتم ها، برای هر کلاس طی فرآیند جداگانه ای الگوها را استخراج می کنند و لذا به ازای هر کلاس، جداگانه اجرا می شود.

2-3-2. روش مبتنی بر محدودیت (ConsEPMiner ) [2]
الگوریتم مبتنی بر محدودیت در دو سطح اجرا می شود؛ تولید الگوهای کاندید و هرس الگوهای اکتشافی. الگوریتم ConsEPMiner از دو نوع محدودیت استفاده می کند تا بتواند بطور موثری فضای جستجو الگوهای نوظهور را هرس کند و محاسبات را ذخیره نماید. محدودیت های ذاتی و خارجی عنوان محدودیت هایی است که در فرآیند استخراج اعمال می شود. محدودیت های خارجی شامل محدودیت حداقل آستانه فراوانی نسبی، نرخ رشد و پیشرفت نرخ رشد است که توسط کاربر قابل تنظیم است. محدودیت ذاتی شامل مجوعه یکسانی از فراوانی نسبی ، نرخ رشد بالا و مبدا یکسان است.

2-3-3. الگوریتم استخراج درخت الگوی تقابل (CP-Tree) [17، 25]
الگوریتم استخراج الگوهای متمایز، با الهام از FP-tree، ساختار گسترش یافته ای ساختار درختی پیشوندی ارائه می دهد. این ساختار به خلاف الگوریتم درخت الگوی مکرر، نیازی به پیوند بین نودها ندارد. الگوریتم توسط جستجوی اول عمقی ، CP-tree را از ریشه پیمایش می کند تا الگوهای نوظهور جهشی قوی را استخراج کند. الگوی نوظهور جهشی قوی، یک نوع خاص از الگوهای نوظهور جهشی است که بایستی دارای حداقل فراونی نسبی باشد. این نوع درخت، کارایی استخراج الگوهای نوظهور را با استفاده از الگوهای نوظهور جهشی قوی بهبود می بخشد و همچنین قادر است که مجموعه داده های چند کلاسه را مدیریت نماید.

2-3-4. روش استخراج با کمک دیاگرام دودیی صفر ZBDD Miner [18]
از آنجایی اینکه روش های ذکر شده، قادر نیستند که داده ها با ابعاد بیشتر از شصت را مدیریت کنند، بعداً، ZBDD EP-Miner شد. این روش از Zero-Suppressed Binary Decision Diagrams (ZBDDs) استفاده می کند تا الگوهای نوظهور را از داده ها با ابعاد بالا استخراج کند. با این وجود، ZBDD EP-miner هنوز شمار زیادی از الگوهای نوظهور را استخراج می کند حتی با اعمال محدودیت های آلفا و بتا [18].
این محدودیت ها استفاده می شوند تا فضای جستجوی الگوهای نوظهور را بیشتر هرس کند. محدودیت آلفا بر اساس مفهوم a-priori است. در نمونه های مثبت ، هر آیتم که فراوانی نسبی اش کمتر از مقدار آلفا باشد، هم از نمونه های مثبت و هم از نمونه های منفی حذف می شود. محدودیت بتا بیشترین مقدار فراوانی برای یک الگوریتم در نمونه های منفی مشخص می کند؛ اگر فراوانی الگوی کاندید بیشتر از بتا باشد، آن الگو از نمونه های آموزشی حذف می شود.

2-3-5. روش استخراج الگوی نوظهور متمایز DP Miner
بر اساس مفهوم مجموعه آیتم بسته ، یک کلاس هم ارزی مجموعه ای از آیتم های مکرر است که همیشه در نمونه های یکسانی از نمونه های آموزشی اتفاق می افتند. مشابه با مفهوم مرز در الگوریتم های مبتنی بر مرز، یک کلاس هم ارزی بوسیله الگوهای بسته و تولیدکننده ها تعیین می شود. الگوهای بسته، همان مجموعه آیتم های ماکزیمال هستند و تولیدکننده ها، همان مجموعه آیتم های کمینه در یک کلاس هم ارزی هستند که همه این آیتم ها دارای فراوانی یکسانی هستند. الگوریتم DPMiner، Discriminative Pattern Miner، الگوهای بسته و تولیدکننده ها را که برای نمایش یک کلاس هم ارزی کافی هستند، بصورت همزمان استخراج می کند. بعلاوه، قادر است که الگوهای با قدرت تمایز دلتا را استخراج کند. الگوهای نوظهور با قدرت تمایز دلتا دارای حداکثر فراوانی در کلاس های مقابل است. با توجه به اینکه الگوریتم های ZBDD EP-miner و DPMiner، محدودیت های آلفا و بتا را بکار می گیرند تا فضای جستجوی الگوها را کاهش دهند؛ ممکن است بعضی از الگوهای نوظهور مفید در نظر گرفته نشوند و تاثیر نامطلوبی در کلاسه بندی داشته باشد.

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

فصل سوم

در کلاسه بندی بر پایه الگوهای نوظهور، همه الگوهای هر کلاس Ci، کلاس iام، از نمونه های آموزشی استخراج می شوند و برای تصمیم گیری در مورد برچسب کلاس نمونه های تست بکار گرفته می شوند. برای کلاسه بندی کردن یک نمونه تست t، M امتیاز محاسبه می شود، بطوری که برای هر کلاس یک امتیاز محاسبه می شود. کلاس با بالاترین امتیاز بعنوان برچسب کلاس برای t در نظر گرفته می شود، label(t) = argmaxci score (t, Ci). تعریفی که در ادامه آمده است، امتیاز مجموع را بعنوان تابع امتیازدهی ارائه می دهد.

تعریف 6: (جمع آوری امتیاز [21]) نمونه تست t و مجموعه الگوهای نوظهور Ei که از کلاس Ci از نمونه های آموزشی استخراج شده اند، داده شده اند. مجموع امتیاز برای t به ازای کلاس Ci بدین شرح تعریف می شود:
بدلیل اینکه تعداد الگوهای نوظهور از کلاس های مختلف ممکن است نامتوازن باشد، نمونه تست t ممکن امتیاز بالاتری برای کلاس Ci با الگوهای بیشتر از دیگر کلاس Cj بدست آورد، حتی اگر برچسب کلاس t کلاس Cj باشد. بنابراین، تابع امتیاز که توسط تعریف 4 معرفی شده است، بایستی جهت کلاسه بندی نمونه تست t تغییر داده شود.
مفهوم امتیاز پایه [21] می تواند کمک کند تا این مشکل حل شود. امتیاز پایه، baseScore(Ci)، از نمونه های آموزشی هر کلاس بدست می آید. با امتیاز پایه، امتیاز جدید یک نمونه تست t برای کلاس Ci که امتیاز نُرم شده، normScore(t, Ci)، نامیده می شود، بصورت نسبت امتیاز Score(t, Ci) و امتیاز پایه baseScore(Ci) تعریف می شود،
normScore(t,C_i )=(score(t,C_i))/(baseScore( C_i))
کلاس با بیشترین امتیاز نُرم شده بعنوان برچسب کلاس نمونه تست t در نظر گرفته می شود و در صورتی که امتیازات بدست آمده از کلاس های مختلف برابر شد، کلاس با بزرگترین نمونه بعنوان برچسب کلاس در نظر گرفته می شود. یک راه برای مشخص کردن امتیاز پایه این است که میانه امتیازات بدست آمده از نمونه های آموزشی کلاس Ci در نظر گرفته شود. برای مثال، فرض کنید 5 نمونه آموزشی از هر کدام از کلاس های مثبت (+) و منفی (-) وجود دارد. با همه EPs موجود از هر کلاس، فرض کنید که امتیازات حاصل از نمونه های مثبت که بوسیله تعریف 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] یک تابع امتیاز ساده تر بر اساس تئوری اطلاعات ارائه دادند که از محاسبه امتیاز پایه برای هر کلاس اجتناب می کند. تابع امتیاز نمونه تست t بوسیله معادله های 1 و 2 قابل محاسبه است.
فرمول 3-1L(t||C_i )=-∑_(k=1)^p▒〖log〗_2⁡〖P(X_k│C_i ),X_k∈E_i and 〗 X_k∈t برچسب کلاس Ci به نمونه تست t اختصاص داده می شود در صورتی که L(t||Ci) کمترین مقدار به ازای کلاس Ci داشته باشد. به ازای مجموعه آیتم X، P(X|Ci) تقریبا با معادله 2 محاسبه می شود،
در این معادله، |X ∩C_i | تعداد نمونه هایی متعلق به کلاس Ci و دارای مجموعه آیتم X ، |X| تعداد کل نمونه های آموزشی شامل X ، |D| تعداد کل نمونه های آموزشی، و |Ci| تعداد نمونه های آموزشی متعلق به کلاس Ci را نشان می دهند. بعلاوه، برای اطمینان از اینکه حداقل یک EP برای کلاسه بندی نمونه تست t یافت می شود، ما همه آیتم های تکی را جدای از آن که حداقل آستانه ها را ارضا می کنند یا خیر برای کلاسه بندی نمونه تست t در نظر می گیریم.

درخت الگوی مکرر دینامیک (DFP-tree)
درخت الگوی مکرر گسترش یافته ساختارهای مبتنی بر درخت های پیشوندی است [15، 16]. درخت الگوی مکرر نمایش فشرده ای از داده است که اطلاعات کاملی از داده های اصلی را در خود ذخیره می کند. در FP-tree، هر مسیر مجموعه آیتم هایی را که دارای پیشوند یکسانی هستند را نشان می دهد و هر گره یک آیتم و فراوانی آن را نشان می دهد. بعلاوه، همه گره هایی که آیتم یکسانی را شامل می شوند از طریق پیوند-گره به هم متصل شده اند. از طریق پیوند-گره همه نمونه هایی که دارای آیتم مشابهی هستند به آسانی قابل دستیابی و شمارش هستند. راس همه پیوند-گره ها برای هر آیتم در یک جدول هدر ذخیره می شوند. بعلاوه، آیتم ها در جهت کاهش فراوانی شان در داده ها مرتب می شوند و در ساختار درخت ذخیره می شوند. اگر چه FP-tree به نظم خاصی وابسته نیست ولی در حالتی که مرتب شده باشد سرعت اجرای عملیات استخراج بسیار بیشتر از حالتی است که درخت نامنظم باشد. برای نمایش الگوهای نوظهور، ما ساختار FP-tree را تغییر می دهیم همانطوری که در تعریف ادامه آمده است.

3- دانش اولیه……………………………………………………… 24
3-1 الگوهای نوظهور………………………………………………. 24
3-2 درخت الگوی مکرر دینامیک DFP-tree ا……………………..30

فصل چهارم

در این فصل، ما روش های پیشنهادی را با جزییات بیان می کنیم. در روش اول DFP-SEPSF، ترتیب آیتم ها در نظر گرفته نمی شود در حالیکه در روش دوم DFP-SEPSF، درخت الگوی مکرر با توجه به ترتیب آیتم ها ساخته می شود. این روش ها FP-tree را بصورت دینامیک بر اساس ویژگی های جریانی بصورت پایین-بالا می سازند. با ویژگی های جریانی، الگوهای غیرضرور و بی ربط حذف می شوند قبل از آنکه در ساختار DFP-tree قرار گیرند. این می تواند کمک کند تا فرآیند استخراج الگو بصورت کارایی هدایت کند تا الگوهای نوظهور با قدرت پیش بینی قوی استخراج کند. ما یک روش جدید از استخراج الگوهای نوظهور را ارائه می دهیم که الگوهای نوظهور با قدرت پیش بینی بالا را از کلاس های مختلف همزمان استخراج می کند. بعلاوه، روش پیشنهادی قادر است تا داده های با ابعاد بالا را با اعمال محدودیت های ذکر شده در این مطالعه اداره کند. در ویژگی های جریانی، ویژگی ها بصورت دینامیک تولید می شوند و در همان زمان پردازش می شوند. همانطوری که ویژگی ها یکی یکی می رسند، FP-tree بایستی بصورت افزایشی از دیگاه دیگری که بر اساس ویژگی های جریانی است، ساخته شود. وقتی که ویژگی جدیدی می رسد، DFP-tree از طریق گره های خارجی ساخته می شود. از آنجایی که ما هر ویژگی را به محض ورودش پردازش می کنیم، هیچ نمونه ای برای ایجاد FP-tree وجود ندارد. بعبارت دیگر، درخت الگوی مکرر بر پایه ویژگی ها برای ویژگی های جریانی ساخته می شود، و لذا FP-tree بر پایه نمونه ها ساخته نمی شود. در حالیکه درخت الگوی مکرر مرسوم [15، 16] از ریشه بصورت بالا-پایین بوسیله نمونه ها ساخته می شود. DFP-SEPSF یک روش جدید برای ساختن FP-tree ارائه می دهد به طوری که درخت حاصل می تواند ساخته شود وقتی که ویژگی ها یکی یکی می رسند.

4-2- درخت الگوی مکرر دینامیک نامرتب 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 با استفاده از لیست مشخصه گره های پدر اضافه می شود. در این فرآیند، گره های جدید به گره های خارجی بعنوان پدرهایشان اضافه می شوند. با اعمال محدودیت ها، فراوانی بعضی از گره های پدر بیشتر از جمع فراوانی گره های فرزندانشان است. گره های جدید حاصل از ویژگی های بعدی می توانند به این گره های پدر اضافه شوند. ما هم این گره های پدر و هم گره های برگ را بعنوان گره های خارجی. اساساً، در مرحله سوم، فرایند بروزسانی، مشخص می کند که گره های ویژگی بعدی به کدام گره های خارجی اضافه شوند. این مراحل، در بخش های ادامه به صورت جزیی شرح داده خواهد شد.

4- راهکارهای ارائه شده برای استخراج الگوهای نوظهور قوی مبتنی بر ویژگی های جریانی…………………………………………………………… 34
4-1 مقدمه ……………………………………………………….34
4-2- درخت الگوی مکرر دینامیک نامرتب Unordered Dynamic FP-treeا…………………………………………………………. 35
4-3 درخت الگوی مکرر دینامیک مرتب Ordered Dynamic FP-tree ا……………………………………………………………………44
4-4 روش استخراج الگوها SEP-Miner ا………………………56

فصل پنجم

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

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

فصل ششم

6- نتیجه گیری و کارهای آینده…………………………………… 97
اختصارات…………………………………………………………… 99
واژه نامه فارسی به انگلیسی…………………………………. 100
واژه نامه انگلیسی به فارسی…………………………………. 108
فهرست منابع…………………………………………………… 116

Abstract

Mining a minimal set of strongly predictive emerging patterns from a high imensional dataset is a challenging issue for making an accurate emerging pattern classifier. he problem becomes even more sever when features are not available as a whole; ther 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 startedIn this study, we propose a novel dynamic structure to construct the frequent pattern tree on arrival of new features and to mine emerging patterns onlineDFP-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 orderingMoreover, 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.



بلافاصله بعد از پرداخت به ایمیلی که در مرحله بعد وارد میکنید ارسال میشود.


فایل pdf غیر قابل ویرایش

قیمت25000تومان

خرید فایل word

قیمت35000تومان