در مقایسه با قوانین انجمنی، الگوهای نوظهور قادر هستند که تمایلات نوظهور[1] در مجموعه داده های با محدودیت زمانی[2] را استخراج کنند و یا تمایزات مفید بین کلاس های مختلف را کشف نمایند [1]. مطالعه و پژوهش در رابطه با الگوهای نوظهور اساسا به دو دسته قابل تقسیم است؛ الگوریتم های استخراج الگوهای نوظهور و الگوریتم های کلاسه بندی بر پایه این الگوها. ما در ابتدا الگوریتم های مرتبط با استخراج الگوهای نوظهور را شرح می دهیم و سپس الگوریتم های مشهور کلاسه بندی را ارائه می دهیم.
- روش مبتنی بر مرز[3]
روش های مبتنی بر مرز با الهام از الگوریتم Max-miner [14] پیشنهاد شده اند. این روش ها، مفهوم مرز[4] [1] را بکار می گیرد تا ساختار مناسبی را برای نمایش مختصری برای الگوهای کاندید ارائه دهند. در هر مرز، کوچکترین و بزرگترین عضو هر مجموعه کاندید قابل نمایش است. الگوریتم اختلاف مرز[5]، الگوهای نوظهور کمینه و بیشینه[6] را استخراج می کند و بدین ترتیب مرز الگوهای استخراجی را تنظیم می کند. الگوریتم های مبتنی بر مرز قادر نیستند که الگوهای نوظهور را بصورت همزمان از کلاس های مختلف استخراج کنند. این الگوریتم ها، برای هر کلاس طی فرآیند جداگانه ای الگوها را استخراج می کنند و لذا به ازای هر کلاس، جداگانه اجرا می شود.
- روش مبتنی بر محدودیت (ConsEPMiner[7]) [2]
الگوریتم مبتنی بر محدودیت در دو سطح اجرا می شود؛ تولید الگوهای کاندید و هرس الگوهای اکتشافی. الگوریتم ConsEPMiner از دو نوع محدودیت استفاده می کند تا بتواند بطور موثری فضای جستجو الگوهای نوظهور را هرس کند و محاسبات را ذخیره نماید. محدودیت های ذاتی[8] و خارجی[9] عنوان محدودیت هایی است که در فرآیند استخراج اعمال می شود. محدودیت های خارجی شامل محدودیت حداقل آستانه فراوانی نسبی، نرخ رشد و پیشرفت نرخ رشد[10] است که توسط کاربر قابل تنظیم است. محدودیت ذاتی شامل مجوعه یکسانی از فراوانی نسبی[11]، نرخ رشد بالا[12] و مبدا یکسان[13] است.
- الگوریتم استخراج درخت الگوی تقابل[14] (CP-Tree) [17، 25]
الگوریتم استخراج الگوهای متمایز، با الهام از FP-tree، ساختار گسترش یافته ای ساختار درختی پیشوندی ارائه می دهد. این ساختار به خلاف الگوریتم درخت الگوی مکرر، نیازی به پیوند بین نودها ندارد. الگوریتم توسط جستجوی اول عمقی[15]، CP-tree را از ریشه پیمایش می کند تا الگوهای نوظهور جهشی قوی[16] را استخراج کند. الگوی نوظهور جهشی قوی، یک نوع خاص از الگوهای نوظهور جهشی[17] است که بایستی دارای حداقل فراونی نسبی باشد. این نوع درخت، کارایی استخراج الگوهای نوظهور را با استفاده از الگوهای نوظهور جهشی قوی بهبود می بخشد و همچنین قادر است که مجموعه داده های چند کلاسه را مدیریت نماید.
- روش استخراج با کمک دیاگرام دودیی صفر[18] ZBDD Miner [18]
از آنجایی اینکه روش های ذکر شده، قادر نیستند که داده ها با ابعاد بیشتر از شصت را مدیریت کنند، بعداً، ZBDD EP-Miner شد. این روش از Zero-Suppressed Binary Decision Diagrams (ZBDDs) استفاده می کند تا الگوهای نوظهور را از داده ها با ابعاد بالا استخراج کند. با این وجود، ZBDD EP-miner هنوز شمار زیادی از الگوهای نوظهور را استخراج می کند حتی با اعمال محدودیت های آلفا و بتا [18].
این محدودیت ها استفاده می شوند تا فضای جستجوی الگوهای نوظهور را بیشتر هرس کند. محدودیت آلفا بر اساس مفهوم a-priori است. در نمونه های مثبت[19]، هر آیتم که فراوانی نسبی اش[20] کمتر از مقدار آلفا باشد، هم از نمونه های مثبت و هم از نمونه های منفی حذف می شود. محدودیت بتا بیشترین مقدار فراوانی[21] برای یک الگوریتم در نمونه های منفی مشخص می کند؛ اگر فراوانی الگوی کاندید بیشتر از بتا باشد، آن الگو از نمونه های آموزشی حذف می شود.
- روش استخراج الگوی نوظهور متمایز [22]DP Miner
بر اساس مفهوم مجموعه آیتم بسته[23]، یک کلاس هم ارزی[24] مجموعه ای از آیتم های مکرر[25] است که همیشه در نمونه های یکسانی از نمونه های آموزشی اتفاق می افتند. مشابه با مفهوم مرز در الگوریتم های مبتنی بر مرز، یک کلاس هم ارزی بوسیله الگوهای بسته[26] و تولیدکننده ها[27] تعیین می شود. الگوهای بسته، همان مجموعه آیتم های ماکزیمال هستند و تولیدکننده ها، همان مجموعه آیتم های کمینه در یک کلاس هم ارزی هستند که همه این آیتم ها دارای فراوانی یکسانی هستند. الگوریتم DPMiner، Discriminative Pattern Miner، الگوهای بسته و تولیدکننده ها را که برای نمایش یک کلاس هم ارزی کافی هستند، بصورت همزمان استخراج می کند. بعلاوه، قادر است که الگوهای با قدرت تمایز دلتا[28] را استخراج کند. الگوهای نوظهور با قدرت تمایز دلتا دارای حداکثر فراوانی در کلاس های مقابل است. با توجه به اینکه الگوریتم های ZBDD EP-miner و DPMiner، محدودیت های آلفا و بتا را بکار می گیرند تا فضای جستجوی الگوها را کاهش دهند؛ ممکن است بعضی از الگوهای نوظهور مفید در نظر گرفته نشوند و تاثیر نامطلوبی در کلاسه بندی داشته باشد.
[1] Emerging trends
[2] Time-stamped datasets
[3] Border based
[4] Border
[5] Border differentiation
[6] Maximal
[7] Constrain-based emerging pattern miner
[8] Inherent constraints
[9] External constraints
[10] Growth rate improvement
[11] The same subset support
[12] Top growth rate
[13] The same origin
[14] Contrast pattern tree miner
[15] Depth first search
[16] Strong jumping emerging pattern
[17] Jumping emerging pattern
[18] Zero suppressed binary decision diagram miner
[19] Positive instances
[20] Support
[21] Frequency
[22] Discriminative emerging pattern miner
[23] Itemset closure
[24] Equivalence class
[25] Frequent itemset
[26] Closed patterns
[27] Generators
[28] δ-discriminative