(LUẬN văn THẠC sĩ) ứng dụng khai phá luật kết hợp trong phân tích dữ liệu sử dụng web

GIỚI THIỆU TỔNG QUAN

Khai phá dữ liệu sử dụng web

Sự bùng nổ của Internet đã biến World Wide Web thành một kho dữ liệu khổng lồ với hàng triệu máy chủ trên toàn cầu Tài nguyên này chứa đựng nhiều thông tin quý giá cho cá nhân, tổ chức và cộng đồng Gần đây, lĩnh vực khai phá web (Web Mining) đã phát triển mạnh mẽ, thu hút sự chú ý của nhiều nhà nghiên cứu và nhóm phát triển ứng dụng.

Khai phá dữ liệu sử dụng web (Web Usage Mining) là một lĩnh vực nghiên cứu quan trọng trong khai phá web, nơi các máy chủ web ghi lại hoạt động của người dùng qua các yêu cầu truy cập Từ các hồ sơ truy cập web, hay còn gọi là web log, việc áp dụng các kỹ thuật khai phá dữ liệu cho phép khám phá tri thức hữu ích liên quan đến tương tác của người dùng với Internet, đặc biệt là các trang web.

Hình 1.1: Một trích đoạn dữ liệu web log

Khai phá dữ liệu là quá trình phức tạp nhằm phát hiện các mẫu giá trị, mới mẻ và hữu ích trong dữ liệu Đặc biệt, trong lĩnh vực khai phá web, có nhiều phương pháp khác nhau được áp dụng để phát hiện các 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ả áp dụng phương pháp khai phá luật kết hợp để xác định xu hướng truy cập của người dùng thông qua các tập phổ biến Phân tích này hỗ trợ trong việc cấu trúc lại website theo các phân nhóm hiệu quả hơn, xác định vị trí đặt banner quảng cáo tối ưu và gắn quảng cáo sản phẩm phù hợp với người dùng quan tâm, nhằm đạt hiệu quả cao nhất trong chiến lược tiếp thị.

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 mại điện tử, việc hiểu rõ thói quen và xu hướng mua sắm của người dùng là rất quan trọng để xây dựng chiến lược quảng cáo hiệu quả Các nhà phát triển hệ thống cần nắm bắt thông tin này để thiết kế website có cấu trúc khoa học và tiện dụng Một câu hỏi quan trọng đặt ra là liệu có thể xác định nhóm các trang web thường xuyên được truy cập cùng nhau dựa trên dữ liệu truy cập (web log), từ đó phản ánh thói quen và xu hướng truy cập của người dùng hay không.

Dữ liệu đầu vào (Input) là một tập hợp lớn các bản ghi truy cập web (web log) với các trường thông tin xác định, được trích xuất từ tập tin log.

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 khai phá dữ liệu, bài toán phát hiện mối quan hệ kết hợp được giải quyết bằng mô hình luật kết hợp và các thuật toán tương ứng Việc phát hiện mối liên hệ giữa các trang web trong dữ liệu truy cập web đã trở thành một thách thức quan trọng Sau khi dữ liệu đã được tiền xử lý và phân tách theo từng người dùng và phiên truy cập, vấn đề đặt ra là xác định các trang web thường được truy cập cùng nhau Thuật toán khai phá luật kết hợp giúp phát hiện mối tương quan giữa người dùng truy cập các trang web khác nhau, như giữa trang giới thiệu sản phẩm điện tử và trang quảng cáo dụng cụ thể thao Ngoài ứng dụng trong thương mại điện tử, các luật kết hợp còn hỗ trợ các nhà phát triển web tái cấu trúc trang của họ để nâng cao trải nghiệm người dùng Hơn nữa, chúng cũng có thể được áp dụng trong các cơ chế tìm kiếm để tải trước các trang web, giảm thời gian chờ đợi của người dùng khi truy cập vào máy chủ xa.

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 chỉ cải tiến các thuật toán khai thác luật kết hợp hiện có hay đề xuất thuật toán mới, mà còn tiếp cận vấn đề từ góc độ dữ liệu đầu vào.

Tư tưởng Chia để trị (Divide and Conquer) được áp dụng để xử lý tập dữ liệu vào bằng cách phân chia chúng thành các tập con có kích thước phù hợp với bộ nhớ, cho phép xử lý độc lập và tổng hợp kết quả Luận văn sẽ trình bày cơ sở toán học và chứng minh tính đúng đắn của chiến lược này, đồng thời đề xuất mô hình phân tích dữ liệu từ các web log để tạo ra luật kết hợp Các số liệu thực nghiệm sẽ được cung cấp đầy đủ để so sánh Phương pháp Chia để trị mang lại nhiều ưu điểm, trong đó nổi bật là khả năng tối ưu hóa hiệu suất xử lý và giảm thiểu tài nguyên cần thiết.

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ý

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.

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.

LUẬT KẾT HỢP VÀ CÁC KỸ THUẬT KHAI PHÁ LUẬT KẾT HỢP

Khái niệm về luật kết hợp và tập phổ biến

Trong một tập mục I = {i1, i2,…, in}, mỗi phần tử được gọi là một mục (item) và đôi khi còn được gọi là thuộc tính Tập I được xem như là tập các thuộc tính Mỗi tập con của I được gọi là một tập mục (itemset), và số lượng phần tử trong một tập mục được xác định là độ dài hay kích thước của nó.

Trong cơ sở dữ liệu giao dịch D = {t1, t2,…, tm}, mỗi giao dịch ti là một tập con của tập hợp I Số lượng giao dịch trong cơ sở dữ liệu thường được gọi là lực lượng của tập D, phản ánh quy mô và tính đa dạng của dữ liệu giao dịch.

D ký hiệu là |D| hay card(D)) là rất lớn

Trong lĩnh vực khai thác dữ liệu, tập mục Y là một tập con không giao nhau với tập mục X, và luật kết hợp (association rule) được ký hiệu là Y Luật này thể hiện mối liên hệ giữa tập mục Y và tập mục X, cho thấy sự xuất hiện của X có thể kéo theo sự xuất hiện của Y trong các giao dịch Một tập mục được coi là xuất hiện trong giao dịch t nếu nó là tập con của t Độ hỗ trợ của một tập mục, ký hiệu là sup(X), được định nghĩa là tỷ lệ các giao dịch trong tập D chứa tập mục X, được tính bằng công thức sup(X) = C(X)/|D|.

Trong phân tích dữ liệu, độ hỗ trợ (sup(Y)) và độ tin cậy (conf(Y)) là hai chỉ số quan trọng để đánh giá giá trị của luật kết hợp Y Độ hỗ trợ được tính bằng tỷ lệ số giao dịch chứa UY trong tập dữ liệu D, cụ thể là sup(Y) = P(∪Y) = C(∪Y)/|D| Trong đó, C(∪Y) là số lượng giao dịch có chứa UY Độ tin cậy, ngược lại, đo lường tỷ lệ giữa số giao dịch chứa UY và số giao dịch chứa X, được tính bằng conf(Y) = P(Y|X) = C(∪Y)/C(X) = sup(Y)/sup(X) Ký hiệu C(X) đại diện cho số lượng giao dịch có chứa X.

