際際滷

際際滷Share a Scribd company logo

An efficient implementation of pattern growth approach

Esranur retmen
Esranur retmen
1 of 18
ESRANUR RETMEN 080401040
Bu sunumda Pattern growth yakla脹m脹nn 巽eitli y旦nleri incelenip, bu algoritma i巽in verimli stratejilere deinilecektir. FIM algoritmalar脹 iki kategoride s脹n脹fland脹r脹labilir: Candidate generate-and-test approach Pattern growth approach 聴lk yakla脹m脹n eksiklikleri; Veritaban脹n脹 巽ok kez tarama gereklilii ok fazla candidate itemset 端retilmesi ihtiyac脹 聴temsetler 巽ok b端y端k olduunda subset kontrol端n端n maliyet gerektirmesi
D: verilmi bir transactional database, I:itemlar脹n k端mesi olsun. I daki itemlar脹n herhangi bir kombinasyonu D de frequent olabilir ve FIM probleminin arama uzay脹ndand脹r. Arama uzay脹 s旦zl端ksel s脹ralamada olabilecei gibi bir aa巽 taraf脹ndan g旦steriliyor olabilir. Bir itemset in candidate extensionlar脹 p ile tan脹mlans脹n.
M Mesela; I={a,b,c,d,e} i巽in Figure 1 de ki arama uzay脹 aac脹nda "ac" nin candidate extensionlar脹 "d" ve "e" dir, "b" olamaz 巽端nk端 "b", "c" den 旦nce gelmitir.
Patterng growth yakla脹m脹 b旦l-y旦net y旦ntemini benimser. rnein Figure 1 deki arama uzay脹 5 ayr脹k arama uzay脹na b旦l端nebilir. a y脹 i巽eren itemsetler b yi i巽eren a y脹 i巽ermeyen itemsetler c yi i巽eren a ve b yi i巽ermeyen itemsetler d yi i巽eren a, b ve c yi i巽ermeyen itemsetler yaln脹z e yi i巽eren itemsetler B旦ylelikle database 5 k脹s脹ma b旦l端n端r ve her k脹s脹m conditional database olarak adland脹r脹l脹r.
i iteminin conditional databaseine D聴 dersek, i yi i巽eren t端m itemsetler baka bir bilgiye ihitya巽 olmaks脹z脹n D聴 taraf脹ndan mining edilebilir. Her conditional database ayn脹 prosed端r端 takip ederek recursive olarak b旦l端n端r. Pattern growth algoritmas脹n脹n iki temel ilemi vard脹r. Frequent itemlar脹 saymak Yeni conditional databaseler oluturmak Yeni conditional databaselerin toplam say脹s脹 ve her bir conditional database in mining maliyeti bir Pattern growth algoritmas脹n脹n performans脹n脹 etkileyen anahtar fakt旦rlerdir.
Arama uzay脹n脹 b旦ld端端m端zde, t端m itemlar ayn脹 s脹ralama ile s脹ralan脹rlar. Bu s脹ralamaya Item search s脹ras脹 denilmektedir. Bir item 脹n yar脹 arama uzay脹 ondan sonraki item lar脹 i巽erir, sonrakileriyse i巽eremez. Literat端rde iki item search s脹ras脹 旦nemlidir. Statik s旦zdizimsel s脹ralama Dinamik artan frequency s脹ralama 聴htiyac脹m脹z olan daha k端巽端k bir conditional database olduundan, artan frequency s脹ralama yaparken en y端ksek frequency li olan脹 旦ne yerletiririz. B旦ylelikle frequent extension 巽ok b端y端k olmam脹 olur.
An efficient implementation of pattern growth approach
Conditional databaselerin saklanmas脹 i巽in farkl脹 veri yap脹lar脹 旦nerilebilir. FP-tree ve AFOPT-tree gibi algoritmalar aa巽 tabanl脹 yap脹lar脹, Hyperstructure gibi algoritmalar ise dizi tabanl脹 yap脹lar脹 kullan脹r. Aa巽 tabanl脹 yap脹lar maliyeti azaltabilirler, 巽端nk端 kopyalanm脹 ilemler bir araya getirilebilir ve farkl脹 ilemler 旦ne eklenerek paylaabilir. Ancak dataset b端y端kse, maliyet y端kselir. Dizi tabanl脹 yap脹lar az maliyet gerektirir. Ancak bu yap脹larda farkl脹 ilemler paylaamazlar. Genel olarak, aa巽 tabanl脹 yap脹lar脹n dense(youn) databaselerde, dizi tabanl脹 yap脹lar脹nsa sparse(seyrek) databaselerde kullan脹m脹 uygundur.
Database 巽ok k端巽端k olmad脹脹 m端ddet巽e conditional database oluturma olduk巽a maliyetlidir. Buna bir alternatif olarak sahte construction g旦sterilir yani, y端ksek frequently li construction databaselerde ilemleri g旦steren pointerlar kullanmak. Buna ramen sahte construction fiziksel construction kadar etkili deildir. Artan frequent s脹ral脹 itemsetler h脹zl脹ca alt construction databaseler yapabilir, bu s脹ra ile birlikte kullan脹l脹脹 zaman bu stratejinin kullan脹l脹 olduu g旦r端lm端t端r.
Aac脹n dolama maliyeti yukar脹dan-aa脹ya dolama stratejisi ile minimuma 巽ekilebilir. FP-Tree de azalan frequent s脹raya g旦re yap脹l脹r. Dolay脹s脹yla FP-Tree aa脹dan yukar脹 dolama stratejisini kullan脹r. Ve FP-Tree her node da parent balant脹 ve node balant脹lar脹na sahiptir. AFOPT algoritma ise artan frequency kullan脹r, bu y端zden yukar脹dan aa脹ya dolama stratejisini benimsemitir. Ve pointerlar eklemeye gerek yoktur. FP-Treenin burada avantaj脹 azalan frequency s脹ra kullanarak 旦ne ekleme payla脹m ihtimalini art脹rmas脹 y旦n端yle AFOPT dan daha kompakt oluudur. AFOPT taraf脹ndan benimsenen artan frequency s脹ra, aa巽taki tek dallanmalar脹 etkilemektedir. Bu problem AFOPT da tek dallanmalar脹 saklamak i巽in dizi kullan脹m脹 ile hafifletilmitir.
An efficient implementation of pattern growth approach
Conditional database i巽in 3 farkl脹 yap脹 kullan脹l脹r; array, AFOPT-tree ve buckets Dinamik artan frequenti benimser. Conditional databaseler her levelda fiziksel olarak yap脹lan脹r.
Buckets teknii uygun ve farkl脹 frequenty itemlar脹n say脹s脹 10 civar脹ndayken etkilidir. Aa巽 yap脹s脹 dense database de, dizi yap脹s脹 ise sparse database de verimli olur. Hangi yap脹y脹 se巽memiz gerektiini aa脹daki parametreler, kullanarak belirleyebiliriz; Sadece top-bucket_size frequent itemlar脹 i巽eren itemsetler kullan脹lan bucketlar脹 sayar. Eer minimum eikdeeri >tree_min_sup veya b端t端n frequent itemlar脹n ortalamas脹 > tree_avg_sup ise geriye kalan t端m conditional databaseler AFOPT-Tree kullanarak g旦sterilir. Aksi halde sonraki tree_alphabet_size 脹n frequenti y端ksek itemlar脹n脹n conditional databaseleri AFOPT-Tree kullanarak g旦sterilir ve geriye kalan conditional databaselerse dizi kullanarak g旦sterilir.
An efficient implementation of pattern growth approach
Transactional database D nin ve minimum eikdeerinin verildii durumda, AFOPT algoritmas脹 t端m frequent itemsetleri mining etmek i巽in, orijinal database i iki kere tarar. 聴lk taramada, D deki t端m frequent itemlar, artan frequent s脹ralama i巽inde grupland脹r脹l脹r ve F={i1,i2,,im} eklinde g旦sterilir. Dier taramay脹 ise D聴j i巽in her bir ij de conditional database yap脹land脹rmak i巽in yapar脹z. 聴kinci tarama esnas脹nda, her bir t ilemindeki frequent i d端端k olan itemlar kald脹r脹l脹r ve geriye kalan itemlar Fdeki s脹raya g旦re grupland脹r脹l脹r. t ilemi, grupland脹rman脹n ard脹ndan t nin ilk item 脹 ij ise, D聴j nin i巽ine al脹n脹r. Geriye kalan mining ilemleri sadece conditional databaselere uygulan脹r. B旦ylelikle orijinal database e ulamaya gerek kalmaz.
D聴j i巽inde bir t ilemi varsayal脹m, t nin i巽inde i1 den sonraki item ij olsun, bu durumda t D聴j nin i巽ine yerletirilir. Bu ad脹ma push-right denir. Itemlar脹 artan frequent s脹ralamaya g旦re grupland脹rmak her defas脹nda k端巽端k bir conditional database in push-right edilmesini salar.
An efficient implementation of pattern growth approach

