Archives

Romanian Journal of Information Technology and Automatic Control / Vol. 13, No. 4, 2003


Frequent Patterns Discovery without Candidates Generation

Cornelia GYÖRÖDI

Abstract:

Infomația implicită din bazele de date, în principal relațiile interesante de asociere dintre seturi de obiecte, care conduc la formarea de reguli de asociere, ar putea scoate în evidență tipare folositoare în activitățile de suport al deciziilor, previziuni financiare, politici de marketing, chiar și efectuarea de diagnostice medicale precum și în multe alte aplicații. Acest lucru a atras multă atenție în cercetările recente din domeniul data mining [I]. Așa cum este arătat în [2], descoperirea regulilor de asociere ar putea necesita scanări iterative ale unor baze mari de date, lucru care este costisitor din punct de vedere al timpului de procesare. Mulți autori și-au concentrat cercetările asupra problemei descoperirii eficiente a regulilor de asociere din bazele de date [2], [3]. Un algoritm de descoperire a regulilor de asociere, foarte influent, A priori [2], acest algoritm a fost dezvoltat pentru descoperirea regulilor de asociere, din baze de date tranzacționale de dimensiuni mari, bazat pe generarea de candidați și eliminarea celor care nu îndeplineau criteriile de suport și încredere impuse. Un pas important în îmbunătățirea performanțelor acestor algoritmi a fost făcut prin introducerea unei structuri de date compacte, numită arbore de tipare frecvente sau FP-tree [3] și a algoritmilor de descoperire asociați, FP-growth [3], care se baza pe descoperirea tiparelor frecvente fără generarea unor candidați suplimentari. Metoda introdusă de autor în [6] și [7], numită DynFPGrowth, îmbunătățește performanțele algoritmilor bazați pe FP-tree, prin reducerea numărului de scanări de la două la una singură și prin introducerea unui proces de actualizare dinamică a structurii FP-tree. Lucrarea prezintă, de asemenea, folosirea cadrului de dezvoltare și de comparare a algoritmilor de descoperire a regulilor de asociere, introdus in [8], în vederea validării metodei introduse și pe baza datelor obținute în urma unui studiu de performanță, care arată avantajele metodei introduse.

Keywords:
tipare frecvente, reguli de asociere, algoritmi, A priori, FP-Growth, DynFPGrowth.

View full article:

CITE THIS PAPER AS:
Cornelia GYÖRÖDI, "Frequent Patterns Discovery without Candidates Generation", Romanian Journal of Information Technology and Automatic Control, ISSN 1220-1758, vol. 13(4), pp. 76-88, 2003.