Theo định nghĩa, ta có 0 ≤ sup(Y) ≤ 1 và 0 ≤ conf(Y) ≤ 1 Trong quan niệm xác suất, độ hỗ trợ được hiểu là xác suất xuất hiện của tập mục ∪ Y, trong khi đó, độ tin cậy là xác suất có điều kiện của sự kiện Y khi sự kiện đó đã xảy ra.

Luật kết hợp Y được xem là tri thức có giá trị, hay còn gọi là luật kết hợp mạnh, khi xảy ra đồng thời với điều kiện sup(Y) ≥ minsup và conf(Y) ≥ minconf Trong đó, minsup và minconf là hai giá trị ngưỡng đã được xác định trước Một tập mục có độ hỗ trợ vượt qua ngưỡng minsup sẽ được gọi là tập phổ biến.

Luật kết hợp trong dữ liệu sử dụng web

Sau khi hoàn tất việc tiền xử lý dữ liệu truy cập web và xác định rõ dữ liệu cho từng người dùng cùng từng phiên truy cập, một vấn đề quan trọng cần xem xét là các trang web hoặc tài nguyên nào thường được truy cập đồng thời Khi đã phân định được các phiên truy cập, chúng ta có thể áp dụng mô hình luật kết hợp vào dữ liệu đã thu thập Mỗi trang web hoặc tài nguyên được truy cập sẽ được coi là một mục, trong khi mỗi phiên truy cập sẽ được xem như một giao dịch.

Dữ liệu truy cập web hiện nay được coi là một cơ sở dữ liệu giao dịch, cho phép áp dụng các thuật toán khai phá luật kết hợp để xác định mối liên hệ giữa các trang web thường xuyên được truy cập cùng nhau Trong bối cảnh khai phá web, các luật kết hợp giúp nhận diện các tập hợp trang web có tần suất truy cập cao hơn một ngưỡng nhất định, mà không cần phải có liên kết siêu liên kết giữa chúng Việc áp dụng các giải thuật này có thể phát hiện các mối tương quan giữa những người dùng đã truy cập vào các trang web khác nhau.

Khai phá luật kết hợp là quá trình tìm kiếm các mẫu phổ biến từ các tập mục trong cơ sở dữ liệu giao dịch Nguồn gốc của phương pháp này xuất phát từ bài toán phân tích giỏ hàng tại siêu thị, nhằm xác định những mặt hàng thường được mua cùng nhau Trong lĩnh vực khai phá web, mục tiêu là xác định các trang web có mối liên hệ và thường được truy cập đồng thời với xác suất nhất định Ví dụ, một luật kết hợp trong khai phá web có thể chỉ ra rằng nếu người dùng truy cập vào website của CNN, thì có 60% khả năng họ cũng sẽ truy cập vào 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 là một trong những kỹ thuật phổ biến trong khai thác dữ liệu, được Agrawal và cộng sự giới thiệu để giải quyết bài toán phân tích giỏ hàng tại siêu thị Kể từ đó, nhiều thuật toán khác đã được phát triển, cho thấy lĩnh vực này vẫn thu hút sự quan tâm lớn từ các nhà nghiên cứu.

Khai phá luật kết hợp từ dữ liệu sử dụng web liên quan đến các trang thường được truy cập cùng nhau trong một phiên Trong ngữ cảnh này, các luật kết hợp chỉ ra các trang được truy cập đồng thời với độ hỗ trợ vượt qua một ngưỡng nhất định Agrawal và các cộng sự đã phát triển giải thuật AIS, cho phép tạo ra các tập ứng viên trong mỗi lần duyệt qua cơ sở dữ liệu giao dịch Tuy nhiên, giải thuật này chưa hiệu quả do tạo ra quá nhiều tập ứng viên, dẫn đến tăng dung lượng bộ nhớ và yêu cầu nhiều lần duyệt qua cơ sở dữ liệu, đồng thời sinh ra các luật chỉ có một mục tham gia.

Chính Agrawal và các cộng sự đã phát triển nhiều phiên bản của giải thuật Apriori, bao gồm Apriori, AprioriTid và AprioriHybrid Giải thuật Apriori và AprioriTid tạo ra các tập mục dựa trên các tập phổ biến từ lần duyệt trước mà không cần xem xét các giao dịch AprioriTid cải tiến từ Apriori bằng cách sử dụng cơ sở dữ liệu ngay trong lần duyệt đầu tiên, giúp quá trình đếm ở các lần duyệt sau nhanh hơn với mã nhỏ hơn nhiều so với cơ sở dữ liệu gốc, nâng cao hiệu năng gấp 3 lần so với giải thuật AIS Tiến xa hơn, Agrawal giới thiệu giải thuật AprioriHybrid, trong đó các bước duyệt ban đầu sử dụng Apriori và chuyển sang AprioriTid trong các bước sau nếu kích thước của tập ứng viên có thể được lưu trữ trong bộ nhớ.

Mặc dù có nhiều phiên bản của giải thuật Apriori, nhưng chúng thường tạo ra quá nhiều tập ứng viên không phổ biến với độ dài 2 Để khắc phục vấn đề này, giải thuật Băm và cắt tỉa trực tiếp (DHP – Direct Hashing and Pruning) đã được phát triển, giúp giảm kích thước các tập ứng viên bằng cách loại bỏ những tập mục có độ hỗ trợ thấp hơn ngưỡng minsup Nhờ khả năng lọc bỏ hiệu quả, DHP tỏ ra vượt trội hơn Apriori, đặc biệt trong những trường hợp mà DHP hoàn thành sớm hơn nhiều so với Apriori trong quá trình xử lý cùng một bộ dữ liệu.

Khả năng mở rộng (scalability) là yếu tố quan trọng trong khai phá dữ liệu, với các giải thuật cần đáp ứng sự gia tăng nhanh chóng của dữ liệu Eui-Hong và các cộng sự đã phát triển khả năng mở rộng cho phân bố dữ liệu và ứng viên thông qua giải thuật phân bố dữ liệu thông minh (IDD) và giải thuật phân bố hỗn hợp (HD) Giải thuật IDD 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 ứng viên và di chuyển dữ liệu hiệu quả Giải thuật HD, được cải tiến từ IDD, áp dụng kỹ thuật phân đoạn động nhằm duy trì cân bằng tải tốt hơn trong quá trình xử lý.

Một trong những kỹ thuật nhằm nâng cao khả năng mở rộng trong khai phá dữ liệu là sử dụng cấu trúc dữ liệu bản đồ hỗ trợ phân đoạn (SSM - Segment Support Map) Kỹ thuật này giúp giảm số lượng các tập ứng viên cần đếm, nhờ vào việc SSM chứa độ hỗ trợ của các tập mục có độ dài 1 Các độ hỗ trợ này được cộng lại để xác định giá trị giới hạn trên cho các tập mục có độ dài k Việc áp dụng cấu trúc dữ liệu SSM trong giải thuật Apriori giúp giảm chi phí khởi tạo các tập mục có độ dài lớn.

Để giảm số lượng các tập mục trong SSM, cần kiểm tra xem các độ hỗ trợ có lớn hơn ngưỡng hỗ trợ hay không Bên cạnh đó, các tập mục có độ dài 1 với độ hỗ trợ nhỏ hơn ngưỡng sẽ bị loại bỏ sớm, giúp giảm thiểu số lượng tập mục ở các cấp cao hơn cần được đếm.

