Xây dựng thuật toán IHAUI để khai thác dữ liệu dựa trên độ hữu ích trung bình

TỔNG QUAN

Tổng quan về khai phá dữ liệu

1.1.1 Nhu cầu về khai phá dữ liệu

Chúng ta đang sống trong thời đại dữ liệu, nơi hàng terabytes và petabytes thông tin được tạo ra và lưu trữ mỗi ngày từ nhiều lĩnh vực như kinh doanh, xã hội, khoa học, kỹ thuật và y tế Sự bùng nổ dữ liệu này ảnh hưởng đến mọi khía cạnh của cuộc sống hàng ngày và được truyền tải qua mạng máy tính và World Wide Web (WWW).

Sự bùng nổ trong khối lượng dữ liệu hiện có là hệ quả của quá trình tin học hóa xã hội và sự phát triển nhanh chóng của các công cụ thu thập và lưu trữ dữ liệu Các doanh nghiệp toàn cầu đã tạo ra lượng dữ liệu khổng lồ, bao gồm giao dịch bán hàng, hồ sơ giao dịch chứng khoán, giới thiệu sản phẩm, chương trình khuyến mãi, hồ sơ công ty và phản hồi từ khách hàng.

 Các cơ sở dữ liệu lớn xử lý hàng trăm triệu giao dịch mỗi tuần

 http://top-10-list.org/2010/02/16/top-10-largest-databases-list/

1 Library of Congress: chứa hơn 125 triệu mục, trong đó bao gồm các tờ báo, sách nấu ăn và thủ tục tố tụng của chính phủ

2 Central Intelligence Agency: không rõ kích thước chính xác của cơ sở dữ liệu này, nhưng có hàng trăm mục dữ liệu thêm vào mỗi tháng và bao gồm số liệu thống kê dân số, bản đồ,…

3 Amazon: chứa hơn 250 nghìn sách, 55 triệu khách hàng, và hơn 40 Terabytes dữ liệu

1 Một petabyte là một đơn vị thông tin hoặc lưu trữ máy tính bằng một nghìn triệu triệu byte, hay một ngàn terabyte, tương đương một triệu gigabyte

4 YouTube: hàng trăm triệu clip được xem hàng ngày, tăng gấp đôi mỗi 5 tháng

5 ChoicePoint: cơ sở dữ liệu có thể đạt tới mặt trăng và trở lại ít nhất

6 Sprint: có hơn 50 triệu thuê bao Ít nhất 3.000 tỷ cơ sở dữ liệu trên

350 bản ghi cuộc gọi hang ngày và 70.000 lần chèn mỗi giây

7 Google: theo thống kê hơn 90 triệu cuộc tìm kiếm mỗi ngày và được gọi là vua của CSDL internet

8 AT&T: tương tự như Sprint là công ty viễn thông lâu đời Nó chứa hơn 310 terabyte thông tin và gần 2.000 tỷ hang

9 National Energy Research SCC là trung tâm tính toán nghiêm cứu năng lượng quốc gia là CSDL lớn thứ 2 trên thế giới

10 World Data Center for Climate: CSDL này được điều khiển và duy trì bởi trung tâm tính toán khí hậu Đức

 Trung tâm tính toán khoa học nghiên cứu năng lượng quốc gia Mỹ

 http://www.nersc.gov/assets/pubs_presos/NERSCplan-FY2014-

 Dự đoán sẽ đạt được một Exabyte 2 vào năm 2023

Hoạt động khoa học và kỹ thuật liên tục tạo ra hàng Petabyte dữ liệu từ các lĩnh vực như viễn thám, đo lường, thí nghiệm khoa học, hiệu năng hệ thống, quan sát kỹ thuật và giám sát môi trường.

 Ít nhất có 2.39 tỷ trang (23/9/2016), và 4.68 tỷ trang (16/6/2017)

2 Một exabyte là một ngàn petabyte

 Ít nhất có 242.39 triệu trang Web ở Hà Lan (23/9/2016), và 246.03 triệu trang (16/6/2017)

Sự bùng nổ và phổ biến của dữ liệu đã đưa chúng ta vào thời đại dữ liệu, nơi việc phát hiện thông tin giá trị từ khối lượng lớn dữ liệu trở nên cần thiết Để chuyển đổi dữ liệu thành tri thức, cần có những công cụ mạnh mẽ và linh hoạt, dẫn đến sự ra đời của khai thác dữ liệu Đây là một lĩnh vực mới, năng động và đầy hứa hẹn, sẽ tiếp tục đóng vai trò quan trọng trong quá trình chuyển mình từ thời đại dữ liệu sang thời đại thông tin.

1.1.2 Khai thác dữ liệu là sự tiến hóa của công nghệ thông tin

Khai thác dữ liệu có thể được xem như là một kết quả của sự tiến hóa tự nhiên của công nghệ thông tin

Tập hợp dữ liệu và khởi tạo CSDL

- Xử lý file thô sơ

- Hệ thống CSDL phân cấp và mạng

- Công cụ mô hình dữ liệu: Mô hình quan hệ thực tế

- Phương pháp đánh chỉ số và truy nhập

- Giao diện người dùng, nhập liệu và kết xuất

- Xử lý truy vấn, tối ưu truy vấn

- Quản lý giao dịch: Khôi phục, điều khiển tương tranh

- Xử lý giao dịch trực tuyến

- Mô hình dữ liệu mở rộng: Quan hệ mở rộng , quan hệ - đối tượng, suy luận

- Ứng dụng mở rộng: Không gian, thời gian, đa phương tiện, tích cực, khoa học, cở sở tri thức

Kho dữ liệu và khai phá dữ liệu

- Kho dữ liệu và OLAP

- Khai thác dữ liệu và phát hiện tri thức: Phân lớp, phân cụm, kết hợp, phân tích mẫu, phân tích ngược lại …

- Ứng dụng KPDL mở rộng: Khai phá dữ liệu dòng, khai phá text, khai phá web

Hệ CSDL dựa trên Web

- Hệ CSDL dựa trên XML

- Sự tích hợp với phục hồi thông tin

- Dữ liệu và tích hợp thông tin

Thế hệ mới của dữ liệu tích hợp và các hệ thống thông tin

Hình 1.1: Sự tiến hóa công nghệ CSDL [2]

Khai thác dữ liệu là một bước tiến quan trọng trong công nghệ thông tin và hệ thống thông tin, bắt nguồn từ những năm 1960 với sự phát triển từ hệ thống xử lý tập tin đến các cơ sở dữ liệu phức tạp Những nghiên cứu trong thập niên 1970 đã chuyển đổi dữ liệu từ dạng phân cấp sang cơ sở dữ liệu quan hệ, cùng với sự ra đời của các công cụ mô hình hóa dữ liệu và phương pháp truy cập hiệu quả Người dùng có thể tương tác với cơ sở dữ liệu qua ngôn ngữ truy vấn thân thiện, tối ưu hóa truy vấn và quản lý xung đột giao tác, trong khi các phương pháp xử lý giao tác trực tuyến (OLAP) cho phép thực hiện các truy vấn giống như giao tác chỉ đọc Sự phổ biến của cơ sở dữ liệu quan hệ đã chứng minh tính hiệu quả trong việc lưu trữ, bảo đảm và quản lý dữ liệu, ngay cả với những cơ sở dữ liệu lớn.

