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 -