Luận văn Khai phá dữ liệu Web bằng kỹ thuật phân cụm

hất lượng mô hình. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 69 3.2. Khai phá theo sử dụng Web Việc nắm bắt được những đặc tính của người dùng Web là việc rất quan trọng đối với người thiết Web site. Thông qua việc khai phá lịch sử các mẫu truy xuất của người dùng Web, không chỉ thông tin về Web được sử dụng như thế nào mà còn nhiều đặc tính khác như các hành vi của người dùng có thể được xác định. Sự điều hướng đường dẫn người dùng Web mang lại giá trị thông tin về mức độ quan tâm của người dùng đến các WebSite đó. Dựa trên những tiêu chuẩn khác nhau người dùng Web có thể được phân cụm và các tri thức hữu ích có thể được lấy ra từ các mẫu truy cập Web. Nhiều ứng dụng có thể giúp lấy ra được các tri thức. Ví dụ, văn bản siêu liên kết động được tạo ra giữa các trang Web có thể được đề xuất sau khi khám phá các cụm người dùng Web, thể hiện độ tương tự thông tin. Thông qua việc phát hiện mối quan hệ giữa những người dùng như sở thích, sự quan tâm của người dùng Web ta có thể dự đoán một cách chính xác hơn người sử dụng đang cần gì, tại thời điểm hiện tại có thể dự đoán được kế tiếp họ sẽ truy cập những thông tin và họ cần thông tin gì. Giả sử rằng tìm được độ tương tự về sự quan tâm giữa những người dùng Web được khám phá từ hiện trạng (profile) của người dùng. Nếu Web site được thiết kết tốt sẽ có nhiều sự tương quan giữa độ tương tự của các chuyển hướng đường dẫn và tương tự giữa sự quan tâm của người dùng. Khai phá theo sử dụng Web là khai phá truy cập Web (Web log) để khám phá các mẫu người dùng truy nhập vào WebSite. Thông qua việc phân tích và khảo sát những quy tắc trong việc ghi nhận lại quá trình truy cập Web ta có thể chứng thực khách hàng trong thường mại điện tử, nâng cao chất lượng dịch vụ thông tin trên Internet đến người dùng, nâng cao hiệu suất của các hệ thống phục vụ Web. Thêm vào đó, để tự phát triển các Web site bằng việc huấn luyện từ các mẫu truy xuất của người dùng. Phân tích quá trình đăng nhập Web của người dùng cũng có thể giúp cho việc xây dựng các dịch vụ Web theo yêu cầu đối với từng người dùng riêng lẽ được tốt hơn. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 70 Hiện tại, ta thường sử dụng các công cụ khám phá mẫu và phân tích mẫu. Nó phân tích các hành động người dùng, lọc dữ liệu và khai phá tri thức từ tập dữ liệu bằng cách sử dụng trí tuệ nhân tạo, KPDL, tâm lý học và lý thuyết thông tin. Sau khi tìm ra các mẫu truy cập ta thường sử dụng các kỹ thuật phân tích tương ứng để hiểu, giải thích và khám phá các mẫu đó. Ví dụ, kỹ thuật xử lý phân tích trực tuyến, tiền phân loại hình thái dữ liệu, phân tích mẫu thói quen sử dụng của người dùng. Kiến trúc tổng quát của quá trình khai phá theo sử dụng Web như sau: Hình 3.6. Kiến trúc tổng quát của khai phá theo sử dụng Web 3.2.1. Ứng dụng của khai phá theo sử dụng Web - Tìm ra những khách hàng tiềm năng trong thương mại điện tử. - Chính phủ điện tử (e-Gov), giáo dục điện tử (e-Learning). - Xác định những quảng cáo tiềm năng. - Nâng cao chất lượng truyền tải của các dịch vụ thông tin Internet đến người dùng cuối. - Cải tiến hiệu suất hệ thống phục vụ của các máy chủ Web. - Cá nhân dịch vụ Web thông quan việc phân tích các đặc tính cá nhân người dùng. - Cải tiến thiết kế Web thông qua việc phân tích thói quen duyệt Web và phân tích các mẫu nội dung trang quy cập của người dùng. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 71 - Phát hiện gian lận và xâm nhập bất hợp lệ trong dịch vụ thương mại điện tử và các dịch vụ Web khác. - Thông qua việc phân tích chuỗi truy cập của người dùng để có thể dự báo những hành vi của người dùng trong quá trình tìm kiếm thông tin. 3.2.2. Các kỹ thuật được sử dụng trong khai phá theo sử dụng Web Luật kết hợp: Để tìm ra những trang Web thường được truy cập cùng nhau của người dùng những lựa chọn cùng nhau của khách hàng trong thương mại điện tử. Kỹ thuật phân cụm: Phân cụm người dùng dựa trên các mẫu duyệt để tìm ra sự liên quan giữa những người dùng Web và các hành vi của họ. 3.2.3. Những vấn đề trong khai khá theo sử dụng Web. Khai phá theo cách dùng Web có 2 việc: Trước tiên, Web log cần được làm sạch, định nghĩa, tích hợp và biến đổi. Dựa vào đó để phân tích và khai phá. Những vấn đề tồn tại: - Cấu trúc vật lý các Web site khác nhau từ những mẫu người dùng truy xuất. - Rất khó có thể tìm ra những người dùng, các phiên làm việc, các giao tác. Vấn đề chứng thực phiên người dùng và truy cập Web: Các phiên chuyển hướng của người dùng: Nhóm các hành động được thực hiện bởi người dùng từ lúc họ truy cập vào Web site đến lúc họ rời khỏi Web site đó. Những hành động của người dùng trong một Web site được ghi và lưu trữ lại trong một file đăng nhập (log file) (file đăng nhập chứa địa chỉ IP của máy khách, ngày, thời gian từ khi yêu cầu được tiếp nhận, các đối tượng yêu cầu và nhiều thông tin khác như các giao thức của yêu cầu, kích thước đối tượng,...). 3.2.3.1. Chứng thực phiên người dùng Chứng thực người dùng: Mỗi người dùng với cùng một Client IP được xem là cùng một người. Chứng thực phiên làm việc: Mỗi phiên làm việc mới được tạo ra khi một địa chỉ mới được tìm thấy hoặc nếu thời gian thăm một trang quá ngưỡng thời gian cho phép (ví dụ 30 phút) đối với mỗi địa chỉ IP. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 72 3.2.3.2. Đăng nhập Web và xác định phiên chuyển hướng người dùng Dịch vụ file đăng nhập Web: Một file đăng nhập Web là một tập các sự ghi lại những yêu cầu người dùng về các tài liệu trong một Web site, ví dụ: 216.239.46.60 - - [04/April/2007:14:56:50 +0200] "GET /~lpis/curriculum/C+Unix/ Ergastiria/Week-7/filetype.c.txt HTTP/1.0" 304 - 216.239.46.100- - [04/April/2007:14:57:33 +0200]"GET /~oswinds/top.html HTTP/ 1.0" 200 869 64.68.82.70 - - [04/April/2007:14:58:25 +0200] "GET /~lpis/systems/rdevice/r- device_examples.html HTTP/1.0" 200 16792 216.239.46.133 - - [04/April/2007:14:58:27 +0200] "GET /~lpis/publications/crc- chapter1. html HTTP/1.0" 304 - 209.237.238.161 - - [04/April/2007:14:59:11+0200] "GET /robots.txt HTTP/1.0" 404 276 209.237.238.161 - - [04/April/2007:14:59:12 +0200] "GET /teachers/pitas1.html HTTP/1.0" 404 286 216.239.46.43 - - [04/April/2007:14:59:45 +0200] "GET /~oswinds/publication Nguồn từ: Hình 3.7. Minh họa nội dung logs file 3.2.3.3. Các vấn đề đối với việc xử lý Web log - Thông tin được cung cấp có thể không đầy đủ, không chi tiết. - Không có thông tin về nội dung các trang đã được thăm. - Có quá nhiều sự ghi lại các đăng nhập do yêu cầu phục vụ bởi các proxy. - Sự ghi lại các đăng nhập không đầy đủ do các yêu cầu phục vụ bởi proxy. - Đặc biệt là việc lọc các mục đăng nhập: Các mục đăng nhập với tên file mở rộng như gif, jpeg, jpg. Các trang yêu cầu tạo ra bởi các tác nhân tự động và các chương trình gián điệp. - Ước lượng thời gian thăm trang: Thời gian dùng để thăm một trang là một độ đo tốt cho vấn đề xác định mức độ quan tâm của người dùng đối với trang Web đó, nó cung cấp một sự đánh giá ngầm định đối với trang Web đó. - Khoảng thời gian thăm trang: Đó là khoảng thời gian giữa hai yêu cầu trang khác nhau liên tiếp. - Quy lui: Nhiều người dùng rời trang bởi họ đã hoàn thành việc tìm kiếm và họ không muốn thời gian lâu để chuyển hướng. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 73 3.2.3.4. Phương pháp chứng thực phiên làm việc và truy cập Web Chứng thực phiên làm việc: Nhóm các tham chiếu trang của người dùng vào một phiên làm việc dựa trên những phương pháp giải quyết heuristic: Phương pháp heuristics dựa trên IP và thời gian kết thúc một phiên làm việc (ví dụ 30 phút) được sử dụng để chứng thực phiên người dùng. Đây là phương pháp đơn giản nhất. Các giao tác nội tại của phiên làm việc có thể nhận được dựa trên mô hình hành vi của người dùng (bao hàm phân loại tham chiếu “nội dung” hoặc “chuyển hướng” đối với mỗi người dùng). Trọng số được gán cho mỗi trang Web dựa trên một số độ đo đối với sự quan tâm của người dùng (ví dụ khoảng thời gian xem một trang, số lần lui tới trang). 3.2.4. Quá trình khai phá theo sử dụng Web Khai phá sử dụng Web có 3 pha [22]: Tiền xử lý, khai phá và phân tích đánh giá, biểu diễn dữ liệu. 3.2.4.1. Tiền xử lý dữ liệu Chứng thực người dùng, chứng thực hoạt động truy nhập, đường dẫn đầy đủ, chứng thực giao tác, tích hợp dữ liệu và biến đổi dữ liệu. Trong pha này, các thông tin về đăng nhập Web có thể được biến đổi thành các mẫu giao tác thích hợp cho việc xử lý sau này trong các lĩnh vực khác nhau. Trong giai đoạn này gồm cả việc loại bỏ các file có phần mở rộng là gif, jpg,... Bổ sung hoặc xóa bỏ các dữ liệu khuyết thiếu như cache cục bộ, dịch vụ proxy. Xử lý thông tin trong các Cookie, thông tin đang ký người dùng kết hợp với IP, tên trình duyệt và các thông tin lưu tạm. Chứng thực giao tác: Chứng thực các phiên người dùng, các giao tác. 3.2.4.2. Khai phá dữ liệu Sử dụng các phương pháp KPDL trong các lĩnh vực khác nhau như luật kết hợp, phân tích, thống kê, phân tích đường dẫn, phân lớp và phân cụm để khám phá ra các mẫu người dùng. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 74 + Phân tích đường dẫn [8][9][22]: Hầu hết các các đường dẫn thường được thăm được bố trí theo đồ thị vật lý của trang Web. Mỗi nút là một trang, mỗi cạnh là đường liên kết giữa các trang đó. Thông qua việc phân tích đường dẫn trong quá trình truy cập của người dùng ta có thể biết được mối quan hệ trong việc truy cập của người giữa các đường dẫn liên quan. Ví dụ: - 70% các khách hàng truy cập vào /company/product2 đều xuất phát từ /company thông qua /company/new, /company/products và /company/product1. - 80% khách hàng truy cập vào WebSite bắt đầu từ /company/products. - 65% khách hàng rời khỏi site sau khi thăm 4 hoặc ít hơn 4 trang. + Luật kết hợp [8]: Sự tương quan giữa các tham chiếu đến các file khác nhau có trên dịch vụ nhờ việc sử dụng luật kết hợp. Ví dụ: - 40% khách hàng truy cập vào trang Web có đường dẫn /company/product1 cũng truy cập vào /company/product2. - 30% khách hàng truy cập vào /company/special đều thông qua /company/product1. Nó giúp cho việc phát triển chiến lược kinh doanh phù hợp, xây dựng và tổ chức một cách tốt nhất không gian Web của công ty. + Chuỗi các mẫu: Các mẫu thu được giữa các giao tác và chuỗi thời gian. Thể hiện một tập các phần tử được theo sau bởi phân tử khác trong thứ tự thời gian lưu hành tập giao tác. Quá trình thăm của khách hàng được ghi lại trên từng giai đoạn thời gian. Ví dụ: 30% khách hàng thăm /company/products đã thực hiện tìm kiếm bằng Yahoo với các từ khóa tìm kiếm. 60% khách hàng đặt hàng trực tuyến ở /company/product1 thì cũng đặt hàng trực tuyến ở /company/product4 trong 15 ngày. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 75 + Quy tắc phân loại [22]: Profile của các phần tử thuộc một nhóm riêng biệt theo các thuộc tính chung. Ví dụ như thông tin cá nhân hoặc các mẫu truy cập. Profile có thể sử dụng để phân loại các phần tử dữ liệu mới được thêm vào CSDL. Ví dụ: Khách hàng từ các vị trí địa lý ở một quốc gia hoặc chính phủ thăm site có khuynh hướng bị thu hút ở trang /company/product1 hoặc 50% khách hàng đặt hàng trực tuyến ở /company/product2 đều thuộc nhóm tuổi 20-25 ở Bờ biển Tây. + Phân tích phân cụm: Nhóm các khách hàng lại cùng nhau hoặc các phần tử dữ liệu có các đặc tính tương tự nhau. Nó giúp cho việc phát triển và thực hiện các chiến lược tiếp thị khách hàng cả về trực tuyến hoặc không trực tuyến như việc trả lời tự động cho các khách hàng thuộc nhóm chắc chắn, nó tạo ra sự thay đổi linh động một WebSite riêng biệt đối với mỗi khách hàng. 3.2.4.3. Phân tích đánh giá Phân tích mô hình [22]: Thống kê, tìm kiếm tri thức và tác nhân thông minh. Phân tích tính khả thi, truy vấn dữ liệu hướng tới sự tiêu dùng của con người. Trực quan hóa: Trực quan Web sử dụng lược đồ đường dẫn Web và đưa ra đồ thị có hướng OLAP. Ví dụ: Querying: SELECT association-rules(A*B*C*) FROM log.data WHERE (date>= 970101) AND (domain = ''edu'' )AND (support = 1.0) AND (confidence = 90.0) 3.2.5. Ví dụ khai phá theo sử dụng Web Ví dụ này sử dụng phương pháp khai phá phân lớp và phân cụm, luật kết hợp có thể được dùng để phân tích số lượng người dùng. Sau đó người thiết kế Web có thể đưa ra nhiều dịch vụ khác nhau tại các thời điểm khác nhau theo các quy tắc của người dùng truy cập Web site. Chất lượng dịch vụ tốt sẽ thúc đẩy số lượng người dùng thăm Web site. Quá trình thực hiện như sau: Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 76 - Chứng thực người dùng truy cập vào Web site, phân tích những người dùng đặc biệt tìm ra những người dùng quan trọng thông qua mức độ truy cập của họ, thời gian lưu lại trên đó và mức độ yêu thích trang Web. - Phân tích các chủ đề đặc biệt và chiều sâu nội dung Web. Ví dụ, hoạt động thường ngày của một quốc gia, giới thiệu các tour,... Quan hệ khá tự nhiên giữa người dùng và nội dung Web. Tìm ra những dịch vụ hấp dẫn và tiện lợi với người dùng. Tùy theo mức độ hiệu quả hoạt động truy cập Web site và điều kiện của việc duyệt Web site ta có thể dự kiến và đánh giá nội dung Web site tốt hơn. Dựa trên dữ liệu kiểm tra ta xác định mức độ truy xuất của người dùng qua việc phân tích một Web site và phân tích yêu cầu phục vụ thay đổi từng giờ, từng ngày như sau [16]: Thời gian Số người truy cập Thời gian Số người truy cập 00:00-00:59 936 12:00-12:59 2466 01:00-01:59 725 13:00-13:59 1432 02:00-02:59 433 14:00-14:59 1649 03:00-03:59 389 15:00-15:59 1537 04:00-04:59 149 16:00-16:59 2361 05:00-05:59 118 17:00-17:59 2053 06:00-06:59 126 18:00-18:59 2159 07:00-07:59 235 19:00-19:59 1694 08:00-08:59 599 20:00-20:59 2078 09:00-09:59 1414 21:00-21:59 2120 10:00-10:59 2424 22:00-22:59 1400 11:00-11:59 2846 23:00-23:59 1163 Bảng 3.1. Thống kê số người dùng tại các thời gian khác nhau Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 77 Hình 3.8. Phân tích người dùng truy cập Web 3.3. Khai phá cấu trúc Web WWW là hệ thống thông tin toàn cầu, bao gồm tất cả các Web site. Mỗi một trang có thể được liên kết đến nhiều trang. Các siêu liên kết thay đổi chứa đựng ngữ nghĩa chung chủ để của trang. Một siêu liên kết trỏ tới một trang Web khác có thể được xem như là một chứng thực của trang Web đó. Do đó, nó rất có ích trong việc sử dụng những thông tin ngữ nghĩa để lấy được thông tin quan trọng thông qua phân tích liên kết giữa các trang Web. Sử dụng các phương pháp khai phá người dùng để lấy tri thức hữu ích từ cấu trúc Web, tìm ra những trang Web quan trọng và phát triển kế hoạch để xây dựng các WebSite phù hợp với người dùng. Mục tiêu của khai phá cấu trúc Web là để phát hiện thông tin cấu trúc về Web. Nếu như khai phá nội dung Web chủ yếu tập trung vào cấu trúc bên trong tài liệu thì khai phá cấu trúc Web cố gắng để phát hiện cấu trúc liên kết của các siêu liên kết ở mức trong của tài liệu. Dựa trên mô hình hình học của các siêu liên kết, khai phá cấu trúc Web sẽ phân loại các trang Web, tạo ra thông tin như độ tương tự và mối quan hệ giữa các WebSite khác nhau. Nếu trang Web được 0 500 1000 1500 2000 2500 3000 00 :00 -00 : 5 9 01 :00 -01 :59 02 :00 -02 :59 03 :00 -03 :59 04 :00 -04 :59 05 :00 -05 :59 06 :00 -06 :59 07 :00 -07 :59 08 :00 -08 :59 09 :00 -09 :59 10 :00 -10 :59 11 :00 -11 :59 12 :00 -12 :59 13 :00 -13 :59 14 :00 -14 :59 15 :00 -15 :59 16 :00 -16 :59 17 :00 -17 :59 18 :00 -18 :59 19 :00 -19 :59 20 :00 -20 :59 21 :00 -21 :59 22 :00 -22 :59 23 :00 -23 :59 Số người Th ời gi an S ố n g ư ờ i Thời gian Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 78 liên kết trực tiếp với trang Web khác thì ta sẽ muốn phát hiện ra mối quan hệ giữa các trang Web này. Chúng có thể tương tự với nhau về nội dung, có thể thuộc dịch vụ Web giống nhau do đó nó được tạo ra bởi cùng một người. Những nhiệm vụ khác của khai phá cấu trúc Web là khám phá sự phân cấp tự nhiên hoặc mạng lưới của các siêu liên kết trong các Web site của một miền đặc biệt. Điều này có thể giúp tạo ra những luồng thông tin trong Web site mà nó có thể đại diện cho nhiều miền đặc biệt. Vì thế việc xử lý truy vấn sẽ trở nên dễ dàng hơn và hiệu quả hơn. + Việc phân tích liên kết Web được sử dụng cho những mục đích[1]: - Sắp thứ tự tài liệu phù hợp với truy vấn của người sử dụng. - Quyết định Web nào được đưa vào lựa chọn trong truy vấn. - Phân trang. - Tìm kiếm những trang liên quan. - Tìm kiếm những bản sao của Web. + Web được xem như là một đồ thị [1]: - Đồ thị liên kết: Mỗi nút là một trang, cung có hướng từ u đến v nếu có một siêu liên kết từ trang Web u sang trang Web v. Hình 3.9. Đồ thi liên kết Web Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 79 - Đồ thị trích dẫn: Mỗi nút cho một trang, không có cung hướng từ u đến v nếu có một trang thứ ba w liên kết cả u và v. - Giả định: Một liên kết từ trang u đến trang v là một thông báo đến trang v bởi trang u. Nếu u và v được kết nối bởi một đường liên kết thì rất có khả năng hai trang Web đó đều có nội dung tương tự nhau. 3.3.1. Tiêu chuẩn đánh giá độ tương tự - Khám phá ra một nhóm các trang Web giống nhau để khai phá, ta phải chỉ ra sự giống nhau của hai nút theo một tiêu chuẩn nào đó. Tiêu chuẩn 1: Đối với mỗi trang Web d1 và d2. Ta nói d1 và d2 quan hệ với nhau nếu có một liên kết từ d1 đến d2 hoặc từ d2 đến d1. Hình 3.10. Quan hệ trực tiếp giữa 2 trang Tiêu chuẩn 2: Đồng trích dẫn: Độ tương tự giữa d1 và d2 được đo bởi số trang dẫn tới cả d1 và d2. Hình 3.11. Độ tương tự đồng trích dẫn Tương tự chỉ mục: Độ tương tự giữa d1 và d2 được đo bằng số trang mà cả d1 và d2 đều trở tới. Hình 3.12. Độ tương tự chỉ mục d1 d2 2 d1 d2 2 d1 d2 2 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 80 3.3.2. Khai phá và quản lý cộng đồng Web Cộng đồng Web là một nhóm gồm các trang Web chia sẽ chung những vấn đề mà người dùng quan tâm. Các thành viên của cộng đông Web có thể không biết tình trạng tồn tại của mỗi trang (và có thể thậm chí không biết sự tồn tại của cộng đồng). Nhận biết được các cộng đồng Web, hiểu được sự phát triển và những đặc trưng của các cộng đồng Web là rất quan trọng. Việc xác định và hiểu các cộng đồng trên Web có thể được xem như việc khai phá và quản lý Web. Hình 3.13. Cộng đồng Web Đặc điểm của cộng đồng Web: - Các trang Web trong cùng một cộng đồng sẽ “tương tự” với nhau hơn các trang Web ngoài cộng đồng. - Mỗi cộng đồng Web sẽ tạo thành một cụm các trang Web. - Các cộng đồng Web được xác định một cách rõ ràng, tất cả mọi người đều biết, như các nguồn tài nguyên được liệt kê bởi Yahoo. - Cộng đồng Web được xác định hoàn chỉnh: Chúng là những cộng đồng bất ngờ xuất hiện. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 81 Cộng đồng Web ngày càng được mọi người quan tâm và có nhiều ứng dụng trong thực tiễn. Vì vậy, việc nghiên cứu các phương pháp khám phá cộng đồng là rất có ý nghĩa to lớn trong thực tiễn. Để trích dẫn ra được các cộng đồng ẩn, ta có thể phân tích đồ thị Web. Có nhiều phương pháp để chứng thực cộng đồng như thuật toán tìm kiếm theo chủ đề HITS, luồng cực đại và nhát cắt cực tiểu, thuật toán PageRank,... 3.3.2.1. Thuật toán PageRank Google dựa trên thuật toán PageRank [brin98], nó lập chỉ mục các liên kết giữa các Web site và thể hiện một liên kết từ A đến B như là xác nhận của B bởi A. Các liên kết có những giá trị khác nhau. Nếu A có nhiều liên kết tới nó và C có ít các liên kết tới nó thì một liên kết từ A đến B có giá trị hơn một liên kết từ C đến B. Giá trị được xác định như thế được gọi là PageRank của một trang và xác định thứ tự sắp xếp của nó trong các kết quả tìm kiếm (PageRank được sử dụng trong phép cộng để quy ước chỉ số văn bản để tạo ra các kết quả tìm kiếm chính xác cao). Các liên kết có thể được phân tích chính xác và hiệu quả hơn đối với khối lượng chu chuyển hoặc khung nhìn trang và trở thành độ đo của sự thành công và việc biến đối thứ hạng của các trang. Hình 3.14. Kết quả của thuật toán PageRank PageRank không đơn giản chỉ dựa trên tổng số các liên kết đến. Các tiếp cận cơ bản của PageRank là một tài liệu trong thực tế được xét đến quan trọng Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 82 hơn là các tài liệu liên kết tới nó, nhưng những liên kết về (tới nó) không bằng nhau về số lượng. Một tài liệu xếp thứ hạng cao trong các phần tử của PageRank nếu như có các tài liệu thứ hạng cao khác liên kết tới nó. Cho nên trong khái niệm PageRank, thứ hạng của một tài liệu được dựa vào thứ hạng cao của các tài liệu liên kết tới nó. Thứ hạng ngược lại của chúng được dựa vào thứ hạng thấp của các tài liệu liên kết tới chúng. 3.3.2.2. Phương pháp phân cụm nhờ thuật toán HITS Thuật toán HITS (Hypertext-Induced Topic Selection) do Kleinberg đề xuất, là thuật toán phát triển hơn trong việc xếp thứ hạng tài liệu dựa trên thông tin liên kết giữa tập các tài liệu. Định nghĩa: - Authority: Là các trang cung cấp thông tin quan trọng, tin cậy dựa trên các chủ đề đưa ra. - Hub: Là các trang chứa các liên kết đến authorities - Bậc trong: Là số các liên kết đến một nút, được dùng để đo độ ủy quyền. - Bậc ngoài: Là số các liên kết đi ra từ một nút, nó được sử dụng để đo mức độ trung tâm. Trong đó: Mỗi Hub trỏ đến nhiều Authority, mỗi Authority thì được trỏ đến bởi nhiều Hub. Chúng kết hợp với nhau tạo thành đồ thi phân đôi. Hình 3.15. Đồ thị phân đôi của Hub và Authority Các Authority and hub thể hiện một quan hệ tác động qua lại để tăng cường lực lượng. Nghĩa là một Hub sẽ tốt hơn nếu nó trỏ đến các Authority tốt và ngược lại một Authority sẽ tốt hơn nếu nó được trỏ đến bởi nhiều Hub tốt. Hub Authoritie Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 83 Hình 3.16. Sự kết hợp giữa Hub và Authority Các bước của phương pháp HITS Bước 1: Xác định một tập cơ bản S, lấy một tập các tài liệu trả về bởi Search Engine chuẩn được gọi là tập gốc R, khởi tạo S tương ứng với R. Bước 2: Thêm vào S tất cả các trang mà nó được trỏ tới từ bất kỳ trang nào trong R. Thêm vào S tất cả các trang mà nó trỏ tới bất kỳ trang nào trong R Với mỗi trang p trong S: Tính giá trị điểm số Authority: ap (vector a) Tính giá trị điểm số Hub: hp (vector h) Với mỗi nút khởi tạo ap và hp là 1/n (n là số các trang) Bước 3. Trong mỗi bước lặp tính giá trị trọng số Authority cho mỗi nút trong S theo công thức:    pqq qp ha : Bước 4. Mỗi bước lặp tính giá trị trọng số Hub đối với mỗi nút trong S theo công thức    pqq pq ah : 1 1 7 1 2 3 4 5 7 6 h(1) = a(5) + a(6) + a(7) a(1) = h(2) + h(3) + h(4) Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 84 Lưu ý rằng các trọng số Hub được tính toán nhờ vào các trọng số Authority hiện tạo, mà các trọng số Authority này lại được tính toán từ các trọng số của các Hub trước đó. Bước 5. Sau khi tính xong trọng số mới cho tất cả các nút, các trọng số được chuẩn hóa lại theo công thức:    Sp p Sp p handa 1)(1)( 22 Lặp lại bước 3 cho tới khi các hp và ap không đổi. Ví dụ: Tập gốc R là {1, 2, 3, 4} Hình 3.17. Đồ thị Hub-Authority Kết quả tính được như sau: Hình 3.18. Giá trị trọng số các Hub và Authority Giá trị trọng số của Authority Giá trị trọng số của Hub 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 85 KPDL Web là một lĩnh vực nghiên cứu mới, có triển vọng lớn. Các kỹ thuật được áp dụng rộng rãi trên thế giới như KPDL văn bản trên Web, KPDL không gian và thời gian liên tục trên Web. Khai phá Web đối với hệ thống thương mại điện tử, khai phá cấu trúc siêu liên kết Web,... Cho tới nay kỹ thuật KPDL vẫn phải đương đầu với nhiều thử thách lớn trong vấn đề KPDL Web. 3.4. Áp dụng thuật toán phân cụm dữ liệu trong tìm kiếm và phân cụm tài liệu Web Ngày nay, nhờ sự cải tiến không ngừng của các Search engine về cả chức năng tìm kiếm lẫn giao diện người dùng đã giúp cho người sử dụng dễ dàng hơn trong việc tìm kiếm thông tin trên web. Tuy nhiên, người sử dụng thường vẫn phải duyệt qua hàng chục thậm chí hàng ngàn trang Web mới có thể tìm kiếm được thứ mà họ cần. Theo tâm lý chung, người dùng chỉ xem qua vài chục kết quả đầu tiên, họ thiếu kiên nhẫn và không đủ thời gian để xem qua tất cả kết quả mà các search engine trả về. Nhằm giải quyết vấn đề này, chúng ta có thể nhóm các kết quả tìm kiếm thành thành các nhóm theo các chủ đề, khi đó người sử dụng có thể bỏ qua các nhóm mà họ không quan tâm để tìm đến nhóm chủ đề quan tâm. Điều này sẽ giúp cho người dùng thực hiện công việc của họ một cách hiệu quả hơn. Tuy nhiên vấn đề phân cụm dữ liệu trên Web và chọn chủ đề thích hợp để nó có thể mô tả được nội dung của các trang là một vấn đề không đơn giản. Trong luận văn này, ta sẽ xem khía cạnh sử dụng kỹ thuật phân cụm để phân cụm tài liệu Web dựa trên kho dữ liệu đã được tìm kiếm và lưu trữ. 3.4.1. Hướng tiếp cận bằng kỹ thuật phân cụm Hiện nay, để xác định mức độ quan trọng của một trang web chúng ta có nhiều cách đánh giá như PageRank, HITS, …Tuy nhiên, các phương pháp đánh giá này chủ yếu đều dựa vào các liên kết trang để xác định trọng số cho trang. Ta có thể tiếp cận cách đánh giá mức độ quan trọng theo một hướng khác là dựa vào nội dung của các tài liệu để xác định trọng số, nếu các tài liệu "gần Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 86 nhau" về nội dung thì sẽ có mức độ quan trọng tương đương và sẽ thuộc về cùng một nhóm. Giả sử cho tập S gồm các trang web, hãy tìm trong tập S các trang chứa nội dung câu hỏi truy vấn ta được tập R. Sử dụng thuật toán phân cụm dữ liệu để phân tập R thành k cụm (k xác định) sao cho các phần tử trong cụm là tương tự nhau nhất, các phần tử ở các cụm khác nhau thì phi tương tự với nhau. Từ tập S-R, chúng ta đưa các phần tử này vào một trong k cụm đã được thiết lập ở trên. Những phần tử nào tương tự với trọng tâm của cụm (theo một ngưỡng xác định nào đó) thì đưa vào cụm này, những phần tử không thỏa mãn xem như không phù hợp với truy vấn và loại bỏ nó khỏi tập kết quả. Kế tiếp, chúng ta đánh trọng số cho các cụm và các trang trong tập kết quả theo thuật toán sau: INPUT: tập dữ liệu D chứa các trang gồm k cụm và k trọng tâm OUTPUT: trọng số của các trang BEGIN Mỗi cụm dữ liệu thứ m và trọng tâm Cm ta gán một trọng số tsm. Với các trọng tâm Ci, Cj bất kỳ ta luôn có tsi>tsj nếu ti tương tự với truy vấn hơn tj. Với mỗi trang p trong cụm m ta xác định trọng số trang pwm. Với mỗi pwi, pwj bất kỳ, ta luôn có pw1>pw2 nếu pw1 gần trọng tâm hơn pw2. END Hình 3.19. Thuật toán đánh trọng số cụm và trang Như vậy, theo cách tiếp cận này ta sẽ giải quyết được các vấn đề sau: + Kết quả tìm kiếm sẽ được phân thành các cụm theo các chủ đề khác nhau, tùy vào yêu cầu cụ thể người dùng sẽ xác định chủ đề mà họ cần. + Quá trình tìm kiếm và xác định trọng số cho các trang chủ yếu tập trung vào nội dung của trang hơn là dựa vào các liên kết trang. + Giải quyết được vấn đề từ/cụm từ đồng nghĩa trong câu truy vấn của người dùng. + Có thể kết hợp phương pháp phân cụm trong lĩnh vực khai phá dữ liệu với các phương pháp tìm kiếm đã có. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 87 Hiện tại, có một số thuật toán phân cụm dữ liệu được sử dụng trong phân cụm văn bản như thuật toán phân cụm phân hoạch (k-means, PAM, CLARA), thuật toán phân cụm phân cấp (BIRCH, STC),... Trong thực tế phân cụm theo nội dung tài liệu Web, một tài liệu có thể thuộc vào nhiều nhóm chủ đề khác nhau. Để giải quyết vấn đề này ta có thể sử dụng thuật toán phân cụm theo cách tiếp cận mờ. 3.4.2. Quá trình tìm kiếm và phân cụm tài liệu Về cơ bản, quá trình phân cụm kết quả tìm kiếm sẽ diễn ra theo các bước được thể hiện như sau [31]: - Tìm kiếm các trang Web từ các Website thỏa mãn nội dung truy vấn. - Trích rút thông tin mô tả từ các trang và lưu trữ nó cùng với các URL tương ứng. - Sử dụng kỹ thuật phân cụm dữ liệu để phân cụm tự động các trang Web thành các cụm, sao cho các trang trong cụm “tương tự” về nội dung với nhau hơn các trang ngoài cụm. Hình 3.20. Các bước phân cụm kết quả tìm kiếm trên Web 3.4.2.1. Tìm kiếm dữ liệu trên Web Nhiệm vụ chủ yếu của giai đoạn này là dựa vào tập từ khóa tìm kiếm để tìm kiếm và trả về tập gồm toàn văn tài liệu, tiêu đề, mô tả tóm tắt, URL,… tương ứng với các trang đó. Dữ liệu web Tìm kiếm và trích rút dữ liệu Tiền xử lý Biểu diễn dữ liệu Áp dụng thuật toán phân cụm Biểu diễn kết quả Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 88 Nhằm nâng cao tốc độ xử lý, ta tiến hành tìm kiếm và lưu trữ các tài liệu này trong kho dữ liệu để sử dụng cho quá trình tìm kiếm (tương tự như các Search Engine Yahoo, Google,…). Mỗi phần tử gồm toàn văn tài liệu, tiêu đề, đoạn mô tả nội dung, URL,… 3.4.2.2. Tiền xử lý dữ liệu Quá trình làm sạch dữ liệu và chuyển dịch các tài liệu thành các dạng biểu diễn dữ liệu thích hợp. Giai đoạn này bao gồm các công việc như sau: Chuẩn hóa văn bản, xóa bỏ các từ dừng, kết hợp các từ có cùng từ gốc, số hóa và biểu diễn văn bản,.. 3.4.2.2.1. Chuẩn hóa văn bản Đây là giai đoạn chuyển văn bản thô về dạng văn bản sao cho việc xử lý sau này được dễ dàng, đơn giản, thuật tiện, chính xác so với việc xử lý trực tiếp trên văn bản thô mà ảnh hưởng ít đến kết quả xử lý. Bao gồm: + Xóa các thẻ HTML và các loại thẻ khác để trích ra các từ/cụm từ. + Chuyển các ký tự hoa thành các ký tự thường. + Xóa bỏ các dấu câu, xoá các ký tự trắng dư thừa,... 3.4.2.2.2. Xóa bỏ các từ dừng Trong văn bản có những từ mang ít thông tin trong quá trình xử lý, những từ có tần số xuất hiện thấp, những từ xuất hiện với tần số lớn nhưng không quan trọng cho quá trình xử lý đều được loại bỏ. Theo một số nghiên cứu gần đây cho thấy việc loại bỏ các từ dùng có thể giảm bởi được khoảng 20-30% tổng số từ trong văn bản. Có rất nhiều từ xuất hiện với tần số lớn nhưng nó không hữu ích cho quá trình phân cụm dữ liệu. Ví dụ trong tiếng Anh các từ như a, an, the, of, and, to, on, by,... trong tiếng Việt như các từ “thì”, “mà”, “là”, “và”, “hoặc”,... Những từ xuất hiện với tần số quá lớn cũng sẽ được loại bỏ. Để đơn giản trong ứng dụng thực tế, ta có thể tổ chức thành một danh sách các từ dừng, sử dụng định luật Zipf để xóa bỏ các từ có tần số xuất hiện thấp hoặc quá cao. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 89 3.4.2.2.3. Kết hợp các từ có cùng gốc Hầu hết trong các ngôn ngữ đều có rất nhiều các từ có chung nguồn gốc với nhau, chúng mang ý nghĩa tương tự nhau, do đó để giảm bởt số chiều trong biểu diễn văn bản, ta sẽ kết hợp các từ có cùng gốc thành một từ. Theo một số nghiên cứu [5] việc kết hợp này sẽ giảm được khoảng 40-50% kích thước chiều trong biểu diễn văn bản. Ví dụ trong tiếng Anh, từ user, users, used, using có cùng từ gốc và sẽ được quy về là use; từ engineering, engineered, engineer có cùng từ gốc sẽ được quy về là engineer. Ví dụ xử lý từ gốc trong tiếng Anh: - Nêu một từ kết thúc bằng “ing” thì xóa “ing”, ngoại trừ trường hợp sau khi xóa còn lại 1 ký tự hoặc còn lại “th”. - Nếu một từ kết thúc bằng “ies” nhưng không phải là “eies” hoặc “aies” thì thay thế “ies” bằng “y”..... - Nếu một từ kết thúc bằng “es” thì bỏ “s”. - Nếu một từ kết thúc bởi "s" và đứng trước nó là một phụ âm khác “s” thì xóa “s”. - Nếu một từ kết thúc bằng “ed”, nếu trước nó là một phụ âm thì xóa “ed” ngoại trừ sau khi xóa từ chỉ còn lại một ký tự, nếu đứng trước là nguyên âm “i” thì đổi “ied” thành “y”. 3.4.2.3. Xây dựng từ điển Việc xây dựng từ điển là một công việc rất quan trọng trong quá trình vector hóa văn bản, từ điển sẽ gồm các từ/cụm từ riêng biệt trong toàn bộ tập dữ liệu. Từ điển sẽ gồm một bảng các từ, chỉ số của nó trong từ điển và được sắp xếp theo thứ tự. Một số bài báo đề xuất [31] để nâng cao chất lượng phân cụm dữ liệu cần xem xét đến việc xử lý các cụm từ trong các ngữ cảnh khác nhau. Theo đề xuất của Zemir [19][31] xây dựng từ điển có 500 phần tử là phù hợp. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 90 3.4.2.4. Tách từ, số hóa văn bản và biểu diễn tài liệu Tách từ là công việc hết sức quan trọng trong biểu diễn văn bản, quá trình tách từ, vector hóa tài liệu là quá trình tìm kiếm các từ và thay thế nó bởi chỉ số của từ đó trong từ điển. Ở đây ta có thể sử dụng một trong các mô hình toán học TF, IDF, TF- IDF,... để biểu diễn văn bản. Chúng ta sử dụng mảng W (trọng số) hai chiều có kích thước m x n, với n là số các tài liệu, m là số các thuật ngữ trong từ điển (số chiều), hàng thứ j là một vector biểu diễn tài liệu thứ j trong cơ sở dữ liệu, cột thứ i là thuật ngữ thứ i trong từ điển. Wij là giá trị trọng số của thuật ngữ i đối với tài liệu j. Giai đoạn này thực hiện thống kê tần số thuật ngữ ti xuất hiện trong tài liệu dj và số các tài liệu chứa ti. Từ đó xây dựng bảng trọng số của ma trận W theo công thức sau: Công thức tính trọng số theo mô hình IF-IDF: Trong đó: tfij là tần số xuất hiện của ti trong tài liệu dj idfij là nghịch đảo tần số xuất hiện của ti trong tài liệu dj. hi là số các tài liệu mà ti xuất hiện. n là tổng số tài liệu. 3.4.2.5. Phân cụm tài liệu Sau khi đã tìm kiếm, trích rút dữ liệu và tiền xử lý và biểu diễn văn bản chúng ta sử dụng kỹ thuật phân cụm để phân cụm tài liệu. INPUT: Tập gồm n tài liệu và k cụm. OUTPUT: Các cụm Ci (i=1,..,k) sao cho hàm tiêu chuẩn đạt giá trị cực tiểu. BEGIN Bước 1. Khởi tạo ngẫu nhiên k vector làm đối tượng trọng tâm của k cụm. Wij= )log()]log(1[ i ijijij h n tfidftf  nếu ti  dj 0 nếu ngược lại (ti dj) Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 91 Bước 2. Với mỗi tài liệu dj xác định độ tương tự của nó đối với trọng tâm của mỗi cụm theo một trong các độ đo tương tự thường dùng (như Dice, Jaccard, Cosine, Overlap, Euclidean, Manhattan). Xác định trọng tâm tương tự nhất cho mỗi tài liệu và đưa tài liệu vào cụm đó. Bước 3. Cập nhận lại các đối tượng trọng tâm. Đối với mỗi cụm ta xác định lại trọng tâm bằng cách xác định trung bình cộng của các vector tài liệu trong cụm đó. Bước 4. Lặp lại bước 2 và 3 cho đến khi trong tâm không thay đổi. END. Hình 3.21. Thuật toán k-means trong phân cụm nội dung tài liệu Web Vấn đề xác định trọng tâm của cụm tài liệu: Xét một cụm văn bản c, trong đó trọng tâm C của cụm c được tính nhờ vào vector tổng D (    cd dD ) của các văn bản trong cụm c: || c D C  Trong đó, |c| là số phần tử thuộc tập tài liệu c. Trong kỹ thuật phân cụm, trọng tâm của các cụm được sử dụng để làm đại diện cho các cụm tài liệu. Vấn đề tính toán độ tương tự giữa 2 cụm tài liệu: Giả sử ta có 2 cụm c1, c2, khi đó độ tương tự giữa 2 cụm tài liệu được tính bằng mức độ “gần nhau” giữa 2 vector trọng tâm C1, C2: Sim(c1,c2)= sim(C1,C2) Ở đây, ta hiểu rằng c1 và c2 cũng có thể chỉ gồm một tài liệu vì khi đó có thể coi một cụm chỉ gồm 1 phần tử. Trong thuật toán k-means, chất lượng phân cụm được đánh giá thông quan hàm tiêu chuẩn     k i x iC i mxE D 1 2 )( , trong đó x là các vector biểu diễn tài liệu, mi là các trọng tâm của các cụm, k là số cụm, Ci là cụm thứ i. - Độ phức tạp của thuật toán k-means là O((n.k.d).r). Trong đó: n là số đối tượng dữ liệu, k là số cụm dữ liệu, d là số chiều, r là số vòng lặp. Sau khi phân cụm xong tài liệu, trả về kết quả là các cụm dữ liệu và các trọng tâm tương ứng. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 92 3.4.6. Kết quả thực nghiệm + Dữ liệu thực nghiệm là các trang Web lấy từ 2 nguồn chính sau: - Các trang được lấy tự động từ các Website trên Internet, việc tìm kiếm được thực hiện bằng cách sử dụng Yahoo để tìm kiếm tự động, chương trình sẽ dựa vào URL để lấy toàn văn của tài liệu đó và lưu trữ lại phục vụ cho quá trình tìm kiếm sau này (dưa liệu gồm hơn 4000 bài về các chủ đề “data mining”, “web mining”, “Cluster algorithm”, “Sport”). - Tìm kiếm có chọn lọc, phần này được tiến hành lấy thủ công, nguồn dữ liệu chủ yếu được lấy từ các Web site: Gồm hơn 250 bài báo chủ đề “bóng đá”. - Việc xây dựng từ điển, sau khi thống kê tần số xuất hiện của các từ trong tập tài liệu, ta áp dụng định luật Zipf để loại bỏ những từ có tần số xuất hiện quá cao và loại bỏ những từ có tần số quá thấp, ta thu được bộ từ điển gồm 500 từ. Số tài liệu Số cụm Thời gian trung bình (giây) Tiền xử lý và biểu diễn văn bản Phân cụm tài liệu 50 10 0,206 0,957 50 15 0,206 1,156 100 10 0,353 2,518 100 15 0,353 3,709 150 10 0,515 4,553 150 15 0,515 5,834 250 10 0,824 9,756 250 15 0,824 13,375 Bảng 3.2. Bảng đo thời gian thực hiện thuật toán phân cụm Ta thấy rằng thời gian thực hiện thuật toán phụ vào độ lớn dữ liệu và số cụm cần phân cụm. Ngoài ra, với thuật toán k-means còn phụ thuộc vào k trọng Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 93 tâm khởi tạo ban đầu. Nếu k trọng tâm được xác định tốt thì chất lượng và thời gian thực hiện được cải thiện rất nhiều. Phần giao diện chương trình và một số đoạn mã code điển hình được trình bày ở phụ lục. 3.5. Tổng kết chương 3 Chương này tác giả đã trình bày một số hướng tiếp cận trong khai phá Web như khai phá dữ liệu toàn văn của tài liệu Web, khai phá cấu trúc Web, khai phá sử dụng Web và một số thuật toán đang được áp dụng trong khai phá Web. Phần này cũng trình bày một số chức năng trong quy trình của hệ thống thực nghiệm như tìm kiếm và trích chọn dữ liệu trên Web, tiền xử lý dữ liệu, chuẩn hoá văn bản, xoá bỏ từ dừng, xây dựng từ điển, tách từ và biểu diễn văn bản, phân cụm tài liệu và đánh giá kết quả thực nghiệm. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 94 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Luận văn đã nêu lên được những nét cơ bản về khai phá dữ liệu, khám phá tri thức và những vấn đề liên quan, kỹ thuật phân cụm dữ liệu và đi sâu vào một số phương pháp phân cụm truyền thống, phổ biến như phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ, phân cụm dựa trên lưới, phân cụm dựa trên mô hình và theo hướng tiếp cận mờ. Luận văn tập trung vào một hướng nghiên cứu và phát triển mới trong khai phá dữ liệu đó là khai phá Web, một hướng đang thu hút sự quan tâm của nhiều nhà khoa học. Phần này trình bày những vấn đề về các hướng tiếp trong khai phá Web như khai phá tài liệu Web, khai phá cấu trúc Web và khai phá theo hướng sử dụng Web. Một kỹ thuật trong khai phá Web đó là phân cụm dữ liệu Web. Tác giả cũng đã trình bày một hướng tiếp cận trong việc sử dụng các kỹ thuật phân cụm trong khai phá dữ liệu Web. Đề xuất và xây dựng một chương trình thực nghiệm phân cụm tài liệu Web áp dụng trong tìm kiếm dữ liệu với thuật toán k-means dựa trên mô hình vector biểu diễn văn bản TF-IDF. Lĩnh vực khai phá Web là một vấn đề khá mới mẽ, rất quan trọng và khó, bên cạnh những kết quả nghiên cứu đã đạt được nó đã đặt ra những thách thức lớn đối với các nhà nghiên cứu. Khai phá Web là một lĩnh vực đầy triển vọng, phức tạp và còn là vấn đề mở. Hiện chưa có một thuật toán và mô hình biểu diễn dữ liệu tối ưu trong khai phá dữ liệu Web. Mặc dù đã cố gắng, nỗ lực hết mình song do thời gian nghiên cứu, trình độ của bản thân có hạn và điều kiện nghiên cứu còn nhiều hạn chế nên không thể tránh khỏi những khuyết thiếu và hạn chế, tác giả rất mong nhận được những góp ý, nhận xét quý báu của quý thầy cô và bạn bè để kết quả của đề tài hoàn thiện hơn. Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 95 Hướng phát triển: - Tiếp tục nghiên cứu, đề xuất và cải tiến một số kỹ thuật mới trong phân cụm dữ liệu như phân cụm mờ, các thuật toán phân cụm song song,... nhằm nâng cao hiệu suất khai phá dữ liệu trên hệ thống dữ liệu lớn, phân tán. - Nghiên cứu các mô hình biểu diễn và xử lý văn bản mới như mô hình mờ, mô hình tập thô,... nhằm nâng cao hiệu quả xử lý và khai phá dữ liệu đặc biệt là xử lý dữ liệu trong môi trường Web.. - Áp dụng các kỹ thuật KPDL vào lĩnh vực thương mại điện tử, chính phủ điện tử,... Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 96 PHỤ LỤC Chương trình được viết trên nền .NET Framework 2.0 và ngôn ngữ lập trình Visual Basic 2005, cơ sở dữ liệu được lưu trữ và quản lý bằng SQL Server 2005. Sau đây là một số mã lệnh và giao diện xử lý của chương trình. Một số modul xử lý trong cương trình 1. Chuẩn hoá xâu văn bản Private Function Chuanhoa(ByVal S As String) As String For i = 1 To 9 S = S.Replace(Str(i) + ".", Str(i)) S = S.Replace(Str(i) + ",", Str(i)) Next i = 0 Do While i < S.Length - 1 If (Not Char.IsLetterOrDigit(S(i))) And (S(i) " ") Then S = S.Remove(i, 1) S = S.Insert(i, " ") Else i = i + 1 End If Loop i = 0 Do While i < S.Length - 1 If ((Char.IsDigit(S(i))) And (Not Char.IsDigit(S(i + 1)))) Or ((Not Char.IsDigit(S(i))) And (Char.IsDigit(S(i + 1)))) Then S = S.Insert(i + 1, " ") i = i + 1 End If i = i + 1 Loop S = S.ToLower(VN) i = 0 Do While i < S.Length - 2 If S(i) + S(i + 1) = " " Then S = S.Remove(i, 1) Else i = i + 1 End If Loop S = S.Trim Return S End Function Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 97 2. Xoá từ dừng Private Function XoaTuDung(ByVal S As String) As String For i = 0 To ListTD.Count - 1 S = S.Replace(" " + ListTD.Item(i) + " ", " ") Next i i = 0 Do While i < S.Length Do While (i < S.Length - 1) And (S(i) = " ") i = i + 1 Loop j = i + 1 Kt = False Do While (j < S.Length) And (Not Kt) If S(j) " " Then j = j + 1 Else Kt = True End If Loop If i = j - 1 Then S = S.Remove(i, 1) End If i = j Loop S = S.Trim() Return S End Function 3. Xây dựng từ điển Private Sub XayDungTuDien(ByVal Doc As ArrayList) For Each S In Doc list = New ArrayList(S.Split(" ")) For Each ST In list If Trim(ST) "" Then i = TuDien.IndexOf(ST) If (i < 0) Then TuDien.Add(Trim(ST)) TuDienTS.Add(1) Else TuDienTS(i) = TuDienTS(i) + 1 End If End If Next Next 'Sap xep theo giam dan cua tan so tu trong tap Van ban If (TuDien(0) = " ") Or (TuDien(0) = "") Then TuDien.RemoveAt(0) End If Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 98 QuikSort(0, TuDien.Count - 1, TuDien, TuDienTS) Do While (TuDien.Count>500) And (TuDienTS(0) > Int(NumDoc * (MaxWork / 100))) TuDien.RemoveAt(0) TuDienTS.RemoveAt(0) Loop Do While (TuDien.Count > MaxWork) TuDien.RemoveAt(MaxWork) TuDienTS.RemoveAt(MaxWork) Loop End Sub 4. Vector hoá văn bản Private Sub VectorVB(ByVal Collect As ArrayList) Vector = Array.CreateInstance(GetType(Byte), NumDoc, NumWord) i = 0 For Each S In Collect List = New ArrayList(S.Split(" ")) For Each ST In List If Trim(ST) "" Then k = TuDien.IndexOf(ST) If k > 0 Then Vector(i, k) = Vector(i, k) + 1 End If End If Next i = i + 1 Next End Sub 5. Xây dựng bảng trọng số Private Sub XDTrongSo(ByVal Vector As Array) Dim thongke(NumWord) As Integer For i = 0 To NumWord - 1 thongke(i) = 0 For j = 0 To NumDoc - 1 If Vector(j, i) > 0 Then thongke(i) = thongke(i) + 1 End If Next Next W = Array.CreateInstance(GetType(Double), NumDoc, NumWord) For i = 0 To NumDoc - 1 For j = 0 To NumWord - 1 If Vector(i, j) > 0 Then W(i, j)=(1 + Math.Log(Vector(i, Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 99 j)))*(Math.Log(NumDoc)-Math.Log(thongke(j))) Else W(i, j) = 0.0 End If Next Next End Sub 6. Thuật toán k-means Private Sub PhanCumKMean() Randomize(NumDoc) 'Buoc 1: KHOI TAO CAC TRONG TAM i = 0 Do While i < k r = CInt(Int(NumDoc * Rnd())) If Not rnum.Contains(r) Then rnum.Add(r) For j = 0 To NumWord - 1 C(i, j) = W(r, j) Next i = i + 1 End If Loop For i = 0 To NumDoc - 1 Cum(i) = 0 Next check1 = True Do While check1 'Buoc 2:Tinh toan khoang cach va xac dinh cum cho cac pt. For i = 0 To NumDoc - 1 min = Double.MaxValue Cum(i) = 0 For j = 0 To k - 1 dis = 0 For m = 0 To NumWord - 1 temp = W(i, m) - C(j, m) dis = dis + Math.Abs(temp * temp) Next dis = Math.Sqrt(dis) If dis < min Then min = dis Cum(i) = j End If Next Next 'Buoc 3: Cap nhat lai Trong tam check1 = False For i = 0 To k - 1 'Cap nhat lan luot Trong tam tung cum For j = 0 To NumWord - 1 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 100 n = 0 sum = 0 For m = 0 To NumDoc - 1 If Cum(m) = i Then sum = sum + W(m, j) n = n + 1 End If Next sum = sum / n If C(i, j) sumThen C(i, j) = sum check1 = True End If Next Next Loop End Sub Một số giao diện chương trình 1. Công cụ tìm kiếm tự động tài liệu trên Internet và lưu trữ vào CSDL 2. Công cụ tìm kiếm chọn lọc tài liệu trên Internet và lưu trữ vào CSDL Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 101 3. Trích chọn dữ liệu, tiền xử lý, xây dựng từ điển và vector hóa văn bản 4. Phân cụm tài liệu và biểu diễn kết quả Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 102 TÀI LIỆU THAM KHẢO Tài liệu tiếng Việt [1] Cao Chính Nghĩa, “Một số vấn đề về phân cụm dữ liệu”, Luận văn thạc sĩ, Trường Đại học Công nghệ, ĐH Quốc gia Hà Nội, 2006. [2] Hoàng Hải Xanh, “Về các kỹ thuật phân cụm dữ liệu trong data mining”, luận văn thạc sĩ, Trường ĐH Quốc Gia Hà Nội, 2005 [3] Hoàng Thị Mai, “Khai phá dữ liệu bằng phương pháp phân cụm dữ liệu”, Luận văn thạc sĩ, Trường ĐHSP Hà Nội, 2006. Tài liệu tiếng Anh [4] Athena Vakali, Web data clustering Current research status & trends, Aristotle University,Greece, 2004. [5] Bing Liu, Web mining, Springer, 2007. [6] Brij M. Masand, Myra Spiliopoulou, Jaideep Srivastava, Osmar R. Zaiane, Web Mining for Usage Patterns & Profiles, ACM, 2002. [7] Filippo Geraci, Marco Pellegrini, Paolo Pisati, and Fabrizio Sebastiani, A scalable algorithm for high-quality clustering of Web Snippets, Italy, ACM, 2006. [8] Giordano Adami, Paolo Avesani, Diego Sona, Clustering Documents in a Web Directory, ACM, 2003. [9] Hiroyuki Kawano, Applications of Web mining- from Web search engine to P2P filtering, IEEE, 2004. [10] Ho Tu Bao, Knowledge Discovery and Data Mining, 2000. [11] Hua-Jun Zeng, Qi-Cai He, Zheng Chen, Wei-Ying Ma, Jinwen Ma, Learning to Cluster Web Search Results, ACM, 2004. [12] Jitian Xiao, Yanchun Zhang, Xiaohua Jia, Tianzhu Li, Measuring Similarity of Interests for Clustering Web-Users, IEEE, 2001. [13] Jiawei Han, Micheline Kamber, Data Mining: Concepts and Techniques, University of Illinois at Urbana-Champaign, 1999. [14] Khoo Khyou Bun, “Topic Trend Detection and Mining in World Wide Web”, A thesis for the degree of PhD, Japan, 2004. [15] LIU Jian-guo, HUANG Zheng-hong , WU Wei-ping, Web Mining for Electronic Business Application, IEEE, 2003. [16] Lizhen Liu, Junjie Chen, Hantao Song, The research of Web Mining, IEEE, 2002 Khai phá dữ liệu Web bằng kỹ thuật phân cụm Hoàng Văn Dũng 103 [17] Maria Rigou, Spiros Sirmakessis, and Giannis Tzimas, A Method for Personalized Clustering in Data Intensive Web Applications, 2006. [18] Miguel Gomes da Costa Júnior, Zhiguo Gong, Web Structure Mining: An Introduction, IEEE, 2005. [19] Oren Zamir and Oren Etzioni, Web document Clustering: A Feasibility Demonstration, University of Washington, USA, ACM, 1998. [20] Pawan Lingras, Rough Set Clustering for Web mining, IEEE, 2002. [21] Periklis Andritsos, Data Clusting Techniques, University Toronto,2002. [22] R. Cooley, B. Mobasher, and J. Srivastava, Web mining: Information and Pattern Discovery on the World Wide Web, University of Minnesota, USA, 1998. [23] Raghu Krishnapuram, Anupam Joshi, and Liyu Yi, A Fuzzy Relative of the K -Medoids Algorithm with Application toWeb Document and Snippet Clustering, 2001 [24] Raghu Krishnapuram,Anupam Joshi, Olfa Nasraoui, and Liyu Yi, Low- Complexity Fuzzy Relational Clustering Algorithms for Web Mining, IEEE, 2001. [25] Raymond and Hendrik, Web Mining Research: A Survey, ACM, 2000 [26] Rui Wu, Wansheng Tang,Ruiqing Zhao, An Efficient Algorithm for Fuzzy Web-Mining, IEEE, 2004. [27] T.A.Runkler, J.C.Bezdek, Web mining with relational clustering, ELSEVIER, 2002. [28] Tsau Young Lin, I-Jen Chiang , “A simplicial complex, a hypergraph, structure in the latent semantic space of document clustering”, ELSEVIER, 2005. [29] Wang Jicheng, Huang Yuan, Wu Gangshan, and Zhang Fuyan, Web Mining: Knowledge Discovery on the Web, IEEE, 1999. [30] WangBin, LiuZhijing, Web Mining Research, IEEE, 2003. [31] Wenyi Ni, A Survey of Web Document Clustering, Southern Methodist University, 2004. [32] Yitong Wang, Masaru Kitsuregawa, Evaluating Contents-Link Coupled Web Page Clustering for Web Search Results, ACM, 2002. [33] Zifeng Cui, Baowen Xu , Weifeng Zhang, Junling Xu, Web Documents Clustering with Interest Links, IEEE, 2005.