Từ giữa những năm 1980, hệ cơ sở dữ liệu quan hệ đã phát triển mạnh mẽ, thúc đẩy sự ra đời của các mô hình dữ liệu nâng cao như mô hình quan hệ mở rộng, mô hình hướng đối tượng và mô hình suy diễn Các hệ cơ sở dữ liệu ứng dụng phục vụ cho nhiều lĩnh vực như không gian vũ trụ, y học, đa phương tiện, và các ngành khoa học kỹ thuật cũng phát triển nhanh chóng Đặc biệt, sự xuất hiện của các hệ cơ sở dữ liệu hỗn hợp và hệ thống thông tin Internet toàn cầu như WWW đã đóng vai trò chủ đạo trong ngành công nghiệp thông tin.

Sự phát triển vượt bậc của kỹ thuật phần cứng đã dẫn đến sự ra đời của siêu máy tính và các thiết bị thu thập dữ liệu, đáp ứng nhu cầu lưu trữ ngày càng gia tăng Điều này đóng vai trò quan trọng trong ngành công nghiệp cơ sở dữ liệu và thông tin, tạo ra các kho dữ liệu khổng lồ có khả năng quản lý giao tác, đảm bảo thông tin và phân tích dữ liệu hiệu quả.

Hiện nay, dữ liệu có thể được lưu trữ trong nhiều loại thùng chứa khác nhau, trong đó kho dữ liệu (Data Warehouse) nổi bật như một giải pháp tổ chức nguồn dữ liệu hỗn hợp dưới một sơ đồ thống nhất tại một địa điểm duy nhất, hỗ trợ quản lý ra quyết định Quy trình xử lý kho dữ liệu bao gồm làm sạch dữ liệu, tích hợp dữ liệu, và xử lý giao tác trực tuyến (OLAP), cho phép người dùng nhìn nhận dữ liệu từ nhiều chiều khác nhau Mặc dù công cụ OLAP giúp phân tích dữ liệu đa chiều, việc tích hợp các công cụ phân tích sâu hơn như phân lớp, gom nhóm và phân tích theo thời gian thực là cần thiết Tuy nhiên, kích thước dữ liệu trong cơ sở dữ liệu và kho dữ liệu rất lớn, tạo ra thách thức trong việc phân tích hiệu quả và có lợi.

Sự phát triển của công cụ phân tích dữ liệu là cần thiết để khai thác thông tin hữu ích từ khối lượng dữ liệu khổng lồ, nhằm tránh tình trạng giàu dữ liệu nhưng nghèo thông tin Việc phân tích dữ liệu trở nên khó khăn khi dữ liệu bị nhiễu, dẫn đến hiện tượng "Data Tombs" Các công cụ hỗ trợ ra quyết định cần dựa vào tri thức thu được từ dữ liệu, thay vì chỉ dựa vào dữ liệu thô Tuy nhiên, quá trình này thường tốn thời gian và có độ chính xác không cao Các công cụ khai thác dữ liệu giúp chuyển đổi dữ liệu thành thông tin có giá trị, được gọi là "dữ liệu vàng".

“golden nuggets” cho quá trình khám phá tri thức

Hình 1.2: Thế giới là dữ liệu phong phú nhưng thông tin nghèo nàn [2]

Theo Plato, "Sự cần thiết, là người mẹ của sáng chế" KPDL (Khoa học Phân tích Dữ liệu) ra đời như một giải pháp hiệu quả cho nhu cầu khai thác thông tin Được xem như một công nghệ tri thức, KPDL giúp các nhà phân tích tìm ra những thông tin hữu ích từ kho dữ liệu tích trữ trong suốt quá trình hoạt động của công ty và tổ chức.

1.1.3 Khai phá dữ liệu và khai phá tri thức

Khai phá dữ liệu là quá trình trích xuất tri thức từ khối lượng lớn dữ liệu, nhằm phát hiện những thông tin ẩn, hữu ích mà trước đây chưa được biết đến Đây là một nhiệm vụ không đơn giản, đòi hỏi kỹ thuật và công cụ phù hợp để khai thác kiến thức từ dữ liệu.

Phát hiện tri thức trong cơ sở dữ liệu là một quá trình quan trọng nhằm nhận diện các mẫu có giá trị, mới mẻ và hữu ích tiềm năng từ dữ liệu.

Hình 1.3: Khai phá dữ liệu – tìm kiếm tri thức trong dữ liệu [2]

Lĩnh vực KDD (Khai thác dữ liệu) đang phát triển nhanh chóng và thu hút sự quan tâm của nhiều nhóm nghiên cứu trên toàn cầu, dẫn đến sự xuất hiện của nhiều cách tiếp cận khác nhau Do đó, trong các tài liệu khoa học, nhiều thuật ngữ tương đương với KDD đã được sử dụng, bao gồm chiết lọc tri thức, phát hiện thông tin, thu hoạch thông tin, khai quật dữ liệu và xử lý mẫu dữ liệu.

Mô hình khai phá dữ liệu đã được cải tiến để phù hợp với mục tiêu kinh doanh và phát triển của từng tổ chức, đồng thời tồn tại một số mô hình có thiên hướng công nghệ.

1.1.4 Các bước chính của quá trình khai phá dữ liệu

Khai thác các mẫu phổ biến

Itemset phổ biến là tập hợp các mặt hàng xuất hiện thường xuyên trong một tập dữ liệu Chẳng hạn, sự kết hợp giữa sữa và bánh mì trong dữ liệu giao dịch giỏ hàng được xem là một itemset phổ biến.

Các tập mẫu phổ biến là công cụ quan trọng trong khai thác luật kết hợp và sự tương quan của dữ liệu Chúng được áp dụng trong các quá trình phân lớp, gom cụm và nhiều công việc khai thác dữ liệu khác Khai thác tập phổ biến đóng vai trò thiết yếu trong nghiên cứu và phát triển các ứng dụng khai thác dữ liệu.

1.2.2 Khai thác mẫu phổ biến, tập phổ biến

Khai thác mẫu phổ biến là quá trình tìm kiếm các mối quan hệ tuần hoàn và phổ biến trong tập dữ liệu Một phần quan trọng của khai thác này là khai thác luật kết hợp, nhằm phát hiện mối tương quan giữa các itemset trong tập dữ liệu giao tác Ví dụ điển hình cho phương pháp này là phân tích giỏ hàng tại các cửa hàng và siêu thị.

Khai thác tập phổ biến là quá trình tìm kiếm các tập item phổ biến nhằm phát hiện sự kết hợp và mối liên quan giữa các item trong những tập dữ liệu giao dịch lớn Nhiều công ty đã áp dụng phương pháp này để khai thác những mối liên hệ thú vị từ dữ liệu khổng lồ, giúp các nhà phân tích phát triển chiến lược kinh doanh, thiết kế catalog, marketing, và phân tích thói quen mua sắm của khách hàng.

Hình 1.6: Ví dụ chọn giỏ hàng trong siêu thị [2]

Phân tích giỏ hàng là một ứng dụng phổ biến trong khai thác các tập item, giúp phân tích thói quen mua sắm và tìm ra mối liên hệ giữa các sản phẩm mà khách hàng chọn mua Việc khám phá các mối quan hệ kết hợp này hỗ trợ các nhà bán lẻ phát triển chiến lược marketing hiệu quả, dựa trên những sản phẩm thường được người tiêu dùng mua chung.