Giải thuật tiến hóa đang được sử dụng phổ biến trong nhiều lĩnh vực khoa học kỹ thuật để giải quyết các bài toán phức tạp Những giải thuật này mô phỏng cơ chế tiến hóa trong sinh học và áp dụng vào các bài toán tìm kiếm và tối ưu Đặc biệt, giải thuật tiến hóa đã được áp dụng hiệu quả trong việc khai phá luật hợp, như đã được trình bày trong tài liệu [8].

Giải thuật AprioriAll là một phiên bản cải tiến của giải thuật Apriori, được thiết kế để khai thác các mẫu tuần tự (sequential patterns) Trong quá trình sinh tập ứng viên và duyệt cơ sở dữ liệu giao dịch, thuộc tính định danh người dùng được đưa vào nhằm tối ưu hóa quy trình Mục tiêu chính của giải thuật này là giảm kích thước của tập ứng viên, từ đó giảm số lần duyệt cơ sở dữ liệu, giúp tăng hiệu quả trong việc khai thác dữ liệu.

Dựa trên khái niệm về luật kết hợp thời gian thực, các tác giả đã đề xuất những chiến lược hiệu quả hơn trong việc tìm kiếm các tập phổ biến Thời gian là yếu tố quan trọng trong tất cả các giao dịch và cần được xem xét trong quá trình thu thập dữ liệu, đặc biệt khi không phải tất cả các mục đều tồn tại trong suốt giai đoạn thu thập Khái niệm thời gian thực cũng được áp dụng cho độ hỗ trợ và độ tin cậy, trong đó độ hỗ trợ thời gian thực được định nghĩa là khoảng cách thời gian tối thiểu Vì vậy, một luật kết hợp chỉ được xem xét nếu nó đáp ứng cả ngưỡng độ hỗ trợ thông thường và ngưỡng độ hỗ trợ thời gian thực.

Nhiều nghiên cứu đã cải tiến giải thuật Apriori nhằm nâng cao hiệu quả sinh luật kết hợp Một phiên bản nâng cấp của Apriori, được trình bày trong [22], sử dụng cơ chế duyệt cơ sở dữ liệu theo cả hai chiều tiến và lui để tăng hiệu suất 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 tập ứng viên ngắn hơn nhờ vào cấu trúc cây băm (xem [19]) Một phiên bản khác, IApriori, được giới thiệu trong [20], tối ưu hóa việc kết nối các tập mục để giảm kích thước tập ứng viên Cuối cùng, một giải thuật khác 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ờ đó giảm thời gian và tăng hiệu năng xử lý.

Suneetha và Krishnamoorti đã giới thiệu một phiên bản cải tiến của thuật toán Apriori, nhằm khắc phục nhược điểm của các biến thể trước đó, đó là việc phải duyệt cơ sở dữ liệu giao dịch nhiều lần Phiên bản mới này áp dụng phương pháp tiếp cận Top-Down, thay vì Bottom-Up như trước đây.

Up 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

Khai phá sử dụng Web với giải thuật Apriori

Thuật toán Apriori là một phương pháp kinh điển trong khai phá luật kết hợp, dựa trên nguyên lý rằng bất kỳ tập con nào của một tập phổ biến cũng đều là tập phổ biến Mục tiêu chính của thuật toán này là xác định tất cả các tập phổ biến có thể có trong cơ sở dữ liệu giao dịch Thuật toán hoạt động theo nguyên tắc quy hoạch động, bắt đầu từ các tập phổ biến có độ dài 1 và dần dần tìm kiếm các tập có độ dài lớn hơn Các mục trong thuật toán được sắp xếp theo một thứ tự cố định, giúp tối ưu hóa quá trình tìm kiếm.

Input: Cơ sở dữ liệu giao dịch D = {t 1 , t 2 ,…, t m }

Output: Tập hợp tất cả các tập phổ biến

Tính sup(i j ) = count(i j )/m cho mỗi mục i 1 , i 2 ,…, i n 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à C 1 = {i 1 , i 2 ,…, i n };

Tập các tập phổ biến có độ dài 1 là 1 = {i j | i j ∈ C1, sup(i j ) ≥ minsup}; k=1; termination = false;

Để tạo tập ứng viên C k+1, cần kết hợp các phần tử có độ dài k với k-1 mục trùng nhau Đồng thời, loại bỏ những ứng viên chứa tập con có độ 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 C k+1 Nếu độ hỗ trợ lớn hơn minsup thì kết nạp phần tử đó vào k+1 ;

Thủ tục tạo tập ứng viên C k+1 nhằm sinh ra 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 Quy trình này thực hiện bằng cách nối các tập mục có chung tiền tố và áp dụng nguyên lý Apriori để loại bỏ những tập không thỏa mãn.

Để sinh các tập mục L k+1, ta kết hợp hai tập phổ biến P k và Q k có độ dài k, trong đó chúng trùng nhau ở k-1 mục đầu tiên Các tập mục này sẽ là ứng viên cho tập phổ biến có độ dài k+1.

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 đó i 1 ≤i2≤…≤ik-1≤ik≤ik’

Bước tỉa là quá trình giữ lại tất cả các ứng viên L k+1 đáp ứng nguyên lý Apriori, tức là mọi tập con có độ dài k của nó đều phải là tập phổ biến Cụ thể, với mọi tập con X thuộc Lk+1 và có kích thước nhỏ hơn hoặc bằng k, thì X phải thuộc 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:

Để sinh các luật kết hợp, đố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 điều kiện conf(s (I-s)) = supp(I)/supp(I-s) ≥ minconf, trong đó minconf là ngưỡng tin cậy cho trước.

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

Sau khi tiền xử lý dữ liệu từ web log, chúng ta xác định các phiên truy cập của người dùng, trong đó mỗi phiên được coi là một giao dịch và mỗi trang truy cập là một mục Việc áp dụng thuật toán Apriori giúp xác định các trang thường được truy cập cùng nhau, từ đó cung cấp những tri thức hữu ích cho tiếp thị điện tử và tổ chức lại website nhằm tối ưu hóa trải nghiệm người dùng Các trang đã truy cập sẽ được ký hiệu để dễ dàng quản lý và phân tích.

Cơ sở dữ liệu giao dịch D bao gồm 9 giao dịch với các tập mục như bảng 2.2 Chúng tôi đã áp dụng giải thuật Apriori cho cơ sở dữ liệu này với các ngưỡng được chọn là minsup = 2/9 (khoảng 22%) và minconf = 70%.

B ng 2.2 Cơ sở dữ liệu giao dịch D

Bước đầu tiên là duyệt cơ sở dữ liệu giao dịch D để xác định độ hỗ trợ cho các tập phổ biến có độ dài 1 Những tập mục có độ hỗ trợ dưới 2/9 sẽ bị loại bỏ, nhưng 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 được coi là tập phổ biến (hình 2.1).

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: Kết nối các tập mục có độ dài 1 để tạo ra các tập mục có độ dài 2, sau đó duyệt cơ sở dữ liệu giao dịch D nhằm xác định mức độ hỗ trợ cho từng tập mục Các tập mục có độ hỗ trợ nhỏ hơn 2/9 sẽ bị loại bỏ, từ đó thu được các tập phổ biến (hình 2.2).

