TỔNG QUAN VỀ KHAI THÁC WEB
Khai thác Web (Web mining)
Sự phát triển mạnh mẽ của Internet và Intranet mang lại nhiều lợi ích to lớn, khiến Internet trở thành kênh thông tin quan trọng về khoa học, kinh tế, thương mại và quảng cáo Chi phí duy trì trang Web trên Internet thấp hơn nhiều so với việc đăng tin trên báo chí, đồng thời cho phép cập nhật nhanh chóng tới hàng triệu người dùng toàn cầu Điều này chứng tỏ tầm quan trọng của Internet trong đời sống con người trên mọi lĩnh vực Từ đó, một khối lượng thông tin đa dạng khổng lồ đã được tạo ra, biến World Wide Web thành một lĩnh vực phong phú cho nghiên cứu khai thác dữ liệu Nghiên cứu về khai thác Web đang phát triển mạnh mẽ, bao gồm nhiều lĩnh vực như thu hồi thông tin và trí tuệ nhân tạo.
Khai thác Web, mặc dù chưa có định nghĩa rõ ràng, được hiểu là kỹ thuật phân tích và khai thác thông tin hữu ích từ World Wide Web Nó có thể được hình dung như sự kết hợp giữa khai thác dữ liệu và môi trường Internet, nhằm mục đích tối ưu hóa việc thu thập và xử lý thông tin.
Khai thác Web = Khai thác dữ liệu + World Wide Web
Khai thác Web là quá trình tìm kiếm và chọn lọc các mô hình cũng như tri thức hữu ích từ cơ sở dữ liệu Web lớn, nhằm đáp ứng nhu cầu của người dùng, nhà quản lý và các nhà nghiên cứu hiện nay.
Đặc điểm của khai thác Web
Sau đây là những thách thức cũng như thuận lợi trong lĩnh vực khai thác Web
Dữ liệu Web quá lớn để tổ chức thành kho dữ liệu
Cơ sở dữ liệu truyền thống thường có kích thước nhỏ và được lưu trữ tập trung, trong khi kích thước của Web lại rất lớn, lên đến hàng terabytes, và không ngừng thay đổi, phân tán trên nhiều máy tính toàn cầu Tính đến tháng 04/2016, đã có hơn 1 tỷ website trên Internet, với trung bình 44 triệu website mới xuất hiện trong 4 tháng đầu năm 2016 Thống kê vào tháng 01/2016 cho thấy có hơn 60 nghìn tỷ trang web được đánh chỉ số trên Google, với kích thước trung bình từ 5-10KB mỗi trang, tạo nên tổng kích thước khổng lồ cho các trang web này Sự gia tăng nhanh chóng số lượng trang web khiến việc xây dựng một kho dữ liệu để lưu trữ, sao chép hay tích hợp dữ liệu trên Web trở nên gần như không khả thi.
Hình 2.1 Thống kê số lượng Website (tháng 04/2016) [1]
[1] http://news.netcraft.com/archives/2016/04/21/april-2016-web-server-survey.html
[2] http://expandedramblings.com/index.php/by-the-numbers-a-gigantic-list-of-google- stats-and-facts/.
Độ phức tạp của trang Web là rất lớn
Dữ liệu trên Web không đồng nhất, khác với các cơ sở dữ liệu truyền thống, với nhiều loại ngôn ngữ, định dạng và từ vựng đa dạng Các trang Web được coi là “một thư viện kỹ thuật số khổng lồ” nhưng lại thiếu sự sắp xếp theo tiêu chuẩn, gây khó khăn cho việc tìm kiếm thông tin cần thiết.
Web là nguồn tài nguyên mà thông tin có độ thay đổi cao
Web không chỉ thay đổi thông tin mà còn có sự gia tăng liên tục về số lượng trang Web Theo thống kê, trong tháng 04/2016, Google đã nhận được hơn 87 triệu yêu cầu gỡ bỏ URL từ các chủ sở hữu bản quyền và tổ chức Các công ty quảng cáo và trung tâm dịch vụ Web thường xuyên cập nhật trang Web của họ, đồng thời, sự kết nối thông tin và truy cập vào các bản ghi Web cũng được cải tiến liên tục.
Web phục vụ cộng đồng người dùng rộng lớn và đa dạng
Theo thống kê, tính đến tháng 11/2015, toàn cầu có hơn 3.2 tỷ người sử dụng Internet, và con số này vẫn đang gia tăng Mỗi người dùng có kiến thức và nhu cầu khác nhau, nhưng phần lớn không hiểu rõ về cấu trúc mạng thông tin hoặc cách tìm kiếm hiệu quả, dẫn đến việc họ thường "lạc" trong kho tàng thông tin khổng lồ Hệ quả là nhiều người cảm thấy nhàm chán vì mất thời gian và công sức tìm kiếm nhưng lại nhận được thông tin không hữu ích, thậm chí là thông tin vô ích.
[3] https://www.google.com/transparencyreport /removals/copyright/
[4] http://www.itu.int/en/ITU-D/Statistics/Pages/stat/default.aspx
Chỉ một phần rất nhỏ của thông tin trên Web là thực sự có ích
Hầu hết mọi người bắt đầu tìm kiếm thông tin trên mạng bằng Google, với khoảng 80% người dùng internet chọn nền tảng này trong số các công cụ tìm kiếm hiện có.
Khi tìm kiếm tài liệu về toán học lớp 5 trên Google bằng cách thông thường, với từ khóa “toán lớp 5”, người dùng sẽ nhận được khoảng 2.490.000 kết quả chỉ trong 0,38 giây Tuy nhiên, khi lướt qua 100 kết quả đầu tiên, hầu hết đều là các trang sao chép từ những nguồn uy tín hoặc bài báo khác Điều này cho thấy rằng việc tìm kiếm thông tin có thể gặp khó khăn trong việc lọc ra những bài viết chất lượng trong số hàng triệu kết quả mà Google cung cấp.
Sự khác biệt rõ rệt giữa tìm kiếm trong cơ sở dữ liệu truyền thống và cơ sở dữ liệu Web đã tạo ra những thách thức đáng kể Những thách thức này chính là động lực thúc đẩy nghiên cứu và phát triển trong lĩnh vực khai thác dữ liệu Web.
Bên cạnh những khó khăn cũng có một số thuận lợi cho khai thác Web do lượng thông tin trên Web rất phong phú:
Trang Web được cấu trúc theo quy định của ngôn ngữ định dạng, bao gồm nội dung như văn bản, hình ảnh và dữ liệu đa phương tiện Nó còn chứa các thẻ để tổ chức cấu trúc nội dung, khiến trang Web trở thành một loại dữ liệu bán cấu trúc Điều này mang lại nhiều thuận lợi cho việc khai thác Web.
Một website không chỉ bao gồm các trang riêng lẻ mà còn có các liên kết kết nối giữa các trang đó Khi tác giả tạo ra một liên kết từ trang này đến trang khác, nó giúp cải thiện khả năng điều hướng và trải nghiệm người dùng.
Trang Y được xem là hữu ích khi người dùng truy cập vào, cho thấy tầm quan trọng của nó qua số lượng liên kết trỏ đến Những liên kết này cung cấp thông tin quý giá về mối liên quan, chất lượng và cấu trúc nội dung của trang Web, đồng thời là nguồn tài nguyên phong phú cho việc khai thác thông tin trên Internet.
Một máy chủ Web thường đăng ký một bản ghi đầu vào (Weblog entry) cho mỗi lần truy cập trang Web, bao gồm; địa chỉ IP, URL, timestamp
Do đó, việc phân tích dữ liệu Weblog có thể thu được nhiều thông tin hữu ích như; xu hướng truy cập Web, cấu trúc Web.
Các lĩnh vực trong khai thác Web (Web mining)
Khai thác Web là quá trình tìm kiếm các mô hình dữ liệu thông qua ba phương pháp chính: khai thác nội dung, khai thác cấu trúc và khai thác sử dụng Hình 2.2 minh họa sự phân loại các lĩnh vực nghiên cứu trong khai thác Web.
Hình 2.2 Các lĩnh vực trong khai thác Web [2]
2.3.1 Khai thác nội dung trang Web
Khai thác nội dung trang Web là quá trình thu thập tri thức từ thông tin có trên trang Web Quá trình này được chia thành hai lĩnh vực chính: khai thác trực tiếp nội dung từ trang Web và cải thiện khả năng tìm kiếm nội dung thông qua các công cụ tìm kiếm khác.
Khai thác nội dung trang Web (Web Page summarization) liên quan đến việc truy xuất thông tin từ các loại văn bản khác nhau như văn bản có cấu trúc, văn bản bán cấu trúc và văn bản siêu liên kết Lĩnh vực này tập trung vào việc khai thác nội dung chính của các văn bản để cung cấp thông tin hữu ích và dễ hiểu.
Tối ưu kết quả trả về trong tìm kiếm là quá trình sắp xếp và chọn lọc các trang web phù hợp nhất với yêu cầu của người dùng Sau khi xác định các trang web thỏa mãn, các yếu tố như tiêu đề trang, loại nội dung, URL và các liên kết trong trang được sử dụng để phân lớp và đưa ra tập con kết quả tối ưu nhất.
2.3.2 Khai thác cấu trúc trang Web
Các kết nối giữa các văn bản siêu liên kết trên World Wide Web không chỉ chứa thông tin nội dung mà còn phản ánh mức độ quan trọng của các trang web thông qua các liên kết trỏ tới chúng Đồng thời, các liên kết ra từ một trang web cho thấy sự liên quan đến các chủ đề khác Việc khai thác cấu trúc Web là quá trình xử lý nhằm rút ra tri thức từ cách tổ chức và liên kết giữa các tham chiếu của các trang web.
2.3.3 Khai thác sử dụng Web
Khai thác sử dụng Web, hay khai thác hồ sơ Web, là quá trình xử lý thông tin từ các hồ sơ truy cập Web để thu thập dữ liệu hữu ích Các Web Server ghi lại và lưu trữ thông tin về tương tác của người dùng khi nhận yêu cầu truy cập Phân tích hồ sơ truy cập của các Website giúp dự đoán hành vi người dùng và hiểu cấu trúc Web, từ đó cải thiện thiết kế hệ thống Hai chiến lược chính trong khai thác Web là phân tích mô hình truy cập và phân tích xu hướng cá nhân.
Phân tích các mô hình truy cập (General Access Pattern tracking) thông qua việc xem xét hồ sơ Web giúp nhận diện các xu hướng và mô hình truy cập của người dùng Những phân tích này có thể hỗ trợ trong việc tái cấu trúc các trang web thành các phân nhóm hiệu quả hơn, xác định vị trí quảng cáo tối ưu và gắn kết quảng cáo sản phẩm cụ thể với từng đối tượng người dùng, từ đó nâng cao hiệu quả tiếp thị.
Phân tích xu hướng cá nhân thông qua việc theo dõi việc sử dụng (Customized Usage Tracking) giúp chuyên biệt hóa các website cho từng nhóm đối tượng người dùng Thông tin hiển thị, cấu trúc sâu của trang web và định dạng tài nguyên có thể tự động điều chỉnh theo mô hình truy cập của từng người dùng theo thời gian.
Các bài toán được đặt ra trong khai thác Web
Các bài toán của khai thác Web đều cần bao hàm tính đặc thù của Web Có thể chia khai thác Web thành hai loại bài toán sau:
Các bài toán chung của khai thác dữ liệu văn bản với việc bổ sung các yếu tố của miền ứng dụng dữ liệu Web:
Các bài toán phân lớp, phân cụm và phân đoạn trong khai thác dữ liệu Web tương tự như trong khai phá dữ liệu văn bản, nhưng có những đặc thù riêng của Web, chẳng hạn như các siêu liên kết dẫn đến các trang khác Những bài toán này thường được điều chỉnh để phù hợp với môi trường Internet, ví dụ như phân cụm và phân lớp các trang Web được trả về từ máy tìm kiếm.
Các bài toán phát hiện ràng buộc và luật kết hợp không chỉ liên quan đến nội dung văn bản mà còn bao gồm các yếu tố đặc thù của trang web, như sự ràng buộc giữa các trang web, mối liên hệ giữa người dùng và các trang web mà họ quan tâm trong phiên làm việc, cũng như sự ràng buộc của nhóm người dùng với tập hợp các trang web mà tất cả thành viên trong nhóm cùng chú ý.
Các bài toán khai thác dữ liệu mang tính đặc thù của Web
Bài toán dự báo trong lĩnh vực khai thác dữ liệu web tập trung vào việc phân tích yếu tố thời gian của sự xuất hiện các trang web để dự đoán xu hướng về nội dung, cấu trúc và hình thức trình bày của chúng trong tương lai Ngoài ra, việc khai thác trình tự sử dụng web trong một phiên làm việc cũng là một chủ đề nghiên cứu được nhiều nhà khoa học quan tâm.
Các bài toán Dự đoán nhu cầu (Response prediction) và đánh giá khách hàng khai thác Web (Customer evaluation) liên quan đến đối tượng sử dụng CSDL Web
Mộ số bài toán điển hình nhất của khai thác dữ liệu Web như là; tìm kiếm, phân cụm, phân lớp, trích chọn thông tin.
Khai thác sử dụng Web
Khai thác sử dụng Web là một trong ba xu thế chính của khai thác Web, bao gồm ba giai đoạn liên quan và phụ thuộc vào nhau: thu thập dữ liệu và tiền xử lý dữ liệu, phát hiện mô hình và phân tích mô hình Quá trình này được mô tả trong hình 2.3 và được nghiên cứu bởi Liu và các đồng sự.
Trong giai đoạn thu thập và tiền xử lý dữ liệu, các nguồn dữ liệu chính cho khai thác Web bao gồm máy chủ Log Files, với các bản ghi truy cập máy chủ Web và bản ghi máy chủ ứng dụng, hoặc từ các CSDL khách hàng Dữ liệu Web sau đó được làm sạch và phân chia thành các giao dịch đại diện cho hoạt động của từng người dùng trong các chuyến thăm khác nhau đến trang Web Ngoài ra, các nguồn kiến thức khác như nội dung, cấu trúc và kiến thức ngữ nghĩa từ ontology của trang Web, như danh mục sản phẩm hoặc hệ thống phân cấp khái niệm, cũng có thể được sử dụng để tăng cường dữ liệu giao dịch của người dùng.
Hình 2.3 Quá trình khai thác sử dụng Web [1]
Trong giai đoạn phát hiện mô hình, các hoạt động thống kê, cơ sở dữ liệu và máy học được thực hiện nhằm xây dựng mô hình ẩn phản ánh hành vi điển hình của người sử dụng Đồng thời, giai đoạn này cũng cung cấp số liệu thống kê tóm tắt về tài nguyên Web, phiên và người sử dụng.
Trong giai đoạn phân tích mô hình, đây là bước cuối cùng trong quy trình khai thác dữ liệu từ Web, nơi các mô hình đã được phát hiện và thống kê sẽ được xử lý và lọc Kết quả thu được có thể là sự tổng hợp các mô hình, được sử dụng làm đầu vào cho các ứng dụng như công cụ giới thiệu, công cụ trực quan, phân tích Web và các công cụ tạo báo cáo Toàn bộ quá trình này được minh họa trong hình 2.3.
2.5.1 Phân tích mô hình truy cập Web
Trong khai thác Web, phân tích mô hình truy cập Web tập trung vào việc khám phá các mô hình truy cập phổ biến của người dùng Nhóm người dùng này được coi là đối tượng nghiên cứu chính trong bài toán phân tích mô hình truy cập Web.
Thông tin truy cập của người dùng được ghi lại trong Web Server Log theo định dạng Log chung (CLF) hoặc Log chung mở rộng (ECLF) Dữ liệu lưu trữ liên quan đến phiên truy cập bao gồm địa chỉ IP của người dùng, thời gian bắt đầu truy cập, nhu cầu người dùng (phương thức, địa chỉ Web, giao thức), mã trạng thái phản hồi (bình thường, không hoàn chỉnh, không tìm thấy, v.v.) và kích thước dữ liệu truy cập Web.
Dữ liệu truy cập Web lưu trữ tại Web Server Log cung cấp cho các nhà khai thác dữ liệu cơ sở dữ liệu quý giá để thực hiện các bài toán khai thác dữ liệu Web Họ có thể tìm ra mối quan hệ nội dung giữa các trang Web dựa trên các địa chỉ URL liên kết, cũng như phân tích thói quen và xu hướng truy cập của người dùng.
Hiện nay, việc khai thác và sử dụng Web không chỉ chú trọng vào việc phát hiện tri thức tiềm ẩn từ nội dung trang Web lưu trữ tạm thời trên máy chủ, mà còn tập trung vào việc phân tích hành vi sử dụng Web của người dùng.
Thuật toán khai thác Web cần chú ý đến việc lưu trữ các trang Web hiệu quả trong bối cảnh dung lượng bộ nhớ hạn chế của vùng Web-cache Các giải pháp điều phối cache được triển khai nhằm loại bỏ các trang Web không hữu ích, tương tự như việc quản lý bộ nhớ trong hệ điều hành Luật kết hợp là một yếu tố quan trọng trong phân tích mô hình truy cập Web, với thuật toán Apriori và các biến thể của nó được sử dụng phổ biến để phát hiện luật kết hợp từ Log Files.
Cho một CSDL giao dịch D = {t 1 ,t 2 , ,t n }, 1≤ i ≤n Trong đó mọi t i là một giao dịch và là một tập con thuộc D
Cho hai tập mục X và Y là các tập con của D, với luật kết hợp được ký hiệu là X → Y, trong đó X ∩ Y = ∅ Luật này thể hiện mối ràng buộc của tập mục Y theo tập mục X, nghĩa là “X kéo theo Y” trong sự xuất hiện trong giao dịch Tập mục X được gọi là xuất hiện trong giao dịch t nếu như X ⊆ t, có thể hiểu là “mọi tên mặt hàng trong X đều xuất hiện trong phiếu giao dịch t”.
Giá trị của luật kết hợp XY được thể hiện thông qua hai độ đo là; độ hỗ trợ supp(XY) và độ tin cậy conf(XY)
Độ hỗ trợ của một tập mục X (ký hiệu supp(X) được định nghĩa là:
Supp(XY) = Supp(XY) là tỷ lệ giao dịch có chứa (X Y) trong tập
Conf(XY) = supp(XY)/supp(X) là tỷ lệ tập giao dịch có chứa (X Y) so với tập giao dịch có chứa X
Theo định nghĩa, độ hỗ trợ (supp) và độ tin cậy (conf) của mối quan hệ giữa hai tập mục X và Y đều nằm trong khoảng từ 0 đến 1 Cụ thể, độ hỗ trợ thể hiện xác suất xuất hiện đồng thời của tập mục X và Y, trong khi độ tin cậy phản ánh xác suất có điều kiện của Y khi đã biết X xảy ra.
Luật kết hợp XY được coi là một “tri thức” (hoặc mẫu có giá trị) nếu xảy ra đồng thời
Trong quy trình khai thác luật kết hợp, supp(X→Y) phải lớn hơn hoặc bằng minsup và conf(X→Y) phải lớn hơn hoặc bằng minconf, trong đó minsup và minconf là hai ngưỡng đã được xác định trước Tập mục X được coi là phổ biến khi độ hỗ trợ của nó đạt ngưỡng minsup (supp(X) ≥ minsup).
Mục tiêu của khai thác luật kết hợp là xác định tất cả các luật kết hợp có giá trị Để đạt được điều này, trước tiên cần tìm ra tất cả các tập phổ biến, vì mỗi tập phổ biến sẽ đóng vai trò là tập XY trong luật kết hợp XY.
2.5.2 Phân tích xu hướng cá nhân
Phân tích xu hướng cá nhân hóa đòi hỏi dữ liệu cũng phải mang tính cá nhân, có thể từ Log Files của máy khách, CSDL khách hàng, hoặc dữ liệu thu thập trực tuyến Dưới đây là một số nội dung liên quan đến việc phân tích xu hướng cá nhân mà không cần đến CSDL khách hàng và các hệ thống tư vấn khách hàng.
Phân tích xu hướng cá nhân từ máy khách
Hệ thống khai phá sử dụng Web, như hình 2.4 [1] cho thấy, thu thập dữ liệu người dùng từ máy khách Thông tin này được các phần mềm hệ thống tại máy khách trích xuất, giúp cung cấp dữ liệu tư vấn phù hợp cho từng người dùng cụ thể.
Hình 2.5 [2] trình bày hệ thống dựa theo Log Files xây dựng các ontology sử dụng Web để tư vấn người sử dụng hệ thống
Hình 2.4 Sinh tư vấn dựa trên trích chọn tiểu sử người dùng [2]
Hình 2.5 Hệ thống tư vấn hướng cá nhân: kiến trúc hệ thống (trên) và sinh ontology sử dụng Web (dưới) [2]
Khai thác cấu trúc Web
2.6.1 Khai thác đồ thị Web
Khai thác đồ thị Web là một lĩnh vực quan trọng trong khai thác cấu trúc Web, với đồ thị Web được coi như một mạng xã hội Trong đó, mỗi trang Web được xem là một đỉnh, và liên kết giữa các trang thể hiện mối quan hệ giữa chúng Tùy thuộc vào bài toán nghiên cứu, đồ thị Web có thể được phân tích dưới dạng có hướng hoặc không có hướng Một trong những vấn đề nổi bật trong lĩnh vực này là bài toán tính hạng trang Web, đóng vai trò quan trọng trong việc xác định vị trí và độ tin cậy của các trang trên Internet.
Web được sử dụng để dẫn dắt người dùng trên trang và các trang có hạng cao thường được hiển thị trước Trong máy tìm kiếm, hạng trang Web quyết định thứ tự hiển thị kết quả, với các trang có hạng cao hơn được ưu tiên Hơn nữa, hạng trang Web còn được áp dụng trong việc phát hiện địa chỉ Email spam trong mạng lưới Email.
Email có hạng thấp thì khả năng đó là một địa chỉ spam rất cao
2.6.2 Khai thác cấu trúc trang Web
Khai thác cấu trúc trang Web là quá trình phát hiện các mô hình từ tập hợp kiến trúc trang Web, trong đó dữ liệu bao gồm khung trang Web với các đối tượng, thẻ và cấu trúc giữa các thẻ Kết quả của quá trình này hỗ trợ cho các bài toán khai thác dữ liệu Web khác.
Theo nghiên cứu, bài toán trích chọn tự động tin tức trên Web có thể được giải quyết bằng cách tiếp cận khoảng cách cây Cấu trúc cây được sử dụng để biểu diễn các trang Web, và độ đo chi phí chuyển đổi cây (Tree Edit Distance) được áp dụng để đánh giá mức độ tương tự về cấu trúc giữa các trang Thuật toán RTDM (Restricted Top-Down) đóng vai trò quan trọng trong quá trình này.
Mapping) mô hình trích chọn tin tức từ cổng thông tin (portal) báo điện tử gồm các bước:
Kỹ thuật phân cụm cấu trúc được áp dụng để phân tích các trang báo điện tử, trong đó độ đo khoảng cách giữa hai trang web được coi là chi phí chuyển đổi cấu trúc trang web.
Sinh các mô hình trích chọn dưới dạng cây
Evaluate and assess the performance of extraction models based on the RTMD algorithm, focusing on the valuation of vertex replacement, vertex insertion, and vertex removal operations.
Áp dụng mô hình để trích chọn tin tức
Hình 2.6 trình bày quá trình trích chọn tự động qua bốn bước mô tả trên [2]
Mô hình này đã được áp dụng thành công trong sản phẩm Viennews, với chủ đề "Các kênh báo điện tử trên thiết bị điện thoại di động thông minh", và đã giành giải ba tại cuộc thi Trí tuệ Việt Nam năm 2006.
Hình 2.6 Quá trình trích chọn thông tin tự động trên Web [2]
Tổng quan về khai thác tăng trưởng mô hình duyệt Web
Kỹ thuật khai thác mô hình con đường duyệt giúp khám phá hành vi chuyển hướng của người dùng trong môi trường Web, từ đó cho phép các nhà thiết kế cải thiện thiết kế và hiệu suất trang Web Nhiều nghiên cứu đã tập trung vào lĩnh vực này, bao gồm các thuật toán quét toàn bộ (FS) và quét chọn lọc (SS).
Các thuật toán như MAFTP có những hạn chế khi chỉ khám phá mô hình con đường duyệt đơn giản, nơi một trang không thể xuất hiện nhiều lần Hơn nữa, chúng chỉ xem xét chuyển tiếp tiến trong cơ sở dữ liệu trình tự duyệt, dẫn đến việc phát hiện các mô hình con đường duyệt không đủ cho môi trường Web Để nắm bắt hành vi chuyển hướng người dùng một cách chính xác, cần có mô hình con đường duyệt không đơn giản, bao gồm cả chuyển tiếp lùi Phương pháp này được trình bày trong thuật toán khai thác mô hình duyệt thường xuyên (MFTP) và thuật toán tích hợp các mô hình con đường duyệt và luật kết hợp (IPA).
Thuật toán MAFTP là một kỹ thuật cải tiến cho việc duy trì các mô hình con đường duyệt khi có trình tự người dùng mới được thêm vào cơ sở dữ liệu Nó phân vùng cơ sở dữ liệu thành các đoạn và quét từng đoạn để phát hiện sớm các trình tự duyệt thường xuyên Tuy nhiên, MAFTP chỉ xem xét các chuyển tiếp tiến và không giải quyết các trường hợp trình tự có thể bị xóa Khai thác mô hình trình tự tương tự như khai thác mô hình duyệt Web, với điểm khác biệt là mô hình duyệt Web yêu cầu có liên kết giữa các trang Zaki và đồng sự đã đề xuất thuật toán ISL, dựa trên mô hình phát hiện trình tự sử dụng các lớp tương đương, cho phép cập nhật cấu trúc dàn khi cơ sở dữ liệu thay đổi Thuật toán IncSpan, dựa trên PrefixSpan, khai thác các mô hình trình tự thông qua cơ sở dữ liệu chiếu Tuy nhiên, cả ISL và IncSpan chỉ xử lý các trường hợp có trình tự người dùng mới được thêm vào.
Thuật toán ISL và IncSpan được sử dụng để khai thác mô hình trình tự trong môi trường Web, nơi các trình tự sử dụng có thể xuất hiện bất kỳ lúc nào Để khắc phục những hạn chế của các thuật toán trước đó, Lee và đồng sự đã đề xuất thuật toán IncWTP, cho phép khám phá các mô hình con đường duyệt phức tạp và xem xét cả hai trường hợp chèn và xóa dữ liệu trong cơ sở dữ liệu Đặc biệt, thuật toán này chỉ yêu cầu một số lượng nhỏ ứng cử viên trình tự duyệt được tính từ cơ sở dữ liệu ban đầu, giúp tối ưu hóa quy trình khai thác.
Thuật toán IncWTP sử dụng cấu trúc dàn mở rộng để giữ các trình tự ứng cử viên có độ hỗ trợ lớn hơn không, đồng thời lưu giữ thứ tự của các trình tự trong cấu trúc dàn nhằm nâng cao hiệu quả khai thác mô hình tăng trưởng Do kích thước lớn của cấu trúc dàn, nó được lưu trữ trên ổ cứng và mỗi cấp trong dàn sẽ được nạp vào bộ nhớ theo lượt trong quá trình khai thác Tuy nhiên, quá trình nhập/xuất này tốn nhiều thời gian Thuật toán cũng cho phép các ứng viên α ở mức k sinh ra ứng viên α ở mức k+1 nếu chúng là mô hình duyệt Web đủ tiêu chuẩn với Support(α) ≥ min_sup, trong đó min_sup là ngưỡng tối thiểu do người dùng chỉ định Khi giảm min_sup, khả năng sinh ra các ứng cử viên mới tăng cao, yêu cầu quét lại cơ sở dữ liệu để đếm độ hỗ trợ Hơn nữa, việc thêm trình tự mới cũng làm tăng khả năng sinh ứng viên mới.
Trong luận văn này, tôi đề xuất thuật toán WebTP sử dụng cấu trúc cây để lưu trữ các ứng viên theo cấp, với tất cả các ứng cử viên trình tự có độ hỗ trợ bằng một và các TIDs được lưu trữ trên cây nhằm nâng cao hiệu quả khai thác mô hình tăng trưởng Thuật toán IntWebTP cho phép duyệt cấu trúc cây một lần để tìm ra các mô hình duyệt Web mỗi khi điều chỉnh min_sup mà không cần duyệt lại cơ sở dữ liệu ban đầu Ngoài ra, thuật toán RemoveLink được sử dụng để cập nhật mô hình duyệt Web khi xóa liên kết trong cấu trúc WebSite.
THUẬT TOÁN KHAI THÁC MÔ HÌNH DUYỆT WEB
Các vấn đề liên quan
Khai thác mô hình duyệt Web là quá trình phát hiện các mô hình truy cập của người dùng thông qua các bản ghi Web Để bắt đầu, chúng ta cần định nghĩa rõ ràng mô hình duyệt Web.
Cho I = { x 1 , x 2 , , x n } là một tập hợp của tất cả các trang Web trong một Website
Một trình tự duyệt S = là danh sách các trang Web được sắp xếp theo thời gian duyệt, trong đó mỗi trang Web (wi ∈ I, 1 ≤ i ≤ m) có thể xuất hiện nhiều lần.
Chiều dài |S| của một trình tự duyệt S là tổng số của các trang Web trong S Một trình tự duyệt với chiều dài l được gọi là một trình tự duyệt l
Trong lý thuyết chuỗi, nếu có hai trình tự duyệt α = và β = với m ≤ n, và tồn tại các chỉ số i1 < i2 < < im sao cho bi1 = a1, bi2 = a2, , bim = am, thì ta nói rằng β bao gồm α, nghĩa là α là một chuỗi con của β, trong khi β là chuỗi cha của α Ví dụ, với hai chuỗi α = và β = , ta có thể thấy rằng α là chuỗi con của β và β là chuỗi cha của α.
Cơ sở dữ liệu trình tự duyệt D, như trong Bảng 3.1, bao gồm một tập hợp các bản ghi, mỗi bản ghi chứa một TID và một trình tự sử dụng Trình tự sử dụng là chuỗi duyệt thể hiện hành vi duyệt Web thành công của người dùng Độ hỗ trợ của trình tự duyệt α, ký hiệu là Support (α), được tính bằng tỷ lệ giữa số lượng trình tự duyệt chứa α và tổng số trình tự trong D Độ hỗ trợ của α cũng chính là số lượng trình tự duyệt có chứa α.
Một chuỗi duyệt α = được coi là mô hình duyệt Web nếu Support(α) đạt hoặc vượt qua ngưỡng tối thiểu min_sup mà người dùng chỉ định, và có sự liên kết giữa các phần tử x i và x i + 1 trong cấu trúc của trang Web, với điều kiện 1≤ i ≤ l-1.
Một cấu trúc Website như được thể hiện trong hình 3.1, mỗi đỉnh là một trang Web và mỗi cung thể hiện cho mối liên kết giữa các trang Web
Bảng 3.1 Cơ sở dữ liệu trình tự duyệt
Cấu trúc dữ liệu được sử dụng cho khai thác mô hình duyệt Web
Để tối ưu hóa mô hình duyệt Web, kết quả khai thác trước đó được tận dụng để khám phá các mô hình mới, giúp giảm thời gian khai thác Trong nghiên cứu này, cấu trúc cây được áp dụng để lưu trữ các kết quả khai thác trước đó Khi thiết lập min_sup ở mức 50%, chỉ những mô hình duyệt Web đạt tiêu chuẩn mới được lưu trữ trong cấu trúc cây Một mô hình duyệt α = được coi là đủ tiêu chuẩn khi Support(α) ≥ 1 và tồn tại một liên kết từ xi đến xi+1 (với mọi i, 1≤ i ≤ l-1) trong cấu trúc của trang Web.
Hình 3.2 Cấu trúc cây đơn giản
AB AD BC BD CD CE DA EA ED
ABC ABD BCD AB BCE AB CDA CEA CED DAB DAD EAB
Để tối ưu hóa quá trình khai thác tương tác các mô hình duyệt Web và tăng tốc độ khai thác, cấu trúc cây đã được mở rộng để ghi thêm thông tin Mỗi nút trong cấu trúc cây chứa một trình tự duyệt Web với support lớn hơn hoặc bằng một, và support được nối thêm vào phần trên của mỗi nút Thông tin này đóng vai trò quan trọng trong việc tính toán và tích lũy support như một phần của quá trình khai thác mô hình gia tăng.
Các TIDs trình tự duyệt được thêm vào phần dưới mỗi nút nhằm giảm thiểu số lần quét cơ sở dữ liệu không cần thiết Điều này khác biệt so với cấu trúc cây đơn giản, nơi mà tất cả các ứng cử viên trình tự duyệt có độ hỗ trợ bằng một (tính theo min_sup) được đưa vào cấu trúc cây.
Chúng ta có thể sử dụng cấu trúc cây để nhanh chóng xác định các mô hình duyệt Web khi điều chỉnh min_sup Ví dụ, khi giảm min_sup từ 50% xuống 20%, người dùng chỉ cần duyệt qua các mức của cấu trúc cây để tìm các mô hình có support ≥ min_sup Hơn nữa, để tìm mô hình duyệt Web tối đa mà không cần quan tâm đến các mô hình khác, người dùng chỉ cần trả về các mô hình có support ≥ min_sup ở mức cao nhất của cấu trúc cây Ví dụ, trong hình 3.2, mô hình duyệt Web được nêu rõ.
và là mô hình duyệt Web tối đa
Các mô hình duyệt Web từ cơ sở dữ liệu trình tự duyệt được trình bày trong Bảng 3.1, với kết quả cuối cùng hiển thị trong Hình 3.3, trong đó giá trị min_sup được thiết lập ở mức 50%.
Giả sử một website có 300 trang, nếu giữ các ứng viên có độ hỗ trợ lớn hơn hoặc bằng 1 trong cấu trúc cây mà không dựa vào cấu trúc trang web, sẽ có khoảng 89.700 ứng cử viên với chiều dài 2 cần lưu giữ Với thiết lập min_sup là 50%, số ứng cử viên còn lại sẽ là khoảng 49.333.
Phương pháp sinh ứng viên được dựa theo phương pháp được đề xuất trong
Xét một dãy có k phần tử, được gọi là k-sequence, trong đó mỗi lần một phần tử xuất hiện trong các thành phần khác nhau của dãy đều được tính vào giá trị k Tập hợp tất cả các dãy phổ biến k-sequence được ký hiệu là L k, trong khi tập các dãy ứng viên k-sequence được ký hiệu là C k.
Cho L k-1 là tập tất cả các dãy phổ biến (k-1)-sequence, ta cần tạo ra tập cha
Superset của tập tất cả các dãy phổ biến k-sequence được định nghĩa thông qua khái niệm về dãy con liên tục Cụ thể, cho dãy s = và một dãy con c, thì c được coi là dãy con liên tục của s nếu nó thỏa mãn bất kỳ điều kiện nào sau đây.
1 c nhận được từ s bằng cách lược bỏ phần tử s 1 hoặc s n
2 c nhận được từ s bằng cách lược bỏ một phần tử từ thành phần s i mà s i có ít nhất hai phần tử
3 c là dãy con liên tục của c’, và c’ là dãy con liên tục của s
Hai mô hình duyệt Web s 1 = và s 2 = có thể kết hợp để tạo thành một trình tự duyệt k nếu và chỉ nếu và giống nhau, hoặc giống như Điều này có nghĩa là sau khi loại bỏ trang đầu tiên trong mô hình s 1 và trang cuối cùng trong mô hình s 2, chúng ta sẽ có trình tự duyệt (k-2) giống nhau Dãy ứng viên mới được tạo ra là dãy s 1 được mở rộng với phần tử cuối cùng trong s 2.
Ứng cử viên trình tự duyệt được tạo ra từ việc kết hợp hai mô hình duyệt Web và Đối với ứng cử viên trình tự l của α, nó được sinh ra từ trình tự con có chiều dài (l-1) của α Chúng ta không cần kiểm tra tất cả các trình tự duyệt Web con với chiều dài l-1 cho mỗi ứng cử viên trình tự l Trong ví dụ này, không cần kiểm tra các mô hình như , và vì tất cả các mô hình đã lưu trữ trên cây đều đủ tiêu chuẩn và tham gia vào quá trình sinh ứng viên.
Hình 3.3: cấu trúc cây mở rộng
Thuật toán
Thuật toán InWebTP khai thác mô hình duyệt Web bằng cách thêm các trình tự duyệt vào cơ sở dữ liệu Thuật toán hoạt động từ cấp độ đầu tiên đến cấp độ cuối cùng của cấu trúc cây Tại mỗi cấp độ, nó kiểm tra sự hiện diện của các mô hình trong cấu trúc cây; nếu có, TID sẽ được thêm vào node và giá trị support của node đó sẽ tăng lên Nếu mô hình chưa tồn tại trong cấu trúc cây, một node mới sẽ được tạo ra.
Dữ liệu đầu vào: tập các giao dịch được thêm vào InsTID, cấu trúc cây T
Dữ liệu ra: Tất cả các mô hình duyệt Web sau khi thêm tập InsTID int level = InsTID.getLevelCount(); for(int i = 1; i