Khai thác dữ liệu để rút ra các quy luật kết hợp trong mua sắm trực tuyến không chỉ thúc đẩy sự phát triển của ngành thương mại điện tử mà còn đáp ứng nhanh chóng và tiện lợi nhu cầu mua sắm ngày càng gia tăng.

Trong quá trình khai thác luật kết hợp, việc khai thác tập phổ biến là một nhiệm vụ quan trọng nhưng tốn nhiều thời gian Nhiều thuật toán khai thác luật đã tập trung vào việc tối ưu hóa quy trình này để khai thác nhanh chóng tập phổ biến hay tập phổ biến đóng Nhiều tác giả đã nghiên cứu và phát triển các thuật toán hiệu quả cho bài toán khai thác tập phổ biến, trong đó có các thuật toán tiêu biểu như Apriori, AprioriTid, Eclat và đặc biệt là FP-Growth Phương pháp FP-Growth được cải tiến với khả năng khai thác các tập phổ biến dựa trên cây chỉ qua việc duyệt cơ sở dữ liệu chỉ hai lần.

Khai thác dựa trên giá trị hữu ích

Khai thác tập phổ biến thường chỉ chú trọng vào sự xuất hiện của các item mà không xem xét các giá trị khác như số lượng hay giá cả, dẫn đến việc các item trong giao dịch được coi là tương đương Tuy nhiên, thực tế cho thấy giá trị của các item là khác nhau, với những item có giá trị cao thường xuất hiện ít hơn so với các item có giá trị thấp Do đó, vấn đề đặt ra là mở rộng việc khai thác các itemset phổ biến sang khai thác các itemset hữu ích.

Việc mua sắm kim cương và quần áo cho thấy sự khác biệt về giá trị hữu ích, trong đó kim cương thường mang lại giá trị cao hơn dù xuất hiện ít hơn trong giao dịch Phương pháp khai thác dữ liệu dựa trên độ hữu ích, được Chan đề xuất, tính toán giá trị hữu ích của một item bằng tích của giá trị và số lượng trong giao dịch Một itemset được coi là có độ hữu ích cao khi đạt ngưỡng đã định Thuật toán hai pha của Liu giúp giảm số lượng ứng viên qua việc cắt tỉa ở pha đầu và tính toán giá trị hữu ích thực tế ở pha sau Vấn đề chính là giảm số ứng viên và thời gian duyệt dữ liệu Vào năm 2011, Lin và cộng sự đã phát triển HUP-Tree để khai thác các itemset hữu ích cao, bắt đầu bằng việc tính toán giá trị hữu ích và chọn tập 1-itemset ứng viên, sau đó tạo HUP-Tree từ bảng header sắp xếp theo độ phổ biến Cuối cùng, các itemset hữu ích cao được khai thác từ HUP-Tree, trong khi phương pháp WIT-Tree sử dụng thuộc tính “bao đóng giảm” để loại bỏ ứng viên không phù hợp, giúp rút ngắn thời gian khai thác.

Khai thác dựa trên giá trị hữu ích trung bình

Độ hữu ích của một itemset được xác định bởi tổng giá trị hữu ích của các item trong tất cả các giao dịch mà không phụ thuộc vào số lượng item trong itemset Do đó, độ hữu ích của itemset sẽ tăng theo số lượng item, và trong cùng một giao dịch, itemset có chiều dài lớn hơn sẽ mang lại giá trị hữu ích cao hơn Vì lý do này, việc áp dụng một ngưỡng chung cho tất cả các itemset là không hợp lý.

Để giải quyết vấn đề hiện tại, một độ đo mới được đề xuất là giá trị hữu ích trung bình AU (Average Utility) Giá trị hữu ích trung bình được tính bằng tổng giá trị hữu ích của itemset chia cho độ dài của itemset Nếu giá trị này vượt quá ngưỡng đã định, itemset sẽ được phân loại là itemset có độ hữu ích trung bình cao, hay còn gọi là HAUI (High Average Utility Itemset).

Khi áp dụng giá trị hữu ích trung bình, tính bao đóng có thể bị phá vỡ, dẫn đến việc một itemset có giá trị hữu ích trung bình không đạt ngưỡng vẫn có khả năng kết hợp với các item khác để tạo thành itemset có độ hữu ích trung bình cao Vấn đề này cần được giải quyết trong khai thác dữ liệu do số lượng ứng viên lớn và chi phí tính toán cao.

Trong nghiên cứu của Hong, Lee & Wang, giá trị cận trên hữu ích trung bình (UB) được sử dụng để giảm số lượng ứng viên, bằng cách loại bỏ các itemset không đạt ngưỡng UB Từ tập các r-itemset thỏa mãn ngưỡng UB, các tác giả tạo ra các (r+1)-itemset và lựa chọn những itemset có độ hữu ích trung bình cao (HAUI) Mặc dù các itemset có UB không thỏa ngưỡng bị loại, nhưng giá trị của chúng vẫn được xem xét trong việc tính toán UB cho các itemset khác Phương pháp này cho phép tính toán lại UB cho các itemset còn lại sau khi loại trừ các itemset không đạt yêu cầu, nhằm tối ưu hóa quá trình lựa chọn.

Một số cấu trúc dữ liệu khác đã được đề cập nhằm tăng tốc độ tính toán, điển hình là cấu trúc bảng chỉ mục trong nghiên cứu của Lan, Hong và Tseng.

Năm 2014, Tien Lu, Bay Vo, Hien T Nguyen và Tzung-Pei Hong đã phát triển thuật toán HAUI-Tree, sử dụng giá trị cận trên trung bình để loại bỏ các ứng viên không cần thiết, đồng thời khai thác tính bao đóng giảm của tập ngưỡng trên hữu ích trung bình Thuật toán này giúp tăng tốc độ phát sinh ứng viên so với các phương pháp sử dụng Index Table và tiết kiệm bộ nhớ Ngoài ra, nghiên cứu còn đề xuất một cấu trúc itemset nhằm giảm thời gian tính toán, cải thiện hiệu suất trong việc phát sinh và tính toán giá trị cho các ứng viên.

Mục tiêu của luận văn

 Đề xuất một cấu trúc dữ liệu mới để cải thiện cách tính toán các giá trị cho các itemsets (BitArray) nhanh hơn

 Thực nghiệm và so sánh thuật toán đề xuất với các phương pháp trước đó và đưa ra các nhận xét

 Đề xuất thuật toán khai thác tập hữu ích trung bình trên CSDL tăng trưởng

Chương này tổng quan về khai thác dữ liệu và khai thác tri thức, nhấn mạnh tầm quan trọng của chúng Quá trình khai thác tri thức bao gồm nhiều giai đoạn, trong đó giai đoạn khai thác dữ liệu đóng vai trò quan trọng nhất.

Khai phá dữ liệu là quá trình khám phá ra các mẫu được quan tâm từ lượng lớn dữ liệu:

Mẫu kết quả khai phá cần thể hiện tri thức một cách dễ hiểu, hợp lệ với mức độ chắc chắn cao, hữu dụng và mới mẻ đối với người dùng.

