Thuật toán khai phá nhanh tập lợi ích cao với số lượng phần tử tối thiểu

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018 DOI: 10.15625/vap.2018.00066 THUẬT TOÁN KHAI PHÁ NHANH TẬP LỢI ÍCH CAO VỚI SỐ LƯỢNG PHẦN TỬ TỐI THIỂU Nguyễn Mạnh Hùng 1, Đậu Hải Phong2 1 Phòng Sau đại học - Học viện Kỹ thuật Quân sự 2 Khoa Toán và Tin học, Trường Đại học Thăng Long manhhungk12@mta.edu.vn, phong4u@gmail.com TÓM TẮT: Khai phá tập lợi ích cao trong cơ sở dữ liệu giao dịch là một trong nhiệm vụ phổ biến trong khai phá dữ liệu và có ứng dụng rộng rãi trong nhiều lĩnh vực thực tế. Các thuật toán truyền thống thường đưa ra một số lượng lớn tập các phần tử có lợi ích cao gây khó khăn cho phân tích của người dùng. Một khái niệm “tập lợi ích cao với số lượng phần tử tối thiểu” được đề xuất năm 2016 của tác giả Philippe Fournier-Viger và các đồng sự. Thuật toán MinFHM khai phá tập lợi ích cao với số lượng phần tử tối thiểu dựa trên cấu trúc EUCS (Estimated Utility Co-Occurrence Structure) để loại bớt tập ứng viên nhằm giảm không gian tìm kiếm. Tuy nhiên, cấu trúc EUCS sử dụng ngưỡng TWU (Transaction Weighted Utility), đây là một ngưỡng cao hơn mức cần thiết. Do đó, số lượng tập ứng viên được sinh ra lớn hơn rất nhiều so với thực tế tập lợi ích cao với số lượng phần tử tối thiểu được sinh ra. Trong bài báo này chúng tôi đề xuất một chiến lược mới để tỉa tập ứng viên nhằm giảm không gian tìm kiếm và đề xuất thuật toán ImprovedMinFHM khai phá hiệu quả tập lợi ích cao với số lượng phần tử tối thiểu. Kết quả thử nghiệm trên các bộ dữ liệu cho thấy rằng thuật toán ImprovedMinFHM có tốc độ thực hiện nhanh hơn và sinh ra số lượng ứng viên ít hơn so với thuật toán MinFHM. Từ khóa: High Utility Mining, TWU, EUCS, ImprovedMinFHM. I. GIỚI THIỆU Ngày nay, việc tìm kiếm các tri thức tiềm ẩn trong khối lượng dữ liệu khổng lồ đang gia tăng nhanh chóng là bài toán rất được quan tâm. Khai phá tập lợi ích cao (HUIs) là một dạng bài toán khó để tìm kiếm các tập có giá trị lợi ích lớn hơn một ngưỡng cho trước. Không giống như tìm tập phổ biến, bài toán tìm tập lợi ích cao cho phép đánh giá mức độ quan trọng của từng phần tử trong dữ liệu. Trong các thuật toán khai phá tập lợi ích cao truyền thống [1], [2], [3], [4], [5], [6], [7], thì chúng sinh ra một số lượng lớn các tập lợi ích cao. Điều này làm tốn dung lượng lưu trữ và thời gian để phân tích một lượng lớn tập lợi ích cao [8], [9]. Để giải quyết vấn đề này, đã có một số nhóm thuật toán khai phá tập lợi ích cao đại diện được đề xuất như: tập lợi ích đóng (Closed HUIs- CHUI)[8], tập lợi ích lớn nhất (Maximal HUIs-MaxHUI) [10], bộ sinh tập lợi ích cao (Generator of HUIs - GHUI) [9]. Năm 2016, nhóm Philippe Fournier Viger [11] và cộng sự đã đề xuất bài toán khai phá tập lợi ích cao với số lượng phần tử tối thiểu (MinHUIs) nhằm giải quyết vấn đề thường thấy của các thuật toán khai phá tập lợi ích cao là các tập lợi ích cao được sinh ra gồm nhiều phần tử nhưng lại đại diện cho những trường hợp ít gặp. Ví dụ, có một vài khách hàng mua số lượng lớn các mặt hàng dẫn đến các mặt hàng này có khả năng là tập lợi ích cao. Nhưng với mục đích quảng cáo, tiếp thị thì các nhà bán hàng chỉ quan tâm đến tìm kiếm một số ít các mặt hàng sinh ra lợi nhuận cao. Khi đó, nhà bán hàng có thể tập trung giới thiệu, quảng cáo một số ít mặt hàng cho số lượng lớn khách hàng hơn là quá nhiều mặt hàng cho số ít khách hàng. Một trong những thách thức trong khai phá tập lợi ích cao là các tập lợi ích không có tính chất đóng (closure properties) [12], điều này sẽ làm bùng nổ số lượng ứng viên và tăng thời gian duyệt dữ liệu để kiểm tra các ứng viên. Để giảm số lượng ứng viên thì đa số các thuật toán đều sử dụng ngưỡng TWU (Transactions Weighted Utility) do Liu[13] đề xuất. Thuật toán MinFHM [11] là mở rộng của thuật toán FHM [2] sử dụng một cấu trúc lượng giá lợi ích đồng xuất hiện của một cặp phần tử (EUCS) làm điều kiện để cắt tỉa tập ứng viên và kết hợp với một vài thuộc tính cho khai phá MinHUIs. Kết quả cho thấy rằng thuật toán MinFHM nhanh hơn rất nhiều so với các thuật toán FHM [2], CHUD [8], GHUI-Miner [9]. Trong bài báo này, chúng tôi đề xuất một chiến lược cắt tỉa mới và thuật toán ImprovedMinFHM để giảm số lượng ứng viên và không gian tìm kiếm cho bài toán khai phá tập lợi ích cao với số lượng phần tử tối thiểu. Nội dung tiếp theo của bài báo được tổ chức như sau: Phần II, những vấn đề liên quan đến khai phá tập lợi ích cao với số lượng phần tử tối thiểu; Phần III, đề xuất chiến lược cắt tỉa mới và thuật toán ImprovedMinFHM; Phần IV, Kết quả đánh giá; Phần cuối là kết luận. II. VẤN ĐỀ LIÊN QUAN Cho một cơ sở dữ liệu gồm các giao dịch Ti là D ={T1,T2,T3,Tn}, các giao dịch được xác định duy nhất bởi tid, tập I={i1,i2,i3,in} gồm các phần tử (item) có thể xuất hiện trong các giao dịch. Một tập phần tử X với X I được gọi là tập k-phần tử khi số lượng phần tử của X là k. Nguyễn Mạnh Hùng, Đậu Hải Phong 507 Để thuận tiện trong giải thích các khái niệm, chúng tôi đưa ra một cơ sở dữ liệu giao dịch như Bảng 1 và lợi ích ngoài của các phần tử được cho trong Bảng 2. Bảng 1. Cơ sở dữ liệu giao dịch Tid Transactions 1 a:1, b:5, c:1, d:3, e:1 2 b:4, c:3, d:3, e:1 3 a:1, c:1, d:1 4 a:2, c:6, e:2 5 b:2, c:2, e:1 Bảng 2. Lợi ích các phần tử Item a b c d e Utility 5 2 1 2 3 Định nghĩa 1 [2] - Lợi ích trong (internal utility) của mỗi phần tử là giá trị của mỗi phần tử trong từng giao dịch. Ký hiệu: O(ik,Tj) - là lợi ích trong của phần tử ik trong giao dịch Tj. Định nghĩa 2 [2] - Lợi ích ngoài (external utility) của mỗi phần tử là giá trị lợi ích của mỗi phần tử trong bảng lợi ích. Ký hiệu: S(ik) là lợi ích ngoài của phần tử ik. Định nghĩa 3 [2] - Lợi ích của một phần tử trong giao dịch là tích của lợi ích trong và lợi ích ngoài của phần tử đó. Ký hiệu: U( ik,Tj) = S(ik) * O(ik,Tj) là lợi ích của phần tử ik trong giao dịch Tj. Định nghĩa 4 [2] - Lợi ích của một tập phần tử X trong một giao dịch Tj là tổng giá trị lợi ích tất cả phần tử của tập X trong giao dịch Tj. Ký hiệu: U(X,Tj) = ∑ ( ) - là lợi ích của tập phần tử X trong một giao dịch Tj. Ví dụ, U({cd},T2) = 3*1 + 3*2 = 9. Định nghĩa 5 [2] - Lợi ích của một tập phần tử X trong cơ sở dữ liệu là tổng lợi ích của tập phần tử X trong tất cả giao dịch chứa X. Ký hiệu: U(X) = ∑ ( ) . Ví dụ, xét tập {ad}, ta thấy {ad}, xuất hiện trong các giao dịch: T1, T5 nên ta có: U({cd}) = U({cd}, T1) + U({cd}, T2) + U({cd}, T3) = (1*1 +3*2) + (3*1 + 3*2) + (1*1 +1*2) = 7 + 9 + 3 = 19. Định nghĩa 6 [2] - Lợi ích của một giao dịch là tổng lợi ích của các phần tử trong giao dịch đó. Ký hiệu: TU(Tj) = ∑ ( ) - là lợi ích của giao dịch Tj. Ví dụ, TU(T3) = 1*5 + 1*1 + 1*2 = 8. Định nghĩa 8 [2] - Lợi ích giao dịch của một tập phần tử X là tổng lợi ích của các giao dịch có chứa tập phần tử X. Ký hiệu: TWU(X) = ∑ ( ) là lợi ích giao dịch của tập phần tử X. Ví dụ: TWU({cd}) = TU(T1) + TU(T2) + TU(T3)= 25 + 20 + 8 = 53. Định nghĩa 9 [2] - Tập phần tử lợi ích cao: Tập phần tử X được gọi là tập phần tử lợi ích cao (HU - High Utility) nếu U(X) ≥ minutil, ngược lại gọi X là tập phần tử lợi ích thấp. Trong đó minutil là ngưỡng lợi ích tối thiểu cho trước. Ví dụ, lợi ích tối thiểu minutil = 12 thì tập {ad} là tập phần tử lợi ích cao. Tính chất 1 [7] Cho tập phần tử X. Nếu TWU(X) < minutil thì tập phần tử X và tất cả các tập phần tử mở rộng của tập X đều là các tập lợi ích thấp. Định nghĩa 10 [6] Cho một tập phần tử X và một giao dịch T với X ⊆ T, tập hợp tất cả các phần tử sau phần tử cuối cùng của tập X trong giao dịch T được ký hiệu là T\X. Ví dụ, trong bảng 1 T2\{abc} = {de}, T2\{cd} = {e}. Định nghĩa 11 [6] Lợi ích còn lại của tập phần tử X trong giao dịch T, ký hiệu là ru(X,T), là tổng lợi ích của tất cả các phần tử trong T\X trong T. Ký hiệu: ru(X,T) = ∑i∈(T\X)U(i,T). Ví dụ, ru({abc},T2) = 5*1+4*1 = 9. Định nghĩa 12 [6] Danh sách lợi ích (utility-list) của tập X là một danh sách trong đó mỗi phần tử tập gồm tid, iutil, rutil. Trong đó: - tid là định danh của giao dịch chứa X. - iutil là lợi ích của X trong tid, hay U(X, tid). - rutil là lợi ích còn lại của tập phần tử X trong giao dịch tid - ru(X, tid). 508 THUẬT TOÁN KHAI PHÁ NHANH TẬP LỢI ÍCH CAO VỚI SỐ LƯỢNG PHẦN TỬ TỐI THIỀU Tính chất 2 [6] Lợi ích của một tập phần tử là tổng giá trị iutil trong danh sách lợi ích của nó. Tính chất 3 [6] Cho tập phần tử X với một danh sách lợi ích, nếu tổng của tất cả iutils và rutils trong danh sách lợi ích mà nhỏ hơn ngưỡng minutil thì tất cả các tập X’ là mở rộng của X cũng không là tập lợi ích cao. Năm 2016, Philippe Fournier và cộng sự đã đề xuất một khái niệm tập lợi ích cao với số lượng phần tử tối thiểu (Minimal HUIs - MinHUIs) nhằm khắc phục những nhược điểm của tập lợi cao truyền thống thường gồm nhiều phần tử, đại diện cho những trường hợp hiếm gặp. Định nghĩa 13 [11] Một tập X được gọi là tập lợi ích cao có số lượng phần tử tối thiểu nếu U(X) ≥ minutil và không tồn tại tập con Y X mà U(Y) ≥ minutil. Ví dụ, giả sử minutil = 15, với cơ sở dữ liệu giao dịch và bảng lợi ích ngoài trong Bảng 1 và Bảng 2, ta có các tập lợi ích sau: - MinHUIs: {ac}:28, {bc}:28, {bd}:30, {be}:31, {ce}:27. - MaxHUIs: {abcde}: 25. - CHUIs: {ac}:28, {ace}:31, {abcde}:25, {bce}:37, {bcde}:40, {ce}:27. - GHUIs: {a}:20, {ab}:15, {ae}:24, {b}:22, {bd}:30, {de}:18, {e}:15. - HUIs khác: {bc}:28, {bcd}:34, {bde}:36, {be}:31. Một vấn đề xảy ra với các tập MaxHUIs, CHUIs, GHUIs là số lượng sẽ tăng lên nhanh khi minutil được giảm đi. Nhưng với MinHUIs thì số lượng có thể tăng, giảm hoặc giữ nguyên, điều này thể hiện qua tính chất 4. Tính chất 4 [11] Nếu minutil thấp thì số lượng MinHUIs có thể tăng, giảm hoặc giữ nguyên. Ngoài ra, nếu minutil = 1 thì số lượng tập MinHUIs bằng I. Ví dụ, với minutil = 20 thì MinHUIs gồm: {a}, {b}, {ce}; với minutil = 25 thì MInHUIs gồm: {bc}, {bd}, {be}, {ac} và {c, e}; với minutil=30 thì MinHUIs gồm: {bd}, {be}, and {ace}. Tính chất 5 [11] Nếu tập X là MinHUIs thì tất cả các tập chứa tập X sẽ không là MinHUIs. Để giảm số lượng kết nối trong thuật toán FHM [2] sử dụng phương pháp cắt tỉa ước lượng giá trị lợi ích xuất hiện cùng nhau (EUCP - Estimated Utility Co-occurrence Pruning) dựa trên cấu trúc ước lượng giá trị lợi ích xuất hiện cùng nhau (EUCS - Estimated Utility Co-Occurrence Structure). Một cách cụ thể là thuật toán FHM sử dụng EUCS để lưu trữ TWU của tất cả các cặp phần tử (a, b). Dựa vào tính chất đóng của TWU, tất cả các tập chứa cặp phần tử (a, b) có TWU(ab) nhỏ hơn ngưỡng lợi ích tối thiểu sẽ không phải là tập lợi ích cao để ngừng việc ghép nối các danh sách lợi ích. Dựa trên ý tưởng của thuật toán FHM [2] để khai phá tất cả các tập lợi ích cao, Philippe Fournier và cộng sự đã xây dựng thuật toán MinFHM [11] để khai phá tập lợi ích cao với số lượng phần tử tối thiểu. Tuy nhiên, theo Định nghĩa 13 một tập là tập lợi ích cao với số lượng phần tử tối thiểu thì không tồn tại tập con là tập lợi ích cao với số lượng phần tử tối thiểu. Dựa vào tính chất này, chúng tôi đề xuất một chiến lược cắt tỉa mới giảm số lượng tập ứng viên, không gian tìm kiếm và thuật toán ImproveFHM để khai phá hiệu quả tập lợi ích cao với số lượng phần tử tối thiểu. III. ĐỀ XUẤT THUẬT TOÁN Trong phần này chúng tôi đề xuất thuật toán ImprovedMinFHM được cải tiến từ thuật toán MinFHM [11] cho bài toán khai phá tập lợi ích cao với số lượng phần tử tối thiểu với một chiến lược cắt tỉa làm giảm số lượng tập ứng viên. Theo Định nghĩa 13, các tập phần tử lợi ích cao tối thiểu sẽ không có tập con là tập phần tử lợi ích cao. Trong thuật toán MinFHM, để xác định các tập lợi ích cao với số lượng phần tử tối thiểu có kích thước từ 2 phần tử trở lên, cần phải xây dựng danh sách lợi ích cho tập phần tử Pxy. Tuy nhiên, theo Định nghĩa 13, Pxy chỉ có thể là tập lợi ích cao với số lượng phần tử tối thiểu khi cả x, y và xy đều không phải là tập lợi ích cao. Từ nhận xét trên, chúng tôi đề xuất chiến lược cắt tỉa tập ứng viên như sau: - Xây dựng danh sách lợi ích cao tối thiểu - LstMinimalHUIs như Định nghĩa 14 - Tỉa tập ứng viên Pxy khi hoặc x hoặc y hoặc xy thuộc LstMinimalHUIs. Định nghĩa 14. Danh sách tập lợi ích cao với số lượng phần tử tối thiểu được kí hiệu là LstMinimalHUIs và được định nghĩa như sau: LstMinimalHUIs ={ X| X là tập lợi ích cao với số lượng phần tử tối thiểu} Thuật toán ImprovedMinFHM được chúng tôi đề xuất gồm các thủ tục chính sau: - Thủ tục ImprovedMinFHM được bổ sung thêm phần tạo danh sách lợi ích cao tối thiểu LstMinimalHUIs so với thuật toán MinFHM [11]. Nguyễn Mạnh Hùng, Đậu Hải Phong 509 - Thủ tục Search được bổ sung thêm cải tiến quan trọng đó là điều kiện cắt tỉa theo LstMinimalHUIs với việc kiểm tra x, y và xy có thuộc danh sách lợi ích cao tối thiểu - LstMinimalHUIs. Nếu x, y và xy đều không thuộc thì mới tiến hành xây dựng danh sách cho tập phần tử Pxy. Điều này làm giảm thời gian xây dựng tập danh sách cho tập Pxy và số lượng ứng viên được sinh ra. - Thủ tục Construct giống như trong thuật toán MinFHM [11]. Dưới đây là chi tiết các thủ tục: Thuật toán: ImprovedMinFHM Input: D: a transaction database, minutil: a user-specified threshold Output: the minimal high-utility itemsets 1. Scan D to calculate the TWU of single items; 2. I∗ = each item i such that TWU(i) ≥ minutil; 3. Let ≻ be the total order of TWU ascending values on I∗; 4. Scan D to build the utility-list of each item i∈I∗ and build the EUCS; 5. For each item i ∈ I∗ such that SUM({i}.utilitylist.iutils) ≥ minutil build the LstMinimalHUIs; 6. Search (∅, I∗, minutil, EUCS); Procedure Search Input: P: an itemset; ExtensionsOfP: a set of extensions of P; minutil: a user-specified threshold; EUCS: the EUCS; LstMinimalHUIs: the current minimal high-utility itemsets. Output: The minimal high-utility itemsets 1. foreach itemset Px ∈ExtensionsOfP do 2. if SUM(Px.utilitylist.iutils)+SUM(Px.utilitylist.rutils) ≥ minutil then 3. ExtensionsOfPx=∅ 4. foreach itemset Py∈ExtensionsOfP such that y x do 5. if (x LstMinimalHUIs) and (y LstMinimalHUIs) and (xy LstMinimalHUIs) then 6. if (x, y, c) ∈ EUCS such that c ≥ minutil) then 7. Pxy.utilitylist =Construct (P, Px, Py); 8. ExtensionsOfPx =ExtensionsOfPx Pxy; 9. if SUM(Pxy.utilitylist.iutils) ≥ minutil then 10. insert Px into LstMinimalHUIs; 11. endif 12. endif 13. endfor 14. Search (Px, ExtensionsOfPx, minutil); 15. endif 16. endfor Procedure Construct Input: P: an itemset, Px: the extension of P with an item x, Py: the extension of P with an item y; Output: the utility-list of P xy 1. UtilityListOfP xy ← ∅; 2. foreach tuple ex ∈ P x.utilitylist do 3. if ey ∈ P y.utilitylist and ex.tid = exy.tid then 4. if P.utilitylist 6= ∅ then 5. Search element e ∈ P.utilitylist such that e.tid = ex.tid.; 6. exy ← (ex.tid, ex.iutil + ey.iutil − e.iutil, ey.rutil); 7. end 8. else 9. exy ← (ex.tid, ex.iutil + ey.iutil, ey.rutil); 10. end 11. UtilityListOfP xy ← UtilityListOfP xy {exy}; 12. end 13. end 14. return UtilityListPxy; 510 THUẬT TOÁN KHAI PHÁ NHANH TẬP LỢI ÍCH CAO VỚI SỐ LƯỢNG PHẦN TỬ TỐI THIỀU IV. KẾT QUẢ ĐÁNH GIÁ 4.1. Môi trường và dữ liệu Thuật toán được thực hiện trên máy tính HP core 7 due 2.4GHz với 4 GB bộ nhớ, chạy trên Windows 7. Chương trình được viết bằng ngôn ngữ Java. Dữ liệu thử nghiệm gồm: Mushroom_utility [14] và Accidents_utility [14]. Đặc điểm của bộ dữ liệu được mô tả phía dưới: Bảng 3. Bảng tham số tập dữ liệu thử nghiệm Database T D N Accidents 30 340.194 145 Mushroom 23 8.124 119 Trong đó: T - là số phần tử trung bình trong một giao dịch; N - là số phần tử khác nhau; D - số giao dịch. Các phần tử trong bộ dữ liệu được sinh lợi ích ngoài (external utility) với phân phối loga chuẩn (log-normal) trong khoảng từ 1 đến 1.000, lợi ích trong (internal utility) sinh ngẫu nhiêu trong khoảng 1 đến 5. Tất cả mã nguồn của thuật toán dùng so sánh và bộ dữ liệu có thể lấy tại thư viện khai phá dữ liệu mở SPMF [14]. 4.2. Số lượng tập ứng viên Kết quả thực nghiệm hai thuật toán MinFHM [11] và ImprovedMinFHM trên các ngưỡng lợi ích tối thiểu khác nhau thì cho số lượng ứng viên được sinh ra khác nhau và có cùng số lượng tập lợi ích cao. Bảng 4, cho biết số lượng tập ứng viên gồm 3 phần tử (3-itemsets) trở lên của 02 thuật toán với các ngưỡng lợi ích tối thiểu (minutil) khác nhau. Kết quả cho thấy thuật toán ImprovedMinFHM không có tập ứng viên nào có kích thước từ 3 phần tử trở lên. Bảng 4. So sánh số lượng ứng viên có kích thước từ 3 phần tử trở lên được sinh ra của thuật toán MinFHM và ImprovedMinFHM minutil MinFHM ImprovedMinFHM Mushroom 250.000 945 0 220.000 1.073 0 200.000 1.029 0 Accidents 12.000.000 2.019 0 11.000.000 2.184 0 10.000.000 1.980 0 4.3. Thời gian thực hiện Kết quả thử nghiệm, so sánh giữa thuật toán ImprovedMinFHM và thuật toán MinFHM [11] trên tập dữ liệu Mushroom và Accidents với các ngưỡng lợi ích tối thiểu khác nhau được thể hiện trong Hình 1 và Hình 2. Hình 1. So sánh thời gian thực hiện trên tập dữ liệu Mushroom Hình 2. So sánh thời gian thực hiện trên tập dữ liệu Accidents Nguyễn Mạnh Hùng, Đậu Hải Phong 511 V. KẾT LUẬN Trong bài báo này chúng tôi tìm hiểu bài toán khai phá tập lợi ích cao với số lượng phần tử tối thiểu, phân tích điểm các hạn chế của thuật toán MinFHM (thuật toán duy nhất hiện nay) và đề xuất chiến lược cắt tỉa tập ứng viên theo LstMinimalHUIs. Từ chiến lược đề xuất và thuật toán MinFHM[11], chúng tôi đã đề xuất thuật toán ImprovedMinFHM khai phá hiệu quả tập lợi ích cao với số lượng phần tử tối thiểu. Kết quả thực nghiệm so sánh với thuật toán MinFHM trên một số bộ dữ liệu cho thấy thuật toán đề xuất ImprovedMinFHM cho số lượng tập ứng viên ít hơn và thời gian thực hiện nhanh hơn. VI. TÀI LIỆU THAM KHẢO [1] A. C. F. and T. S. K. “Efficient Tree Structures for Highutility Pattern Mining in Incremental Databases”. 2009. [2] P. Fournier-Viger, C. W. Wu, S. Zida, and V. S. Tseng. “FHM: Faster High-Utility Itemset Mining Using Estimated Utility Co-occurrence Pruning”. in Foundations of Intelligent Systems, 2014, pp. 83-92. [3] G. C. Lan, T. P. Hong, and V. S. Tseng. “An efficient projection-based indexing approach for mining high utility itemsets”. Knowl. Inf. Syst., vol. 38, no. 1, pp. 85-107, Jan. 2014. [4] S. Krishnamoorthy. “Pruning Strategies for Mining High Utility Itemsets”. Expert Syst Appl, vol. 42, no. 5, pp. 2371-2381, Apr. 2015. [5] Y. C. Li, J. S. Yeh, and C. C. Chang. “Isolated items discarding strategy for discovering high utility itemsets”. Data Knowl. Eng., vol. 64, no. 1, pp. 198-217, Jan. 2008. [6] M. Liu and J. Qu. “Mining High Utility Itemsets Without Candidate Generation” in Proceedings of the 21st ACM International Conference on Information and Knowledge Management, New York, NY, USA, 2012, pp. 55-64. [7] Y. Liu, W. Liao, and A. Choudhary. “A Two-phase Algorithm for Fast Discovery of High Utility Itemsets” in Proceedings of the 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, Berlin, Heidelberg, 2005, pp. 689-695. [8] “Efficient Algorithms for Mining the Concise and Lossless Representation of High Utility Itemsets - IEEE Journals & Magazine”. [Online]. Available: https://ieeexplore.ieee.org/document/6871427/. [Accessed: 16-May- 2018]. [9] P. Fournier-Viger, C. W. Wu, and V. S. Tseng. “Novel Concise Representations of High Utility Itemsets Using Generator Patterns” in Advanced Data Mining and Applications, 2014, pp. 30-43. [10] B. E. Shie, P. S. Yu, and V. S. Tseng. “Efficient algorithms for mining maximal high utility itemsets from data streams with different models”. Expert Syst. Appl., vol. 39, no. 17, pp. 12947-12960, Dec. 2012. [11] P. Fournier Viger, C. W. Lin, C. W. Wu, V. S. Tseng, and U. Faghihi. “Mining Minimal High-Utility Itemsets”. 2016, vol. 9827, pp. 88-101. [12] R. Agrawal and R. Srikant. “Fast Algorithms for Mining Association Rules in Large Databases”, presented at the Proceedings of the 20th International Conference on Very Large Data Bases, 1994, pp. 487-499. [13] Y. Liu, W. Liao, and A. Choudhary. “A Fast High Utility Itemsets Mining Algorithm” in Proceedings of the 1st International Workshop on Utility-based Data Mining, New York, NY, USA, 2005, pp. 90-99. [14] P. Fournier-Viger, A. Gomariz, T. Gueniche, A. Soltani, C. W. Wu, and V. S. Tseng. “SPMF: A Java Open-source Pattern Mining Library”. J Mach Learn Res, vol. 15, no. 1, pp. 3389-3393, Jan. 2014. FAST MINING MINIMAL HIGH-UTILITY ITEMSETS Nguyen Manh Hung, Dau Hai Phong ABSTRACT: Mining high utility itemsets in transaction databases is one of the common tasks in data mining and has wide applications in many areas. Traditional mining high utility itemsets algorthithms often offer a large number of high utility itemsets causing difficulty for analyzing them. A concept of "high utility itemsets with the minimum number of itemsets" proposed in 2016 by Philippe Fournier-Viger et al. The MinFHM algorithm for high utility itemsets with the minimum number of itemsets based on the Estimated Utility Co-Occurrence Structure (EUCS) to prune candidate itemsets to reduce search space. However, the EUCS structure uses the Transaction Weighted Utility (TWU) threshold, which is a higher threshold than required. As a result, the number of candidate itemsets is much greater than the actual high utility itemsets with the minimum number of itemsets generated. In this paper, we propose a new strategy for pruning candidate itemsets to reduce search space and propose ImprovedMinFHM algorithms for mining high utility itemsets with minimal number of itemsets. The experimental results show that the ImprovedMinFHM algorithm is faster and produces fewer candidates itemsets than the MinFHM algorithm.