Đăng ký Đăng nhập
Trang chủ Kỹ thuật phân lớp áp dụng cho dạng dữ liệu có liên kết...

Tài liệu Kỹ thuật phân lớp áp dụng cho dạng dữ liệu có liên kết

.PDF
26
327
64

Mô tả:

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ......................................... Nguyễn Việt Tân ĐỀ TÀI:Kỹ thuật phân lớp áp dụng cho dạng dữ liệu có liên kết Chuyênngành: Truyền dữ liệu và mạng máy tính Mãsố: 60.48.15 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – 2012 Luậnvănđượchoànthànhtại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Ngườihướngdẫnkhoahọc.: PGS .TS Từ Minh Phương Phảnbiện 1: ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… Phảnbiện 2: ……………………………………………………………… ……………………………………………………………… ……………………………………………………………… LuậnvănsẽđượcbảovệtrướcHộiđồngchấmluậnvănthạcsĩtạiHọc việnCôngnghệBưuchínhViễnthông Vàolúc: .......giờ ....... ngày ....... tháng ....... .. năm ........ Cóthểtìmhiểuluậnvăntại: - ThưviệncủaHọcviệnCôngnghệBưuchínhViễnthông -1- MỞ ĐẦU Phân loại hay phân lớp là kỹ thuật khai phá dữ liệu đã được nghiên cứu và sử dụng rộng rãi. Đây là phần quan trọng trong các dạng ứng dụng như phân loại văn bản, nhận dạng chữ viết, giọng nói, phân loại protein v.v. Việc phân lớp là nhằm dự đoán các nhãn phân lớp cho những mẫu chưa biết hoặc cho các bộ dữ liệu mới. Đầu vào cho việc phân lớp là một tập các mẫu dữ liệu huấn luyện, trong đó các đối tượng đều đã có nhãn phân lớp. Đầu ra sẽ là một mô hình phân lớp dựa trên những mẫu huấn luyện đã cho. Trên thực tế tồn tại một số bài toán trong đó giữa các đối tượng cần phân lớp có các liên kết với nhau. Chẳng hạn, khi phân loại trang web, ngoài nội dung trang, các trang lại có các siêu liên kết. Hay khi phân loại protein, các protein thường có các liên kết tương ứng với quan hệ tương tác giữa chúng. Các quan hệ liên kết cũng là dạng dữ liệu tiêu biểu với các ứng dụng cho mạng máy tính. Từ thực tế này, một vấn đề đặt ra là tận dụng các thông tin liên kết trong dữ liệu để tăng hiệu quả và độ chính xác cho thuật toán phân lớp. Nguyên tắc chung của việc phân lớp dữ liệu có liên kết là tạo ra các ràng buộc, theo đó những đối tượng liên kết với nhau cần có nhãn phân lớp tương tự nhau. Dựa trên nguyên tắc chung này, nhiều thuật toán và kỹ thuật cụ thể đã được phát triển và ứng dụng. Một trong những tiếp cận sớm nhất chú ý tới mối liên kết giữa các đối tượng trong dữ liệu có liên kết là của Chakrabarti và các cộng -2sự [3]. Họ đề xuất một mô hình xác suất cho phân loại trang web bằng cách sử dụng kết hợp giữa nội dung của trang đã phân lớp, nhãn phân lớp của các trang liên kết và nội dung của các trang liên kết. Gần đây, Macskassy và Provost [9] đã thử nghiệm phân lớp tập hợp cho dữ liệu liên kết bằng cách kết hợp một bộ phân lớp liên kết (relation classifier) với một phương thức suy luận tập hợp (collective inferencing). Sen và các cộng sự [10] cũng đã so sánh bốn phương pháp phân loại tập hợp cho dữ liệu có liên kết. Bên cạnh các phương pháp phân loại sử dụng bộ phân lớp liên kết, một hướng tiếp cận khác là phương pháp học bán giám sát (semi-supervised learning) dựa trên đồ thị, trong đó tiêu biểu phải kể đến phương pháp trường ngẫu nhiên Gauss (Gaussian random field) [12], phương pháp nhất quán địa phương và toàn cục [11]. Luận văn này sẽ tập trung vào việc nghiên cứu, phân tích và đánh giá thực nghiệm các kỹ thuật phân lớp cho dữ liệu có liên kết. Một nội dung quan trọng của luận văn là nghiên cứu việc kết hợp các phương pháp đã có để tận dụng cả thông tin liên kết lẫn thông tin cục bộ của dữ liệu; cụ thể là phương pháp phân lớp tập hợp kết hợp một bộ phân lớp liên kết, một bộ phân lớp cục bộ và một phương thức suy luận tập hợp. Kết quả phân lớp theo cách này sẽ được đánh giá và so sánh với kết quả của các phương pháp phân lớp sử dụng từng bộ phân lớp riêng lẻ cũng như so sánh với phương pháp phân lớp liên kết không sử dụng suy luận tập hợp. Liên quan tới nội dung của luận văn, chúng tôi cũng đã đề xuất một phương pháp khác để phân lớp cho dữ liệu có liên kết. Phương -3pháp này kết hợp một bộ phân lớp liên kết với một bộ phân lớp cục bộ bằng kỹ thuật Co-training. Nội dung và kết quả của phương pháp này đã được báo cáo tại Hội thảo Quốc gia lần thứ XIV "Một số vấn đề chọn lọc của Công nghệ Thông tin và Truyền thông" tại Cần Thơ vào tháng 10 năm 2011. Luận văn được chia thành 3 chương chính như sau: Chương 1 - Tổng quan về phân lớp dữ liệu: Chương này trình bày các khái niệm về phân lớp, các bước đề giải quyết một một bài toán phân lớp và một số vấn đề cần quan tâm trong việc phân lớp dữ liệu. Bốn thuật toán phân lớp phổ biến hiện nay dành cho dữ liệu dạng truyền thống là cây quyết định, mạng Bayes, mạng Nơ-ron và SVM cũng sẽ được trình trong chương này. Chương 2 - Phân lớp cho dữ liệu có liên kết: Giới thiệu về dạng dữ liệu có liên kết và các phương pháp phân lớp cho dữ liệu có liên kết. Ngoài ra, chương này còn trình bày bốn thuật toán phân lớp dành cho dữ liệu liên kết là wvRN, CDRN, NBC, NLB cùng với ba phương thức suy luận tập hợp áp dụng để phân lớp tập hợp là GS, RL, IC. Chương 3 - Thực nghiệm và kết quả: Chương này sẽ mô tả chi tiết về các công cụ, dữ liệu, phương pháp thực nghiệm và toàn bộ quá trình tiến hành thực nghiệm. Kết quả thực nghiệm theo các phương pháp khác nhau cũng sẽ được phân tích, so sánh và đánh giá. -4- Chương I - TỔNG QUAN VỀ PHÂN LỚP DỮ LIỆU 1.1. Giới thiệu về phân lớp dữ liệu Phân lớp là một trong những kỹ thuật phổ biến nhất của học máy và khai phá dữ liệu. Đây là một tiến trình xử lý nhằm xếp các mẫu dữ liệu hay các đối tượng vào một trong các lớp đã được định nghĩa trước. Cách sắp xếp này dựa vào giá trị của các thuộc tính của một mẫu dữ liệu hay đối tượng. Sau khi đã xếp tất cả các đối tượng biết trước vào các lớp tương ứng, lúc này mỗi lớp được đặc trưng bởi tập các thuộc tính của các đối tượng chứa trong lớp đó. Thông thường, các bộ phân lớp có thể học dựa trên các mẫu dữ liệu huấn luyện. Dữ liệu dùng để huấn luyện này bao gồm các thông tin về x và y cho mỗi điểm dữ liệu (data-point), trong đó x là một vector chứa các đặc trưng của mẫu dữ liệu và y biểu thị một nhóm các nhãn phân lớp. Những nhãn phân lớp này chỉ có thể nhận một số hữu hạn các giá trị. Bài toán phân lớp được phát biểu như sau: Cho một tập các mẫu huấn luyện (xi1, xi2, …., xik, yi), i=1,….,N. Nhiệm vụ là phải ước lượng được một bộ phân lớp hay một mô hình xấp xỉ dưới dạng một hàm y = f(x) chưa biết mà có thể phân lớp chính xác cho bất kỳ mẫu nào thuộc tập các mẫu huấn luyện. Có nhiều cách để biểu diễn một mô hình phân lớp và có nhiều thuật toán giải quyết vấn đề này. Các thuật toán phân lớp tiêu biểu bao gồm: mạng nơ-ron, cây quyết định, mạng Bayes, kNN, SVM v.v. -5Tất cả các mô hình phân lớp dựa trên những thuật toán kể trên đều có khả năng phân lớp cho các mẫu dữ liệu mới dựa vào những mẫu tương tự đã được học. Quá trình phân lớp dữ liệu gồm hai bước: Bước 1 - Học (training): Mục đích của bước này là xây dựng một mô hình xác định một tập các lớp dữ liệu. Mô hình này được xây dựng bằng cách phân tích các bộ dữ liệu của một cơ sở dữ liệu, mỗi bộ dữ liệu được xác định bởi giá trị của các thuộc tính. Giả sử mỗi bộ dữ liệu đã thuộc về một trong các lớp đã đựơc định nghĩa trước, điều này được xác định bởi một trong các thuộc tính, gọi là thuộc tính phân lớp. Trong ngữ cảnh của bài toán phân lớp, mỗi bộ dữ liệu được xem như là một mẫu, một ví dụ, hay một đối tượng. Những bộ dữ liệu được phân tích để xây dựng mô hình phân lớp được lấy từ trong tập dữ liệu học hay dữ liệu huấn luyện. Những bộ dữ liệu riêng lẻ tạo thành tập dữ liệu huấn luyện còn gọi là những mẫu huấn luyện (training samples) và được chọn ngẫu nhiên từ một kho các mẫu. Bước này được xem là học có giám sát, ngược lại với học có giám sát là học không có giám sát (unsupervised learing), tiêu biểu là bài toán gom cụm (clustering) trong đó các lớp mà các mẫu huấn luyện thuộc về là không biết trước và số lớp dữ liệu cũng không được biết trước. .Mô hình phân lớp được đưa ra sau khi đã phân tích xong tập dữ liệu huấn luyện thường có dạng là những quy tắc phân lớp, cây quyết định hay các công thức toán học. -6Bước 2 - Phân lớp (classification): Bước này sử dụng mô hình phân lớp đã được xây dựng ở bước 1 để kiểm tra, đánh giá và thực hiện phân lớp. Trong mô hình phân lớp, thuật toán phân lớp giữ vai trò trung tâm, quyết định tới sự thành công của mô hình phân lớp. Do vậy chìa khóa của vấn đề phân lớp dữ liệu là tìm ra được một thuật toán phân lớp nhanh, hiệu quả, có độ chính xác cao và có khả năng mở rộng được. Bước đầu tiên là đánh giá độ chính xác của mô hình phân lớp bằng cách sử dụng một tập các mẫu đã được phân lớp để kiểm tra gọi là bộ thử (test set). Những mẫu này được chọn ngẫu nhiên và độc lập với các mẫu đã được học ở bước 1 gọi là mẫu thử (test sample). Nếu độ chính xác của một mô hình là chấp nhận được, thì mô hình đó có thể được sử dụng để phân lớp những bộ dữ liệu mới hoặc những mẫu dữ liệu mà giá trị nhãn phân lớp là chưa biết. 1.2. Các phương pháp đánh giá độ chính xác của mô hình phân lớp Ước lượng độ chính xác của bộ phân lớp là quan trọng ở chỗ nó cho phép dự đoán được độ chính xác của các kết quả phân lớp những dữ liệu tương lai. Độ chính xác còn giúp so sánh các mô hình phân lớp khác nhau. Hai kỹ thuật đánh giá độ chính xác phổ biến hiện nay là holdout và k-fold cross-validation. Cả hai kỹ thuật này đều dựa trên các phân hoạch ngẫu nhiên tập dữ liệu ban đầu. -7Trong phương pháp holdout, dữ liệu dưa ra được phân chia ngẫu nhiên thành 2 phần: tập dữ liệu huấn luyện và tập dữ liệu kiểm tra. Thông thường 2/3 dữ liệu cấp cho tập dữ liệu huấn luyện, phần còn lại cho tập dữ liệu kiểm tra. Tập huấn luyện dùng để xây dựng bộ phân lớp, sau đó độ chính xác của bộ phân lớp này sẽ được ước lượng dựa trên tập kiểm tra. Trong phương pháp k-fold cross validation, tập dữ liệu ban đầu được chia ngẫu nhiên thành k tập con (fold) có kích thước xấp xỉ nhau S1, S2, …, Sk. Quá trình học và kiểm tra được thực hiện k lần. Tại lần lặp thứ i, Si là tập dữ liệu kiểm tra, các tập còn lại hợp thành tập dữ liệu đào tạo. Độ chính xác là toàn bộ số phân lớp đúng chia cho tổng số mẫu của tập dữ liệu ban đầu. 1.3. Một số vấn đề trong bài toán phân lớp Trong những năm gần đây, có rất nhiều thuật toán cải tiến cho bài toán phân lớp nhưng chưa có một thuật toán nào hay một hệ thống phân lớp nào có khả năng phân lớp chính xác tuyệt đối cho các mẫu hay các đối tượng mới là những mẫu chưa được học. Độ chính xác của các thuật toán phân lớp chỉ đạt được ở một mức độ nhất định đối với tập mẫu thử. Độ chính xác này có thể gần như tuyệt đối hay thấp phụ thuộc vào sự trùng hợp của tập mẫu thử với tập mẫu đã được học. Gốc của vấn đề này là tính quá khớp (overfitting) và quá khái quát (overgeneralization) của các thuật toán phân lớp này. Một số thuật toán đưa ra mô hình phân lớp rất phức tạp để có thể phân lớp -8chính xác cho các mẫu học nhưng không chắc rằng mô hình này có thể phân lớp chính xác cho các mẫu mới, đây chính là sự quá khớp. Rõ hơn, thuật toán mang tính quá khớp dữ liệu nghĩa là mô hình của thuật toán này đưa ra phân lớp rất tốt cho những mẫu dữ liệu đã biết nhưng không thể phân lớp chính xác cho các mẫu dữ liệu mới chưa được biết trước. Sự quá khái quát xuất hiện khi hệ thống sử dụng dữ liệu sẵn có và cố gắng phân tích cho số lượng lớn dữ liệu với các luật quá khái quát. Cả hai vấn đề này có thể là nguyên nhân của độ chính xác phân lớp không tốt. Đây là lĩnh vực nghiên cứu của các thuật toán thống kê, như mạng Neural cây quyết định, Support Vector Machine. 1.4. Một số thuật toán phân lớp truyền thống Bốn thuật toán phân lớp truyền thống sẽ được trình bày trong phần này tương ứng với 4 mục con sau: 1.4.1. Cây quyết định (Decision Trees) 1.4.2. Mạng Bayes (Bayesian network) 1.4.3. Mạng Nơ-ron (Neural Network) 1.4.4. Support Vector Machine (SVM) -9- Chương 2 - PHÂN LỚP CHO DỮ LIỆU CÓ LIÊN KẾT 2.1. Giới thiệu về dữ liệu có liên kết Dữ liệu có liên kết, được gọi là Networked data hay Linked data, là trường hợp đặc biệt của dữ liệu quan hệ khi mà các đối tượng trong đó có các kết nối với nhau. Ví dụ, các trang web được kết nối với nhau bằng các siêu liên kết, tài liệu được kết nối bằng các trích dẫn, tham khảo v.v. Các phương pháp phân lớp cho dữ liệu liên kết về cơ bản dựa trên giả thiết Homophily (nguyên lý đồng đẳng): “các đối tượng liên quan với nhau có xu hướng thuộc cùng một lớp”. Đây là một nguyên lý dựa trên các nghiên cứu và phân tích trên mạng xã hội cho rằng: sự giao tiếp giữa các đối tượng giống nhau xảy ra với tỉ lệ cao hơn so với giao tiếp giữa các đối tượng không giống nhau. Các đối tượng thường tìm kiếm, lựa chọn và kết bạn với những người giống với họ, có thể là về giới tính, về tuổi tác, về địa vị xã hội, về tầng lớp, về đặc điểm hành vi cá nhân, về niềm tin, lý tưởng.v.v. Vì dựa trên giả thiết Homophily nên nguyên tắc chung của các bộ phân lớp quan hệ cho dữ liệu liên kết là tạo ra các ràng buộc, theo đó những đối tượng liên kết với nhau cần có nhãn phân lớp tương tự nhau. Hầu hết các bộ phân lớp kiểu này chỉ quan tâm tới liên kết giữa các nút chứ không quan tới các thuộc tính cục bộ của từng nút. Một trong những vấn đề chính cần lưu ý khi phân lớp dữ liệu có liên kết là việc dự đoán nhãn của một nút có thể có ảnh hưởng đến -10các nút mà nó liên kết tới, và ngược lại. Hơn nữa, các nút không có liên kết trực tiếp lại có thể liên kết gián tiếp thông qua một chuỗi các liên kết. Chính vì vậy, một kỹ thuật đã được công nhận rộng rãi là: các nút nên được ước tính và suy ra cùng một lúc thay vì từng nút một. Kỹ thuật này được gọi là phân lớp tập hợp (collective classification). Bài toán phân lớp tập hợp cho dữ liệu có liên kết được phát biểu như sau: Cho đồ thị G = (V, E, X) trong đó: V là tập nút (đỉnh) gồm n nút tương ứng với n đối tượng; E là tập các cạnh – ei, j E biểu thị một cạnh nối giữa 2 nút vi và vj ; Xi là thuộc tính phân lớp của nút vi có thể nhận giá trị c K con V X. Cho trước các giá trị xi thuộc Xi cho tập V. Khi đó, phân lớp tập hợp là một tiến trình kết hợp một thuật toán phân lớp liên kết với một phép suy luận tập hợp để suy U K luận đồng thời các giá trị xi thuộc Xi cho các đỉnh còn lại, V =V- V . Như vậy, phân lớp tập hợp cho dữ liệu liên kết được thực hiện nhờ hai thủ tục:  Thủ tục thứ nhất là phân lớp liên kết (relational classification), theo đó nhãn phân lớp được xác định dựa trên các hàng xóm thông qua một thuật toán phân lớp liên kết;  Thủ tục thứ hai là suy luận tập hợp (collective inference). Bản chất của bước này là xác định nhãn phân lớp đồng thời cho các nút trên mạng. 2.2. Các thuật toán phân lớp liên kết -11Bốn thuật toán phân lớp liên kết sẽ được trình bày trong phần này tương ứng với 4 mục con sau: 2.2.1. Thuật toán phân lớp liên kết Weighted-Vote Relational Neighbor (wvRN) 2.2.2. Thuật toán phân lớp liên kết Class-Distribution Relational Neighbor (CDRN) 2.2.3. Thuật toán phân lớp liên kết Network-Only Bayes Classifier (NBC) 2.2.4. Thuật toán phân lớp liên kết Network-Only LinkBased Classifier (NLB) 2.3. Phân lớp tập hợp và các phương thức suy luận tập hợp Để phân lớp dữ liệu dạng liên kết người ta có thể chỉ cần sử dụng một thuật toán phân lớp liên kết. Tuy nhiên như đã trình bày ở trên, phương pháp phân lớp tập hợp kết hợp một thuật toán phân lớp liên kết với một phương thức suy luận tập hợp ngày càng được quan tâm và áp dụng. Phương thức suy luận tập hợp giúp suy luận và ước tính đồng thời nhãn phân lớp cho tất cả các nút cần phân lớp. Phương pháp này đã được công nhận có khả năng nâng cao độ chính xác so với phương pháp ước tính nhãn phân lớp cho từng nút một. Tùy thuộc vào từng ứng dụng, mục tiêu sẽ là suy ra các nhãn với xác suất kết hợp hay xác suất biên là tối đa đối với mỗi nút. Ngoài ra, nếu cần ước tính xác suất nhãn phân lớp, phương thức suy luận tập -12K hợp sẽ ước tính phân phối xác suất biên P( X i  c G ,) cho mỗi Xi U x và c X với  là các giá trị được khởi tạo trước dựa trên các kết quả phân lớp của bộ phân lớp truyền thống (local classifier) sử dụng các đặc trưng không phải dạng liên kết. Ba phương thức suy luận tập hợp sẽ được trình bày trong phần này tương ứng với 3 mục con sau: 2.3.1. Phương thức suy luận tập hợp Gibbs Sampling (GS) 2.3.2. Phương thức suy luận tập hợp Relaxation Labeling (RL) 2.3.3. Phương thức suy luận tập hợp Iteractive Classification (IC) 2.4. Phân lớp tập hợp kết hợp bộ phân lớp liên kết và bộ phân lớp truyền thống Các bộ phân lớp liên kết chỉ quan tâm tới cấu trúc liên kết của một nút. Nếu tất cả các nút trong tập kiểm tra được kết nối tới ít nhất một nút trong tập huấn luyện thì không có vấn đề gì, nhưng trên thực tế có rất nhiều dữ liệu không thỏa mãn điều kiện này. Khi đó, bộ phân lớp liên kết sẽ không thể phân lớp cho những nút không có nút hàng xóm trong tập huấn luyện. Để bù đắp những thiếu hụt trên, bộ phân lớp tập hợp có thể kết hợp một bộ phân lớp liên kết với một bộ phân lớp truyền thống nhằm -13cố gắng tăng độ chính xác khi phân lớp. Với cách sử dụng bộ phân lớp truyền thống trong bước lặp đầu tiên (t=1) của quá trình suy luận tập hợp, bộ phân lớp tập hợp bảo đảm rằng tất cả các nút sẽ có xác suất phân lớp ban đầu. Bộ suy luận tập hợp sau đó sẽ sử dụng bộ phân lớp liên kết và dựa vào các xác suất ban đầu đó để tiếp tục phân lớp. 2.5. Một số phương pháp phân lớp cho dữ liệu dạng liên kết khác Bên cạnh các phương pháp phân loại quan hệ cho dữ liệu liên kết nêu trên, một hướng tiếp cận được sử dụng rộng rãi khác là phương pháp học bán giám sát (semi-supervised learning) dựa trên đồ thị. Trong số những phương pháp kiểu này phải kể tới: phương pháp Mincut của Blum and Chawla (2001); phương pháp định danh nút (Node Identifiers) của Perlich và Provost (2006); phương pháp trường ngẫu nhiên Gauss (Gaussian Random Fields) của Zhu và cộng sự (2003) và phương pháp nhất quán cục bộ và địa phương (Local and Global Consistency) của Zhu và các cộng sự (2004). -14- Chương 3 - THỰC NGHIỆM VÀ KẾT QUẢ 3.1. Dữ liệu Dữ liệu thực nghiệm là bộ dữ liệu được sử dụng rộng rãi WebKB (http://www.cs.cmu.edu/~WebKB/). Bộ này bao gồm hơn 8000 trang web lấy từ 4 website bộ môn Khoa học máy tính của các trường đại học: Cornell, Texas, Washington và Wisconsin. Mỗi trang web được lưu vào một tệp tin dạng .html với tên chính là URL thực của trang web đó. Người ta đã thực hiện việc phân lớp thủ công cho từng trang web vào 1 trong 7 lớp: course, department, faculty, project, staff, student, other bằng cách chia vào các thư mục có tên tương ứng. Để tương thích và tiện so sánh với các kết quả nghiên cứu trước đây, chúng tôi loại bỏ các trang web trong lớp other và thực hiện việc phân chia dữ liệu vào 6 lớp còn lại. 3.2. Công cụ Trong quá trình thực nghiệm học và phân lớp, chúng tôi sử dụng 2 bộ công cụ mã nguồn mở: Network Learning Toolkit: Netkit-SRL (http://sourceforge.net/projects/netkit-srl/). Đây là một trong số rất ít công cụ mã nguồn mở có khả năng thực hiện các thuật toán phân lớp cho dữ liệu liên kết như: wvRN, cdRN, NBC, nLB. Mỗi thuật toán phân lớp lại có thể kết hợp với một phương thức suy luận tập hợp như: GS, RL, IC để tạo thành một bộ phân lớp tập hợp. Ngoài ra, Netkit-SRL còn có khả năng liên kết với với công cụ khai phá dữ liệu WEKA. -15Trong trường hợp thực hiện phân lớp tập hợp kết hợp cả bộ phân lớp liên kết lẫn bộ phân lớp cục bộ, Netkit-SRL sẽ nhận kết quả phân lớp cục bộ từ WEKA để khởi tạo xác suất phân lớp ban đầu cho quá trình phân lớp tập hợp. Waikato Environment for Knowledge Analysis: WEKA (http://sourceforge.net/projects/weka/). Đây là công cụ rất tiện dụng trong xây dựng các mô hình khai phá dữ liệu. WEKA triển khai hầu hết các kỹ thuật khai phá dữ liệu như Classification, Clustering, Association Rule,.. Trong mỗi kỹ thuật, WEKA triển khai rất nhiều thuật toán cho phép lựa chọn thuật toán phù hợp với yêu cầu và dữ liệu trong việc khai phá dữ liệu. Ngoài ra, trong quá trình tiền xử lý dữ liệu chúng tôi đã xây dựng và tập hợp các công cụ như liệt kê trong bảng dưới đây. Bảng 3.1. Các thư viện và công cụ hỗ trợ STT Tên công cụ Mô tả 1 GetLink.java Tìm liên kết giữa các trang web trong bộ dữ liệu, tính trọng số và đưa về dạng file .rn 2 GetCocite.java Tìm liên kết dạng Cocite giữa các trang web trong bộ dữ liệu, tính trọng số -16và đưa về dạng .rn 3 WordToVector.java Chuyển dữ liệu Content của các trang web về dạng vector phù hợp với định dạng .arff của WEKA 4 Stopwords.java Loại bỏ các từ dừng 5 LovinsStemmerWrapper.java Rút gọn các từ về dạng PorterStemmerWrapper.java nguyên gốc pruneByFrequency.java Lược bỏ những từ xuất 6 hiện quá nhiều hoặc quá ít 7 BinaryOccurrences.java Tính tần suất xuất hiện TFIDF.java của các từ TermFrequency.java TermOccurrences.java 3.3. Phương pháp thực nghiệm Chúng tôi chia dữ liệu gốc thành 2 tập đặc trưng gọi là Content và Link-Cocite. Tập Content chứa thông tin về các từ xuất hiện trong từng trang web. Tập Link-Cocite chứa thông tin về các liên kết giữa các trang web trong một website. -17Chúng tôi sử dụng công cụ WEKA với bộ phân lớp Naïve Bayes để tiến hành học và phân lớp trên dữ liệu Content. Bộ công cụ Netkit-SRL với bộ phân lớp wvRN sẽ được dùng để học và phân lớp trên dữ liệu Link. Phương thức suy luận tập hợp RL sẽ được sử dụng để kết hợp tạo thành các bộ phân lớp tập hợp. Trên thực tế, chúng tôi đã thử nghiệm trên cả 4 thuật toán phân lớp liên kết và 3 phương thức suy luận tập hợp được trình bày ở chương 2. Tuy nhiên, nếu kết hợp cả bộ phân lớp cục bộ, bộ phân lớp liên kết và bộ suy luận tập hợp thì sẽ thu được rất nhiều khả năng và kết quá. Sau khi lựa chọn kỹ lưỡng, chúng tôi quyết định sử dụng bộ phân lớp cục bộ Naïve Bayes, bộ phân lớp liên kết wvRN và phương thức suy luận tập hợp RL như đã nói ở trên. Đây là các bộ phân lớp và phương thức suy luận tập hợp được đánh giá là rất phù hợp với bài toán phân loại trang web. Kết quả khi áp dụng những lựa chọn trên cũng phù hợp với những kết quả thử nghiệm khác mà chúng tôi đã được kiểm chứng. Sau khi tiến hành thử nghiệm, chúng tôi sẽ đánh giá và so sánh kết quả phân lớp giữa 4 bộ phân lớp sau: bộ phân lớp cục bộ Naïve Bayes; bộ phân lớp liên kết wvRN; bộ phân lớp tập hợp kết hợp giữa wvRN và RL; bộ phân lớp tập hợp kết hợp giữa Naïve Bayes – wvRN và RL. 3.4. Quá trình và kết quả thực nghiệm 3.4.1. Xây dựng và trích chọn các đặc trưng -18Đầu tiên, chúng tôi tiến hành trích chọn đặc trưng của các trang web và chia thành 2 tập chứa các đặc trưng riêng biệt. Đặc trưng thứ nhất của trang web chính là các từ xuất hiện trong trang web đó. Mỗi trang web sẽ được biểu diễn dưới dạng vector theo mô hình không gian vector (Vector Space Model). Mỗi thành phần của vector là một từ khóa riêng biệt xuất hiện trong website và được gán một giá trị gọi là hàm f chỉ mật độ xuất hiện của từ khóa đó. Chúng tôi gọi tập Content là tập chứa các vector này. Một đặc trưng nữa của trang web là các siêu liên kết có trong mỗi trang. Chúng tôi xây dựng một tập tên là Link chứa các thông tin bao gồm: “x”, “y” và “Trọng số liên kết giữa x và y”; trong đó x, y là 2 trang web có liên kết với nhau và cùng nằm trong một website. Thông tin siêu liên kết lại được chia làm 2 loại là Direct Link và Cocite. Direct Link là kiểu liên kết trực tiếp giữa 2 trang web (x có chứa siêu liên kết tới y). Khi đó, trọng số liên kết dạng Direct Link giữa 2 trang x và y là tổng số lần xuất hiệu siêu liên kết từ trang x tới trang y. Cocite là một kiểu liên kết khác. Hai trang x và y gọi là liên kết dạng Cocite (theo z) khi x liên kết trực tiếp với z và y cũng liên kết trực tiếp tới z. Để tính trọng số liên kết kiểu Cocite giữa x và y, ta lấy tổng số lần xuất hiện siêu liên kết từ trang x tới trang z rồi nhân với tổng số lần xuất hiện siêu liên kết từ trang y tới trang z. 3.4.2. Tiền xử lý dữ liệu
- Xem thêm -

Tài liệu liên quan