Khai phá dữ liệu là một yếu tố quan trọng trong quá trình khám phá tri thức, bao gồm các bước lặp đi lặp lại như làm sạch, tích hợp, chọn lựa, biến đổi dữ liệu, và cuối cùng là khai thác, đánh giá mẫu và biểu diễn tri thức.

Khai phá dữ liệu liên quan đến nhiều lĩnh vực khác nhau, bao gồm cơ sở dữ liệu, lý thuyết thống kê, học máy, khoa học thông tin và trực quan hóa.

Các vấn đề quan trọng liên quan đến khai phá dữ liệu bao gồm phương pháp luận khai thác dữ liệu, tương tác người dùng, khả năng co giãn và hiệu suất của dữ liệu Ngoài ra, việc xử lý lượng lớn các kiểu dữ liệu khác nhau và khai thác các ứng dụng khai phá dữ liệu cũng như ảnh hưởng xã hội của chúng là những thách thức cần được giải quyết.

Sự đa dạng của dữ liệu và các nhiệm vụ khai thác dữ liệu tạo ra nhiều thách thức trong nghiên cứu lĩnh vực này Cuối chương, chúng tôi sẽ trình bày những ưu điểm, ứng dụng chính của khai thác dữ liệu và các hướng nghiên cứu đang được chú ý.

CƠ SỞ LÝ THUYẾT

Một số khái niệm

2.1.1 Cơ sở dữ liệu giao dịch

Cơ sở dữ liệu giao dịch D bao gồm ba thành phần chính: tập hợp {I} đại diện cho n item, tập hợp {P} chứa giá trị hữu ích của các item này, và tập hợp {T} là tập hợp m giao dịch được phân tích.

Một itemset {X} là tập hợp các item Ii (I i I), X I, nếu |X|=r thì ta gọi {X} là một r-itemset (r là số lượng item trong itemset {X}), r là độ dài của itemset {X}

Cho CSDL giao dịch D và một itemset {X} I Độ phổ biến của{X} trong D, kí hiệu (X), là số giao dịch mà có {X} xuất hiện trong D

Ví dụ: Cho CSDL sau:

Bảng 2.1: CSDL item trong giao dịch

Mã giao dịch Danh sách item

Ta có ({A}) = 4 vì A chứa trong 4 giao dịch {1, 3, 4, 5}, ({AD}) = 2 vì {AD} chứa trong các giao dịch {4, 5}

Một itemset {X} I được gọi l itemset phổ biến nếu (X) minSupCount(minSupCount là giá trị do người dùng chỉ định)

Ví dụ: Xét CSDL của bảng 2.1 với minSupCount= 3 thì {A} thuộc tập phổ biến vì ({A}) = 4 minSupCount,nhưng {AD} không thuộc tập phổ biến vì ({AD}) = 2 < minSupCount

Trong khai thác tập phổ biến, một tính chất quan trọng là mọi tập con của tập phổ biến đều được coi là phổ biến Điều này có nghĩa là nếu một itemset là phổ biến, thì tất cả các tập con của nó cũng sẽ phổ biến.

X Y, nếu (Y) minSupCount thì (X) minSupCount Mọi tập cha của tập không phổ biến đều không phổ biến, nghĩa là Y X, nếu (X) < minSupCountthì (Y) < minSupCount[2]

Tính chất này được ứng dụng rộng rãi trong các thuật toán khai thác tập phổ biến, giúp tạo ra các ứng viên hiệu quả và tăng tốc độ khai thác dữ liệu.

2.1.6 Ngưỡng hữu ích trung bình tối thiểu

Ngưỡng hữu ích trung bình tối thiểu là giá trị quan trọng trong khai thác dữ liệu, giúp xác định các itemset có giá trị hữu ích cao (HUI) Những itemset này có giá trị hữu ích vượt qua ngưỡng đã được xác định Bên cạnh đó, khai thác theo độ hữu ích trung bình cho phép nhận diện các itemset có giá trị hữu ích trung bình cao (HAUI) khi chúng vượt qua ngưỡng cụ thể.

Với tỉ lệ ngưỡng hữu ích trung bình tối thiểu (do người dùng định trước)

2.1.7 Độ hữu ích Độ hữu ích của item trong giao dịch là tích của số lượng item trong giao dịch đó và giá trị hữu ích của nó u ij =q ij  p i (2.2)

Độ hữu ích của một item Ii trong giao dịch t j được ký hiệu là uij, trong khi q ij đại diện cho số lượng item I trong giao dịch đó Để tính độ hữu ích của một itemset trong giao dịch, ta cần tổng hợp độ hữu ích của tất cả các item thuộc itemset này Công thức tính được biểu diễn như sau: uXj = ∑ { } ({X} j ).

Trong khai thác tập phổ biến, một itemset {X} được coi là có độ hữu ích cao nếu tổng độ hữu ích của nó trong tất cả các giao dịch đạt hoặc vượt qua ngưỡng đã định sẵn.

Ví dụ: Cho CSDL sau với Ngưỡng là 1022

Bảng 2.2: CSDL các giao dịch

Bảng 2.3: Giá trị hữu ích các item

Giá trị hữu ích của item {A}, {B}, {AB} lần lượt là 48, 1050, 1068 Trong đó, chỉ có độ hữu ích của {B}, {AB} thỏa ngưỡng nên {B}, {AB} thuộc tập hữu ích cao

Trong khai thác itemset theo giá trị hữu ích, người ta thường chỉ chú trọng đến tổng giá trị hữu ích của các item mà không xem xét độ dài của itemset Để khắc phục điều này, các nhóm tác giả đã đề xuất một chỉ số mới gọi là độ hữu ích trung bình trong những năm gần đây.

2.1.9 Độ hữu ích trung bình Độ hữu ích trung bình của itemset {X} là tổng độ hữu ích của {X} trong tất cả các giao dịch chia cho độ dài của itemset {X}

Trong đó au x : độ hữu ích trung bình của itemset {X}, t j T là các giao dịch thứ j trong T, u Xj là giá trị hữu ích của itemset {X}, |X| độ dài của itemset

2.1.10 Tập hữu ích trung bình

Itemset được định nghĩa là một tập hợp các mặt hàng có độ hữu ích trung bình cao (HAUI) nếu tổng độ hữu ích của nó trong tất cả các giao dịch đạt hoặc vượt qua ngưỡng đã được xác định trước.

Giá trị hữu ích trung bình của tập hợp {AB} là 525, được tính bằng 1050 chia cho 2 Mặc dù {B} vẫn giữ vị trí là itemset có độ hữu ích trung bình cao, nhưng {AB} lại không đạt được tiêu chí này.

2.1.11 Cận trên độ hữu ích trung bình

Gọi = là độ hữu ích lớn nhất của item trong giao dịch t j , cận trên độ hữu ích trung bình của itemset {X} được tính bằng công thức: ub X =∑ (2.5)

Trong đó ub X : là cận trên độ hữu ích trung bình của itemset {X}, T X là tập hợp các giao dịch chứa itemset {X}

2.1.12 Tập cận trên độ hữu ích trung bình

Trong khai thác tập hữu ích trung bình, tính chất bao đóng giảm bị phá vỡ, dẫn đến việc sinh ra số lượng lớn tổ hợp ứng viên mà không thể loại bỏ bằng tính chất này Để giảm thiểu số ứng viên, các nhóm tác giả đã đề xuất một độ đo mới là cận trên hữu ích trung bình Một itemset được gọi là tập cận trên hữu ích trung bình khi nó có cận trên độ hữu ích trung bình đạt ngưỡng yêu cầu.