Trong bước 2, chúng ta chưa áp dụng nguyên lý Apriori để loại bỏ các tập mục không phù hợp, vì các tập con của các tập mục có độ dài 2 đều là những tập mục có độ dài 1 Như đã phân tích ở bước 1, tất cả các tập mục có độ dài 1 đều là tập phổ biến.

Số lần xuất hiện Độ hỗ trợ

Số lần xuất hiện Độ hỗ trợ

Số lần xuất hiện Độ hỗ trợ

Hình 2.2: oại bỏ các tập mục độ dài 2 có độ hỗ trợ nhỏ hơn minsup=2/9

Bước : Kết nối các tập mục có độ dài 2 để thu được các tập mục có độ dài 3

Trong bước này ta phải sử dụng đến nguyên lý Apriori để loại bỏ bớt những tập mục mà tập con của nó không phải là tập phổ biến

Sau khi kết nối ta thu được các tập sau đây:

Các tập {I 1 , I 3 , I 5 }, {I 2 , I 3 , I 4 }, {I 2 , I 3 , I 5 } và {I 2 , I 4 , I 5 } bị loại bỏ vì tồn tại những tập con của chúng không phải là tập phổ biến Cuối cùng ta còn các tập mục như hình 2.3

Hình 2.3: Các tập phổ biến độ dài 3

Bước 4: Kết nối hai tập mục {I 1 , I 2 , I 3 } và {I 1, I 2 , I 5 } để tạo ra tập mục mới có độ dài 4 là {I 1 , I 2 , I 3 , I 5 } Tuy nhiên, tập mục này bị loại bỏ vì tập con {I 2 , I 3 , I 5 } không phải là tập phổ biến Thuật toán kết thúc.

Số lần xuất hiện Độ hỗ trợ

Số lần xuất hiện Độ hỗ trợ

Tập mục Số lần xuất hiện Độ hỗ trợ

Các tập phổ biến thu được là:

Để sinh ra các luật kết hợp từ tập phổ biến F = {{I 1 }, {I 2 }, {I 3 }, {I 4 }, {I 5 }, {I 1 , I 2 }, {I 1 , I 3 }, {I 1 , I 5 }, {I 2 , I 3 }, {I 2 , I 4 }, {I 2 , I 5 }, {I 1 , I 2 , I 3 }, {I 1 , I 2 , I 5 }}, cần tách các tập này thành hai tập không giao nhau và tính độ tin cậy cho các luật tương ứng Các luật có độ tin cậy vượt ngưỡng minconf = 70% sẽ được giữ lại Ví dụ, với tập phổ biến {I 1 , I 2 , I 5 }, ta có thể xác định các luật kết hợp tương ứng.

R 1 : I 1 , I 2 I 5 conf(R 1 ) = supp({I 1 , I 2 , I 5 })/supp({I 1 , I 2 }) = 2/4 = 50% (R 1 bị loại)

R 4 : I 1 I 2 , I 5 conf(R2) = supp({I1, I2, I5})/supp({I1}) = 2/6 = 33% (R4 bị loại)

R 5 : I 2 I 1 , I 5 conf(R 2 ) = supp({I 1 , I 2 , I 5 })/supp({I 2 }) = 2/7 = 29% (R 5 bị loại)

Theo luật R 2, nếu người dùng quan tâm đến các trang cosmetic.htm và car.htm, thì khả năng cao họ cũng sẽ quan tâm đến trang fashion.htm Điều này có thể được sử dụng làm gợi ý cho một kế hoạch quảng cáo hiệu quả Tương tự, từ luật R 6, nếu người dùng thích xe hơi, họ cũng có thể quan tâm đến thời trang và mỹ phẩm Do đó, việc đặt các banner quảng cáo và liên kết đến các trang fashion.htm và cosmetic.htm trên trang car.htm sẽ tạo sự thuận tiện cho người dùng.

Các kỹ thuật khai phá song song luật kết hợp

Lý thuyết về xử lý song song (parallel processing) bắt đầu cuối những năm

Năm 1940, J Von Neumann đã giới thiệu mô hình otomat tế bào, một dạng tính toán song song với cấu trúc lưới gồm các bộ xử lý trạng thái hữu hạn Kể từ đó, lý thuyết xử lý song song đã trở thành lĩnh vực nghiên cứu quan trọng, tạo ra những tín hiệu tích cực cho việc phát triển mô hình lập trình mới vượt trội hơn so với lập trình tuần tự truyền thống Việc ứng dụng lập trình song song trong khai phá dữ liệu đã thu hút sự quan tâm của nhiều nhà nghiên cứu, đặc biệt trong lĩnh vực khai phá luật kết hợp Nhiều thuật toán khai phá song song luật kết hợp đã được phát triển, trong đó nổi bật là các thuật toán dựa trên nền tảng của thuật toán Apriori do Agrawal và C Shafer đề xuất Các thuật toán này được thiết kế cho hệ thống tính toán song song với kiến trúc không chia sẻ, trong đó mỗi bộ xử lý có bộ nhớ độc lập và có khả năng giao tiếp qua mạng truyền thông bằng cơ chế truyền thông điệp.

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 [2]

Thuật toán đầu tiên phải kể tới đó chính là thuật toán ph n phối độ hỗ trợ

Thuật toán phân phối độ hỗ trợ dựa trên thuật toán Apriori, với N bộ xử lý P1, P2,…, PN, mỗi bộ xử lý xử lý một phần dữ liệu giao dịch D1, D2,…, DN Tại mỗi bước k, các bộ xử lý kết nối các tập phổ biến độ dài k-1 để tạo ra các ứng viên độ dài k, sau đó xác định độ hỗ trợ cục bộ cho từng ứng viên Thông tin về độ hỗ trợ sẽ được trao đổi để cập nhật độ hỗ trợ toàn cục (quá trình đồng bộ hóa) Các bộ xử lý sẽ chọn tập phổ biến k dựa trên minsup và lặp lại quy trình này Tại bước đầu tiên k=1, tất cả bộ xử lý đều bắt đầu từ tập phổ biến độ dài 1, đảm bảo kết quả giống nhau sau mỗi bước Ưu điểm của thuật toán này là không cần trao đổi dữ liệu giữa các bộ xử lý, cho phép chúng hoạt động độc lập và bất đồng bộ Tuy nhiên, nhược điểm là không tận dụng hiệu quả sức mạnh tổng hợp bộ nhớ của toàn hệ thống, với số lượng ứng viên tối đa bị giới hạn bởi dung lượng bộ nhớ |M| của mỗi bộ xử lý.

N, hệ thống sẽ có bộ nhớ tổng thể với dung lượng là N x |M|, nhưng chúng ta vẫn chỉ đếm được |M| tập ứng viên qua mỗi lần lặp bởi vì do tính chất của thuật toán phân phối độ hỗ trợ là mỗi bộ xử lý đều tính toán trên tập ứng viên C k giống hệt nhau Chính vì thế, thuật toán ph n phối liệu (data distribution) đã được đề xuất như một bước cải tiến nhằm khai thác tốt hơn sức mạnh tổng hợp của bộ nhớ hệ thống khi số lượng bộ xử lý tăng lên

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 [2]

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

Phân định các phiên truy cập

Tách các trường dữ liệu

Phân định các phiên truy cập

Tách các trường dữ liệu

Phân định các phiên truy cập

Tách các trường dữ liệu

Phân chia tập các tập phổ biến cho N bộ xử lý

