درخت الگوی مکرر گسترش یافته ساختارهای مبتنی بر درخت های پیشوندی[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 است. در این مطالعه، آیتم، مقدار ویژگی را ثبت می کند، فراوانی کل، فراوانی آیتم و مقدار ویژگی را در داده ثبت می کند، توزیع کلاس، مقدار فراوانی آیتم یا مقدار ویژگی در هر کلاس را ثبت می کند، و هد پیوند-گره یک اشاره گر اشاره کننده به اولین گره حامل آیتم است.
[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