Cận trên hữu ích trung bình của itemset thể hiện độ hữu ích tối đa mà itemset có thể đạt được, với AU X ≤ UB X, cho thấy tổng giá trị hữu ích lớn nhất mà item mang lại cho giao dịch chứa itemset Do đó, nếu một itemset không nằm trong tập cận trên hữu ích trung bình, nó cũng sẽ không thuộc tập hữu ích trung bình Để khai thác tập hữu ích trung bình, chúng ta cần dựa vào tập cận trên hữu ích trung bình Tuy nhiên, trong trường hợp dữ liệu phân bố không đều và sự chênh lệch lớn về độ hữu ích giữa các item, việc loại bỏ các ứng viên dựa trên tập cận trên có thể tiêu tốn nhiều thời gian và bộ nhớ, đặc biệt với các cơ sở dữ liệu có số lượng item lớn Đây là thách thức cho các nhà nghiên cứu trong việc tìm ra phương pháp khai thác và tạo ra tập cận trên một cách hiệu quả và nhanh chóng, đồng thời sử dụng cấu trúc dữ liệu hợp lý để tăng tốc độ tính toán các giá trị.

Tính chất bao đóng giảm

Trong khai thác các itemset dựa trên tập phổ biến, có đề cập đến một tính chất quan trọng về độ phổ biến của các itemset

1 Mọi tập con của tập phổ biến đều phổ biến, nghĩa là X Y, nếu (Y) minSupCount thì (X) minSupCount

2 Mọi tập cha của tập không phổ biến đều không phổ biến, nghĩa là Y

Tính bao đóng giảm trong tập cận trên hữu ích trung bình

Tính bao đóng giảm không áp dụng cho tập hữu ích và tập hữu ích trung bình, vì một itemset không thuộc tập hữu ích trung bình có thể trở thành tập hữu ích trung bình khi kết hợp với itemset khác có giá trị lớn Tuy nhiên, tính chất này có thể áp dụng cho tập cận trên hữu ích trung bình, giúp giảm số lượng ứng viên trong quá trình khai thác, từ đó tăng tốc độ và tối ưu hóa vùng nhớ khi khai thác tập hữu ích trung bình.

1 Mọi tập con của tập cận trên hữu ích trung bình cũng là một tập cận trên hữu ích trung bình, nghĩa là X Y, nếu thì

2 Mọi tập cha của tập không là tập cận trên hữu ích trung bình đều không là tập cận trên hữu ích trung bình, nghĩa là Y X, nếu thì

Thuật toán HAUI-Tree

Khi khai thác dữ liệu, số lượng ứng viên phát sinh rất lớn, do đó, việc tăng tốc độ tính toán các chỉ số cho những ứng viên này trở thành một vấn đề quan trọng Trong thuật toán đề xuất, một tập hợp mục {X} được lưu trữ với các thuộc tính cần thiết.

 Danh sách các item thuộc itemset

 Độ hữu ích trung bình AU{X} của itemset {X}

 Giá trị cận trên hữu ích trung bình UB X của itemset {X}

 Tập hợp T{X} các giao dịch chứa itemset {X}

 Tập hợp Pos {X} các vị trí cuối cùng của item cuối trong itemset {X} tương ứng với giao dịch thuộc T {X}

Các giá trị T{X} và Pos{X} giúp truy xuất nhanh chóng giá trị hữu ích của item trong giao dịch, từ đó tăng tốc độ tính toán Bên cạnh đó, T{X} và Pos{X} còn được áp dụng để tạo ra (r+1)-itemset từ hai r-itemset có cùng tiền tố, giúp tính toán các độ đo cho (r+1)-itemset mới một cách hiệu quả hơn.

 Nút: là một itemset với cấu trúc dữ liệu đã nêu ở trên

 Cạnh: đường nối giữa hai nút

Cây HAUI-Tree có đặc điểm nổi bật là nút cha chính là phần tiền tố của nút con Nút con được hình thành từ sự kết hợp giữa nút cha và một nút khác có cùng cha với nút cha, nằm bên phải của nó.

2.4.2 Thuật toán sử dụng HAUI-Tree

2.4.2.1 Tập dữ liệu giao dịch

Tập dữ liệu đầu vào được lưu trữ dưới dạng tập tin *.txt, có cấu trúc như sau:

Bảng 2.4: Cấu trúc tập tin dữ liệu

Trong bài viết này, m đại diện cho số lượng giao dịch và n là số lượng items được xem xét Mỗi dòng dữ liệu lưu trữ bộ ba (t, i, q), trong đó t là mã giao dịch, i là một item trong tập hợp items, và q là số lượng của item i trong giao dịch t.

Thuật toán đề nghị sử dụng cách lưu trữ dữ liệu như sau:

Bảng 2.5: Biểu diễn dữ liệu giao dịch

Giao dịch Danh sách các item trong giao dịch t 1 {i 1 , i 3, i 7 , …} t 2 {i 1 , i 2, i 9 , …}

Các mục trong danh sách được sắp xếp theo thứ tự tăng dần dựa trên chỉ số Những mục này được tạo ra và lưu trữ dưới dạng cấu trúc dữ liệu của một 1-itemset, bao gồm tất cả các thuộc tính đã được đề cập.

2.4.2.2 Thuật toán khai thác với HAUI-Tree

Bước 1: Tính toán các độ đo cần thiết cho có 1-itemset từ tập dữ liệu ban đầu, tạo

HAUUB 1 là tập các 1-itemset là tập cận trên hữu ích trung bình

Bước 1: Khởi tạo MaxU là tập chứa maxU của các giao dịch trong T

Bước 2: Khởi tạo L 1 là tập các 1-itemset được tạo từ tất cả các Item được xét Mỗi itemset {X} chứa các thông tin au{X}, ub{X}, T{X}, Pos{X}

Bước 3: Duyệt các giao dịch Ti trong tập T

Với mỗi giao dịch T i ta tính toán:

L Thêm Ti vào T{X}, cập nhật vị trí {X} trong Ti vào Pos{X}

Cập nhật au{x}, ub{x} của itemset {X} trong tập L1

