M Đ UỞ Ầ
ỹ ữ ậ ế ợ
ọ ấ
ậ ế ợ ụ ệ ữ
ơ ở ữ ệ
ậ ậ ổ ế
ề ứ
ồ ế ợ ượ ư ướ c nhi u nhà nghiên c u trong n ề
ổ ế truy n th ng ứ ượ ổ ế ậ ế ớ c và th gi ố trong th c t c nhu c u c a ng
ự ọ
ủ ừ ể ề ề ậ ổ ế truy n th ng
ứ
ề ọ ủ
ổ ế ọ
ợ ậ ộ Khai phá lu t k t h p là m t trong nh ng k thu t quan ủ ữ ệ tr ng nh t trong khai phá d li u. M c đích chính c a khai ầ ử ố khác phá lu t k t h p là tìm ra m i quan h gi a các ph n t ậ ế ợ nhau trong c s d li u. Bài toán khai phá t p lu t k t h p ậ g m hai bài toán con đó là khai phá t p ph bi n và sinh lu t k t h p. Trong đó, bài toán khai phá t p ph bi n đã thu hút i quan tâm. đ ậ ự ế ẫ v n Nh ng khai phá t p ph bi n ạ ườ ầ ủ ế còn nhi uề h n ch , không đáp ng đ i ử ụ nh đánh giá s quan tr ng c a t ng ph n t ư ầ ử trong s d ng ơ ở ữ ệ . Đ kh c ph c nh ng ừ ữ ụ ắ ị t ng giao d ch hay trong c s d li u ố , nhi u nhà ế ủ khai phá t p ph bi n ạ h n ch c a ở ộ trong đó có tính đ nế ấ nghiên c u đã đ xu t mô hình m r ng ứ ộ ơ ở ữ ầ ử trong c s d m c đ quan tr ng khác nhau c a các ph n t ố WFI; khai phá ư ệ li u nh : khai phá t p ph bi n có tr ng s t p ậ l i ích cao ậ HUI.
ộ ậ ứ ổ ế
ọ ậ ổ ế
ấ ấ
ứ ượ
ế ề ử ụ
ọ
ưỡ
i ích th c t
ứ ầ M t trong nh ng thách th c trong khai phá t p ph bi n có ố ậ i ích cao đó là t p ph bi n có tr ng s , t p ố ả ầ c sinh ra và không gian tìm ki m. H u i ích cao đ u s d ng tính ị i ích tr ng s giao d ch – TWU do Liu và ẫ ng TWU v n còn ẫ ầ ử , do đó v n ế t,
ộ ố ượ ờ ế ữ ọ ậ ợ ố tr ng s và t p l ợ l i ích cao không có tính ch t đóng tính ch t làm gi m s ượ ng ng viên đ l ậ ế ậ ợ h t các thu t toán khai phá t p l ố ủ ợ ấ ch t đóng c a l ố ự ộ c ng s công b năm 2005. Tuy nhiên, ng ự ế ủ ậ ớ ợ c a các t p ph n t khá cao so v i l ớ còn phát sinh m t s l ng l n các ng viên không c n thi ố do đó tiêu t n th i gian và không gian tìm ki m.
ứ ậ
ề ọ ữ đã ch n đ tài “
ố , trên Nghiên c u phát tri n mô ợ ọ i
ủ ậ ơ ở nh ng nghiên c u, nh n xét và đánh giá ở Trên c s ứ ể ứ nghiên c u sinh ậ ph n tầ ử có tr ng s và l ậ hình, thu t toán khai phá t p ế ứ ề ích cao” làm đ tài nghiên c u cho lu n án ti n sĩ c a mình.
ụ ứ M c tiêu nghiên c u
ậ
ổ ế Nghiên c u các thu t toán khai phá t p ph bi n, ố ứ ổ ế ậ ợ ọ ậ t p ph bi n có tr ng s và t p l ậ i ích cao.
ự ữ ệ ấ
ề ế ơ ở ự ể
ổ ế ậ ọ ố
ằ ệ Xây d ng mô hình, đi u ki n, c u trúc d li u nh m ả gi m không gian tìm ki m và d a trên c s đó đ xây ự d ng các thu t toán khai phá t p ph bi n có tr ng s và ậ ợ t p l ậ i ích cao.
ươ
Ổ Ế
Ổ
Ậ
Ề
Ch
ng 1.
T NG QUAN V KHAI PHÁ T P PH BI N
ớ
ệ
1.1. Gi
ơ ệ ớ ậ t ng h tr
ế
ọ ấ ử
i thi u chung ổ ế ộ ậ ấ ả
ỉ ỗ ầ ử ầ ử ị
ặ ấ ệ
ớ ủ ầ
ả ặ
ậ ị
ậ ầ ử ố ươ ỉ
ả
ầ ử ữ ệ ụ ể
ượ ọ ể ố
ậ ợ ố ầ ầ ử ậ có s l n Khai phá t p ph bi n là tìm ra các t p ph n t ỗ ợ ố ể ấ ưỡ i thi u (minsupp). xu t hi n l n h n m t ng ứ ữ ạ ổ ế Tuy nhiên, khai phá t p ph bi n có nh ng h n ch . Th ư ầ nh t, nó x lý t có t m quan tr ng nh t c các ph n t ạ ộ ứ ch có tr ng nhau. Th hai, trong m t giao d ch m i ph n t ế ệ ạ ữ ấ thái xu t hi n ho c không xu t hi n. Rõ ràng nh ng h n ch ề ổ ố ế ậ này làm cho bài toán khai phá t p ph bi n truy n th ng ụ ư ự ế ơ ở ữ ệ ợ , ví d nh trong không phù h p v i các c s d li u th c t ị ọ ặ ỗ ơ ở ữ ệ c s d li u c a siêu th , m i m t hàng có t m quan tr ng ỗ ố ượ ng mua các m t hàng trong m i hay giá c khác nhau, s l ổ giao d ch cũng khác nhau,… Vì v y, mô hình khai phá t p ph ữ ả ế ấ xu t ng quan gi a các ph n t bi n ch ph n ánh m i t ủ ư ơ ở ữ ệ ệ hi n trong c s d li u, nh ng không ph n ánh ý nghĩa c a ữ ắ ừ c đi m trên d li u. Đ kh c ph c nh ng nh t ng ph n t ổ ế ậ có hai mô hình đ c đ a ra: T p ph bi n có tr ng s WFI và T p l ượ ư i ích cao HUI.
ổ ế
ậ
1.2. T p ph bi n
ậ ậ ế
ấ ố ầ ưỡ ớ ơ
ượ c trong c s d li u l n đ
ấ
ề ữ ệ
ệ ữ ậ ố ổ ế ầ Khai phá t p ph bi n là quá trình tìm ki m t p các ph n ệ ộ ử t ng cho có s l n xu t hi n cùng nhau l n h n m t ng ơ ở ữ ệ ớ ướ c R. Agrawal, T. Imielinski tr ầ ừ ấ nhu c u bài toán và A. Swami đ xu t năm 1993, xu t phát t ệ ể ị ơ ở ữ ệ phân tích d li u trong c s d li u giao d ch, đ phát hi n ị ạ i siêu th . các m i quan h gi a các t p hàng hóa đã bán t
ệ ị ữ t s khác nhau gi a các
ệ ự ệ ủ ự ấ Vi c xác đ nh này không phân bi ỉ ự hàng hóa mà ch d a vào s xu t hi n c a chúng.
ộ ố ươ ổ ế ậ M t s ph ng pháp khai phá t p ph bi n:
ươ ự Ph ệ ế ố ng pháp d a trên quan h k t n i
ươ ử ụ ấ Ph ng pháp s d ng c u trúc cây
ươ ưở ậ ố ệ Ph ng pháp tăng tr ự ng đ quy d a trên h u t
ộ ố ươ M t s ph ng pháp song song
ọ
ậ
ố ổ ế 1.3. T p ph bi n có tr ng s
ủ ư
ậ
ố ượ
ưỡ ơ
ỗ ả ộ ổ ế ộ ậ ự ổ ế ọ Năm 1998, nhóm c a Ramkumar đã đ a ra mô hình khai ố Weight Frequent Itemsets – ộ ọ ư ố có m t tr ng s khác nhau nh : ộ ậ ng,…M t t p các i ích, giá c , đ quan tr ng hay s l ố ủ ọ ị ầ ử là ph bi n có tr ng s khi giá tr có tr ng s c a ướ ớ c. D a trên mô hình này ố ậ
ượ ọ ổ ế phá t p ph bi n có tr ng s ( ầ ử WFI). Trong đó, m i ph n t ọ ợ l ọ ố ph n t ng cho tr chúng l n h n m t ng ề đã có nhi u thu t toán khai phá t p ph bi n có tr ng s ố c công b . đ
ộ ố ươ ọ M t s ph ng pháp khai phá t p ậ ph bi n ổ ế có tr ng s ố:
ự ậ ả ọ ố Thu t toán d a trên kho ng tr ng s
ậ ả ử ụ Thu t toán s d ng b ng băm
ổ ế ự ậ ấ ố ỉ ọ Thu t toán d a trên tr ng s ph bi n x p x
ậ ự Thu t toán d a trên cây WIT
ẫ ề ấ 1.4. Đ xu t thu t toán khai phá m u ph bi n ổ ế có tr ngọ
ậ ề ọ số theo chi u d c
ậ ể ự ữ ư
ậ ậ ấ ề ổ ế
ọ ổ ế ố ớ
ử ụ ấ
ậ ậ
ả ử ẻ ộ ệ
ẫ ớ
ầ ự ủ D a trên nh ng u đi m c a thu t toán VMDG khai phá ậ t p ph bi n, đ xu t thu t toán khai phá t p ph bi n có ọ tr ng s v i tên g i VMWFP (Vertical Mining of Weighted ừ Frequent Patterns Using Diffset Groups) s d ng c u trúc. T ự thu t toán VMWFP xây d ng thu t toán song song PVMWFP ơ ớ K t qu th nghi m trên các c ế trên mô hình chia s b nh . ị ầ ử ớ ở ữ ệ và 3984 giao d ch sinh ng u nhiên s d li u v i 52 ph n t ậ ậ ể ế đ ti n hành so sánh thu t toán song song PVMWFP v i thu t ượ ế toán tu n t ả ư Hình 1.1. c k t qu nh VMWFP đ
ế ả Hình 1.. K t qu so sánh PVMWFP và VMWFP
ậ ợ
1.5. T p l
i ích cao
ộ ự
ụ ắ
ậ
ậ ườ ử ụ qua hai tr ng s
ợ ợ ậ ư Năm 2003 Chan và c ng s đã đ a ra mô hình khai phá t p ể ữ ợ High Utility Itemsets – HUI), đ kh c ph c nh ng l i ích cao ( ổ ế ế ủ ổ ế ạ h n ch c a mô hình khai phá t p ph bi n và t p ph bi n ố ọ i s d ng đánh có tr ng s . Trong mô hình này cho phép ng ố ọ ầ ử ủ ừ ọ ượ ầ c t m quan tr ng c a t ng ph n t giá đ ọ i ích trong và l khác nhau g i là l i ích ngoài.
ệ ự ư ộ Năm 2005, Ying Liu và c ng s đ a ra khái ni m l
ị ọ
ầ ử ủ ổ ị
ượ ầ ử
ố ợ i ích t
ậ ả ợ i ích ệ X, ký hi u là i ích c a các giao d ch có ấ ấ X. Đây là giá tr có tính ch t đóng, tính ch t ể i thi u ng l ứ ậ i ích cao ch a t p
ộ ậ ố ủ giao d ch có tr ng s c a m t t p ph n t ợ ằ c tính b ng t ng l TWU(X) đ ị ứ ậ ch a t p ph n t ưỡ ỏ ơ ả ằ ả này đ m b o r ng TWU(X) nh h n ng ậ ợ thì t p X không có kh năng sinh ra t p l X.
ứ ủ ậ ợ ữ ộ M t trong nh ng thách th c c a khai phá t p l i ích cao:
ấ ấ T p l
ậ ợ ủ ậ ả i ích không có tính ch t đóng, tính ch t này đ m i ích cao thì các t p con c a nó cũng là
ậ ợ ộ ậ ả b o m t t p là t p l ậ ợ t p l i ích cao.
ậ ậ ợ Đa s các thu t toán khai phá t p l i ích cao đ u s
ụ ể ắ ỉ ậ ứ
ự ế ủ ớ ử ề ưỡ ng TWU đ c t t a t p ng viên. Đây là ng ng ộ ậ ị ợ c a m t t p i ích th c t
ầ ử d ng ng ề cao h n r t nhi u so v i giá tr l ph n t ố ưỡ ơ ấ .
ố ượ ứ ậ Do v y, s l ng các ng c viên đ
ấ ớ ứ ế ế
ẫ ử ượ c sinh ra r t l n d n ể ờ đ n không gian tìm ki m và th i gian ki m tra các ng viên có chi phí cao.
M t s ph ng pháp khai phá t p l
ộ ố ươ ư ử ụ ủ
ụ ợ
ấ i ích cây con (utility subtree) và và l ủ ụ ộ ả ầ ậ ợ ệ i ích cao hi u qu g n ợ i ích (utilitylist) c a Liu đây nh : s d ng danh sách l ủ ỉ ố ế ợ ả ứ ả (2012); b ng ch s k t h p b ng ng viên c a Guo (2013); ợ ướ ệ ủ ầ ử ặ cùng xu t hi n c a Philippe c tính l i ích các c p ph n t ợ ử ụ i (2014); s d ng d ng l ích c c b (local utility) c a Zida (2016).
ươ
Ậ
Ậ Ợ
Ch
ng 2.
Ự
THU T TOÁN KHAI PHÁ T P L I ÍCH CAO D A TRÊN MÔ HÌNH CWU
ậ ợ ệ ả 2.1. Mô hình hi u qu khai phá t p l i ích cao
ề ặ ấ Đ t v n đ
ố ư Nh chúng ta đã bi
ượ ế c phân tích
ầ ử
ầ ử ủ ậ (cid:0) ậ
ố ơ
ấ ặ ằ ủ ợ ổ
ứ ứ ằ ặ ợ
ậ ợ ậ t, đa s các thu t toán khai phá t p l i ở ề ử ụ ích cao đ trên đ u s d ng mô hình TWU làm ộ ậ ứ ơ ở ể ắ ỉ ớ ộ c s đ c t t a các t p ng viên. V i m t ph n t a, m t ề ố ộ ậ ầ ử ậ có a là ti n t {aX}, ta t p ph n t {X} và m t t p ph n t ự ươ , có ng t có TWU({aX}) là c n trên c a AU({aX}). T ủ {aX} TWU({X}) là c n trên c a AU({X}). Ta th y {X} ị ị ố ẽ ớ ứ nên s giao d ch ch a {X} s l n h n ho c b ng s giao d ch ậ ị i ích c a các giao d ch ch a {aX}. V y, TWU({X}) là t ng l ơ ẽ ớ ổ ch a {X} s l n h n ho c b ng TWU({aX}) là t ng l i ích ứ ị ủ c a các giao d ch ch a {aX}.
ậ ậ ợ Trong các thu t toán khai phá t p l
ả ử ấ ả
ề ố
ứ
ể ẫ
ề ứ ể ỉ
ệ ề i ích cao theo chi u ầ ử ề ố ậ a, là ph n t s , {aX} là t t c các t p có ti n t sâu. Gi ậ ấ ả ầ ử b. Khi khai phá t c các t p có ti n t là ph n t {bX} là t ầ ử ư ẽ ậ a. Nh ng khi các t p trong {bX} s không còn ch a ph n t ầ ử ồ ủ ị ợ a. tính TWU({bX}) có th v n g m giá tr l i ích c a ph n t ơ ớ ủ ậ Đi u này làm TWU({bX}) là c n trên c a AU({bX}) l n h n ậ ứ ế ầ m c c n thi t và khi dùng TWU({bX}) đ t a các t p ng ả ẽ viên s không hi u qu .
ừ ữ ề ậ ấ ở T nh ng phân tích
ậ (Candidate Weight Utility) và thu t toán HP khai phá t p l trên, lu n án đ xu t mô hình CWU ậ ợ i
ự ằ ả ố ượ ậ ứ ng t p ng
ích cao d a trên mô hình này nh m gi m s l viên [II].
ề ấ Đ xu t mô hình CWU
ề ể
T nh ng nh n xét trên, lu n án đ xu t mô hình CWU đ ắ ủ ể ừ ữ ụ kh c ph c nh ấ ậ ậ ượ c đi m c a mô hình TWU.
ị ậ [II] T p ti n t Đ nh nghĩa 2.1.
ậ ầ ộ ề ố ủ c a m t ph n t ướ ứ trong t p I mà đ ng tr ầ ử ầ c ph n t ậ It là t p ử It:
ử các ph n t SetPrefix(It) = {j I | j It}.
ị [II] Ti n t ứ ự
1
ộ ậ c a m t t p ph n t ướ ứ ầ ử ầ ử ầ c ph n t có th t đ u tiên y
ề ố ủ Đ nh nghĩa 2.2. ầ ử ậ Y là t p các ph n t trong I đ ng tr ệ ủ ậ c a t p Y, kí hi u là SetPrefix(Y) và
(2.1) SetPrefix(Y) = {j I | j y1}
ị ố ợ Đ nh nghĩa 2.3.
ọ [II] L i ích ng viên có tr ng s (CWU – ầ ử Y, ký hi u là
ượ ư ị Candidate Weighted Utility) c a t p ph n t CWU(Y) đ ứ ủ ậ ệ ặ c xác đ nh nh sau:Đ t X = SetPrefix(Y), thì
(cid:0) ế N u X = thì .
ứ ị Đ nh nghĩa 2.4. ể ợ [II] Khi CWU(Y) α v i ớ α là ng ậ ợ ọ c, ta g i Y là t p l
ậ ợ ượ ứ ọ c g i là t p l i, Y đ
ọ ố ưỡ i ng t ứ ướ i ích ng viên cho tr thi u l i ích ng ố ọ viên có tr ng s cao (HCWU High Candidate Weighted ượ ạ Utility). Ng c l i ích ng viên có ố ấ tr ng s th p (LCWU – Low Candidate Weighted Utility).
k1,Yk
Tính ch t 2.1. ỏ ầ ử ề ố ủ I, Yk (cid:0) ậ [II] Cho 3 t p ph n t I và Yk1 là ti n t
có th t c a Y ề ố ủ ậ ớ ứ ự I, Y ụ ể k. C th : Y c a t p Y
k1 k = k1) =
ớ
ấ k1 (cid:0) th a mãn Y = {y1, y2,…, yk1 | yi yi+1 v i i=1..k2} là ti n t {y1, y2,…, yk1, yk | yi yi+1 v i i=1..k1} thì SetPrefix(Y SetPrefix(Yk).
ầ ử ậ [II] Xét 2 t p ph n t
k1 là t p (k1)ph n t HCWUs.
ầ ử ậ ị Đ nh lý 2.1. ầ ử , Y có th t và là ti n t ứ ự , Y ề ố ủ c a Y ậ k là t p k k. N uế
ph n t Yk (cid:0) HCWUs thì Yk1 (cid:0)
ậ ầ ử Đây là tính ch t đóng c a các t p ph n t theo mô hình
ấ ế CWU. Nghĩa là, n u CWU( ủ Yk1) < thì CWU(Yk) <
ồ ả ử s . [II] Gi Đ nh lý 2.2
α (cid:0) ưỡ HCWUs g m các t p Y có ậ là , HUs g m các t p Y có AU(Y) ướ ồ ể ố ị CWU(Y) ợ ng ng l ậ α ớ v i HCWUs. c. Khi đó HUs i thi u cho tr α i ích t
ố ứ
ể
ẳ
ơ
ị
Đ kh ng đ nh mô hình CWU có s ng viên ít h n mô
ổ ề
ậ
ư hình TWU, lu n án đ a ra hai b đ sau.
ề ệ ấ ỳ ậ . [II] Cho t p b t k Y, ta luôn có CWU(Y) ≤ M nh đ 2.1
TWU(Y).
ề ệ ồ
ậ (cid:0) . [II] Cho HCWUs g m các t p Y có CWU(Y) ồ là các ố ướ ể ợ ậ M nh đ 2.2 và HTWUs g m các t p Y có TWU(Y) ưỡ i thi u cho tr α c, thì HCWUs i ích t ng l α ng α ớ , v i HTWUs.
ậ ự i ích cao d a trên ch ỉ
2.2. Thu t toán HP khai phá t p l ế
ầ ậ
ế ừ ậ ớ ậ ợ ố s hình chi u và mô hình CWU ậ Trong ph n này, lu n án trình bày thu t toán HP đ ủ c a Gou (2013) ượ ả c c i ộ ố ả ế v i m t s c i ti n sau: thu t toán PB ti n t
ế ợ ử ụ S d ng k t h p hai mô hình TWU và CWU;
ầ ử ế S p các ph n t
ố ạ sau khi đã lo i các ph n t ị ừ trong t ng giao d ch gi m d n theo AU ể ưỡ ầ ử ỏ ơ i thi u. ầ i ích t ả ợ ng l nh h n ng
ử ụ ậ cượ s d ng trong thu t toán: ộ ố ấ đ a. M t s c u trúc
ả ứ , l
ọ ố ợ ậ k g m: các t p kph n t i ích th c t ứ ầ ử ợ i ích ng ự ế ủ ậ ứ c a t p ng viên
ồ B ng ng viên TC viên có tr ng s CWU và l AU.
ả
ị ị ấ ệ
X g m kph n t
ỉ ố có th
ậ ứ ồ
ầ ử ồ ỉ ố X c a t p X g m: các giao d ch T ứ ậ ủ ậ j ch a t p B ng ch s IT ủ ậ ầ ử ố ủ cu i cùng c a t p X xu t hi n trong giao X, v trí p c a ph n t ồ ể ầ ử ừ ả ị d ch T j và U(X,Tj). T b ng ch s IT ầ ử ớ ề ố là v i ti n t tính nhanh các t p ng viên g m (k+1)ph n t ậ t p ph n t X.
i ch a giá tr l ị
ị ả ứ
ớ ề ố i ích cao v i ti n t ấ ả ậ ợ t c t p l
i s tính đ
ượ ự ẽ ầ ủ ị ợ i ích c a ph n ứ j). j ch a i và U(i, T ầ ử i thì là ph n t ầ ử ớ i = c CWU(Y) v i ph n t
ợ B ng giao d ch l i ích UT ồ ị ừ ử t i trong t ng giao d ch g m: giao d ch T Sau khi tìm t ả d a vào b ng UT ListItemPrefix(Y).
ệ ế ả ự K t qu th c nghi m
ế ả ử ữ ệ ớ
ậ ộ ữ ệ
K t qu th nghi m, so sánh gi a thu t toán HP v i các ậ thu t toán Two Phase, PB trên b d li u T30I4D100K và Mushroom.
ệ
ượ
Hình 2.. S l
c sinh
ự ờ Hình 2.. Th i gian th c hi n trên T30I4D100K
ố ượ ứ ng ng viên đ ra trên T30I4D100K
ượ
ệ
Hình 2.. S l
ng ng viên đ
c sinh
ố ượ ứ ra trên Mushroom
ự ờ Hình 2.. Th i gian th c hi n trên Mushroom
ậ ợ
ậ
ự i ích cao d a trên ch s
ỉ ố
2.3. Thu t toán song song PPB khai phá t p l
ế
ợ
hình chi u và danh sách l
i ích
ậ ậ ợ Thu t toán song song PPB [V] khai phá t p l
ượ ệ ạ ố
ứ ể
ộ ố ớ i ích cao ề c công b trong t p chí Công ngh Thông tin và Truy n đ ụ ứ thông: “Các công trình nghiên c u, phát tri n và ng d ng CNTTTT" v i m t s đóng góp sau:
ớ ợ
ể i ích đ sinh ứ i ích cao, lo i nhanh các ng viên và
ạ ộ ử ầ ử ừ ả ỉ ố ế ợ Dùng b ng ch s k t h p v i danh sách l ậ ợ ậ ứ t p ng viên, tìm t p l ộ ậ ử đ c l p x lý các ph n t trên t ng b x lý.
ả ượ ư ợ Gi n l ữ c thông tin l u tr trong danh sách l i ích.
ậ ợ ự i ích cao
ậ ẻ ộ Xây d ng thu t toán song song khai phá t p l ớ trên mô hình chia s b nh .
ộ ố ấ ượ ử ụ ồ ậ c s d ng trong thu t toán PPB g m: a. M t s c u trúc đ
ự ế i ích th c t , l
ị ệ ể ộ ầ ậ ồ ầ ử ợ k g m: các t p kph n t AU ạ ủ ứ i c a ng viên – RU. Các giá tr AU, RU trong c tính trong cùng m t l n duy t đ tính TWU,
ả B ng TC ợ i ích còn l và l ượ ả b ng TC 1 đ trong đó RU(X) = TWU(X) – AU(X).
ả ị
ầ ử ủ ậ ố
ị ợ ồ ỉ ố X c a t p X g m: các giao d ch T ủ j; itutil(X, Tj) – giá tr l
ủ ậ ầ ử ị ợ ạ ứ ậ j ch a t p ệ ấ ủ ậ cu i cùng c a t p X xu t hi n trong i ích c a t p X trong giao ậ i sau t p còn l i ích các ph n t
j.
B ng ch s IT ị X; v trí p c a ph n t ị giao d ch T d ch Tị j; rutil(X, Tj) – giá tr l X trong giao d ch Tị
ế ệ ả ự K t qu th c nghi m
ậ ệ ế ả ử
ậ
ưỡ ổ ợ i ích cao khi thay đ i ng
ượ ớ ữ ộ ữ ệ ự ố i ích t c sinh ra t ng ng viên đ
ứ ố i ích t i thi u khác nhau. ự ể ệ
ưỡ ữ ậ
ươ ộ ữ ệ ể ố K t qu th nghi m, so sánh gi a thu t toán PPBMiner ớ v i thu t toán HP [II] trên b d li u T30I4D100K và ậ ệ ờ Mushroom. Hình 2.5 so sánh th i gian th c hi n khai phá t p ể Hình 2.6 so ợ i thi u, l ng l ứ ươ ố ượ ng ng v i các sánh s l ợ ưỡ Hình 2.7 và Hình 2.8 so ng l ng ố ứ ậ ợ ờ i ích cao và s ng sánh th i gian th c hi n khai phá t p l ợ ớ ứ viên sinh ra gi a hai thu t toán t ng ng v i các ng i ng l ích t i thi u khác nhau trên b d li u Mushroom.
ệ
ờ
ượ
Hình 2.. S l
c sinh
ự Hình 2.. Th i gian th c hi n trên T30I4D100K
ố ượ ứ ng ng viên đ ra trên T30I4D100K
ệ
ượ
Hình 2.. S l
ng ng viên đ
c sinh
ự ờ Hình 2.. Th i gian th c hi n trên Mushroom
ố ượ ứ ra trên Mushroom
ậ
2.4. Thu t toán CTUPRO+
ậ
ậ
Thu t toán CTUPRO+ [III] cho khai phá t p l thu t toán CTUPRO ệ ầ ử ụ ậ
ầ ử i thi u trong ph n 2.2. Thu t toán CTUPRO+ s i ích nén, các ph n t
ẫ ợ ể i ích AU đ các ph n t
i ích và đ
ậ ợ i ích cao s d ng mô hình CWU ử ắ trong cây s p ẽ ợ ầ ử i ích cao s có l ượ ướ c. Sau đó, c khai phá tr ủ ợ ừ ậ ạ ằ i ích c a i b ng cách tr đi l
ượ ượ ả ế ừ đ c c i ti n t ớ ượ c gi [II] đ ấ ụ d ng c u trúc cây m u l ợ ầ ế x p tăng d n theo l ề ố ủ ậ ợ c a các t p l là ti n t ẽ ượ ậ ị giá tr CWU s đ c c p nh t l ề ố các ti n t c khai phá. đã đ
ộ ố ấ a. M t s c u trúc
ượ ỉ ố trong CSDL đ c đánh ch s 1, 2, 3,… theo
ầ ử Các ph n t ầ ứ ự th t tăng d n theo AU.
ầ ả
ố ầ ử ứ
ế chung ọ i ích có tr ng s cao đ ả ồ
ị
ng c a ph n t
(item), l ố ượ ố ầ ử i ích th c t
ọ ỏ ỏ ế – GlobalItemTable g mồ ượ ắ c s p ỉ ố ầ ử ợ i ích ầ ử ẫ ợ i
ử B ng ph n t ợ các ph n t ng viên l ầ x p tăng d n theo AU. Trong b ng này g m: ch s ộ ơ ợ ầ ử i ích trên m t đ n v ph n t (index), ph n t ủ ổ (quantity), l (utility), t ng s l ứ ự ế ủ ợ ng viên có tr ng s (CWU), l c a ph n t ố ủ (AU) và con tr tr đ n g c c a nhánh trong cây m u l ích nén chung (GlobalCUPTree).
ủ
ị ợ ớ ng ng v i giá tr l
ố ủ
ứ ồ ch sỉ ố ứ i ích ng ỏ ứ ố ượ ng ỏ ỏ ủ ừ ng ng c a t ng ph n t
ỏ ỏ ế ỗ M i nút c a GlobalCUPTree bao g m: ứ ả ươ (index), m ng CWU t ả ậ ọ viên có tr ng s c a 1 t p, m ng con tr ch a s l ươ ị ầ ử t trong giao d ch, con tr tr ứ ế đ n nút anh em cùng m c, con tr tr đ n nút cha.
ả
M ng CWU[] ủ ậ ế ị = {T0, T1,…, Tn}, trong đó: Ti là ứ ỉ ố ầ ử ừ nút ch s i đ n nút ch a t
giá tr CWU c a t p ph n t Ti.
T p I =
ị ượ ứ
ỉ ố
ẫ ợ
ầ ắ ầ ừ i ích nén, b t đ u t ủ ỏ PST c a ph n t b i con tr c tr
ầ ử ậ ậ ợ {i1, i2,…, in} là t p h p các ph n t ớ ạ ươ ng ng v i các HCWU trong giao d ch đ c ánh x t ỉ ố ch s trong GlobalItemTable sau đó chèn các ch s index ố ủ nút g c c a nhánh vào cây m u l ử 1 trong ỏ ở ượ i cây đ GlobalItemTable.
ả ự
ệ
ế
K t qu th c nghi m
ế ệ ữ
ả ử ậ ậ ề ờ
ệ
ệ
ờ
ự ờ Hình 2.. Th i gian th c hi n trên T5N5D100K
ự Hình 2.. Th i gian th c hi n trên T10N5D100K
ể ợ K t qu th nghi m, so sánh gi a thu t toán CTUPRO+ ớ v i các thu t toán TwoPhase, CTUPRO v so sánh th i gian ự ớ th c hi n trên b d li u T5N5D100K và T10N5D100K v i ưỡ ng ộ ữ ệ ố i thi u khác nhau. ệ ng l i ích t
ươ
Ậ
Ch
ng 3.
Ậ Ợ Ợ
Ệ
Ề
THU T TOÁN KHAI PHÁ T P L I ÍCH CAO TRÊN CÂY DANH SÁCH L I ÍCH VÀ ĐI U KI N RTWU
ữ ệ ậ ợ ả ệ 3.1. C u trúc d li u hi u qu cho khai phá t p l i ích
ấ cao
ậ ậ ợ Trong thu t toán khai phá t p l
ế
ạ ầ ử ẫ trong cây đ ầ c s p x p gi m d n theo TWU nên s
ẽ ế ầ ầ
ế ố ấ ử ụ i ích cao s d ng c u trúc ữ ượ ỉ ư ư ỗ ữ c cây có nh ng h n ch nh m i nút trên cây ch l u tr đ ữ ơ ế ả ộ , d n đ n kh năng nén không cao. H n n a, các m t ph n t ố ả ế ượ ắ ầ ử ph n t ấ ả ơ ắ ề nút trong cây s nhi u h n s p x p gi m d n theo t n su t ữ ư làm t n không gian l u tr và tìm ki m.
ộ ự ậ
ậ ợ ứ
ả ử ụ ợ s d ng c u trúc danh sách l
ấ ủ ậ ầ ử ữ Năm 2012, Liu và c ng s (2012) đã trình bày thu t toán ậ i ích cao không sinh viên ng viên. Trong thu t i ích (utility ắ ỉ và thông tin c t t a thông tin c a t p ph n t
khai phá t p l toán nhóm tác gi ể ư list) đ l u tr không gian tìm ki m. ế
ấ ắ ạ ể ữ
ư ụ
ỗ
ấ
ứ ậ ể ắ ỉ ư ế
ầ ầ
ầ ử ượ ắ đ ấ ố ả ấ ế ế ệ ớ
ậ ế ụ Đ kh c ph c nh ng h n ch trong c u trúc cây và t n ầ ợ ậ ủ ể i ích, trong ph n này lu n án d ng u đi m c a danh sách l ế ợ ẫ ợ ộ ấ i ích nén (CUP) k t h p trình bày m t c u trúc cây m u l ầ ử ợ và danh i ích, trong đó m i nút ch a t p ph n t danh sách l ả ậ ệ ủ ợ i ích c a nó. C u trúc này có th c t t a hi u qu t p sách l ữ ả ứ ng viên làm gi m không gian tìm ki m và l u tr . Trong cây ệ ấ ả các ph n t c s p x p gi m d n theo t n su t xu t hi n, ệ ắ làm gi m s nút xu t hi n trong cây so v i vi c s p x p theo TWU.
ả ấ c u trúc cây CUP a. Mô t
ầ ẽ ậ
ượ ả Trong ph n này, lu n án s trình bày khái ni m, c u trúc ế t ệ c mô t ấ chi ti
ậ ằ ở cây CUP. Quá trình xây d ng cây CUP đ ầ b ng thu t toán ự ố ph n cu i.
ụ ộ Hình 3.. Ví d m t nút trong cây CUP
ả ụ Ví d nh ư Hình 3.1, mô t
ậ
ủ ị ợ
ạ ủ
ộ
ươ ứ ớ trong N.Itemsets t
ỏ ỏ ế ủ
đ n cha c a nút N, N.Links là danh sách con tr ầ ử
đ n các nút có cùng các ph n t ỏ ỏ ế ồ nút N trên cây CUP bao g m: N.Itemset, N.IUtil, N.RUtil, N.TList, N.UList, N.Parent, ầ ử ủ c a N.Links và N.Childs. Trong đó, N.Itemsets là t p ph n t ợ i ích nút, N.IUtil là giá tr l i ích c a N.Itemsets, N.RUTil là l ị còn l i c a N.Itemsets, N.TList là danh sách các giao d ch ủ ừ ợ ứ i ích c a t ng ch a N.Itemsets, N.UList là m t danh sách l ầ ử ng ng v i N.TList, N.Parent là ph n t ỏ con tr tr ỏ ế trong cây, N.Childs là tr ủ danh sách con tr tr đ n các nút con c a nó.
ự ồ ả ư Quá trình xây d ng cây CUP g m các b ướ ượ c đ c mô t nh sau:
ả ể ơ ả ỉ Đ đ n gi n lu n án ch mô t quá trình chèn các ph n t
ậ ầ ị
ầ ả ầ ử vào cây, còn các ph n tính toán các giá tr RUtil, TList, UList ả ẽ ượ s đ trong ph n mô t ậ thu t toán. c mô t
ướ ộ ỗ ợ B c 1, ể ế duy t d li u l n 1 đ đ m đ h tr (support) và
tính TWU cho t ng ph n t ệ ữ ệ ầ ầ ử ừ .
ầ ử ư B
ố có TWU ắ i thi u vào danh sách. Sau đó s p
i ích t ầ ấ ầ ướ ị ệ ừ c 2, duy t t ng giao d ch, đ a các ph n t ể ợ ưỡ ơ ớ l n h n ng ng l ầ ử ả ế x p các ph n t gi m d n theo t n su t.
ướ ự B c 3, xây d ng cây CUP.
ệ
ắ ầ ừ ằ và chèn danh sách ph n t ị này vào cây b t đ u t
ự ư ừ Th c hi n chèn b ng cách l u t ng giao d ch vào danh sách ầ ử ầ ử ph n t nút ư ố g c nh sau:
ể ệ ạ
ớ ki m tra các nút con N c a nút hi n t i và so sánh các trong danh sách chèn còn
ủ ầ ử trong N.Itemset v i các ph n t ả ư ả ướ B c 3.1, ầ ử ph n t ạ ớ l i v i các kh năng x y nh sau:
ế ấ ả ầ ử ố ỉ N u t t c các ph n t gi ng nhau thì ch thêm tid vào
TList.
ế ề ố N u không có 1 ho c nhi u ph n t
ặ ủ ầ ử ầ ệ ạ ồ đ u tiên gi ng nhau i g m: itemsets là các
ớ ạ ạ thì t o nút m i là con c a nút hi n t ầ ử ph n t i trong danh sách. còn l
ộ ề ế ầ ử ầ
ỉ ồ ố khác nhau còn l
ầ ộ ầ ử ủ ố đ u tiên gi ng nhau thì ạ ầ ử i khác nhau
ặ N u có m t ho c nhi u ph n t nút N ch g m ph n gi ng nhau, các ph n t ủ c a nút N thành m t nút con c a nút N, các ph n t ủ c a danh
ậ ợ ậ Thu t toán khai phá t p l i HUIGrowth
ự ượ
ệ ươ ươ ậ ợ Sau khi xây d ng cây CUP thì các t p l ự ng pháp đ quy t ng t
. Quá trình khai phá t p l ự ệ ừ ướ d ầ ộ ầ ố a
ằ ra b ng ph ủ Growth c a Han (2000) ượ c duy t t cây CUP đ ấ Đ u tiên, l y m t ph n t ỏ ự HeaderTable, d a vào con tr liên k t c a a i ích cao đ c tìm ư ậ nh thu t toán FP ậ ợ i ích cao trên ả i lên d a vào b ng HeaderTable. ử i cu i cùng trong b ng ả i để ỏ ế ủ i tr vào nút N
ẫ ệ ế ậ t thu t toán đ ượ c ớ ậ ố i. Chi ti a
ả ề tìm các m u đi u ki n v i h u t ướ i. mô t phía d
ế ệ ả ự K t qu th c nghi m
ậ ầ ế ả ự ệ
ậ
ế
ớ ệ ớ ưỡ ờ ng l
ự
ự
ệ ớ ữ
ệ ớ ữ
ờ ệ
ờ Hình 3.. Th i gian th c hi n v i d ệ li u Mushroom
Hình 3.. Th i gian th c hi n v i d li u T40I4D100K
ộ ữ ệ ậ Trong ph n này, lu n án so sánh k t qu th c hi n thu t toán HUIGrowth [IV] v i thu t toán: UPGrowth, HUI ả ử Miner. K t qu th nghi m, trong Hình 3.2 và Hình 3.3 so ớ ợ ệ ự i ích khác nhau v i sánh th i gian th c hi n v i các ng hai b d li u Mushroom và T40I4D100K.
ỉ ậ ứ
ệ
ề
3.2. Đi u ki n RTWU cho t a t p ng viên
ậ
ố ậ
ấ ủ
ứ ặ ể ế ố ỏ ơ ưỡ ướ ậ ng l
ư
ạ Thu t toán FHM do nhóm FournierViger (2014) đã h n ự ủ ế ch các phép n i có chi phí cao c a thu t toán HUIMiner d a trên tính ch t đóng c a TWU (TransactionWeighted Utility). Đó là, không k t n i các t p sinh ra có ch a c p (x, y) mà ố ợ c. Tuy i thi u cho tr TWU(x, y) nh h n ng i ích t ứ ầ ơ ưỡ nhiên, nh đã phân tích thì TWU là ng ng cao h n m c c n thi t. ế
ể ả
ấ ậ ng pháp c t t a ố ượ Trong thu t toán FHM đ gi m s l ị ợ ắ ỉ ướ ượ ươ ng giá tr l c l
ố ằ ng phép n i b ng ệ ph i ích xu t hi n cùng nhau (EUCP Estimated Utility Cooccurrence Pruning) d aự
ấ ị ợ ướ ượ c l ng giá tr l
ộ
ử ụ ể ư
ữ ấ (a, b) có TWU(ab) nh ậ ợ ể ẽ ợ ầ ử ậ i ích t
ự ầ ử ứ ặ ố i thi u s không ph i là t p l ố ấ ả t c các t p ch a c p ph n t ưỡ ng l ệ ợ ệ ấ trên c u trúc i ích xu t hi n cùng nhau (EUCS Estimated Utility CoOccurrence Structure). M t cách ậ ụ ể ủ c th là thu t toán FHM s d ng EUCS đ l u tr TWU c a ủ ặ ấ ả (a, b). D a vào tính ch t đóng c a t t c các c p ph n t ỏ TWU, t ơ h n ng i ích cao ể ừ đ ng ng vi c ghép n i các danh sách l ả i ích.
ầ ử ượ ắ đ ề ố
ậ ẽ
ể ẫ ử ủ i ích c a ph n t
là ph n t ứ ồ ậ
ậ ợ ậ i ích cao theo Tuy nhiên, thu t toán FHM khai phá các t p l ế ứ ự ừ ả ử ề c s p x p theo th t t s , các ph n t chi u sâu. Gi ầ ử ấ ậ ấ ả ể là ph n t t a, {bX} là t t c các t p có ti n t đi n, {aX} là t ầ ử ứ ậ ư ậ ề ố ả b. Nh v y, các t p ch a c các t p có ti n t ầ ư a. Nh ng khi tính không còn ch a ph n t {bX} s ề ầ ử ị ợ a. Đi u TWU({bX}) có th v n g m giá tr l ủ ứ ơ ớ này làm TWU({bX}) là c n trên c a U({bX}) l n h n m c ẽ ậ ứ ể ỉ ế ầ t và khi dùng TWU({bX}) đ t a các t p ng viên s c n thi ả ệ không hi u qu .
ắ ể ể ậ
ậ ề
ữ ụ Đ kh c ph c nh ng nh ấ ấ ự ầ ự ậ
ấ ậ
ừ ạ ậ ị
ủ ượ c đi m trên c a thu t toán FHM, lu n án đã đ xu t c u trúc RTWU (Retail Transaction EAHUIMiner Weighted Utility), xây d ng thu t toán tu n t ử ụ s d ng c u trúc RTWU và thu t toán song song PEAHUI Miner theo mô hình h t m n (finegrain) t thu t toán EAHUI Miner.
ủ ợ Đ nh nghĩa 3.1.
ầ ử ượ Px ký hi u là exLstPx và đ
ỗ ở ộ ộ i ích m r ng c a m t ộ ị c đ nh nghĩa là m t ố ồ ầ ử bao g m b n , trong đó m i ph n t
ườ ị [VI] Danh sách l ệ ậ t p ph n t ầ ử danh sách các ph n t tr tid, iutil, itemutil và rutil, trong đó: ng:
ứ ủ ị ị tid là đ nh danh c a giao d ch ch a Px.
ợ ầ ử ị iutil là l ủ ậ i ích c a t p ph n t ứ P trong giao d ch tid ch a
Px.
ợ ầ ử ị itemutil là l ủ i ích c a ph n t x trong giao d ch tid
ứ ch a Px.
ợ ạ ủ ầ ử ạ rutil là l i ích còn l i c a các ph n t còn l i trong
ứ ị ầ ử giao d ch tid ch a Px, tính t ừ ầ ử ph n t sau ph n t x.
ợ ở ộ Ngoài ra, danh sách l ủ ậ i ích m r ng c a t p Px còn có các
ườ tr ng sau:
ợ ổ ầ ử ủ ậ i ích c a t p ph n t P trong các
ứ ị sumiutils là t ng l giao d ch tid ch a Px.
ợ ầ ử ủ i ích c a ph n t x trong giao
ổ sumitemutils là t ng l ứ ị d ch tid ch a Px.
ổ ị
ợ ắ ầ ạ ủ i c a giao d ch có th ầ ử ế ế ừ ph n t ứ k ti p sau
ầ ử sumrutils là t ng l i ích còn l ứ ự tid ch a Px, b t đ u tính t t x. ph n t
ị ợ i ích giao d ch còn l [VI] Giá tr lị
Đ nh nghĩa 3.2. ầ ử xy trong giao d ch Tị ị ầ ử xy là t ng l
ạ ị còn l ặ j ch a ứ c p ph n t i trong giao d ch có th t T ạ ủ c pặ i c a ợ ổ i ứ ự j tính từ
j), và
ph n t ầ ử ủ ích c a các ph n t ệ x. ph n t ầ ử Kí hi u là RTWU(xy, T
j ch a c p ph n t
ứ ặ ầ ử
ầ ử ứ ầ ử ướ ỏ trong đó [Tj\ SetPrefix(xy)] – giao d ch Tị x. xy b đi các ph n t c ph n t đ ng tr
[VI] Giá tr l
ị ợ ổ xy trong CSDL là t ng giá tr l
ị i ích giao d ch còn l ị ợ ị ầ ử Đ nh nghĩa 3.3. ầ ử ạ ủ ặ i c a c p ph n t xy trong các giao d ch T ạ ủ i c a ị i ích giao d ch ứ ặ j ch a c p
ầ ử ệ ị ặ c p ph n t còn l ph n t xy trong CSDL. Kí hi u là RTWU(xy) và
ấ ượ [VI] C u trúc RTWU đ ằ ị c xác đ nh b ng
ị Đ nh nghĩa 3.4. ộ ậ ộ m t t p các b ba: (x; y; c) I x I x R.
Trong đó:
ầ ử ậ I là t p các ph n t ộ ơ ở ữ ệ thu c c s d li u;
ứ ướ thu c I (x đ ng tr ộ c y theo m t
ầ ử ộ x, y là 2 ph n t ế ắ cách s p x p nào đó);
ậ ố ự R là t p s th c và c = RTWU(xy).
ị ở ộ
ợ ậ ở ộ ủ ậ ầ ượ
ế
ậ ợ ở ộ ủ ề [VI] Cho hai t p Px, Py là m r ng c a t p P Đ nh lý 3.1. ủ i ích m r ng c a Px và Py l n l t là và hai danh sách l exLstPx và exLstPy. N u min(exLstPx.sumiutls, exLstPy.sumiutls) + RTWU(xy) < minUtil thì Pxy và các các ậ t p m r ng c a nó đ u là các t p l ấ . i ích th p
ị ấ ả ế ậ ậ ự Đ nh lý 3.1 , lu n án đ xu t c i ti n thu t toán
ở ế ầ D a trên ự ấ FHM d a trên c u trúc RTWU, đ ph n ti p. ề ượ c trình bày
ầ ự ề 3.3. Thu t toán tu n t ệ ự EAHUIMiner d a trên đi u ki n
ậ RTWU ậ ầ ồ Trong thu t toán EAHUIMiner g m 2 ph n chính:
ự ợ ở ộ Xây d ng danh sách l i ích m r ng
ậ ợ Khai phá t p l i ích cao EAHUIMiner
ở ộ ứ
ự ớ ậ ỗ ị ầ ử ượ ủ ậ i ích m r ng c a t p ch a 1 ph n t đ c Đ nh nghĩa 3.1 v i t p P là r ng (nghĩa là
ợ Danh sách l xây d ng theo iutil=0) khi quét CSDL l n 1.ầ
ậ 3.3.1. Thu t toán song song PEAHUIMiner
ượ ự Thu t toán PEAHUIMiner đ
ỗ ợ ậ l p trình song song trên môi tr ộ ng b nh
ả ộ
ả ằ ả ề ả c xây d ng trên n n t ng ở ườ ạ i đ ng theo mô hình h t ữ i gi a các
ị ế ậ OpenMP h tr ậ ẻ chia s . Thu t toán song song phân t ằ m n (finegrain) nh m nâng cao kh năng cân b ng t ti n trình.
ả ự ệ ế 3.3.2. K t qu th c nghi m
ả ố ượ ứ S l
ng ng viên: ậ
B ng 3.1 th hi n s l ế ệ ể ệ ố ượ ấ ớ ề ậ ứ ả ơ
ậ ứ ng t p ng ậ viên do hai thu t toán sinh ra. K t qu cho th y thu t toán ậ FHM sinh ra nhi u t p ng vi n h n so v i thu t toán EAHUIMiner.
FHM
ố ượ ậ ứ B ng 3.. So sánh s l ng t p ng viên.
minutil 2500 2500 1000 100K
153.016 153.016 259.876 1.588.018
EAHUIMiner 125.647 125.647 258.921 1.587.927
ự
ờ
ệ Th i gian th c hi n
ả Dataset 10I4D100K 10I4D100K Foodmart Mushroom
ờ ậ ệ ủ
ể ế ậ
ự
ệ ấ ầ ử ỏ ự Th i gian th c hi n c a các thu t toán: EFIM, FHM và ượ Hình 3.4, Hình 3.5, c th hình trên các EAHUIMiner đ ấ ả Hình 3.6 và Hình 3.7. K t qu này cho th y, thu t toán EFIM ướ ủ ơ ở ữ ệ th c hi n r t nhanh trên các c s d li u mà kích th c c a ậ ậ I nh , còn hai thu t toán FHM và EAHUIMiner t p ph n t
ệ ự
ệ
ệ
ự ờ Hình 3.. Th i gian th c hi n trên Mushroom.
ự ờ Hình 3.. Th i gian th c hi n trên Foodmart
ệ
ệ
ự ờ Hình 3.. Th i gian th c hi n trên T10I4D100K
ự ờ Hình 3.. Th i gian th c hi n trên T10I4D200K
ự
ữ
ệ
ậ
ờ
Hình 3.8 và Hình 3.9 so sánh th i gian th c hi n gi a thu t toán tu n t
ầ ự
ậ
ơ ở ữ ệ EAHUIMiner và thu t toán song song PEAHUIMiner trên c s d li u
T10I4D100K, T10I4D200K.
ướ ậ ơ ở ữ ệ th c hi n nhanh h n thu t toán EFIM trong các c s d li u I l n. mà kích th ậ ơ ầ ử ớ c t p ph n t
ệ
ệ
ự ờ Hình 3.. Th i gian th c hi n trên T10I4D100K
ự ờ Hình 3.. Th i gian th c hi n trên T10I4D200K
Ậ
Ế
Ế
Ị K T LU N VÀ KI N NGH
ủ ế ậ ả K t qu chính c a lu n án:
ớ ụ ấ
ằ ữ ệ ậ ậ ả
ạ ượ ậ ợ ọ ự ệ ậ i ích cao. Lu n án đã đ t đ
ả ậ V i m c tiêu xây d ng mô hình, c u trúc d li u và thu t ổ ế toán nh m nâng cao hi u qu thu t toán khai phá t p ph bi n ế ố có tr ng s và t p l c các k t qu chính sau:
ợ ứ ố ọ 1. Mô hình l i ích ng viên có tr ng s (CWU –
ự Candidate Weighted Utility) [II] d a trên phân tích cho
ấ ằ ượ ề ậ th y r ng mô hình TWU đ ử ụ c nhi u thu t toán s d ng
ể ắ ỉ ứ ệ ả đ c t t a ng viên là không hi u qu vì đánh giá ng ưỡ ng
ị ợ ề ơ ớ ự ế ừ cao h n nhi u so v i giá tr l i ích th c t . T mô hình
ậ ợ ề ấ ậ CWU đ xu t hai thu t toán khai phá t p l i ích cao là
ử ụ ỉ ố HP [II] s d ng ch s hình chi u ế , CTUPRO+ [III] sử
ố ượ ụ ấ ứ ơ d ng c u trúc cây cho s l ờ ng ng viên ít h n và th i
ộ ố ự ệ ậ ơ ớ gian th c hi n nhanh h n so v i m t s thu t toán.
ấ 2. C u trúc RTWU ( Remaining Transaction
ị ợ ự ị Weighted Utility) d a trên giá tr l i ích giao d ch còn l ạ i
ợ ủ ặ ở ộ ầ ử ế ợ ớ k t h p v i danh sách l i ích m r ng c a c p ph n t cho
ậ ắ ỉ ậ ứ c t t a t p ng viên. Phân tích thu t toán FHM [26] cho
ế ố ể ấ ả ợ th y đ làm gi m chi phí k t n i (join) danh sách l i ích
ủ ặ ầ ử ư ữ ị ự d a vào l u tr giá tr TWU c a c p ph n t . Tuy nhiên,
ượ ả mô hình TWU đ ắ ỉ ệ c đánh giá không hi u qu cho c t t a
ứ ậ ả ề ấ ấ ng viên. Do đó, lu n án đ xu t c u trúc RTWU làm gi m
ế ố ậ ứ ự ấ chi phí k t n i và t p ng viên. D a trên c u trúc RTWU,
ầ ự ậ ề ấ đ xu t thu t toán tu n t ậ EAHUIMiner [VI] khai phá t p
ậ ợ l i ích cao và thu t toán song song PEAHUIMiner [VI] khai
ậ ợ ả ự ế ệ phá t p l i ích cao cho k t qu th c nghi m có s l ố ượ ng
ự ệ ơ ờ ơ ậ ứ t p ng viên ít h n và th i gian th c hi n nhanh h n khi c ơ
ư ề ị ở ữ ệ s d li u th a và nhi u giao d ch.
ậ ợ ậ 3. Thu t toán song song PPB khai phá t p l i ích
ế ợ ỉ ố ế ợ cao k t h p ch s hình chi u, danh sách l ộ i ích và m t
ươ ư ữ ị ợ ầ ử ph ng pháp l u tr giá tr l ủ i ích c a ph n t trên các
ể ị giao d ch đ tính nhanh giá tr ị iutil và rutil trong danh sách
ợ l i ích.
ẫ ợ ấ 4. C u trúc cây m u l i ích nén (CUP ế ợ ) k t h p
ớ ợ ư ỗ v i danh sách l i ích [IV]. M i nút trên cây CUP l u tr ữ
ầ ử ợ ủ ậ t p ph n t và danh sách l i ích c a nó. Các ph n t ầ ử
ượ ắ ế ệ ả ầ ầ ấ ấ đ c s p x p gi m d n theo t n su t xu t hi n cho s ố
ậ ợ ể ấ nút trên cây là ít nh t. Đ khai phá t p l i ích cao trên cây
ề ậ ấ ậ CUP, lu n án đ xu t thu t toán HUIGrowth [IV].
ậ ậ 5. ổ ế Thu t toán VMWFP [I] khai phá t p ph bi n
ừ ự ấ ậ ợ l i ích cao d a trên c u trúc diffset. T thu t toán
ấ ằ ớ VMWFP cho th y r ng các nhóm, l p các nhóm có th x ể ử
ộ ậ ề ậ ậ ấ lý đ c l p nhau. Do đó, lu n án đ xu t thu t toán song
ẻ ộ ớ song PVMWFP [I] trên mô hình chia s b nh .
ướ ể H ng phát tri n
ọ ậ
ố ổ ế ướ ậ Lu n án t p trung vào b ậ ậ ế ợ
ấ ụ ể ề ấ
ọ
ữ ớ
ổ ế ị ứ ạ ợ ữ ệ ấ ầ ậ ậ ậ
ướ ứ ấ c quan tr ng nh t trong khai phá ậ ợ ọ i lu t k t h p là khai phá t p ph bi n có tr ng s và t p l ậ ích cao. C th , đ xu t các mô hình, c u trúc, thu t toán ậ ố ậ ầ ự và song song khai phá t p ph bi n có tr ng s và t p tu n t ố ơ ở ữ ệ ợ i ích cao trên c s d li u giao d ch. Tuy nhiên, kh i l ượ ng d li u ngày càng l n và ph c t p, c n có nh ng có l ữ ẽ nh ng c u trúc và thu t toán phù h p. Do v y, lu n án s ế ụ ti p t c các h ng nghiên c u sau:
ứ ấ
ậ ả ố ọ
(cid:0) Nghiên c u các mô hình, c u trúc và thu t toán ậ ậ ợ ổ ế ệ hi u qu khai t p ph bi n có tr ng s và t p l i ích cao.
ữ ệ ậ ờ ư (cid:0) Đ a k thu t khai phá d li u m vào các thu t ậ
ề ấ ỹ toán đã đ xu t.
(cid:0) ặ ệ ử ậ
ữ ệ ớ ữ ề ả Cài đ t, th nghi m các thu t toán trên n n t ng ậ l p trình Hadoop và mô hình MapReduce cho nh ng bài toán d li u l n.
