درخت الگوی مکرر گسترش یافته ساختارهای مبتنی بر درخت های پیشوندی[1] است [15، 16]. درخت الگوی مکرر نمایش فشرده ای از داده است که اطلاعات کاملی از داده های اصلی را در خود ذخیره می کند. در FP-tree، هر مسیر مجموعه آیتم هایی را که دارای پیشوند یکسانی هستند را نشان می دهد و هر گره[2] یک آیتم و فراوانی آن را نشان می دهد. بعلاوه، همه گره هایی که آیتم یکسانی را شامل می شوند از طریق پیوند-گره[3] به هم متصل شده اند. از طریق پیوند-گره همه نمونه هایی که دارای آیتم مشابهی هستند به آسانی قابل دستیابی و شمارش هستند. راس[4] همه پیوند-گره ها برای هر آیتم در یک جدول هدر[5] ذخیره می شوند. بعلاوه، آیتم ها در جهت کاهش فراوانی شان در داده ها مرتب می شوند و در ساختار درخت ذخیره می شوند. اگر چه FP-tree به نظم خاصی وابسته نیست ولی در حالتی که مرتب شده باشد سرعت اجرای عملیات استخراج بسیار بیشتر از حالتی است که درخت نامنظم باشد. برای نمایش الگوهای نوظهور، ما ساختار FP-tree را تغییر می دهیم همانطوری که در تعریف ادامه آمده است.
تعریف 7: (درخت الگوی مکرر دینامیک DFP-tree [15]) یک درخت الگوی مکرر دارای یک ریشه تهی[6]، مجموعه ای از زیر درخت های پیشوندی بعنوان بچه های ریشه، و یک جدول هدر توصیف شده در زیر است.
- هر گره در زیردرخت دارای چهار فیلد: مشخصه ID، مقدار یا آیتم value or item، توزیع کلاس class distribution، و پیوند-گره node-link است. ID، یک گره را از مابقی گره ها متمایز می کند، value، نشاندهنده آن است که کدام مقدار ویژگی در گره جاری ذخیره شده است، class distribution، فراوانی آیتم را به ازای هر کلاس که توسط قسمتی از شاخه ای که به گره می رسد، ثبت می کند، و node-link، گره جاری را به گره بعدی که دارای آیتم مشابهی است متصل می کند و اگر گره ای وجود ندارد null می باشد. بعلاوه، تعدادی از گره ها را بعنوان گره های خارجی[7] تعریف می شوند. دو نوع از گره ها بعنوان گره های خارجی تعریف می شوند : (1) گره های برگ[8] (2) گره های پدری[9] که مقدار فراوانی شان بزرگتر از جمع فراوانی همه گره های فرزندانشان[10] باشد.
- هر ورودی در جدول هدر شامل چهار فیلد است: آیتم item، فراوانی کل total frequency، توزیع کلاس class distribution، هد پیوند-گره head of node-link است. در این مطالعه، آیتم، مقدار ویژگی را ثبت می کند، فراوانی کل، فراوانی آیتم و مقدار ویژگی را در داده ثبت می کند، توزیع کلاس، مقدار فراوانی آیتم یا مقدار ویژگی در هر کلاس را ثبت می کند، و هد پیوند-گره یک اشاره گر اشاره کننده به اولین گره حامل آیتم است.
شکل 3-2. یک مثال از درخت الگوی مکرر: هر گره دارای یک ID، یک آیتم، توزیع کلاس آیتم که نشاندهنده قسمتی از مسیر منتهی به گره است، و پیوند-گره. هر ورودی در جدول هدر دارای یک آیتم، فراوانی کل، توزیع کلاس، و هد پیوند-گره. همه گره ها به رنگ قرمز نشان داده شده اند.
مثال 1. یک مثال از درخت الگوی مکرر در شکل 3-1 نشان داده شده است. درخت دارای یک ریشه تهی و 8 گره است.هر گره دارای یک ID، یک آیتم، فراوانی آیتم در هر دو کلاس (توزیع کلاس)، و یک گره-پیوند است. همانطوری که به تصویر کشیده شده است، گره با مشخصه[11] 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 است. همه گره های خارجی به رنگ قرمز نشان داده شده اند.
[1] Prefix tree
[2] Node
[3] Node-link
[4] head
[5] Header table
[6] Null root
[7] External nodes
[8] Leaf nodes
[9] Parent nodes
[10] Child nodes
[11] ID