Bước 4: Duyệt các 1-itemset {X} trong L 1 tạo HAUUBI 1 (các 1-itemset có ub thỏa ngưỡng và HAU1(các 1-itemset có au thỏa ngưỡng

Để tạo ra các HAUUBI r+1, thực hiện hàm đệ quy creatHAUI(HAUUBI1, n) nhằm trộn các itemset từ HAUUBI r Sau đó, tiến hành chọn các itemset phù hợp để đưa vào HAUI.

Khởi tạo Lr+1; for j=i+1 to n do{

Thêm {X} vào L r+1 ; if(auX> ) Thêm {X} vào HAUI;

Việc xây dựng tập HAUUBIr+1 từ HAUUB r dựa trên tính chất bao đóng giảm của tập HAUUBI, giúp tạo ra các ứng viên nhanh chóng, không trùng lặp và loại bỏ những ứng viên không cần thiết Tập L r+1 được hình thành là một tập con của HAUUBI r+1, trong đó các itemset trong L r+1 có cùng tiền tố và chỉ khác nhau ở item cuối cùng, với các item trong itemset được sắp xếp theo thứ tự.

Hàm merge (L r [i], L r [j]) cho phép kết hợp hai r-itemset trong L r, có cùng tiền tố, để tạo ra một (r+1)-itemset cho L r+1 Quá trình này sử dụng các độ đo và thuộc tính của hai r-itemset ban đầu để tính toán các thuộc tính cho (r+1)-itemset mới.

Khi xét trộn 2 r-itemset {XIj }và {XIj}có cùng phần tiền tố là {X} để tạo thành (r+1)-itemset {XI i I j }, ta có:

Đầu tiên, chúng ta thu thập dữ liệu giao dịch và giá trị hữu ích của từng item, như được trình bày trong bảng 2.6 và 2.7, với ngưỡng là 25 Sau đó, tiến hành tính toán độ hữu ích và giá trị cận trên trung bình Cuối cùng, chúng ta hình thành tập L1 và tiến hành khai thác trên tập L1.

Bảng 2.7: Giá trị của các item trong CSDL

Bước 1: Tính toán các độ đo cần thiết cho có 1-itemset từ tập dữ liệu ban đầu, tạo

HAUUB 1 là tập các 1-itemset là tập cận trên hữu ích trung bình

Tính độ hữu ích của các 1-itemset (các item) trong từng giao dịch:

Chúng ta có thể dễ dàng tính toán độ hữu ích của các 1-itemset trong từng giao dịch Sau đó, xác định giá trị hữu ích lớn nhất cho mỗi giao dịch để tính toán giá trị cận trên hữu ích trung bình cho các item, kết quả được trình bày trong bảng dưới đây.

Bảng 2.8: Kết quả tính giá trị hữu ích và au, ub của các 1-itemset

Với Ngưỡng 25, ta thu được tập L 1 (tập các 1-itemset có ub > Ngưỡng) và tiến hành khai thác trên L1

TID u Ak u Bk u Ck u Dk u Ek u Fk mu k t1 3 0 2 6 5 2 6 t2 0 10 25 0 0 0 25 t3 0 0 0 0 10 2 10 t4 0 10 12 0 0 0 12 t5 6 0 8 0 10 0 10 t6 0 0 4 6 0 2 6 t7 0 0 2 6 0 0 6 t8 9 20 0 0 10 6 20 t9 6 0 0 6 0 0 6 t10 0 0 4 0 10 0 10

Ta cũng tính được giá trị AU và UB của các 1-itemset khác, thu được kết quả như bảng 2-9 Căn cứ vào ngưỡng cho trước là 25 ta thu được:

HAUI = {{B},{C},{E}} và HAUUBI = {{A},{B},{C},{E},{F}} Các 1-itemset trong HAUUBI được lưu trữ với các thuộc tính như sau:

Bảng 2.9:Ví dụ HAUI-Tree- Cấu trúc dữ liệu các 1-itemset

Bước 2: Tiến hành hàm đệ quy dựa trên tính chất bao đóng giảm để phát sinh các ứng viên thông qua cấu trúc cây HAUI-Tree.

Hình 2.1: Kết quả kết hợp item {A} với các item khác

AU AB 14.5 AU AC 9.5 AU AE 21.5 AU AF 10

UB AB 20 UB AC 16 UB AE 36 UB AF 26

AU BC 28.5 AU BE 15 AU BF 13

UB BC 37 UB BE 20 UB BF 20

Hình 2.2: Kết quả kết hợp item {B} với các item khác

Hình 2.3: Kết quả kết hợp item {A} theo HAUI-Tree

Tính toán tương tự ta thu được cây như sau:

Hình 2.4: Kết quả cây thu được cây HAUI

Khai thác trên cây HAUI-Tree trên với Ngưỡng là 25, ta được kết quả sau:

AU UB Tx AU UB Tx AU UB Tx AU UB Tx AU UB Tx

Bảng 2.10: Kết quả thu được tập HAU VÀ HAUUB

Tập HAUUB = {{A},{B},{C},{E},{AE},{AF},{AEF},{BC},{EF}}

Thuật toán áp dụng giá trị cận trên trung bình để loại bỏ các ứng viên không cần thiết, đồng thời tận dụng tính bao đóng giảm của tập ngưỡng trên hữu ích trung bình, từ đó nâng cao hiệu quả phát sinh ứng viên Thuật toán sử dụng Index Table để tối ưu hóa thời gian và vùng nhớ Để tăng tốc độ tính toán, nó sử dụng cấu trúc dữ liệu itemset để lưu trữ thông tin, giúp tính toán các itemset thế hệ sau dựa trên các itemset thế hệ trước mà không cần truy xuất lại cơ sở dữ liệu.

Tuy nhiên, trong những trường hợp số lượng 1-itemset trong tập cận trên quá lớn, do ngưỡng quá nhỏ hoặc cơ sở dữ liệu lớn, thuật toán vẫn gặp khó khăn về vấn đề vùng nhớ.

Thuật toán HAUI-Tree yêu cầu phải chạy lại từ đầu mỗi khi cập nhật cơ sở dữ liệu bằng cách thêm mới giao dịch, điều này dẫn đến việc không thể tận dụng kết quả từ các lần chạy trước để tối ưu hóa thời gian thực thi.

Khai thác độ hữu ích trung bình hai pha tăng trưởng

Thuật toán 2-pha được áp dụng để khai thác các itemset từ dữ liệu động, với việc sử dụng giá trị UB nhằm giảm thiểu số lượng ứng viên.

Bước 1: Tính Ngưỡng hữu ích trung bình tối thiểu

( cho các giao dịch mới N và sau khi cập nhật U: và

Bước 2: Tính giá trị hữu ích cho mỗi item Ij trong các giao dịch mới thêm T k :

Bước 3: Tìm giá trị hữu ích lớn nhất của các item trong mỗi giao dịch thêm vào T k

Bước 5: Phát sinh các ứng viên k-itemsets và tính cận trên hữu ích trung bình ubs của các giao dịch mới:

Bước 6: Nếu  , thêm k-itemset vào tập cận trên hữu ích trung bình của các giao dịch mới thêm

Bước 7: Với mỗi k-itemset s trong tập cận trên hữu ích trung bình của các giao dịch ban đầu xuất hiện trong thì:

Bước 8: Với mỗi k-itemset s trong không xuất hiện trong thì:

Bước 9: Với mỗi k-itemset s trong không xuất hiện trong thì:

Bước 9.1: Duyệt lại dữ liệu ban dầu để tính

Bước 10: Phát sinh k-itemset từ tập , nếu bất kỳ k- sub-itemset nào của một ứng viên k-itemset không thuộc thì loại khỏi tập ứng viên

Bước 12: Lập lại bước 5 đến bước 11

Bước 13: Với mỗi s trong , nếu xuất hiện trong thì:

Bước 13.1: Tính giá trị hữu ích trung bình của mỗi item s trong giao dịch mới:

Bước 13.2: Tính giá trị hữu ích trung bình của mỗi item s sau khi cập nhật:

Bước 14: Với mỗi s trong , nếu không xuất hiện trong thì:

Bước 14.1: Tính giá trị hữu ích trung bình của mỗi item s trong giao dịch mới:

Bước 14.2: Duyệt lại dữ liệu ban đầu để tính

Bước 14.3: Tính giá trị hữu ích trung bình của mỗi item s sau khi cập nhật:

Thuật toán khai thác dữ liệu động chỉ tính toán giá trị cho các giao dịch mới, giúp tối ưu hóa quy trình mà không cần phải xử lý lại toàn bộ cơ sở dữ liệu Dựa trên thuật toán 2-pha, phương pháp này mang lại hiệu quả cao trong việc cập nhật và duyệt lại thông tin cần thiết.

UB đã áp dụng các phương pháp để giảm số lượng ứng viên, nhưng chưa thực hiện tính chất bao đóng giảm Đồng thời, việc sử dụng IndexTable giúp tăng tốc độ tính toán và tối ưu hóa bộ nhớ tương tự như thuật toán HAUI-Tree.

Chương này giới thiệu các khái niệm cơ bản về luật kết hợp và quy trình khai thác luật kết hợp Nó cũng đề cập đến giá trị hữu ích và giá trị hữu ích trung bình, đồng thời nêu rõ cơ sở hình thành bài toán khai thác luật kết hợp dựa trên tập hữu ích trung bình.

Chương này trình bày các phương pháp khai thác luật kết hợp dựa trên tập hữu ích trung bình của các tác giả trước, kèm theo ví dụ minh họa cho từng thuật toán Ngoài ra, chương cũng đưa ra những nhận xét quan trọng để làm cơ sở cho việc đề xuất mục đích nghiên cứu ở các bước tiếp theo của luận văn.

XÂY DỰNG THUẬT TOÁN IHAUI-TREE

Cây IHAUI-Tree

 Nút: là một itemset với cấu trúc dữ liệu đã nêu ở trên

Cạnh là đường nối giữa hai nút trong cây IHAUI-Tree Đặc điểm của cây này là nút cha chính là tiền tố của nút con, trong khi nút con được hình thành từ sự kết hợp giữa nút cha và một nút khác có cùng cha với nút cha, nằm bên phải của nó.

Hình 3.1: Cấu trúc cây IHAUI-Tree

Thuật toán IHAUI

 Tập giá trị hữu ích của mỗi item,

 Tỉ lệ ngưỡng hữu ích trung bình tối thiểu (Minimum High Average-Utility Ratio) ,

 CSDL giao dịch ban đầu D ={t 1 ,t 2 ,…,t n },

The high average-utility upper-bound (HAUUB) itemsets and the minimum average utility threshold (D) are essential concepts in analyzing the original dataset These elements help in identifying valuable itemsets that meet or exceed the predefined utility threshold, ensuring efficient data mining and analysis.

 Tập N={t1,t2,…,tk} giao dịch mới được thêm vào

OUTPUT: Tập hữu ích trung bình (high average-utility itemsets - HAU U sau khi thêm T giao dịch N (U=DN)

Bước 1:Tính toán các độ đo cần thiết cho 1-itemset từ tập dữ liệu ban đầu và tập dữ liệu mới được thêm vào

1.1 Khởi tạo L0, L1 là tập các 1-itemset được tạo từ tất cả các items từ tập dữ liệu ban đầu và tập dữ liệu mới Mỗi itemset {X} chứa các thông tin Trans {X} , Pos {X} , au {X} , ub {X}

1.2 Với mỗi giao dịch t k trong tập dữ liệu, ta tính:

1.2.1 Giá trị hữu ích u jk của mỗi items i j : u jk q jk * p j, trong đó: q jk : là số lượng của item i j trong t k pj: là giá trị hữu ích của ij trong tk, j=1 m, k = 1 n

1.2.2: Giá trị hữu ích lớn nhất (maximal item- utility) muk trong mỗi giao dịch tk: mu k = max{u 1k ,u 2k ,…,u mk }, với k =1 n

1.2.4 Cập nhật au{X}, ub{X}, Trans{X}, Pos{X} trong

L0, L1 tương ứng với 2 tập dữ liệu

1.3 Tính các ngưỡng hữu ích trung bình tối thiểu cho tập dữ liệu ban đầu, tập dữ liệu mới thêm N và tập dữ liệu sau khi update U (ngưỡng D , ngưỡng N và ngưỡng U ): ngưỡng D,N = (∑ ∑ ; ngưỡng U = ngưỡng D + ngưỡng N 1.4 Duyệt các 1-itemset X trong L 0 , L 1 :

Tính (tập các các 1-itemset trong L1 có X U ub thỏa ngưỡng U ) và (tập các các 1-itemset X U có X U au thỏa ngưỡng U )

Bước 2: Thực hiện hàm đệ quy IHAUI( , n) để tiến hành tạo ra các từ việc trộn các itemset từ

2.1.1 Khởi tạo //tập các ứng viên (r+1)-itemsets {X} từ giao dịch mới có ub {X}  ngưỡng N

Y = Y + X Thêm Y vào Nếu Y.au > ngưỡng U thì Thêm Y vào

Duyệt lại CSDL ban đầu để tính giá trị Itemset {Y} tương ứng

Nếu Y.ub > ngưỡng U { Thêm {X} vào Thêm {Y} vào Nếu Y.au>ngưỡng U Thêm {Y} vào }

Y = Y + X Nếu Y.ub > ngưỡng U { Thêm {X} vào Thêm {Y} vào Nếu Y.au>ngưỡng U Thêm {Y} vào

Ví dụ minh họa

Cho CSDL các giao dịch và giá trị hữu ích của từng item như Bảng 3.1 và 3.2 như trên, với Ngưỡng là 25

Bảng 3.2: Giá trị hữu ích

Bước 1: Tính toán độ hữu ích, giá trị hữu ích trung bình và cận trên hữu ích trung bình, được kết quả như BẢNG 3.3

Bảng 3.3: Kết quả tính giá trị hữu ích, AU và UB của các 1-itemset

Với Ngưỡng 25, ta thu được tập L 1 (tập các 1-itemset có ub > Ngưỡng) và tiến hành khai thác trên L1 (L 0 rỗng, vì khai thác từ đầu)

Bước 2: Tiến hành thực hiện hàm đệ quy dựa trên tính chất bao đóng giảm, áp dụng các phương pháp tính toán để phát sinh các ứng viên theo cấu trúc cây IHAUI-Tree.

TID u Ak u Bk u Ck u Dk u Ek uFk mu k t1 3 0 2 6 5 2 6 t2 0 10 25 0 0 0 25 t3 0 0 0 0 10 2 10 t4 0 10 12 0 0 0 12 t5 6 0 8 0 10 0 10 t6 0 0 4 6 0 2 6 t7 0 0 2 6 0 0 6 t8 9 20 0 0 10 6 20 t9 6 0 0 6 0 0 6 t10 0 0 4 0 10 0 10

Tính toán tương tự cho các item còn lại, ta thu được cây IHAUI-Tree như sau:

Hình 3.4: Kết quả thu được cây IHAUI-Tree

Khai thác trên cây IHAUI-Tree trên với Ngưỡng là 25, thu được kết quả sau:

Bảng 3.5: Kết quả thu được tập HAU VÀ HAUUB

Tập HAUUB ={{A},{B},{C},{E},{AE},{AF},{AEF},{BC},{EF}}

3.3.2 Cập nhật thêm giao dịch

Giả sử, thêm 3 giao dịch mới (BẢNG 3.5) vào CSDL giao dịch ban đầu (BẢNG 3.1)

Bảng 3.6: CSDL các giao dịch thêm mới

Bước 1: Tính toán độ hữu ích, giá trị hữu ích trung bình và cận trên hữu ích trung bình, được kết quả như BẢNG 3.7

Và giá trị Ngưỡng N tính được là 10 và Ngưỡng U = Ngưỡng D + Ngưỡng N = 10 + 25 = 35

Bảng 3.7: Kết quả tính giá trị hữu ích, AU và UB của các 1-itemset

Với Ngưỡng là 10, ta thu được tập L 1 (tập các 1-itemset có ub > Ngưỡng) và tiến hành khai thác trên L1 (ta có L 0 là L 1 ở lần chạy trước)

Dựa vào L0 và L 1 , ta tính được tập HAUUB của 1-itemset như sau:

Bảng 3.9: 1-itemset sau khi cập nhật

Bước 2: Tiến hành hàm đệ quy dựa trên tính chất bao đóng giảm, áp dụng các phương pháp tính toán để phát sinh các ứng viên theo cấu trúc cây IHAUI-Tree.

TID u Ak u Bk u Ck u Dk u Ek uF k mu k t11 3 10 1 12 0 10 12 t12 0 10 4 6 0 0 10 t13 6 0 2 0 5 2 6

1-Itemset au X ub X 1-Itemset AU X UB X 1-Itemset AU X UB X Ngưỡng

CSDL Trước CSDL Thêm CSDL Cập nhật

Ta nhận thấy {AB} có UB thỏa Ngưỡng N và không nằm trong tập HAUUB D (của lần chạy trước) Do đó, ta tiến hành tính toán lại {AB} Tuy nhiên, sau khi cập nhật, {AB} không còn thỏa mãn điều kiện.

NgưỡngU Vì vậy ta bỏ qua

{AC} có UB thỏa Ngưỡng N nhưng không nằm trong tập HAUUB D của lần chạy trước Do đó, chúng ta cần xem xét lại cơ sở dữ liệu ban đầu để xác định giá trị của {AC} Tuy nhiên, sau khi cập nhật, {AC} vẫn không thỏa mãn Ngưỡng U, vì vậy chúng ta sẽ loại bỏ nó.

{AD} có UB thỏa Ngưỡng N và không nằm trong tập HAUUB D từ lần chạy trước, cho phép {AD} có khả năng thỏa Ngưỡng U sau khi cập nhật Tuy nhiên, khi kiểm tra lại CSDL ban đầu để xác định giá trị của {AD}, chúng ta thấy rằng {AD} sau khi cập nhật vẫn không thỏa Ngưỡng U, do đó ta quyết định bỏ qua {AD}.

AE không đạt Ngưỡng N nhưng có trong tập HAUUB D từ lần chạy trước, nên có khả năng sẽ đạt Ngưỡng U sau khi cập nhật Tuy nhiên, AE vẫn không đạt Ngưỡng U sau khi cập nhật, do đó chúng ta sẽ bỏ qua trường hợp này.

{AF} có UB thỏa Ngưỡng N và nằm trong tập HAUUB D của lần chạy trước, do đó sau khi cập nhật, {AF} có thể thỏa Ngưỡng U Vì vậy, chúng ta cần cập nhật giá trị của {AF} bằng cách cộng {AF} N với {AF} D trong tập HAUUB D để kiểm tra xem có thỏa mãn hay không.

UB sau khi cập nhật thỏa Ngưỡng U , nên ta thêm vào tập HAUUB U

AU AB 1.5 AU AC 6 AU AD 7.5 AU AF 10.5

UB AB 12 UB AC 18 UB AD 12 UB AF 18

AU AB 16 AU AC 15.5 AU AD 18 AU AE 18 AU AF 20.5

UB AB 32 UB AC 34 UB AD 24 UB AE 24 UB AF 44

Tính toán tương tự cho các item còn lại, ta thu được cây kết quả như sau:

Hình 3.7: Kết quả kết hợp các item khác

Khai thác trên cây IHAUI-Tree trên với Ngưỡng là 35, thu được kết quả sau:

AU BC 12.5 AU BD 19 AU BF 10

UB BC 22 UB BD 22 UB BF 12

AU BC 41 AU BD 19 AU BF 23

UB BC 59 UB BD 22 UB BF 32

AU CD 11.5 AU CF 7.5 AU CE 3.5

UB CD 22 UB CF 18 UB CE 6

AU CD 24.5 AU CE 16 AU CF 12.5

UB CD 40 UB CE 22 UB CF 30

Bảng 3.10: Kết quả thu được từ cây IHAUI-Tree

Tập HAUUB = {{A},{B},{C},{D},{E},{F},{AF},{AF},{BC},{CD},{EF}}

Một số nhận xét

Thuật toán sử dụng tính bao đóng giảm của tập cận trên hữu ích trung bình để tối ưu hóa số lượng ứng viên và giá trị cận trên trung bình tối thiểu, từ đó loại bỏ các ứng viên không cần thiết nhằm tăng tốc độ và giảm bộ nhớ trong quá trình khai thác Bên cạnh đó, thuật toán cũng đề xuất một cấu trúc dữ liệu mới, giúp nâng cao hiệu quả tính toán giá trị của itemset và r-itemset dựa trên 1-itemset, thuận tiện cho việc cập nhật dữ liệu.

Tuy nhiên, trong những trường hợp mà số lượng 1-itemset trong tập cận trên hữu ích trung bình mới hoặc số lượng itemset trong tập cận trên hữu ích trung bình của lần chạy trước quá cao (do ngưỡng quá nhỏ hoặc do kích thước CSDL lớn), thuật toán vẫn gặp khó khăn về vấn đề vùng nhớ.

Chương này khám phá tính chất Apriori và ứng dụng của nó trong việc khai thác các tập itemset hữu ích trung bình từ cơ sở dữ liệu có sự biến động Bên cạnh đó, chương cũng phân tích sự thay đổi giá trị của các itemset khi có thêm giao dịch mới, tính toán những thay đổi này và đề xuất cải tiến thuật toán HAUI-Tree để tối ưu hóa việc tính toán các tập itemset.

EF 21 42 35 giá trị của itemset trong cơ sở dữ liệu mới và cập nhật lại tập các itemset hữu ích trung bình Để khi biến động xảy ra, các itemset đã tìm được sẽ được cập nhật mà không cần chạy lại giải thuật từ đầu như HAUI-Tree Đồng thời, chương này cũng trình một cấu trúc dữ liệu cho cho itemset để tối ưu hóa việc tính toán các giá trị khi khai thác và cập nhật giá trị các itemset khi thêm mới giao dịch

Bảng 3.11: Câu trúc itemset của IHAUI và HAUI

THỰC NGHIỆM VÀ ĐÁNH GIÁ

Tiêu đề	Xây Dựng Thuật Toán IHAUI Để Khai Thác Dữ Liệu Dựa Trên Độ Hữu Ích Trung Bình
Tác giả	Nguyễn Minh Tân
Người hướng dẫn	TS. Lê Thị Ngọc Thơ
Trường học	Trường Đại Học Công Nghệ TP. HCM
Chuyên ngành	Công Nghệ Thông Tin
Thể loại	Luận Văn Thạc Sĩ
Năm xuất bản	2018
Thành phố	TP. HỒ CHÍ MINH

Định dạng
Số trang	67
Dung lượng	1,83 MB