Bộ xử lý P 2 Bộ xử lý P N

Tập các tập phổ biến F

Sinh tập phổ biến dựa trên thuật toán xử lý song song

Bộ xử lý P 1 Bộ xử lý P 2 Bộ xử lý P N

Tập các luật kết hợp mạnh

Trong thuật toán này, mỗi bộ xử lý cập nhật độ hỗ trợ cho các tập thuộc tính ứng cử viên riêng của mình, cho phép hệ thống xử lý nhiều tập trong mỗi lần lặp khi số bộ xử lý tăng lên Tuy nhiên, nhược điểm là mỗi bộ xử lý cần truyền và nhận dữ liệu, điều này chỉ khả thi trong môi trường truyền thông nhanh và ổn định Thuật toán phân phối dữ liệu cũng dựa trên Apriori, trong đó cơ sở dữ liệu giao dịch được chia thành N phần, mỗi phần giao cho một bộ xử lý Mỗi bộ xử lý bắt đầu với tập các tập phổ biến có độ dài 1 giống nhau và tại mỗi bước, tạo tập ứng viên C k bằng cách kết nối các tập phổ biến có độ dài k.

N bộ xử lý, còn Pi chỉ giữ lại 1 phần C k i Sau khi đếm xong độ hỗ trợ, mỗi bộ xử lý

Các bộ xử lý chọn ra các tập phổ biến cục bộ F k i từ C k i tương ứng và tiến hành trao đổi F k i với nhau Mục tiêu là để tất cả các bộ xử lý đều nhận được F k, từ đó tạo ra C k+1 cho lần lặp tiếp theo Quá trình này được lặp lại nhiều lần để tối ưu hóa kết quả.

Mặc dù có những cải tiến, nhưng cả hai thuật toán phân phối độ hỗ trợ và phân phối dữ liệu vẫn gặp phải hạn chế lớn do phải đối chiếu tất cả các giao dịch với mọi tập ứng viên, dẫn đến việc cần đồng bộ hóa ở cuối mỗi pha thực hiện Điều này làm giảm hiệu suất hệ thống khi các bộ xử lý phải chờ nhau hoàn thành công việc Để khắc phục vấn đề này, thuật toán phân phối tập ứng viên được đề xuất nhằm tối ưu hóa việc chia sẻ công việc giữa các bộ xử lý, cho phép chúng hoạt động độc lập và giảm thiểu yêu cầu đồng bộ hóa Thuật toán này phân chia tập phổ biến sao cho mỗi bộ xử lý có thể tạo ra các tập ứng viên độc lập mà không chồng chéo lên nhau Sự phân chia dữ liệu phụ thuộc vào cách chia tập ứng viên; nếu không được thực hiện khéo léo, có thể dẫn đến trùng lặp dữ liệu Sau khi phân hoạch, các bộ xử lý hoạt động độc lập mà không cần truyền thông liên tục, chỉ cần chia sẻ thông tin cần thiết để cắt tỉa các ứng viên không cần thiết Thông tin này có thể được truyền theo chế độ dị bộ, cho phép các bộ xử lý tối ưu hóa quá trình cắt tỉa mà không phải chờ đợi.

Trong tập ε = {ABC, ABD, ABE}, tất cả các thành viên đều có phân đầu chung là AB Các tập thuộc tính như ABCD, ABCE, ABDE và ABCDE cũng có tiền tố AB tương tự Nếu sắp xếp các thuộc tính theo thứ tự từ vựng, chúng ta có thể phân chia các tập phổ biến trong F k dựa vào tiền tố có độ dài k-1 đầu tiên, từ đó cho phép các bộ xử lý hoạt động độc lập.

Mô hình khai phá song song luật kết hợp được xây dựng bằng cách áp dụng một trong ba giải thuật khai phá song song đã đề cập, cho phép xử lý N cơ sở dữ liệu giao dịch con D1, D2,…, DN Mỗi cơ sở dữ liệu Di sẽ được xử lý bởi bộ xử lý Pi, và các bộ xử lý này hoạt động phối hợp thông qua một trong ba thuật toán phân phối độ hỗ trợ, phân phối dữ liệu, hoặc phân phối tập ứng viên Tùy thuộc vào thuật toán được áp dụng, các bộ xử lý có thể hoạt động song song và độc lập hoặc cần trao đổi dữ liệu để đồng bộ Mô hình này yêu cầu kết nối qua mạng truyền thông tốc độ cao và sử dụng các công cụ lập trình song song như thư viện MPI Sau khi tìm được tập các tập phổ biến toàn cục, thuật toán sinh luật kết hợp song song sẽ được áp dụng để tìm các luật kết hợp mạnh bằng cách phân chia tập các tập phổ biến cho các bộ xử lý Việc áp dụng các thuật toán xử lý song song giúp tối ưu hóa tài nguyên phần cứng và nâng cao hiệu năng khai phá so với xử lý tuần tự, tuy nhiên, việc xây dựng hệ thống này đòi hỏi sự phức tạp trong lập trình và chi phí lớn.

Những vấn đề đặt ra khi khai phá luật kết hợp từ dữ liệu web log

Dữ liệu truy cập web, hay còn gọi là web log, thường được ghi nhận bởi máy chủ dưới dạng các tập tin văn bản với các trường thông tin xác định Số lượng trường thông tin này phụ thuộc vào cấu hình của phần mềm máy chủ web Thông thường, dữ liệu sử dụng web bao gồm các trường thông tin như địa chỉ IP, thời gian truy cập, và các trang web đã truy cập.

1 Địa chỉ IP/Tên máy khách (IP Address/Remote host field)

2 Thời điểm truy cập (Date/Time field): chỉ ra thời điểm yêu cầu truy cập từ máy khách được máy chủ ghi nhận và đáp ứng

3 HTTP Request: chỉ ra phương thức trao đổi dữ liệu cũng địa chỉ tài nguyên được truy cập trên máy chủ

4 Mã trạng thái (Status code): chỉ ra kết quả của việc thực hiện yêu cầu truy cập (thành công hay không thành công)

5 Dung lượng dữ liệu trao đổi (Transfer volume field): chỉ ra dung lượng dữ liệu (tính bằng KB) được máy chủ trả về cho máy khách

Ngoài ra còn có một số các trường thông tin khác

Khai thác dữ liệu từ các tập tin log của máy chủ web gặp phải nhiều thách thức Luận văn này sẽ tập trung vào những vấn đề quan trọng liên quan đến quá trình này.

 Các yêu cầu truy cập không phản ánh hành vi của người dùng

Dữ liệu sử dụng web có thể bao gồm thông tin về các yêu cầu truy cập không đến từ người dùng Một trang web thường có nhiều thành phần như hình ảnh, đồ họa, video và âm thanh Người dùng chỉ cần tải trang web thông qua các liên kết hoặc nhập địa chỉ vào trình duyệt Sau khi trang được xử lý, máy chủ gửi lại dữ liệu dưới dạng HTML Khi phân tích trang, trình duyệt tự động gửi thêm yêu cầu đến các tập tin đính kèm, và những yêu cầu này cũng được ghi lại trong tập tin log của máy chủ Tuy nhiên, các yêu cầu tự động này không phản ánh hành vi thực sự của người dùng, do đó cần phải lọc chúng khỏi dữ liệu web log trước khi tiến hành khai thác dữ liệu.

