Báo cáo nghiên cứu khoa học: "Một thuật toán khai phá tập mục lợi ích cao trong cơ sở dữ liệu"

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

127
lượt xem 19
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tuyển tập các báo cáo nghiên cứu khoa học của trường đại học huế đề tài: Một thuật toán khai phá tập mục lợi ích cao trong cơ sở dữ liệu...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: "Một thuật toán khai phá tập mục lợi ích cao trong cơ sở dữ liệu"

T P CHÍ KHOA H C, ð i h c Hu , S 65, 2011 M T THU T TOÁN KHAI PHÁ T P M C L I ÍCH CAO TRONG CƠ S D LI U Nguy n Phúc Xuân Quỳnh Trư ng ð i h c Sư Ph m, ð i h c Hu TÓM T T Khai phá t p m c l i ích cao (high-utility itemset) là m t m r ng c a bài toán khai phá t p m c ph bi n, ñã ñư c nhi u tác gi quan tâm v i m c ñích ñánh giá ý nghĩa c a các t p m c trong khai phá lu t k t h p. Thu t toán hai pha (Two-Phase) là m t trong các thu t toán khai phá t p m c l i ích cao. Bài báo này ñ xu t m t c i ti n c a thu t toán Two-Phase. Vi c c i ti n ñư c th c hi n thông qua chi n lư c t a hi u qu hơn các t p m c ng c , c i ti n bư c sinh t p ng viên, nh ñó gi m b t ñư c th i gian th c hi n thu t toán khai phá. 1. ð t v n ñ Khai phá tri th c t d li u là m t trong nh ng v n ñ nh n ñư c nhi u s quan tâm c a các nhà nghiên c u. Trong lĩnh v c này, bài toán khai phá lu t k t h p ñư c nghiên c u r ng rãi. M t hư ng m r ng bài toán là quan tâm ñ n các t p m c ñem l i l i ích cao, quan tâm ñ n m c ñ quan tr ng khác nhau c a các m c d li u. Mô hình khai phá t p m c l i ích cao ñã ñư c Yao và c ng s ñ xu t [7]), t ñó ñã có m t s thu t toán khai phá t p m c l i ích cao ñư c ñưa ra trong [1, 2, 5, 6]. Y.Liu, Liao, Choudhary, 2005 [5] ñã ñưa ra khái ni m l i ích c a giao tác và l i ích c a t p m c tính theo l i ích c a giao tác ch a nó (l i ích twu), t ñó ñ xu t thu t toán Two-Phase [5] khai phá t t c các t p m c l i ích cao, tuy nhiên m t nhi u th i gian trong vi c sinh ng viên v i cơ s d li u l n. V n ñ c a các thu t toán khai phá t p m c l i ích cao là gi m thi u kích thư c c a t p ng viên và ñơn gi n hóa quá trình tính toán l i ích các t p m c. Nh m gi m s lư ng ng viên cho t p m c l i ích cao, gi m th i gian khai phá, bài báo ñ xu t thu t toán Im-Two-Phase trên cơ s c i ti n bư c sinh t p ng viên và tính giá tr twu. 2. Các khái ni m và ñ nh nghĩa cơ b n Ph n này trình bày các ñ nh nghĩa, tính ch t cơ b n v t p m c l i ích cao t [5, 6, 7]. ð nh nghĩa 2.1: Giá tr khách quan c a m c t i m t giao tác M i m c ip trong giao tác Tq, ñư c ñ t tương ng v i m t giá tr ñư c g i là giá tr khách quan (objective value) c a m c ip t i giao tác Tq, ký hi u o(ip, Tq). Ch ng h n, 167
giá tr khách quan c a m c ip trong giao tác Tq có th l y là s ñơn v m c ip bán ñư c trong giao tác Tq (Giá tr xác ñ nh b i c t ch a m c ip và hàng Tq trong CSDL giao tác). B ng 1. CSDL giao tác A B C D E F G T1 0 0 0 4 1 0 0 T2 0 5 0 5 1 0 0 T3 1 0 0 6 0 8 0 T4 10 0 5 0 1 0 0 T5 0 4 17 5 1 1 0 T6 0 0 0 0 0 0 72 ð nh nghĩa 2.2: Giá tr ch quan c a m t m c M i m c ip trong CSDL ñư c ñ t tương ng v i m t giá tr , ñư c g i là giá tr ch quan (subjective value) c a m c ñó, ký hi u s(ip). Giá tr này ñư c cho trong m t b ng kèm theo v i CSDL giao tác g i là b ng l i ích. Ch ng h n, giá tr ch quan c a m c ip d a trên ñánh giá l i nhu n c a m i ñơn v m c d li u ñem l i. B ng 2. B ng l i ích Mc A B C D E F G L i nhu n ($/ñơn v ) 1 3 1 4 7 2 1 L i ích c a m t t p m c ñư c ñánh giá qua hàm 2 bi n như sau: ð nh nghĩa 2.3: Hàm l i ích G i x là giá tr khách quan c a m t m c trong m t giao tác và y là giá tr ch quan c a m t m c. M t hàm 2 bi n f ( x, y ) = R x R R ñơn ñi u tăng theo x và y g i là hàm l i ích, thông thư ng hàm l i ích ñư c xác ñ nh f ( x, y ) = x × y . ð nh nghĩa 2.4: L i ích c a m t m c t i m t giao tác Cho hàm l i ích f ( x, y ) . L i ích c a m c i p t i giao tác Tq , ký hi u u( i p , Tq ) là giá tr c a hàm f ( x, y ) t i o(i p , Tq ) và s (i p ) , t c là: u (i p , Tq ) = f ( o(i p , Tq ) , s (i p ) ). ð nh nghĩa 2.5: L i ích c a m t t p m c t i giao tác Cho t p m c X ⊆ Tq . L i ích c a t p m c X t i giao tác Tq , ký hi u u ( X , Tq ) , là t ng l i ích c a t t c các m c i p thu c X t i giao tác Tq : u( X , Tq ) = ∑ u(i p , Tq ) v i i p ∈X X ⊆ Tq . 168
Ký hi u db X = { q | X ⊆ Tq , Tq ∈ DB} là t p các giao tác ch a t p m c X trong T CSDL DB. ð nh nghĩa 2.6: L i ích c a m t t p m c trong CSDL L i ích (hay còn g i là l i ích th c s ) c a t p m c X trong CSDL DB, ký hi u u(X), là t ng l i ích c a t p m c X t i các giao tác thu c dbx : ∑ u( X , Tq ) = ∑ ∑ u(i p , Tq ) u( X ) = Tq ∈dbX Tq ∈dbX i p ∈X ð nh nghĩa 2.7: L i ích c a m t giao tác L i ích c a giao tác Tq , ký hi u tu( Tq ), là t ng l i ích c a t t c các m c d li u trong giao tác: tu( Tq )= ∑ u(i p , Tq ) . i p ∈Tq ð nh nghĩa 2.8: Giá tr l i ích t i thi u Giá tr l i ích t i thi u (minutil) là tích c a ngư ng l i ích t i thi u δ v i t ng l i ích c a toàn b CSDL. ð nh nghĩa 2.9: T p m c l i ích cao T p m c X là t p m c l i ích cao n u u(X) ≥ minutil (minutil>0). ð nh nghĩa 2.10: Bài toán khai phá t p m c l i ích cao Bài toán khai phá t p m c l i ích cao là bài toán tìm t p t t c các t p m c l i ích cao HU = {X | X ⊆ I , u( X ) ≥ min util} v i CSDL giao tác DB và ràng bu c minutil cho trư c. ð nh nghĩa 2.11: L i ích kéo theo c a t p m c (Transaction Weighted Utility – TWU) Cho t p m c X và dbX là t p t t c các giao tác ch a X. Ta g i t ng l i ích c a t t c các giao tác trong dbX là l i ích kéo theo (l i ích twu) c a X. Ký hi u l i ích kéo theo c a X là twu(X), ta có: ∑ tu(Tq ) = ∑ ∑ u(i p , Tq ) twu(X)=tu(dbX)= Tq ∈db X Tq ∈dbX i p ∈Tq Ví d : Trong ví d b ng 2.1 và b ng 2.2, X={B, D, E}. Có 2 giao tác ch a X là T2 và T5. twu(BDE)= tu(T2)+tu(T5)= (o(B,T2)*s(B,T2)+o(D,T2)*s(D,T2)+o(E,T2)*s(E,T2))+ (o(B,T5)*s(B,T5)+o(C,T5)*s(C,T5)+o(D,T5)*s(D,T5)+o(E,T5)*s(E,T5))+o(F,T5)*s 169
(F,T5)) = (5.3+5.4+1.7)+(4.3+17.1+5.4+1.7+1.2)=42+58=100. ð nh nghĩa 2.12: T p m c có l i ích kéo theo cao Cho giá tr l i ích t i thi u minutil>0, t p m c X là t p m c có l i ích kéo theo cao (hay còn g i là kéo theo cao) n u twu(X) ≥ minutil. ð nh lý 2.1: Tính ch t ph n ñơn ñi u c a l i ích kéo theo Cho Xk là m t k-t p m c, Xk-1 là m t (k-1)-t p m c con c a Xk (Xk-1 ⊂ Xk). N u Xk có l i ích kéo theo cao thì Xk-1 cũng có l i ích kéo theo cao. Ch ng minh: Vì Xk-1 ⊂ Xk, nên dbXk ⊆ dbXk-1. Theo công th c tính twu ñ nh nghĩa 2.11: twu(Xk-1)= ∑ tu(Tq ) ≥ ∑ tu(Tq ) =twu(Xk) k −1 k Tq∈dbX Tq∈dbX Do ñó n u twu(Xk) ≥ minutil thì twu(Xk-1) ≥ minutil. Nh n xét: Tính ch t ph n ñơn ñi u c a l i ích kéo theo có nghĩa là n u m t k- t p m c Xk có ch a t p m c con Xk-1 mà Xk-1 là t p m c có l i ích kéo theo th p thì Xk cũng là t p m c có l i ích kéo theo th p. Các ng viên k-t p m c l i ích kéo theo cao ch có th có ñư c t các k t n i c a các (k-1)-t p m c có l i ích kéo theo cao. D a vào nh n xét này, có th s d ng các phương pháp khai phá t p m c ph bi n ñ tìm các t p m c l i ích twu cao. ð nh lý 2.2: N u X là t p m c l i ích cao thì X cũng là t p m c có l i ích kéo theo cao. Ch ng minh: Vì u(X, Tq) ≤ tu(Tq) nên u(X) = ∑ u( X , Tq ) ≤ ∑ tu(Tq ) = twu(X) Tq ∈db X Tq ∈db X V y, n u u(X) ≥ minutil thì twu(X) ≥ minutil. 3. Thu t toán Im-Two-Phase 3.1. Cơ s lý thuy t Trong thu t toán Two-Phase [5], giá tr twu ñư c so v i minutil ñ sinh t p ng viên cho t p m c l i ích cao. Tuy nhiên, trong bư c tìm ra các 1-t p m c có l i ích twu cao, nh n xét r ng các 1-t p m c có l i ích twu th p không tham gia vào quá trình sinh t p ng viên cho t p m c l i ích cao (theo ñ nh lý 2.1 và 2.2) nên có th b ñi các 1-t p m c này trong t ng giao tác. T ñó, giá tr tu s tr ñi các giá tr l i ích c a 1-t p m c l i ích th p, làm giá tr twu gi m ñi so v i giá tr twu ban ñ u, thu g n các ng viên hơn khi so v i minutil. C th , sau khi ñã có t p WHU1 như trong thu t toán Two-Phase, sau khi ñã có 170
t p WHU1, duy t CSDL l n n a ñ b ñi các 1-t p m c l i ích th p trong t ng giao tác và c p nh t l i ích tu c a t ng giao tác: for m i giao tác T ∈ DB B ñi các m c X ∈ T \WHU1; ∑ u( X , T ) ; C p nh t l i ích tu(T):=tu(T) - X ∈T \ WHU 1 Thu t toán gi l i các câu l nh còn l i như c a thu t toán Two-Phase, tuy nhiên c i ti n bư c n i trong quá trình sinh ng viên cho t p Ck t t p WHUk-1: Thay vì n i hai (k-1)-t p m c trong WHUk-1 v i nhau ñ t o ng viên cho t p Ck như trong thu t toán Two-Phase, thì thu t toán Im-Two-Phase s n i m t (k-1)-t p m c trong WHUk-1 v i 1-t p m c trong WHU1 giúp th i gian th c hi n c a thu t bư c n i ñư c gi m xu ng. M nh ñ 2.1: ð ph c t p c a bư c n i trong bư c sinh ng viên Ck trong thu t k −1 2 toán Two-Phase là O( k (Cm ) ). Ch ng minh: Trong thu t toán Two-Phase, n i hai (k-1)-t p m c trong WHUk-1: s t p m c k −1 trong WHUk-1 t i ña là C m , v i m là s m c. S kh năng ch n 2 t p m c ra t 2 WHUk-1 là C C k − 1 . Khi xét hai (k-1)-t p m c này c n t i ña (k-1) phép so sánh, do ñó m 2 t ng s phép tính là: (k-1) C C k − 1 . Ta có: m Cm−1! Cm−1(Cm−1 − 1) k k k 2 ≈ k .(Cm−1 )2 k (k-1). C C k − 1 = (k-1). = (k-1). 2! (Cm−1 − 2)! k 2 m M nh ñ 2.2: ð ph c t p c a bư c n i c a hàm Im_Gen_Ck trong thu t toán k −1 Im-Two-Phase là O(m. C m ). Ch ng minh: Trong thu t toán Im-Two-Phase, n i m t (k-1)-t p m c trong WHUk-1 v i 1-t p k −1 m c trong WHU1: WHU1 có t i ña m t p m c, WHUk-1 có t i ña C m ph n t , thu t toán ch n m t (k-1)-t p m c trong WHUk-1 v i 1-t p m c trong WHU1, khi n i c n 1 k −1 phép so sánh, nên t ng s phép tính: 1.m. C m , do ñó ñ ph c t p c a thu t toán này k −1 là: O(m. C m ). Như v y, thu t toán Im-Two-Phase ñã gi m th i gian bư c n i sinh t p ng viên 171
k −1 Ck t O(k. ( C m − 1 ) 2 ) trong thu t toán Two-Phase xu ng còn O(m. C m k ). 3.2. N i dung thu t toán Input: CSDL giao tác, giá tr l i ích t i thi u minutil. Output: T p HU g m các t p m c l i ích cao. Method: Các ký hi u: Ck: T p các ng viên k-t p m c có l i ích twu cao. WHUk: T p các k-t p m c có l i ích twu cao. WHU: T p t t c các t p m c có l i ích twu cao. HUk: T p các k-t p m c có l i ích cao. HU: T p t t c các t p m c có l i ích cao. N i dung thu t toán: // Pha 1: Phát hi n các t p m c có l i ích twu cao for m i giao tác T ∈ DB 1. 2. Tính l i ích tu(Tq); 3. k=1; WHU=φ; 4. WHU1={i / i ∈ I, twu(i) ≥ minutil}; 5. for m i giao tác T ∈ DB 6. B ñi các m c X ∈ T \WHU1; 7. ∑ u( X , T ) ; 8. C p nh t l i ích tu(T):=tu(T) - X ∈T \ WHU 1 WHU1={i / i ∈ I, twu(i) ≥ minutil}; //C p nh t l i các ph n t cho WHU1 9. 10. WHU=WHU1; 11. for (k=2; Ck-1≠ φ; k++) 12. Ck = Im_Gen_Ck(WHUk-1); // T o các t p m c ng viên bư c k for m i giao tác T∈DB 13. for m i ng viên c∈Ck 14. If c ⊆ T then 15. 16. twu(c)=twu(c)+tu(T); WHUk={c∈Ck | twu(c)≥minutil}; //L c các k-t p m c có l i ích 17. twu cao WHU=WHU ∪ WHUk; 18. // Pha 2: Phát hi n các t p m c có l i ích cao 19. HU= ∅ ; 172
for m i giao tác T∈DB 20. for m i ng viên w∈WHU 21. If w ⊆ T then 22. 23. u(w)=u(w)+u(w,T); HU={w∈WHU | u(w)≥minutil}; //Tuy n ch n các t p m c l i ích cao 24. Hàm Im_Gen_Ck: Input: T p các (k-1)-t p m c có l i ích kéo theo cao WHUk-1 (Các m c trong t ng ph n t ñư c s p x p theo th t t ñi n). Output: T p các ng viên k-t p m c có l i ích kéo theo cao Ck. Method: //Bư c k t n i C k= ∅ ; 1. for m i (k-1)-t p m c X ∈ WHUk-1 2. for m i 1-t p m c Y ∈ WHU1 3. if X[k-1]
WHU1={B:100, C:75, D:164, E:123, F:116, G:72} - Câu l nh 6-8: B ng 4. K t qu th c hi n câu l nh 6 - 8 B C D E F G tu T1 0 0 4 1 0 0 23 T2 5 0 5 1 0 0 42 T3 0 0 6 0 8 0 40 T4 0 5 0 1 0 0 7 T5 4 17 5 1 1 0 58 T6 0 0 0 0 0 72 72 - Câu l nh 9-10: WHU=WHU1={B:100, D:163, E:123, F:105, G:72} - Câu l nh 11-18: Nh n ñư c các t p v i các giá tr twu tương ng + Bư c k=2 C2={BD:100, BE:100, BF: 58, BG:0, DE:123, DF:98, DG:0, EF: 58, EG:0, FG:0} WHU2={BD:100, BE:100, DE:123, DF:98} WHU={B:100, D:163, E:123, F:105, G:72, BD:100, BE:100, DE:123, DF:98} + Bư c k=3 C3= {BDE:100} WHU3={BDE:100} WHU={B:100, D:163, E:123, F:105, G:72, BD:100, BE:100, DE:123, DF:98, BDE:100}. - Câu l nh 19-24: Có ñư c t p HU v i giá tr l i ích th c s tương ng: HU={D:80, G:72, DE:77, BDE:81} * K t qu th c hi n thu t toán Two-Phase: WHU1={B:100, C:75, D:164, E:123, F:116, G:72} C2= {BC:58, BD:100, BE:100, BF: 58, BG:0, CD:58, CE:75, CF:58 , CG:0 , DE: 123, DF:99, DG:0 , EF:58, EG:0 , FG:0} WHU2= {BD:100, BE:100, CF:75, DE:123, DF:99} C3= {BDE:100} WHU3= {BDE:100} 174
WHU={B:100, C:75, D:164, E:123, F:116, G:72, BD:100, BE:100, CF:75, DF:99, DE:123, DF:100, BDE:100} HU={D:80, G:72, DE:77, BDE:81} * So sánh s lư ng ph n t c a các t p ng viên: B ng 5. So sánh s lư ng ph n t c a các t p c a hai thu t toán WHU1 C2 WHU2 C3 WHU3 WHU Two-Phase 6 15 5 1 1 12 Im-Two-Phase 5 10 4 1 1 10 Như v y, v i thu t toán Im-Two-Phase, s lư ng ng viên ñư c thu g n bư c sinh t p Ck và t p WHUk c a t ng bư c, n u bư c k-1 sinh càng ít ng viên thì th i gian th c hi n bư c k s nhanh hơn và ng viên cho bư c ti p theo s ít hơn, giúp thu t toán th c hi n nhanh hơn. S ph n t trong t p WHU càng ít thì s ti t ki m th i gian tính toán l i ích th c s c a các t p m c hơn do s lư ng các t p m c c n tính l i ích th c s s ít hơn. 3.4. Nh n xét thu t toán Thu t toán s ph i duy t CSDL thêm m t l n so v i thu t toán Two-Phase ñ tính l i giá tr tu và b ñi các 1-t p m c có l i ích twu th p. Tuy nhiên th i gian duy t CSDL thêm m t l n không nh hư ng ñ n hi u năng c a thu t toán trong các CSDL l n do v n ñ sinh t p m c ng viên và tính toán l i ích c a các t p m c m i th c s nh hư ng ñ n th i gian th c hi n c a các thu t toán. M c dù thêm m t l n duy t trư c khi sinh ng viên, tuy nhiên ñi u này làm gi m s lư ng ng viên các bư c sau, nên s gi m s l n duy t CSDL sau này ñ tính l i ích c a các t p m c. N u không thêm l n duy t trư c khi sinh ng viên thì s lư ng ng viên các bư c sau s nhi u hơn và s l n duy t CSDL các bư c sau s nhi u, nh hư ng ñ n th i gian th c hi n c a thu t toán. N u CSDL càng ch a nhi u 1-t p m c có l i ích twu th p thì khi c p nh t giá tr tu b ng cách tr ñi l i ích c a các 1-t p m c có l i ích th p s thu g n ñáng k t p ng viên, gi m các bư c sinh ng viên hơn. k −1 2 Thu t toán ñã gi m th i gian sinh t p ng viên Ck t O( k (Cm ) ) xu ng còn k −1 O(m. C m ). 3.5. Th c nghi m thu t toán Chương trình ñư c cài ñ t b ng ngôn ng Visual C++ 6.0 trên h ñi u hành Windows XP, ch y trên máy tính PC v i Pentium dual core 2.0 GHz CPU, 1GB RAM. K t qu th c nghi m ñư c th trên CSDL th c (Retail) và CSDL nhân t o (T5I200D50K, T5I500D100K). Vì t t c các CSDL này dùng cho vi c khai phá t p m c 175
ph bi n, nên chúng tôi thêm vào s lư ng các m c d li u và giá tr l i ích cho m i m c d li u. B ng 6. ð c ñi m các t p d li u th nghi m T p d li u S giao tác S m c d li u ð dài trung bình giao tác Retail 88.162 16.470 9,79 T5I500D100K 100.000 500 7,62 T51000D100K 100.000 1000 10,1 D a vào k t qu so sánh th i gian th c hi n c a hai thu t toán v i s thay ñ i ngư ng l i ích trên ba CSDL trên, nh n th y r ng thu t toán Im-Two-Phase th c hi n nhanh hơn thu t toán Two-Phase, ñ c bi t khi ngư ng l i ích càng nh . B ng 7. Th i gian th c hi n (giây) c a hai thu t toán v i CSDL Retail Ngư ng l i ích (%) 3 5 8 10 12 Two-phase 22,9 6,17 3,38 3,02 2,72 Im-Two-phase 2,8 0,69 0,32 0,35 0,43 Hình 1. So sánh th i gian th c hi n (giây) c a hai thu t toán v i CSDL Retail B ng 8. Th i gian th c hi n (giây) c a hai thu t toán v i CSDL T5I500D100K Ngư ng l i ích (%) 3 5 8 10 12 Two-phase 305,76 39,49 17,72 8,5 6,02 Im-Two-phase 60,1 8,34 3 1,37 0,59 176
Hình 2. So sánh th i gian th c hi n (giây) c a hai thu t toán v i CSDL T5I500D100K B ng 9. Th i gian th c hi n (giây) c a hai thu t toán v i CSDL T5I1000D100K Ngư ng l i ích (%) 3 5 8 10 12 Two-phase 828,85 33,26 0,41 0,17 0,39 Im-Two-phase 1,3 0,35 0,34 0,33 0,33 Hình 3. So sánh th i gian th c hi n (giây) c a hai thu t toán v i CSDL T51000D100K 4. K t lu n Trên cơ s thu t toán Two-Phase, bài báo ñã ñ xu t m t c i ti n thông qua chi n lư c t a hi u qu hơn các t p m c ng c , c i ti n bư c sinh t p ng viên, nh ñó gi m b t ñư c th i gian th c hi n thu t toán khai phá. Chúng tôi ñã cài ñ t th nghi m v i m t s CSDL l n, c CSDL th c (Retail) và CSDL nhân t o (T5I200D50K, 177
T5I500D100K) và so sánh v i thu t toán Two-Phase, cho th y thu t toán Im-Two-Phase mang l i hi u qu . Hư ng nghiên c u ti p c a chúng tôi là tìm hi u, cài ñ t m t s thu t toán khai phá t p m c l i ích cao trên c u trúc d li u d ng cây, c i ti n, so sánh hi u qu gi a các thu t toán. TÀI LI U THAM KH O [1]. Vũ ð c Thi, Nguy n Huy ð c, Khai phá hi u qu t p m c l i ích cao trong cơ s d li u l n, T p chí Tin h c và ði u khi n h c, 2008. [2]. Nguy n Thanh Tùng, Khám phá t p m c l i ích cao trong cơ s d li u, H i th o M t s v n ñ ch n l c c a Công ngh thông tin và truy n thông, ð i L i, (2007), 181-197. [3]. FIMI, Frequent ItemSet Mining Implementations Repository, 2003, http://fimi.cs.helsinki.fi/data. [4]. IBM Almaden Research Center Intelligent Information Systems, Quest software, 2004. [5]. http://www.almaden.ibm.com/software/quest/Resources/index.shtml. [6]. Ying Liu, Wei-keng Liao, Alok Choudhary, A Fast High Utility Itemsets Mining Algorithm, Proceedings of the 1st international workshop on Utility-based data mining, Chicago, Illinois, (2005), 90-99. [7]. Hong Yao, Howard J, Hamilton, Liqiang Geng, A Uniﬁed Framework for Utility Based Measures for Mining Itemsets, Second International Workshop on Utility-Based Data Mining, Philadelphia, PA, (2006), 28-37. [8]. Hong Yao, Howard J, Hamilton, Cory J, Butz, A Foundational Approach to Mining Itemset Utilities from Databases, Proceedings of the Fourth SIAM International Conference on Data Mining, Orlando, Florida, USA, (2004), 482-486. AN ALGORITHM FOR MINING HIGH ULTILITY ITEMSETS IN DATABASE Nguyen Phuc Xuan Quynh College of Pedagogy, Hue University SUMMARY Developing from the mining associate rules problem, the mining high-utility itemsets problem has been a research topic of interest of many scientists with the aim to evaluate the role of itemsets in databases. Some data mining algorithms for high-utility itemsets have been developed. This article presents an algorithm which improves the Two-Phase algorithm with a strategy of inducing and pruning candidates to induce the execution time. 178