Đăng ký Đăng nhập
Trang chủ Ứng dụng khai phá luật kết hợp trong phân tích dữ liệu dùng web...

Tài liệu Ứng dụng khai phá luật kết hợp trong phân tích dữ liệu dùng web

.PDF
74
93
103

Mô tả:

3 MỤC LỤC LỜI CAM ĐOAN ..................................................................................................... 1 LỜI CẢM ƠN ........................................................................................................... 2 MỤC LỤC ................................................................................................................. 3 DANH MỤC CÁC BẢNG ....................................................................................... 5 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ................................................................. 6 CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN ........................................................... 9 1.1. Khai phá dữ liệu sử dụng web......................................................................... 9 1.2. Phát biểu bài toán khai phá luật kết hợp từ dữ liệu sử dụng web ................. 11 1.3. Hướng tiếp cận của đề tài .............................................................................. 12 1.4. Kết luận chương 1 ......................................................................................... 13 CHƯƠNG 2: LUẬT KẾT HỢP VÀ CÁC KỸ THUẬT KHAI PHÁ LUẬT KẾT HỢP ................................................................................................................ 14 2.1. Khái niệm về luật kết hợp và tập phổ biến.................................................... 14 2.2. Luật kết hợp trong dữ liệu sử dụng web ....................................................... 15 2.3. Một số nghiên cứu về khai phá luật kết hợp ................................................. 15 2.4. Khai phá sử dụng Web với giải thuật Apriori ............................................... 19 2.5. Các kỹ thuật khai phá song song luật kết hợp............................................... 24 2.6. Những vấn đề đặt ra khi khai phá luật kết hợp từ dữ liệu web log ............... 30 2.7. Kết luận chương 2 ......................................................................................... 36 CHƯƠNG : TƯ TƯ NG CHIA Đ T Ị T ONG KHAI PHÁ LUẬT KẾT HỢP ......................................................................................................................... 37 3.1. p dụng chiến lược Chia để trị trong bài toán khai phá luật kết hợp ....... 37 3.2. Cơ sở toán học cho việc áp dụng chiến lược Chia để trị ........................... 38 3.3. Mô hình hệ thống khai phá luật kết hợp từ dữ liệu sử dụng web dựa trên chiến lược Chia để trị ........................................................................................ 40 3.4. Tư tưởng Chia để trị trong khai phá song song luật kết hợp từ dữ liệu sử dụng web .............................................................................................................. 46 3.5. Sinh các tập phổ biến cục bộ ......................................................................... 50 NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 4 3.6. Sinh các luật kết hợp mạnh từ các tập phổ biến ............................................ 51 3.7. Kết luận chương 3 ......................................................................................... 52 CHƯƠNG 4: KẾT QUẢ THỰC NGHIỆM ......................................................... 54 4.1. Đặc trưng của dữ liệu thực nghiệm ............................................................... 54 4.2. Các thao tác tiền xử lý dữ liệu....................................................................... 54 4.2.1. Lọc dữ liệu ............................................................................................. 55 4.2.2. Gán nhãn thời gian ................................................................................. 57 4.2.3. Phân định các phiên truy cập ................................................................. 58 4.3. Một số kết quả thực nghiệm .......................................................................... 63 4.3.1. Mục tiêu của quá trình thực nghiệm ...................................................... 63 4.3.2. Các hệ thống tham gia vào quá trình thực nghiệm ................................ 64 4.3.3. Tổ chức dữ liệu và cách thức tiến hành thực nghiệm ............................ 65 4.3.4. Kết quả thực hiện và đánh giá ................................................................ 66 4.4. Kết luận chương 4 ......................................................................................... 71 KẾT LUẬN ............................................................................................................. 72 TÀI LIỆU THAM KHẢO ..................................................................................... 74 NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 5 DANH MỤC CÁC BẢNG Bảng 2.1: Các phiên truy cập của một người dùng ................................................. 21 Bảng 2.2: Cơ sở dữ liệu giao dịch D ....................................................................... 22 Bảng 2. : Các mẫu web log của một số máy chủ web được thu thập và cung cấp tại trang web http://ita.ee.lbl.gov................................................................................... 34 Bảng 4.1: Các tập tin dữ liệu thực nghiệm .............................................................. 54 Bảng 4.2: Cấu hình máy tính tham gia thử nghiệm ................................................. 64 Bảng 4. : Các bộ dữ liệu thử nghiệm ...................................................................... 66 Bảng 4.4: Kết quả thực nghiệm với 04 bộ dữ liệu trên 03 hệ thống ....................... 67 NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 6 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1: Một trích đoạn dữ liệu web log ................................................................. 9 Hình 2.1: Loại bỏ các tập mục độ dài 1 có độ hỗ trợ nhỏ hơn minsup=2/9 ............ 22 Hình 2.2: Loại bỏ các tập mục độ dài 2 có độ hỗ trợ nhỏ hơn minsup=2/9 ............ 23 Hình 2.3: Các tập phổ biến độ dài 3 ........................................................................ 23 Hình 2.4: Minh họa giải thuật phân phối độ hỗ trợ trên 03 bộ xử lý song song ..... 25 Hình 2.5: Minh họa giải thuật phân phối dữ liệu trên 03 bộ xử lý song song ........ 26 Hình 2.6: Mô hình khai phá song song luật kết hợp từ dữ liệu truy cập web ......... 27 Hình 2.7: Một tập tin web log với các trường thông tin xác định ........................... 31 Hình 2.8: Sự tiêu tốn bộ nhớ khi số mục vào tăng .................................................. 32 Hình 2.9: Cấu hình tập tin log trên Microsoft IIS 7.5 ............................................. 35 Hình 2.10: Các tập tin log được ghi theo từng ngày (từ 20/07 đến 25/07/2012) .... 36 Hình 3.1: Tương quan lực lượng giữa các tập phổ biến cục bộ và toàn cục ........... 38 Hình 3.2: Mô hình khai phá luật kết hợp dựa trên chiến lược Chia để trị .......... 41 Hình 3.3: Mô hình Chia để trị trong khai phá song song luật kết hợp ................ 48 Hình 4.1: Quá trình tiền xử lý dữ liệu truy cập web................................................ 55 Hình 4.2: Yêu cầu truy cập Ri ∈ Sj nếu khoảng cách TS(Ri) - TS(Ro) ≤ θ ............. 60 Hình 4.3: Ri ∈ Sj và Ri+1 ∈ Sj+1 nếu ST(Ri+1) - ST(Ri) ≥ δ....................................... 61 Hình 4.4: Nếu Rk ∈ Sj và Rk tham chiếu đến Ri thì Ri ∈ Sj ..................................... 61 Hình 4.5: p dụng phương pháp heuristic hướng thời gian.................................... 62 Hình 4.6: p dụng phương pháp heuristic hướng cấu trúc ..................................... 62 Hình 4.7: Hệ thống khai phá luật kết hợp dựa trên giải thuật Apriori .................... 65 Hình 4.8a: Biểu đồ so sánh thời gian xử lý của 3 hệ thống với minsup = 0.25% ... 69 Hình 4.8b: Biểu đồ so sánh thời gian xử lý của 3 hệ thống với minsup = 0.5% .... 69 Hình 4.8c: Biểu đồ so sánh thời gian xử lý của 3 hệ thống với minsup = 0.75% ... 70 Hình 4.8d: Biểu đồ so sánh thời gian xử lý của 3 hệ thống với minsup = 1.00% ... 70 NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 7 M ĐẦU Dữ liệu sử dụng web (còn được gọi là dữ liệu truy cập web hay dữ liệu web logs) chứa đựng nhiều thông tin hữu ích phản ánh quá trình tương tác của người dùng với World Wide Web. Dữ liệu này thường được các phần mềm máy chủ web tự động ghi lại dưới dạng các tập tin nhật ký truy cập (web server logs). p dụng các kỹ thuật khai phá dữ liệu, ta có thể phát hiện ra các mẫu (tri thức) tiềm năng và hữu ích từ dữ liệu sử dụng web. Được xem là một trong ba loại hình cơ bản của khai phá web, khai phá sử dụng web đã trở thành một lĩnh vực thu hút sự quan tâm của nhiều nhà nghiên cứu và có nhiều ứng dụng hiệu quả trong thực tế. Trong luận văn này, tác giả tập trung trình bày một hướng nghiên cứu quan trọng trong khai phá sử dụng web, đó là khai phá luật kết hợp từ dữ liệu sử dụng web. Có thể nói khai phá luật kết hợp là một trong những bài toán khai phá dữ liệu điển hình. Từ các luật kết hợp, chúng ta có thể xác định được thói quen cũng như xu hướng truy cập của người dùng, từ đó giúp cho các doanh nghiệp có được những chiến lược kinh doanh phù hợp hoặc giúp cho các nhà phát triển tái cấu trúc lại website sao cho thuận tiện nhất với người dùng. Tuy nhiên, dữ liệu sử dụng web cũng có những nét đặc trưng cơ bản khác với những dạng dữ liệu khác, đó là: dữ liệu thường có dung lượng lớn và phát sinh liên tục theo thời gian thực. Điều này dẫn tới kết quả khai phá dữ liệu tại một thời điểm có thể sẽ không còn phản ánh đúng thực tế ở thời điểm ngay sau đó do dữ liệu đầu vào đã có sự phát sinh mới. Trong điều kiện mà dữ liệu đầu vào thường xuyên thay đổi và thao thác khai phá dữ liệu phải được thực hiện liên tục mỗi khi có dữ liệu mới phát sinh thì chi phí cho quá trình khai phá dữ liệu là rất lớn. Để khắc phục vấn đề này, tác giả đã mạnh dạn đề xuất một phương pháp tiếp cận dựa trên chiến lược Chia để trị khi xử lý tập dữ liệu vào. Tập dữ liệu vào được chia nhỏ thành các phần dữ liệu riêng biệt và tiến hành xử lý độc lập, sau đó sẽ kết hợp lại để thu được kết quả cuối cùng. Phương pháp này giúp làm giảm đáng kế chi phí cho quá trình khai phá dữ liệu trong điều kiện dữ liệu phát sinh liên tục. Khi tiếp cận dựa trên chiến lược Chia để trị thì tập dữ liệu mới phát sinh sẽ được xem là độc lập với các dữ liệu trước đó và quá trình khai phá sẽ chỉ thực hiện với tập dữ liệu mới phát sinh chứ không phải với toàn bộ dữ liệu, nhờ đó sẽ làm giảm đáng kể chi phí cho quá trình khai phá. Trong luận văn này, tác giả cũng dành một phần đáng kể để chỉ ra những cơ sở toán học nhằm chứng minh cho tính đúng đắn của phương pháp được đề xuất. Luận văn NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 8 được xây dựng dựa trên nền tảng những nghiên cứu về khai phá luật kết hợp và khai phá sử dụng web đã được đề xuất từ năm 1995, trong đó đáng chú ý nhất phải kể đến những nghiên cứu của Navathe [16] và Agrawal [3]. Nội dung luận văn được tác giả trình bày bao gồm 04 chương: hương i i thiệu t ng u n: Đặt vấn đề và giới thiệu bài toán mong muốn xử lý, các nghiên cứu trước đó và hướng tiếp cận của đề tài. hương 2 Luật kết hợp và các kỹ thuật kh i phá luật kết hợp: Tập trung trình bày một số khái niệm cơ bản về tập phổ biến và luật kết hợp, các nghiên cứu về khai phá luật kết hợp và một số thuật toán tiêu biểu. Trong chương này, tác giả cũng chỉ ra những khó khăn khi áp dụng khai phá luật kết hợp với dữ liệu web log. hương 3 Tư tưởng “ hi để trị” trong kh i phá luật kết hợp: Trình bày cơ sở toán học cho việc áp dụng tư tưởng Chia để trị và đề xuất thuật toán cho phép tổng hợp các kết quả xử lý trên các tập dữ liệu con để thu được kết quả mong muốn. Tác giả cũng đề xuất mô hình hệ thống phân tích dữ liệu web log để tìm luật kết hợp dựa trên chiến lược Chia để trị . hương o ul ph n t ch liệu và kết u thực nghiệ : Phân tích các đặc trưng dữ liệu web log cũng như trình bày kết quả thực nghiệm và đánh giá. Mặc dù có nhiều cố gắng những chắc chắn không tránh khỏi những thiếu sót, tác giả rất mong sẽ nhận được những ý kiến đóng góp của các thầy giáo, cô giáo và các bạn học viên để tác giả có thể hoàn thiện những kết quả nghiên cứu của mình. NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 9 CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN 1.1. Khai phá dữ liệu sử dụng web Sự bùng nổ của Internet đã khiến cho World Wide Web trở thành một kho dữ liệu khổng lồ với số lượng vô cùng lớn các máy chủ web rải rác khắp nơi trên thế giới. Kho tài nguyên dữ liệu Web tiềm ẩn nhiều mẫu thông tin quý giá đối với mỗi cá nhân, tổ chức hay cả cộng đồng. Trong những năm gần đây, lĩnh vực khai phá web (Web Mining) đã có những bước phát triển mạnh mẽ, thu hút sự quan tâm của nhiều nhà nghiên cứu và các nhóm phát triển ứng dụng. Khai phá dữ liệu sử dụng web (Web Usage Mining) là một hướng nghiên cứu quan trọng trong khai phá web. Các máy chủ web thường ghi lại và tích lũy các dữ liệu phản ánh hoạt động của người dùng mỗi khi nó nhận được một yêu cầu truy cập (hình 1.1). Từ những hồ sơ truy cập web (hay còn gọi là web log), áp dụng các kỹ thuật khai phá dữ liệu có thể giúp khám phá ra các tri thức hữu ích liên quan đến quá trình tương tác của người dùng với Internet mà cụ thể là các trang Web. Hình 1.1: Một trích đoạn dữ liệu web log NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 10 Khai phá dữ liệu được định nghĩa là một quá trình không tầm thường nhằm phát hiện ra những mẫu có giá trị, mới, hữu ích tiềm năng và hiểu được trong dữ liệu [1]. Đối với khai phá sử dụng web nói riêng và khai phá dữ liệu nói chung, có nhiều phương thức tiếp cận khác nhau được sử dụng trong phát hiện mẫu: 1. Phân tích th ng k (Standard Statistical Analysis): Đây là phương pháp thường được sử dụng nhất nhằm trích chọn ra những tri thức liên quan đến người dùng bằng cách phân tích hồ sơ của phiên truy cập sử dụng các kỹ thuật phân tích thống kê tần suất, giá trị trung bình, trung vị,... dựa trên số lần duyệt trang (page view), thời gian duyệt trang (viewing time), chiều dài vết truy cập (navigation path). 2. uật kết hợp (Association Rules): Phát hiện mối quan hệ kết hợp trong tập dữ liệu là một bài toán quan trọng trong khai phá dữ liệu. Bài toán khai phá luật kết hợp thực hiện việc phát hiện ra mối quan hệ giữa các tập thuộc tính (mục) có dạng Y, trong đó và Y là hai tập thuộc tính. Luật kết hợp cho chúng ta biết tập các trang web thường được truy cập cùng với nhau. 3. M u tu n t (Sequential Patterns): sử dụng để phát hiện các mẫu trải dài trên nhiều phiên truy cập mà sự có mặt của các tập mục (item set) được sắp xếp theo thứ tự thời gian của các phiên truy cập. 4. h m cụm (Clustering): sử dụng để nhóm các mục (item) có cùng các đặc trưng thành các tập mục. Đối với khai phá sử dụng web, người ta quan tâm nhiều đến việc phân cụm người dùng (usage clustering) và phân cụm trang web (page clustering). Theo [1 , phân cụm có thể coi là một bài toán mô tả hướng tới việc nhận biết một tập hữu hạn các cụm hoặc các lớp để mô tả dữ liệu. 5. h n l p (Classification): sử dụng để ánh xạ các mục dữ liệu vào các lớp đã được định nghĩa trước. Theo [1], phân lớp thực hiện việc xây dựng các mô hình dự báo nhằm mô tả hoặc phát hiện các lớp/khái niệm cho các dự báo tiếp theo. Trong khai phá sử dụng web người ta sẽ quan tâm nhiều đến việc hồ sơ truy cập của một người dùng sẽ thuộc về một lớp hay một nhóm người dùng cụ thể nào. Trong luận văn này, tác giả lựa chọn hướng tiếp cận dựa trên khai phá luật kết hợp nhằm xác định ra xu hướng truy cập của người dùng được phản ánh bởi các tập phổ biến. Các phân tích này có thể giúp cấu trúc lại các website trong các phân nhóm hiệu quả hơn, hay xác định ra vị trí đặt các banner quảng cáo hiệu quả nhất, NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 11 cũng như gắn việc quảng cáo các sản phẩm nhất định cho những người dùng quan tâm để đạt hiệu quả cao nhất,… 1.2. Phát biểu bài toán khai phá luật kết hợp từ dữ liệu sử dụng web Trong lĩnh vực thương mai điện tử, việc xác định ra thói quen, thị hiếu mua sắm hay xu hướng truy cập thông tin của người dùng là vô cùng quan trọng. Điều này giúp các nhà quản lý có thể đưa ra được những chiến lược quảng cáo hay tiếp thị phù hợp. Đối với các nhà phát triển hệ thống, việc nắm được thói quen hay xu hướng truy cập của người dùng sẽ là những gợi ý hay để xây dựng một website với cấu trúc khoa học và tiện dụng. Bài toán đặt ra là: căn cứ vào dữ liệu truy cập (web log) có thể xác định được ra nhóm các trang web thường được truy cập cùng với nhau hay không vì nhóm này phản ánh thói quen hay xu hướng truy cập của người dùng. Bài toán có thể phát biểu như sau: Dữ liệu đầu vào (Input): là tập các các bản ghi truy cập web (web log) với các trường thông tin xác định, được đọc ra từ tập tin log. Số lượng các bản ghi này là rất lớn. Dữ liệu đầu ra (Output): là tập các trang web (hay tập tin) thường được truy cập cùng với nhau với xác suất trên một ngưỡng nào đó. Trong lĩnh vực khai phá dữ liệu, bài toán này có thể được giải quyết dựa trên mô hình luật kết hợp và các thuật toán khai phá luật kết hợp. Phát hiện mối quan hệ kết hợp trong dữ liệu sử dụng web đã trở thành một trong những bài toán cơ bản của khai phá web. Sau khi dữ liệu truy cập web đã được tiền xử lý, phân tách riêng ứng với từng người dùng và từng phiên truy cập thì một trong những vấn đề thực tiễn đặt ra là những trang web (hay những tập tin tài nguyên) nào thường được truy cập cùng với nhau. Việc sử dụng những giải thuật khai phá luật kết hợp có thể giúp phát hiện ra mối tương quan giữa những người dùng đã viếng thăm trang web giới thiệu các sản phẩm điện tử với những người dùng khác đang viếng thăm trang web quảng cáo các dụng cụ thể thao chẳng hạn. Bên cạnh những ứng dụng trong thương mại điện tử, các luật kết hợp có thể giúp đưa ra những gợi ý cho các nhà phát triển web nhằm tái cấu trúc lại trang web của họ sao cho thuận tiện nhất với người dùng. Các luật kết hợp cũng có thể được ứng dụng trong các cơ chế tìm kiếm nhằm tải trước các trang web để giảm bớt thời gian chờ đợi của người dùng khi truy cập tới một máy chủ web ở xa. NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 12 1.3. Hướng tiếp cận của đề tài Khi áp dụng khai phá luật kết hợp vào dữ liệu web log, ta vấp phải một số những vấn đề sau đây: 1. Dung lượng dữ liệu đọc vào từ tập tin web log có thể quá lớn đến mức không thể áp dụng trực tiếp các giải thuật khai phá luật kết hợp do sự hạn chế về bộ nhớ trong của hệ thống tính toán. 2. Bản thân dữ liệu web log có thể được ghi lại một cách phân tán trên các tập tin rời rạc (theo từng chu kỳ thời gian giờ/ngày/tuần/tháng/năm) và dữ liệu thường xuyên được phát sinh mới sau mỗi chu kỳ. Tuy nhiên khi tiến hành khai phá dữ liệu thì ta cần khai phá toàn bộ dữ liệu từ các tập tin này như một chỉnh thể. Việc dữ liệu phát sinh mới sẽ khiến kết quả khai phá trước đó không còn chính xác và chúng ta phải tiến hành khai phá lại từ đầu sau khi dữ liệu đầu vào đã được cập nhật. Liệu có cách nào có thể tận dụng được các kết quả khai phá trước đó hay không là một vấn đề đặt ra. Trong luận văn, tác giả không tiếp cận dựa trên việc cải tiến các giải thuật khai phá luật kết hợp đã có hay đề xuất áp dụng một giải thuật mới mà tiếp cận giải quyết vấn đề từ góc độ dữ liệu vào. Tư tưởng Chia để trị (Divide and Conquer) được tác giả đề xuất áp dụng khi xử lý tập dữ liệu vào. Chia để trị là một cách tiếp cận hết sức tự nhiên khi giải quyết bài toán. Tập dữ liệu vào sẽ được phân chia thành các tập dữ liệu con (có kích thước phù hợp với bộ nhớ trong) và có thể được xử lý độc lập nhau. Các kết quả xử lý này sẽ được tổng hợp lại để thu được kết quả mong muốn. Trong luận văn, tác giả sẽ tập trung trình bày cơ sở toán học cũng như chứng minh tính đúng đắn của việc áp dụng chiến lược Chia để trị khi xử lý tập dữ liệu vào và đồng thời đề xuất một mô hình hệ thống phân tích dữ liệu thu được từ tập tin các web log để đưa ra các luật kết hợp. Các số liệu thực nghiệm cũng được trình bày một cách đầy đủ để làm cơ sở so sánh. Cách thức tiếp cận dựa trên tư tưởng Chia để trị có nhiều ưu điểm, trong đó có hai ưu điểm lớn nhất đó là: 1. Độc lập với các giải thuật khai phá dữ liệu được sử dụng: Khi tiến hành xử lý các tập dữ liệu con, ta có thể lựa chọn một giải thuật khai phá dữ liệu phù hợp. Thậm chí, không nhất thiết tất cả các tập dữ liệu con đều phải sử dụng cùng một giải thuật mà mỗi tập dữ liệu con có thể dùng một giải thuật khác nhau để xử lý. NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 13 2. Có thể xử lý độc lập trên các hệ thống tính toán khác nhau: Các tập dữ liệu con có thể được xử lý song song và hoàn toàn độc lập trên cùng một hệ thống tính toán hoặc trên các hệ thống khác nhau. 1.4. Kết luận chư ng 1 Chương 1 tập trung giới thiệu bài toán cần giải quyết cũng như hướng tiếp cận của đề tài. Bài toán khai phá luật kết hợp không phải là bài toán mới trong khai phá dữ liệu, tuy nhiên đây là lĩnh vực có nhiều ứng dụng trong thực tế và đang được rất nhiều nhà nghiên cứu quan tâm, đề xuất các thuật toán để giải quyết. Khi áp dụng mô hình luật kết hợp vào dạng dữ liệu đặc thù là dữ liệu web thì việc lựa chọn một thuật toán khai phá dữ liệu phù hợp là yếu tố vô cùng quan trọng. Trong chương 2, tác giả sẽ tập trung trình bày sơ bộ một số các kỹ thuật khai phá luật kết hợp đã được phát triển và các vấn đề gặp phải khi áp dụng với dữ liệu web log. NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 14 CHƯƠNG 2: LUẬT KẾT HỢP VÀ CÁC KỸ THUẬT KHAI PHÁ LUẬT KẾT HỢP 2.1. Khái niệm về luật kết hợp và tập phổ biến Cho một tập mục I = {i1, i2,…, in}, mỗi phần tử thuộc I được gọi là một mục (item). Đôi khi mục còn được gọi là thuộc tính và I cũng được gọi là tập các thuộc tính. Mỗi tập con trong I được gọi là một một tập mục (itemset), số lượng các phần tử trong một tập mục được gọi là độ dài hay kích thước của một tập mục. Cho một cơ sở dữ liệu giao dịch D = {t1, t2,…, tm}, trong đó mỗi ti là một giao dịch và là một tập con của I. Thường thì số lượng các giao dịch (lực lượng của tập D ký hiệu là |D| hay card(D)) là rất lớn. Cho , Y là hai tập mục (hai tập con của I). Luật kết hợp (association rule) được ký hiệu là Y, trong đó và Y là hai tập không giao nhau, thể hiện mối ràng buộc của tập mục Y theo tập mục theo nghĩa sự xuất hiện của sẽ kéo theo sự xuất hiện của Y ra sao trong các giao dịch. Tập mục được gọi là xuất hiện trong giao dịch t nếu như là tập con của t. Độ hỗ trợ của một tập mục (ký hiệu là sup( )) được định nghĩa là tỷ lệ các giao dịch trong D có chứa : sup(X) = C(X)/|D| (2.1) Trong đó C( ) số lượng các giao dịch trong CSDL giao dịch D mà có chứa . Giá trị của luật kết hợp Y được thể hiện thông qua hai độ đo là độ hỗ trợ sup( Y) và độ tin cậy conf( Y). Độ hỗ trợ supp( Y) là tỷ lệ các giao dịch có chứa U Y trong tập D: (2.2) sup( Y) = P( ∪ Y) = C(X ∪ Y)/|D| Trong đó ký hiệu C( ∪ Y) là số lượng các giao dịch có chứa U Y. Độ tin cậy conf( Y) là tỷ lệ các tập giao dịch có chứa U Y so với các tập giao dịch có chứa : (2.3) conf( Y) = P(Y| ) = C( ∪ Y)/C( ) = sup( Y)/sup( ) Trong đó ký hiệu C( ) số lượng các giao dịch có chứa . Từ định nghĩa ta thấy 0 ≤ sup( Y) ≤ 1 và 0 ≤ conf( Y) ≤ 1. Theo quan niệm xác suất, độ hỗ trợ là xác suất xuất hiện tập mục ∪ Y, còn độ tin cậy là xác suất có điều kiện xuất hiện Y khi đã xuất hiện . Luật kết hợp Y được coi là một tri thức (mẫu có giá trị) hay còn gọi là luật kết hợp mạnh (strong association rules) nếu xảy ra đồng thời sup( Y) ≥ minsup NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 15 và conf( Y) ≥ minconf. Trong đó minsup và minconf là hai giá trị ngưỡng cho trước. Một tập mục có độ hỗ trợ vượt qua ngưỡng minsup được gọi là tập phổ biến (frequent itemset). 2.2. Luật kết hợp trong dữ liệu sử dụng web Sau khi dữ liệu truy cập web đã được tiền xử lý, xác định rõ dữ liệu tương ứng với từng người dùng và từng phiên truy cập thì một trong những vấn đề thực tiễn đặt ra là những trang web (hay những tập tin tài nguyên) nào thường được truy cập cùng với nhau. Về cơ bản, một khi đã phân định được các phiên truy cập, ta có thể áp dụng mô hình luật kết hợp vào dữ liệu thu được. Mỗi trang web hay tập tin được truy cập đóng vai trò là một mục, một phiên truy cập được xem là một giao dịch. Dữ liệu truy cập web lúc này được xem là một cơ sở dữ liệu giao dịch và có thể sử dụng các thuật toán khai phá luật kết hợp. Các luật kết hợp có thể được sử dụng để liên kết những trang thường được truy cập cùng với nhau trong một phiên truy cập. Trong ngữ cảnh của khai phá sử dụng web thì các luật kết hợp chỉ ra tập hợp các trang web thường được truy cập cùng với nhau với độ hỗ trợ lớn hơn một ngưỡng quy định trước. Các trang web này không nhất thiết phải được kết nối với nhau thông qua các siêu liên kết (hyperlink). Việc sử dụng các giải thuật khai phá luật kết hợp có thể giúp phát hiện ra mối tương quan giữa những người dùng đã viếng thăm các trang web khác nhau. Khai phá luật kết hợp có thể coi là quá trình tìm ra các mẫu phổ biến (frequent patterns) từ các tập mục nằm trong cơ sở dữ liệu giao dịch. Ý tưởng về khai phá luật kết hợp bắt nguồn từ bài toán Phân tích giỏ hàng ở siêu thị nhằm tìm ra những mặt hàng nào thường được mua cùng với nhau. Trong ngữ cảnh của khai phá web thì khai phá luật kết hợp là nhằm tìm ra những trang web có quan hệ với nhau, được truy cập cùng với nhau với một xác suất nhất định nào đó. Các luật kết hợp trong khai phá sử dụng web thường có dạng: Nếu một người truy cập vào website của CNN thì có 60% khả năng người này cũng sẽ truy cập trang ABC News trong tháng đó 2. . Một số nghiên cứu về khai phá luật kết hợp Khai phá luật kết hợp hay các tập phổ biến là một trong những kỹ thuật khai phá dữ liệu được sử dụng rộng rãi. Giải thuật khai phá luật kết hợp đầu tiên được đề xuất bởi Agrawal và các cộng sự [4, 5] nhằm giải quyết bài toán phân tích giỏ hàng ở siêu thị (market basket analysis). Từ đó cho tới nay, rất nhiều giải thuật NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 16 khác nhau đã được phát triển và khai phá luật kết hợp vẫn là một lĩnh vực thu hút sự quan tâm của nhiều nhà nghiên cứu. Khai phá luật kết hợp từ dữ liệu sử dụng web có liên quan trực tiếp đến các trang (hay tập tin) thường được truy cập cùng với nhau trong một phiên truy cập. Phát biểu trong ngữ cảnh của khai phá sử dụng web thì các luật kết hợp chỉ ra tập các trang được truy cập cùng với nhau với độ hỗ trợ lớn hơn một giá trị ngưỡng nào đó. Agrawal và các cộng sự đã đưa ra giải thuật AIS (xem [4 ). Giải thuật này tạo ra các tập ứng viên trực tiếp trong mỗi lần duyệt qua cơ sở dữ liệu giao dịch. Các tập phổ biến từ lần duyệt trước đó được kiểm tra xem có xuất hiện trong giao dịch hiện thời hay không. Giải thuật này chưa thực sự hiệu quả vì nó tạo ra quá nhiều các tập ứng viên. Điều này dẫn tới việc tăng dung lượng bộ nhớ sử dụng trong khi giải thuật lại yêu cầu phải duyệt qua cơ sở dữ liệu giao dịch nhiều lần và sinh ra những luật chỉ có một mục tham gia. Chính Agrawal và các cộng sự cũng đã phát triển các phiên bản khác nhau của giải thuật Apriori như là: Apriori, AprioriTid và AprioriHybrid (xem [5 ). Các giải thuật Apriori và AprioriTid sinh các tập mục dựa trên những tập phổ biến được tìm thấy ở lần duyệt trước đó mà không cần phải xét tới các giao dịch. Giải thuật AprioriTid được phát triển dựa trên giải thuật Apriori bằng cách sử dụng cơ sở dữ liệu ngay trong lần duyệt đầu tiên. Quá trình đếm trong các lần duyệt tiếp theo có thể được thực hiện bằng các sử dụng các mã được tạo ra từ lần duyệt đầu tiên có kích thước nhỏ hơn nhiều so với cơ sở dữ liệu gốc. Nhờ đó, hiệu năng xử lý của giải thuật này nhanh gấp 3 lần giải thuật AIS. Phát triển một bước nữa, Agrawal đề xuất giải thuật AprioriHybrid. Giải thuật AprioriHybrid được thực hiên dựa trên nguyên tắc: những bước duyệt ban đầu sẽ sử dụng giải thuật Apriori và ở những bước duyệt sau đó sẽ chuyển sang dùng giải thuật AprioriTid nếu kích thước của tập ứng viên có thể lưu trữ vừa trong bộ nhớ. Mặc dù có nhiều phiên bản khác nhau của giải thuật Apriori được phát triển, vấn đề với các giải thuật Apriori đó là chúng tạo ra quá nhiều các tập ứng viên có độ dài 2 không phải là tập phổ biến. Một giải thuật Băm và cắt tỉa trực tiếp (DHP–Direct Hashing and Prunning) [8 đã được phát triển có tác dụng làm giảm kích thước của các tập ứng viên bằng cách lọc bỏ khỏi bảng băm các tập mục có độ hỗ trợ không vượt quá ngưỡng minsup. Nhờ khả năng lọc bỏ rất ưu việt mà giải thuật DHP tỏ ra hiệu quả hơn nhiều so với giải thuật Apriori (trong một số trường NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 17 hợp, với cùng một bộ dữ liệu vào, khi DHP đã thực thi xong thì Apriori mới đang ở lần duyệt thứ 2). Khả năng mở rộng (scalability) là yếu tố vô cùng quan trọng trong khai phá dữ liệu. Các giải thuật cần có khả năng mở rộng để đáp ứng với sự gia tăng nhanh chóng của dữ liệu. Eui-Hong và các cộng sự cố gắng tạo ra khả năng mở rộng đối với sự phân bố dữ liệu và phân bố các ứng viên bằng cách sử dụng giải thuật phân bố dữ liệu thông minh (IDD-Intelligent Data Distribution) và giải thuật phân bố hỗn hợp (HD-Hybrid Distribution) (xem [6 ). Giải thuật IDD giúp giải quyết vấn đề quá tải trong trao đổi dữ liệu và tính toán thừa bằng cách sử dụng bộ nhớ gộp để phân đoạn các ứng viên và di chuyển dữ liệu một cách hiệu quả. Giải thuật HD được cải tiến từ IDD bằng cách sử dụng kỹ thuật phân đoạn động các ứng viên để duy trì tốt cân bằng tải trong xử lý. Một trong những kỹ thuật được sử dụng nhằm đáp ứng khả năng mở rộng trong khai phá dữ liệu đó là sử dụng một cấu trúc dữ liệu gọi là bản đồ hỗ trợ ph n đoạn (SSM - Segment Support Map) [7 . Kỹ thuật này giúp làm giảm số lượng các tập ứng viên phải đếm. Cấu trúc SSM chứa độ hỗ trợ (support count) của các tập mục có độ dài 1. Các độ hỗ trợ riêng lẻ sẽ được cộng vào với nhau để có được giá trị giới hạn trên (ngưỡng) cho các tập mục có độ dài k. Sử dụng cấu trúc dữ liệu SSM trong giải thuật Apriori, chi phí để khởi tạo các tập mục có độ dài 1 có thể được giảm giảm xuống bằng cách kiểm tra các độ hỗ trợ trong SSM có lớn hơn ngưỡng độ hỗ trợ hay không. Hơn thế nữa, các tập mục độ dài 1 có độ hỗ trợ nhỏ hơn ngưỡng sớm bị loại bỏ sẽ giúp giảm số lượng các tập mục ở cấp cao hơn cần phải đếm. Bên cạnh đó, các giải thuật tiến hóa (evolutionary algorithms) cũng đang được sử dụng rộng rãi để giải quyết các bài toán thuộc về nhiều lĩnh vực khoa học kỹ thuật khác nhau. Giải thuật tiến hóa mô phỏng cơ chế tiến hóa trong sinh học và áp dụng chúng trong việc giải quyết các bài toán, đặc biệt là các bài toán tìm kiếm và tối ưu. Giải thuật tiến hóa đã được áp dụng để giải quyết bài toán khai phá luật hợp như giới thiệu trong [8]. Một phiên bản khác của giải thuật Apriori là giải thuật AprioriAll được phát triển nhằm phục vụ cho khai phá các m u tu n t (sequential patterns) [14 . Thuộc tính định danh người dùng được đưa vào tại mỗi bước sinh tập ứng viên và tại mỗi bước duyệt cơ sở dữ liệu giao dịch. Giải thuật có mục đích làm giảm kích thước của tập ứng viên nhằm giảm số lần duyệt cơ sở dữ liệu. NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 18 Dựa trên khái niệm về luật kết hợp thời gian th c (temporal association rule), các tác giả [6, 7] đã đưa ra những chiến lược thực sự hiệu quả hơn. Trường thời gian có mặt trong tất cả các giao dịch và cần phải được xem xét tới trong quá trình tìm kiếm các tập phổ biến đặc biệt là khi không phải tất cả các tập mục đều tồn tại trong suốt giai đoạn thu thập dữ liệu (data gathering period). Khái niệm thời gian thực (temporal) được mở rộng cho độ hỗ trợ và độ tin cậy. Độ hỗ trợ thời gian th c được xem là khoảng cách thời gian t i thiểu (minimum interval width). Do đó, một luật kết hợp sẽ chỉ được xem xét nếu nó thỏa mãn cả ngưỡng độ hỗ trợ thông thường và ngưỡng độ hỗ trợ thời gian thực, Có nhiều nghiên cứu khác nhằm cải tiến giải thuật Apriori để tăng hiệu quả trong việc sinh các luật kết hợp. Một phiên bản nâng cấp của giải thuật Apriori được trình bày trong [22 sử dụng cơ chế duyệt cơ sở dữ liệu giao dịch theo cả hai chiều tiến và lui để làm tăng hiệu quả của thuật toán. iang-wei Liu và các cộng sự cũng đề xuất một giải thuật khai phá luật kết hợp cải tiến với thời gian duyệt các tập ứng viên ngắn hơn nhờ sử dụng cấu trúc cây băm (xem [19 ). Một phiên bản khác của giải thuật Apriori được trình bày trong [20 với tên gọi là IApriori. Giải thuật này tối ưu việc kết nối các tập mục để tạo ra tập phổ biến nhằm làm giảm kích thước của tập ứng viên. Một giải thuật khác được trình bày trong [21 sử dụng cơ chế quét cơ sở dữ liệu chỉ một lần để tạo ra các tập phổ biến nhở đó làm giảm thời gian và tăng hiệu năng xử lý. Suneetha và Krishnamoorti đã đề xuất một phiên bản cải tiến khác của giải thuật Apriori [15]. Giải thuật Apriori và một số biến thể trước đó của nó có nhược điểm là phải duyệt cơ sở dữ liệu giao dịch nhiều lần. Giải thuật do Suneetha và Krishnamoorti đề xuất dựa trên phương pháp tiếp cận Top-Down thay vì BottomUp như giải thuật Apriori truyền thống, nhờ đó làm giảm đáng kể số lần phải duyệt cơ sở dữ liệu giao dịch. Một hướng tiếp cận khác nhằm tăng hiệu năng của các giải thuật khai phá luật kết hợp đó là sử dụng một cấu trúc dữ liệu thực sự phù hợp như cây mẫu phổ biến (frequent pattern tree) chẳng hạn. Han và các cộng sự [8] đã giới thiệu giải thuật nổi tiếng với tên gọi P-Growth. Đây là một trong những giải thuật quan trọng đánh dấu bước phát triển trong những nghiên cứu về khai phá luật kết hợp. Giải thuật này tránh việc phải tạo ra các tập ứng viên và cần ít lần duyệt cơ sở dữ liệu hơn. Giải thuật này đã giúp giải quyết vẫn đề ngẽn cổ chai thường hay gặp phải đối với giải thuật Apriori nhưng bản thân giải thuật này không phải là không có NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 19 những hạn chế. Giải thuật P-Growth không phù hợp áp dụng trong trường hợp ngưỡng độ hỗ trợ (minsup) thường xuyên thay đổi. Mỗi khi ngưỡng độ hỗ trợ thay đổi lại yêu cầu phải xây dựng lại cây P mà công việc này đòi hỏi khá nhiều chi phí về thời gian và bộ nhớ. Giải thuật này không phù hợp cho việc khai phá dữ liệu tăng dần (cơ sở dữ liệu liên tục thay đổi, tập dữ liệu mới liên tục được thêm vào và những tập dữ liệu cũ có thể bị xóa bỏ dẫn tới việc phải xây dựng lại cây P) [9]. Mặc dù có nhiều cải tiến được đề xuất, nhưng hầu hết các giải thuật đều vấp phải vấn đề trở ngại đó là phải duyệt cơ sở dữ liệu giao dịch nhiều lần. Điều này thực sự không tối ưu khi tiến hành khai phá luật kết hợp từ dữ liệu sử dụng web vì dữ liệu sử dụng web có những nét đặc thù riêng với số lượng giao dịch là rất lớn. Các nghiên cứu hiện nay nhằm tăng hiệu năng của các giải thuật khai phá luật kết hợp thường tập trung vào việc giảm số lần duyệt cơ sở dữ liệu giao dịch và giảm chi phí về bộ nhớ. Số lần duyệt cơ sở dữ liệu giao dịch lớn sẽ dẫn tới việc phải truy xuất bộ nhớ ngoài nhiều lần và đặt gánh nặng lên hệ thống vào/ra. 2.4. Khai phá sử dụng Web với giải thuật Apriori Thuật toán Apriori là một thuật toán kinh điển áp dụng trong khai phá luật kết hợp. Thuật toán dựa trên nguyên lý Apriori tập con bất kỳ của một tập phổ biến cũng là một tập phổ biến . Mục đích của thuật toán Apriori là tìm ra được tất cả các tập phổ biến có thể có trong cơ sở dữ liệu giao dịch D. Thuật toán hoạt động theo nguyên tắc quy hoạch động, nghĩa là từ các tập i = { ci | ci là tập phổ biến, |ci| = 1} gồm mọi tập mục phổ biến có độ dài i (1 ≤ i ≤ k), đi tìm tập k+1 gồm mọi tập mục phổ biến có độ dài k+1. Các mục i1, i2,…, in trong thuật toán được sắp xếp theo một thứ tự cố định. Thuật toán Apriori: Input: Cơ sở dữ liệu giao dịch D = {t1, t2,…, tm}. Ngưỡng tối thiểu minsup > 0. Output: Tập hợp tất cả các tập phổ biến. Begin Tính sup(ij) = count(ij)/m cho mỗi mục i1, i2,…, in bằng cách quét CSDL một lần và đếm số lần xuất hiện của mỗi mục; Tập ứng viên có độ dài 1 là C1 = {i1, i2,…, in}; Tập các tập phổ biến có độ dài 1 là 1 = {ij | ij ∈ C1, sup(ij) ≥ minsup}; k=1; termination = false; NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 20 Repeat Fk+1 = ⍉; Tạo tập ứng viên Ck+1 bằng các kết hợp các phần tử có độ dài k có k-1 mục trùng nhau và loại bỏ các ứng viên có chứa tập con độ dài k không thuộc k; Quét CSDL một lần và tính toán độ hỗ trợ cho mỗi phần tử của Ck+1. Nếu độ hỗ trợ lớn hơn minsup thì kết nạp phần tử đó vào k+1; If Fk+1 = ⍉ then termination=true Else k=k+1; Until termination; End; Thủ tục tạo tập ứng viên Ck+1 có nhiệm vụ sinh ra (generation) các tập mục có độ dài k+1 từ các tập mục có độ dài k trong tập k. Thủ tục này được thi hành thông qua việc nối (join) các tập mục có chung các tiền tố (prefix) và sau đó áp dụng nguyên lý Apriori để loại bỏ bớt những tập không thỏa mãn:  Bước nối: Sinh các tập mục Lk+1 là ứng viên của tập phổ biến có độ dài k+1 bằng cách kết hợp hai tập phổ biến Pk và Qk có độ dài k và trùng nhau ở k-1 mục đầu tiên: Lk+1 = Pk + Qk = {i1, i2,…, ik-1, ik, ik’} Với Pk = {i1, i2,…, ik-1, ik} và Qk = {i1, i2,…, ik-1, ik’}, trong đó i1≤i2≤…≤ik-1≤ik≤ik’.  Bước tỉa: Giữ lại tất cả các ứng viên Lk+1 thỏa thỏa mãn nguyên lý Apriori tức là mọi tập con có độ dài k của nó đều là tập phổ biến (∀X ⊆ Lk+1 và |X| = k thì X ∈ Fk). Trong mỗi bước k, thuật toán Apriori đều phải duyệt cơ sở dữ liệu giao dịch D. Khởi động thuật toán sẽ tiến hành duyệt D để có được 1 (loại bỏ những mục có độ hỗ trợ nhỏ hơn minsup). Kết quả của thuật toán là tập gồm các tập phổ biến có độ dài từ 1 đến k: F = F1 ∪ F2 ∪ … ∪ Fk Để sinh các luật kết hợp thì đối với mỗi tập phổ biến I ∈ , ta xác định các tập mục không rỗng là con của I. Với mỗi tập mục con s không rỗng của I ta sẽ thu được một luật kết hợp s (I-s) nếu độ tin cậy thỏa mãn: conf(s (I-s)) = supp(I)/supp(I-s) ≥ minconf với minconf là ngưỡng tin cậy cho trước. NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 21 B ng 2.1: Các phi n truy cập của một người dùng Phiên truy cập Các trang đã truy cập Session 1 /shopping/comestic.htm , /shopping/fashion.htm , /cars.htm Session 2 /shopping/fashion.htm , /news.htm Session 3 /shopping/fashion.htm , /sport.htm Session 4 /shopping/comestic.htm , /shopping/fashion.htm , /news.htm Session 5 /shopping/comestic.htm , /sport.htm Session 6 /shopping/fashion.htm , /sport.htm Session 7 /shopping/comestic.htm , /sport.htm Session 8 /shopping/comestic.htm , /shopping/fashion.htm , /sport.htm , /cars.htm Session 9 /shopping/comestic.htm , /shopping/fashion.htm , /sport.htm Giả sử sau khi tiền xử lý dữ liệu thu được từ web log, ta xác định được các phiên truy cập của người dùng như bảng 2.1. Ở đây mỗi phiên truy cập có thể coi là một giao dịch và mỗi trang được truy cập là một mục. Việc áp dụng giải thuật Apriori có thể giúp xác định được những trang nào thường được truy cập cùng với nhau. Những mẫu thu được sẽ cung cấp những tri thức rất hữu ích phục vụ cho những lĩnh vực như tiếp thị điện tử hay tổ chức lại website sao cho thuận tiện nhất đối với người dùng. Để ngắn gọn, ta ký hiệu các trang đã truy cập như sau: /shopping/comestic.htm I1 /shopping/fashion.htm I2 /sport.htm I3 /news.htm I4 /cars.htm I5 Ta có cơ sở dữ liệu giao dịch D gồm 9 giao dịch với các tập mục như bảng 2.2. p dụng giải thuật Apriori cho cơ sở dữ liệu giao dịch này với các ngưỡng được lựa chọn là minsup = 2/9 ≈ 22% và minconf = 70%. NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ 22 B ng 2.2 Cơ sở dữ liệu giao dịch D Giao dịch Tập mục T01 I1 , I2 , I5 T02 I2 , I4 T03 I2 , I3 T04 I1 , I2 , I4 T05 I1 , I3 T06 I2 , I3 T07 I1 , I3 T08 I1, I2, I3, I5 T09 I1 , I2 , I3 Bước 1: Duyệt CSDL giao dịch D để xác định độ hỗ trợ cho các tập phổ biến có độ dài 1. Các tập mục có độ hỗ trợ nhỏ hơn 2/9 sẽ bị loại bỏ. Trong trường hợp này chưa có tập mục nào bị loại, tất cả các tập đều là tập phổ biến (hình 2.1) Tập mục Số lần xuất hiện Độ hỗ trợ {I1} 6 6/9 {I2} 7 7/9 {I3} 6 6/9 {I4} 2 2/9 {I5} 2 2/9 Tập phổ Số lần biến xuất hiện Độ hỗ trợ {I1} 6 6/9 {I2} 7 7/9 {I3} 6 6/9 {I4} 2 2/9 {I5} 2 2/9 Hình 2.1: oại bỏ các tập mục độ dài 1 có độ hỗ trợ nhỏ hơn minsup=2/9 Bước 2: Tạo ra các tập mục có độ dài 2 bằng cách kết nối các tập mục có độ dài 1, duyệt CSDL giao dịch D để xác định độ hỗ trợ cho từng tập mục và loại bỏ các tập mục có độ hỗ trợ nhỏ hơn 2/9 để thu được các tập phổ biến (hình 2.2). Trong bước 2 này ta chưa cần sử dụng nguyên lý Apriori để tỉa bớt các tập mục không thỏa mãn vì tập con của các tập mục độ dài 2 là những tập mục có độ dài 1 và như đã xét ở bước 1, những tập mục có độ dài 1 đều là tập phổ biến. NGUYỄN VƯƠNG THỊNH – LỚP K15T4 LUẬN VĂN THẠC SỸ
- Xem thêm -

Tài liệu liên quan