Hình 2.7: Một tập tin web log v i các trường thông tin xác định

Để áp dụng mô hình luật kết hợp vào dữ liệu web, cần xác định rõ các mục (item) và giao dịch (transaction) Trong khai phá sử dụng web, mục là các trang hoặc tập tin được truy cập, trong khi giao dịch là các phiên truy cập của người dùng Phiên truy cập được hiểu là tập hợp các trang web mà một người dùng cụ thể duyệt cho một mục đích nhất định Tuy nhiên, việc phân định các phiên truy cập không hề đơn giản, vì các yêu cầu truy cập thường được máy chủ ghi lại theo trình tự thời gian và có thể xen kẽ giữa các phiên của người dùng khác nhau Do đó, cần có cơ chế để xác định yêu cầu truy cập thuộc về phiên nào.

 Dữ liệu cần xử lý quá lớn và thường xuyên thay đổi

Tất cả các giải thuật khai phá luật kết hợp đều bị giới hạn bởi dung lượng bộ nhớ của hệ thống tính toán, đặc biệt khi số lượng bản ghi cần xử lý quá lớn Nếu không áp dụng các kỹ thuật xử lý bổ sung, hệ thống có thể bị treo Dung lượng dữ liệu truy cập web trên máy chủ được ghi lại dưới dạng tập tin log có thể khác nhau đáng kể trong cùng một khoảng thời gian, tùy thuộc vào số lượng truy cập Mỗi ngày, dung lượng này có thể đạt từ vài chục đến hàng trăm megabyte, tương ứng với hàng ngàn đến hàng trăm ngàn bản ghi Sau vài tuần hoặc vài tháng, lượng dữ liệu tích lũy có thể lên tới hàng gigabyte.

Kích thước dữ liệu vào (10^3)

Dung lượng bộ nhớ (MB)

Hình 2.8: S ti u t n bộ nh khi s mục vào tăng

Giới hạn kích thước bộ nhớ trong Giới hạn kích thước dữ liệu vào

Giả sử chúng ta có một máy tính với cấu hình trung bình và dung lượng bộ nhớ khoảng 1GB Khi áp dụng một giải thuật khai phá luật kết hợp, tại một bước nhất định, cần sinh ra các tập ứng viên có độ dài 2 từ 2 mục bất kỳ trong n mục cho trước Mỗi mục được đánh số bằng một số nguyên có dung lượng 4 byte, dẫn đến việc cần xem xét một số lượng lớn các ứng viên.

Dung lượng bộ nhớ cần thiết để lưu trữ tất cả các ứng viên là:

Dung lượng bộ nhớ trong của máy tính, giới hạn ở mức 1GB (2^30 Byte), quy định rằng số lượng mục dữ liệu tối đa không được vượt quá 16,384 (n ≤ 2^14) Điều này có nghĩa là kích thước dữ liệu mà hệ thống có thể xử lý bị hạn chế bởi bộ nhớ trong Hơn nữa, trên các hệ thống PC, chương trình không thể sử dụng toàn bộ dung lượng bộ nhớ mà còn phải chia sẻ với hệ điều hành và các ứng dụng khác, dẫn đến dung lượng thực tế cho tính toán còn thấp hơn Hình 2.8 minh họa sự gia tăng yêu cầu về dung lượng bộ nhớ khi kích thước dữ liệu đầu vào tăng, với đường thẳng nét đứt thể hiện giới hạn bộ nhớ trong và đường thẳng nét liền đậm thể hiện giới hạn kích thước dữ liệu đầu vào.