More Related Content

An efficient implementation of pattern growth approach

  • 1. ESRANUR RETMEN 080401040
  • 2. Bu sunumda Pattern growth yakla脹m脹nn 巽eitli y旦nleri incelenip, bu algoritma i巽in verimli stratejilere deinilecektir. FIM algoritmalar脹 iki kategoride s脹n脹fland脹r脹labilir: Candidate generate-and-test approach Pattern growth approach 聴lk yakla脹m脹n eksiklikleri; Veritaban脹n脹 巽ok kez tarama gereklilii ok fazla candidate itemset 端retilmesi ihtiyac脹 聴temsetler 巽ok b端y端k olduunda subset kontrol端n端n maliyet gerektirmesi
  • 3. D: verilmi bir transactional database, I:itemlar脹n k端mesi olsun. I daki itemlar脹n herhangi bir kombinasyonu D de frequent olabilir ve FIM probleminin arama uzay脹ndand脹r. Arama uzay脹 s旦zl端ksel s脹ralamada olabilecei gibi bir aa巽 taraf脹ndan g旦steriliyor olabilir. Bir itemset in candidate extensionlar脹 p ile tan脹mlans脹n.
  • 4. M Mesela; I={a,b,c,d,e} i巽in Figure 1 de ki arama uzay脹 aac脹nda "ac" nin candidate extensionlar脹 "d" ve "e" dir, "b" olamaz 巽端nk端 "b", "c" den 旦nce gelmitir.
  • 5. Patterng growth yakla脹m脹 b旦l-y旦net y旦ntemini benimser. rnein Figure 1 deki arama uzay脹 5 ayr脹k arama uzay脹na b旦l端nebilir. a y脹 i巽eren itemsetler b yi i巽eren a y脹 i巽ermeyen itemsetler c yi i巽eren a ve b yi i巽ermeyen itemsetler d yi i巽eren a, b ve c yi i巽ermeyen itemsetler yaln脹z e yi i巽eren itemsetler B旦ylelikle database 5 k脹s脹ma b旦l端n端r ve her k脹s脹m conditional database olarak adland脹r脹l脹r.
  • 6. i iteminin conditional databaseine D聴 dersek, i yi i巽eren t端m itemsetler baka bir bilgiye ihitya巽 olmaks脹z脹n D聴 taraf脹ndan mining edilebilir. Her conditional database ayn脹 prosed端r端 takip ederek recursive olarak b旦l端n端r. Pattern growth algoritmas脹n脹n iki temel ilemi vard脹r. Frequent itemlar脹 saymak Yeni conditional databaseler oluturmak Yeni conditional databaselerin toplam say脹s脹 ve her bir conditional database in mining maliyeti bir Pattern growth algoritmas脹n脹n performans脹n脹 etkileyen anahtar fakt旦rlerdir.
  • 7. Arama uzay脹n脹 b旦ld端端m端zde, t端m itemlar ayn脹 s脹ralama ile s脹ralan脹rlar. Bu s脹ralamaya Item search s脹ras脹 denilmektedir. Bir item 脹n yar脹 arama uzay脹 ondan sonraki item lar脹 i巽erir, sonrakileriyse i巽eremez. Literat端rde iki item search s脹ras脹 旦nemlidir. Statik s旦zdizimsel s脹ralama Dinamik artan frequency s脹ralama 聴htiyac脹m脹z olan daha k端巽端k bir conditional database olduundan, artan frequency s脹ralama yaparken en y端ksek frequency li olan脹 旦ne yerletiririz. B旦ylelikle frequent extension 巽ok b端y端k olmam脹 olur.
  • 9. Conditional databaselerin saklanmas脹 i巽in farkl脹 veri yap脹lar脹 旦nerilebilir. FP-tree ve AFOPT-tree gibi algoritmalar aa巽 tabanl脹 yap脹lar脹, Hyperstructure gibi algoritmalar ise dizi tabanl脹 yap脹lar脹 kullan脹r. Aa巽 tabanl脹 yap脹lar maliyeti azaltabilirler, 巽端nk端 kopyalanm脹 ilemler bir araya getirilebilir ve farkl脹 ilemler 旦ne eklenerek paylaabilir. Ancak dataset b端y端kse, maliyet y端kselir. Dizi tabanl脹 yap脹lar az maliyet gerektirir. Ancak bu yap脹larda farkl脹 ilemler paylaamazlar. Genel olarak, aa巽 tabanl脹 yap脹lar脹n dense(youn) databaselerde, dizi tabanl脹 yap脹lar脹nsa sparse(seyrek) databaselerde kullan脹m脹 uygundur.
  • 10. Database 巽ok k端巽端k olmad脹脹 m端ddet巽e conditional database oluturma olduk巽a maliyetlidir. Buna bir alternatif olarak sahte construction g旦sterilir yani, y端ksek frequently li construction databaselerde ilemleri g旦steren pointerlar kullanmak. Buna ramen sahte construction fiziksel construction kadar etkili deildir. Artan frequent s脹ral脹 itemsetler h脹zl脹ca alt construction databaseler yapabilir, bu s脹ra ile birlikte kullan脹l脹脹 zaman bu stratejinin kullan脹l脹 olduu g旦r端lm端t端r.
  • 11. Aac脹n dolama maliyeti yukar脹dan-aa脹ya dolama stratejisi ile minimuma 巽ekilebilir. FP-Tree de azalan frequent s脹raya g旦re yap脹l脹r. Dolay脹s脹yla FP-Tree aa脹dan yukar脹 dolama stratejisini kullan脹r. Ve FP-Tree her node da parent balant脹 ve node balant脹lar脹na sahiptir. AFOPT algoritma ise artan frequency kullan脹r, bu y端zden yukar脹dan aa脹ya dolama stratejisini benimsemitir. Ve pointerlar eklemeye gerek yoktur. FP-Treenin burada avantaj脹 azalan frequency s脹ra kullanarak 旦ne ekleme payla脹m ihtimalini art脹rmas脹 y旦n端yle AFOPT dan daha kompakt oluudur. AFOPT taraf脹ndan benimsenen artan frequency s脹ra, aa巽taki tek dallanmalar脹 etkilemektedir. Bu problem AFOPT da tek dallanmalar脹 saklamak i巽in dizi kullan脹m脹 ile hafifletilmitir.
  • 13. Conditional database i巽in 3 farkl脹 yap脹 kullan脹l脹r; array, AFOPT-tree ve buckets Dinamik artan frequenti benimser. Conditional databaseler her levelda fiziksel olarak yap脹lan脹r.
  • 14. Buckets teknii uygun ve farkl脹 frequenty itemlar脹n say脹s脹 10 civar脹ndayken etkilidir. Aa巽 yap脹s脹 dense database de, dizi yap脹s脹 ise sparse database de verimli olur. Hangi yap脹y脹 se巽memiz gerektiini aa脹daki parametreler, kullanarak belirleyebiliriz; Sadece top-bucket_size frequent itemlar脹 i巽eren itemsetler kullan脹lan bucketlar脹 sayar. Eer minimum eikdeeri >tree_min_sup veya b端t端n frequent itemlar脹n ortalamas脹 > tree_avg_sup ise geriye kalan t端m conditional databaseler AFOPT-Tree kullanarak g旦sterilir. Aksi halde sonraki tree_alphabet_size 脹n frequenti y端ksek itemlar脹n脹n conditional databaseleri AFOPT-Tree kullanarak g旦sterilir ve geriye kalan conditional databaselerse dizi kullanarak g旦sterilir.
  • 16. Transactional database D nin ve minimum eikdeerinin verildii durumda, AFOPT algoritmas脹 t端m frequent itemsetleri mining etmek i巽in, orijinal database i iki kere tarar. 聴lk taramada, D deki t端m frequent itemlar, artan frequent s脹ralama i巽inde grupland脹r脹l脹r ve F={i1,i2,,im} eklinde g旦sterilir. Dier taramay脹 ise D聴j i巽in her bir ij de conditional database yap脹land脹rmak i巽in yapar脹z. 聴kinci tarama esnas脹nda, her bir t ilemindeki frequent i d端端k olan itemlar kald脹r脹l脹r ve geriye kalan itemlar Fdeki s脹raya g旦re grupland脹r脹l脹r. t ilemi, grupland脹rman脹n ard脹ndan t nin ilk item 脹 ij ise, D聴j nin i巽ine al脹n脹r. Geriye kalan mining ilemleri sadece conditional databaselere uygulan脹r. B旦ylelikle orijinal database e ulamaya gerek kalmaz.
  • 17. D聴j i巽inde bir t ilemi varsayal脹m, t nin i巽inde i1 den sonraki item ij olsun, bu durumda t D聴j nin i巽ine yerletirilir. Bu ad脹ma push-right denir. Itemlar脹 artan frequent s脹ralamaya g旦re grupland脹rmak her defas脹nda k端巽端k bir conditional database in push-right edilmesini salar.