Dữ liệu truy cập web thường chỉ được người quản trị máy chủ truy cập và ít khi được công khai vì lý do bảo mật Tuy nhiên, trang web [http://ita.ee.lbl.gov](http://ita.ee.lbl.gov) cung cấp các mẫu truy cập web từ nhiều máy chủ của các công ty và tổ chức nổi tiếng trên thế giới, phục vụ cho nghiên cứu Chúng ta có thể khảo sát các mẫu web log này để đánh giá dung lượng (xem bảng 2.4).

Khi dung lượng dữ liệu cần xử lý vượt quá giới hạn bộ nhớ của hệ thống, một giải pháp tự nhiên là chia nhỏ tập dữ liệu thành các phần có kích thước phù hợp với bộ nhớ và xử lý từng phần một cách độc lập Giải pháp chi tiết cho vấn đề này sẽ được trình bày trong chương tiếp theo.

B ng 2.3: 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

STT Máy chủ web Tổ chức Thời điểm khảo sát

1 EPA-WWW Research Triangle Park, NC

2 SDSC-WWW Trung tâm Siêu máy tính

Khoa Khoa học máy tính thuộc Đại học Calgary, Canada

Công ty ClarkNet – Nhà cung cấp đường truyền Internet tại Washington DC

Trung tâm Vũ trụ Kenedy tại lorida (thuộc NASA)

Một trong những thách thức khi khai thác dữ liệu từ các tập tin server log là dữ liệu luôn được cập nhật liên tục Một số phần mềm máy chủ web cho phép quản trị viên chọn cách ghi lại dữ liệu truy cập trên nhiều tập tin log, với mỗi tập tin mới được tạo ra theo chu kỳ nhất định (ngày/tuần/tháng) hoặc khi dung lượng vượt quá giới hạn Ngoài ra, quản trị viên cũng có thể ghi lại toàn bộ dữ liệu truy cập lên một tập tin log duy nhất, dẫn đến việc kích thước tập tin này sẽ ngày càng tăng.

Giao diện cấu hình ghi dữ liệu truy cập của phần mềm máy chủ web IIS 7.5 cho phép người dùng chọn chế độ ghi log theo lịch trình, trong đó nếu chọn mục "Daily", một tập tin log mới sẽ được tạo ra hàng ngày Ví dụ, vào ngày 24/07, dữ liệu từ 5 ngày trước đó (từ 20/07 đến 24/07) đã được sử dụng để khai phá luật kết hợp, dẫn đến việc thu thập các tập phổ biến và các luật kết hợp tương ứng.

Đến ngày 25/07, dữ liệu đã phát sinh thêm tập tin u_ex120725 trên Microsoft IIS 7.5 Câu hỏi đặt ra là làm thế nào để cập nhật những thay đổi này vào kết quả khai phá? Liệu có cần tiến hành khai phá lại từ đầu với cả 06 tập tin hay chỉ cần khai phá dữ liệu từ tập tin mới và tận dụng kết quả từ lần khai phá trước?

Khi có một cơ sở dữ liệu giao dịch D tại thời điểm t1 và đã khai phá thành công các tập phổ biến cùng luật kết hợp, câu hỏi đặt ra là khi phát sinh thêm giao dịch ∆D tại thời điểm t2, liệu có cần khai phá lại toàn bộ dữ liệu D’ = D ∪ ∆D hay chỉ cần khai thác dữ liệu mới ∆D và sử dụng kết quả từ t1 Vấn đề này rất quan trọng, đặc biệt khi kích thước của D lớn hơn nhiều so với ∆D.

Việc khai phá lại toàn bộ D’ là không cần thiết vì hầu hết các giao dịch trong D’ đã được khai thác trước đó, do đó cần tận dụng các kết quả đã có Chương 3 sẽ giải quyết triệt để vấn đề này dựa trên chiến lược Chia để trị.

Hình 2.10: Các tập tin log được ghi theo từng ngày (từ 20/07 đến 25/07/2012)

Kết luận chương 2

Luật kết hợp là mẫu điển hình trong phân tích mẫu truy cập Web, được trình bày trong chương 2 cùng với các nghiên cứu trước đó Chương này cũng đề cập đến vấn đề khai phá song song luật kết hợp, với các giải thuật xử lý song song được đề xuất bởi Agrawal và C Shafer Ngoài ra, chương 2 chỉ ra những trở ngại cơ bản trong việc khai phá luật kết hợp từ dữ liệu web Để khắc phục những khó khăn này, chương 3 áp dụng tư tưởng Chia để trị nhằm xử lý lượng dữ liệu lớn và thay đổi thường xuyên.

CHƯƠNG : TƯ TƯ NG CHIA Đ T Ị

T ONG KHAI PHÁ LUẬT KẾT HỢP

1 Áp dụng chiến lược Chia để trị trong bài toán khai phá luật kết hợp

Chiến lược Chia để trị (Divide and Conquer) là một trong những phương pháp đầu tiên được áp dụng để giải quyết các bài toán lớn Nguyên tắc của chiến lược này là phân chia bài toán thành các bài toán con, tiếp tục chia nhỏ cho đến khi có thể giải quyết chúng dễ dàng Sau khi tìm ra nghiệm cho các bài toán con, ta kết hợp các nghiệm này để tìm ra nghiệm cho bài toán lớn hơn, cuối cùng đạt được nghiệm cho bài toán ban đầu Thông thường, các bài toán con có hình thức tương tự như bài toán gốc.

Như đã trình bày trong chương 2, dữ liệu web log có hai đặc điểm hết sức quan trọng, đó là:

Kích thước dữ liệu có thể đạt mức lớn đến nỗi các thuật toán khai phá dữ liệu thông thường không thể áp dụng do giới hạn bộ nhớ của hệ thống tính toán.

Dữ liệu web log thường xuyên thay đổi và phát sinh thêm thông tin mới Khi áp dụng các thuật toán khai phá dữ liệu thông thường, chúng ta sẽ phải bắt đầu quá trình khai phá từ đầu mà không thể kế thừa các kết quả đã đạt được trước đó.

Việc áp dụng chiến lược Chia để trị trong khai phá luật kết hợp từ dữ liệu web log là một tư duy tự nhiên Thông thường, quá trình giải quyết bài toán khai phá luật kết hợp được chia thành hai pha.

 Pha 1: Sinh các tập phổ biến

 Pha 2: Sinh luật kết hợp từ các tập phổ biến tìm được ở pha 1

Trong luận văn này, tác giả đề xuất áp dụng chiến lược Chia để trị trong giai đoạn 1 của sinh tập phổ biến Chiến lược này tập trung vào việc chia nhỏ tập dữ liệu cần xử lý, cho phép xử lý từng phần một cách hiệu quả.

Để tìm các tập phổ biến trong cơ sở dữ liệu giao dịch D với ngưỡng hỗ trợ (minsup) là p, chúng ta có thể áp dụng chiến lược Chia để trị Chiến lược này giúp phân chia bài toán lớn thành các bài toán nhỏ hơn, từ đó dễ dàng xác định các tập phổ biến một cách hiệu quả hơn.

Bước 1: Ta chia nhỏ D thành m cơ sở dữ liệu con D 1 , D 2 , …, D m Các c sở dữ liệu con này là các tập con đôi một không giao nhau của D, tức là: D = D 1 ∪ D2

…∪ Dm và Di ∩ Dj = ϕ với ∀i, j ∈ [1, m và i ≠ j.

Bước 2: Áp dụng giải thuật khai phá luật kết hợp cho các cơ sở dữ liệu con D1, D2,…, Dm với ngưỡng độ hỗ trợ p, từ đó thu được các tập F1, F2,…

F_m represents the collection of frequent itemsets corresponding to datasets D_1, D_2, , D_m The frequent itemsets identified within a specific subset of the database D_j are referred to as local frequent itemsets.

Bước 3 trong quy trình phân tích dữ liệu là kết hợp các tập phổ biến từ các tập con F1, F2,…,Fm để tạo ra tập hợp các tập phổ biến tương ứng với cơ sở dữ liệu giao dịch gốc D Những tập phổ biến này được gọi là các tập phổ biến toàn cục (global frequent itemsets) Để áp dụng thành công chiến lược Chia để trị, cần khẳng định rằng việc kết hợp các nghiệm từ các bài toán con sẽ dẫn đến nghiệm của bài toán ban đầu Điều này đòi hỏi phải trả lời hai câu hỏi quan trọng.

1 Việc kết hợp các tập 1 , F 2 , …, m có thể khôi phục lại được tập hay không?

2 Nếu có, thuật toán nào sẽ được sử dụng để xây dựng lại tập từ 1 , F 2 ,…, m ?

2 C sở toán học cho việc áp dụng chiến lược Chia để trị

Ký hiệu * = F1 ∪ F2 ∪ … ∪ Fn cho thấy việc khôi phục tập từ từ các tập F1, F2,…, Fn chỉ khả thi khi F ⊆ F* Điều này có nghĩa là F* phải bảo tồn các tập phổ biến có sẵn trong hệ thống.

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

Nếu F không phải là tập con của F*, điều này cho thấy việc tìm kiếm các tập phổ biến cục bộ trên từng cơ sở dữ liệu con D_j và kết hợp chúng lại có thể đã làm mất đi một số tập phổ biến ban đầu trong D Hình 3.1 minh họa cho vấn đề này Hiện tại, chúng ta không có phương pháp nào để khôi phục các tập phổ biến đã bị mất, do đó chiến lược Chia để trị không còn hiệu quả.

F* chỉ chứa một phần của F, trong khi phần còn lại không thể xác định từ F* do sự kết hợp nghiệm của các bài toán con không giúp tái tạo chính xác nghiệm của bài toán ban đầu Để chứng minh rằng ⊆ F*, chúng ta cần chứng minh rằng mọi phần tử của F đều thuộc F*.

Để chứng minh rằng mọi phần tử thuộc tập F cũng thuộc tập * , ta cần xác định rằng mỗi tập phổ biến I_i ∈ F phải nằm trong ít nhất một trong các tập 1,…, m Điều này có nghĩa là nếu một tập mục là tập phổ biến toàn cục tương ứng với CSDL giao dịch D, thì nó cũng phải là tập phổ biến cục bộ với ít nhất một đoạn CSDL con D_j nào đó của D Cụ thể, nếu sup(D I_i) ≥ p, thì phải tồn tại j ∈ [1, m] sao cho sup(D_j I_i) ≥ p.

D j I i ≥ p Trong đó: Ii là tập mục, p là ngưỡng độ hỗ trợ (minsup), sup ( ) D I i là độ hỗ trợ của I i ứng với cơ sở dữ liệu giao dịch D và sup ( )

D j I i là độ hỗ trợ của Ii ứng với cơ sở dữ liệu giao dịch con Dj

Ta sẽ chứng minh mệnh đề này bằng phương pháp phản chứng:

Giả sử nếu với sup ( ) D I i ≥ p, ∄j ∈ [1, m] sao cho sup ( ) D j I i ≥ p, tức là ∀j ∈ [1, m] ta đều có sup ( ) D j I i < p

Gọi số lần xuất hiện (support count) của I i trong cơ sở dữ liệu D là C I D ( ) i Theo định nghĩa về độ hỗ trợ thì sup ( ) D i D ( ) i

 D Từ giả thiết sup ( ) D I i  p, ta có C I D ( ) i p

Gọi C D j ( ) I i là số lần xuất hiện của Ii trong cơ sở dữ liệu con Dj Theo định nghĩa về độ hỗ trợ thì sup ( ) D j i D j ( ) i j

I  D Từ giả thiết phản chứng: ∀j ∈ [1, m] ta đều có sup ( ) D j I i < p, từ đó suy ra j ( )

C I  p D (∀j ∈ [1, m]) p dụng bất đẳng thức trên lần lượt cho các cơ sở dữ liệu con D 1 , D 2 ,…, D m , ta thu được m bất đẳng thức sau đây:

Cộng các bất đẳng thức trên theo từng vế ta được:

Do D = D 1 ∪ D2 …∪ Dm và các tập D 1 , D 2 ,…, D m đôi một không giao nhau suy ra:

Dễ thấy hai bất đẳng thức (3.1) và (3.5) mâu thuẫn với nhau nên giả thiết phản chứng ban đầu mà chúng ta đưa ra là sai

Nếu một tập mục là tập phổ biến toàn cục ứng với cơ sở dữ liệu D, thì nó cũng là tập phổ biến cục bộ của ít nhất một cơ sở dữ liệu con nào đó của D, tức là thuộc về ít nhất một trong các tập F1, F2, …, Fn, đồng nghĩa với việc nó phải thuộc * Do mọi phần tử thuộc cũng phải thuộc *, nên F ⊆ F* (đpcm) Qua đó, việc áp dụng chiến lược Chia để trị trong khai phá luật kết hợp từ cơ sở dữ liệu giao dịch D là khả thi và có thể khôi phục tập các tập phổ biến toàn cục từ tập các tập phổ biến cục bộ * Trong phần tiếp theo, tác giả sẽ đề xuất 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ị và một thuật toán đơn giản để tìm từ trong *.

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ị

Như đã trình bày trong chương 2, có hai kịch bản có thể xảy ra đối với dữ liệu web log:

Sinh các tập phổ biến cục bộ

Để sinh các tập phổ biến cục bộ từ các mô hình được đề xuất, có thể áp dụng các giải thuật tìm tập phổ biến như Apriori hoặc P-Growth Trong luận văn này, tác giả chọn giải thuật Apriori vì tính đơn giản trong cài đặt và khả năng minh họa hiệu quả cho chiến lược Chia để trị trong việc tìm kiếm các tập phổ biến.

Input: D i : Cơ sở dữ liệu giao dịch con thứ i minsup: Ngưỡng độ hỗ trợ chung

Output: Tập các tập phổ biến cục bộ i function Apriori(Di: CSD giao dịch con, minsup: Ngưỡng support chung)

F 1 = { các tập phổ biến có độ dài 1}; for(k=1; F k != ⍉; k++) {

Ck+1 = Apriori_gen(F k); for each t ∈ D

Hàm Apriori_Gen có chức năng kết nối các tập ứng viên có độ dài k, với k-1 mục đầu tiên giống nhau, nhằm tạo ra các tập phổ biến có độ dài k+1 Cụ thể, hàm này nhận vào tập các tập phổ biến độ dài k và trả về tập ứng viên có độ dài k+1.

C k+1 = ⍉; for each l i ∈ Fk for each l j ∈ Fk if (l i [1]=l j [1]) and (l i [2]=l j [2 ) … and (l i [k-1]=l j [k-1]) and (l i [k] 1) then

Call gen_rules(l k , a m-1 ); end end

Để sinh luật song song, chúng ta cần chia sẻ các tập thuộc tính phổ biến giữa các bộ xử lý trong hệ thống Mỗi bộ xử lý sẽ sinh luật dựa trên các tập phổ biến này bằng cách sử dụng một thuật toán cụ thể Trong quá trình này, để tính độ tin cậy của một luật, các bộ xử lý có thể cần tham chiếu đến độ hỗ trợ của các tập phổ biến được lưu trữ trong bộ nhớ của bộ xử lý khác Do đó, các bộ xử lý cần phải có thông tin về toàn bộ các tập phổ biến trước khi thực hiện thuật toán Khi đã có thông tin đầy đủ, các bộ xử lý sẽ tiến hành sinh luật một cách độc lập và không phụ thuộc lẫn nhau.

Trong chương này, tác giả trình bày ý tưởng và cơ sở toán học cho chiến lược Chia để trị trong khai phá luật kết hợp, đồng thời đề xuất một thuật toán đơn giản để tìm các tập phổ biến toàn cục từ các tập phổ biến cục bộ với độ phức tạp đa thức Tác giả cũng giới thiệu mô hình hệ thống khai phá luật kết hợp từ dữ liệu web log dựa trên chiến lược này và mở rộng cho hệ thống song song với N bộ xử lý Ngoài ra, chương còn phân tích, đánh giá và so sánh ưu nhược điểm của các hệ thống Chương tiếp theo sẽ trình bày các kết quả thực nghiệm nhằm chứng minh ưu điểm của mô hình hệ thống được đề xuất.

Kết luận chương 3

4.1 Đặc trưng của dữ liệu thực nghiệm

Dữ liệu thực nghiệm được thu thập từ máy chủ của Phòng Đào tạo trường Đại học Hàng hải tại địa chỉ http://daotao.vimaru.edu.vn Máy chủ web sử dụng phần mềm Apache Server, được cấu hình để ghi lại nhật ký truy cập hàng ngày.

Dữ liệu mỗi ngày tương ứng với một tập tin log Ta khảo sát trên các tập tin dữ liệu của 04 ngày, từ ngày 20/07/2012 đến ngày 23/07/2012 (bảng 4.1)

B ng Các tập tin dữ liệu th c nghiệm

Tên tập tin Ngày tạo Dung lượng Số bản ghi Số lượng phiên truy cập

Các tập tin log theo định dạng ECL (Extended Common Log Format) là một trong những định dạng log phổ biến Mỗi bản ghi giao dịch trong định dạng này bao gồm 9 trường thông tin cơ bản, được ngăn cách bởi dấu cách trống.

1 Trường tên máy khách (Remote host field)

2 Trường định danh (Identification field)

3 Trường xác thực người dùng (Authuser field)

4 Trường thời gian (Date/time field)

6 Trường mã trạng thái (Status code field)

7 Trường dung lượng dữ liệu trao đổi (Transfer volume field)

8 Trường đối tượng tham chiếu (Referrer field)

9 Trường tác nhân phía người dùng (User agent field)

4.2 Các thao tác tiền xử lý dữ liệu

Dữ liệu web log nguyên thủy không thể trực tiếp áp dụng cho các mô hình khai phá dữ liệu mà cần phải trải qua quá trình tiền xử lý Theo nghiên cứu của Markov và Larose, để khai phá luật kết hợp từ dữ liệu web, dữ liệu web log phải trải qua các giai đoạn tiền xử lý cụ thể Quá trình này sẽ chuyển đổi dữ liệu thành các bản ghi có cấu trúc hơn.

KẾT QUẢ THỰC NGHIỆM