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:
………………………………………………………………
………………………………………………………………

kỹ

thuật

khai

phá

dữ

liệu

đã

được
nghiên

cứu

và

sử

dụng

rộng

rãi.

Đây

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.



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

sự

[3].

Họ

đề

xuất

một

mô

hình

xác

suất

cho

phân

loại


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


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



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


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



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ụ,



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Ữ

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


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.
-5-

Tấ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

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


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ó


Bướ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

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


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.
-7-

Trong 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

đó

độ

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


1.3.

Một

số

vấn

đề

trong

bài

toán

phân

lớpTrong 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



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
-8-

chí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

thống

kê,

như

mạng

Neural

cây

quyết

định,

Support

Vector
Machine.

1.4.

Một

số


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)



CHO

DỮ

LIỆU

CÓ

LIÊNKẾT

2.1.

Giới

thiệu

về

dữ

liệu

có

liên



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



đố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
-10-

cá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ỹ



với

n

đối

tượng;

E

là

tập

các

cạnh

–

e
i, j


E

biểu

thị


phép

suy

luận

tập

hợp

để

suy
luận đồng thời các giá trị xi thuộc Xi cho các đỉnh còn lại, V
U
=V- V
K
.

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

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
-11-

Bốn

thuật

toá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


Thuật

toán

phân

lớp

liên

kết

Network-Only

Link-

Based

Classifier

(NLB)2.3.

Phân

lớp

tập


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


độ

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
-12-

hợp

sẽ

ước

tính

phân

phối

xác


x
U

và

c



X

với



là

các

giá

trị

được

khởi

tạo


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



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


cố 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ẽ


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



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


Fields)

của

Zhu

và
cộng

sự

(2003)

và

phương

pháp

nhất

quán

cục

bộ

và


liệu

thực

nghiệm

là

bộ

dữ

liệu

được

sử

dụng

rộng

rãi
WebKB

( />
Bộ

này


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

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,



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.
B
ả
ng

3.1.

Các

thư


for

Knowledge

Analysis:
WEKA

( />
Đây là

công
cụ

rất

tiện

dụng

trong

xây

dựng

các

mô

hình


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ý


giữa các trang web trong
bộ dữ liệu, tính trọng số
-16- 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.

và

đưa

về

dạng

.rn
3 WordToVector.java Chuyển dữ liệu Content


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 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

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



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



dữ

liệu
-19-

Trước khi tiến hành phân lớp, dữ liệu cần được xử lý và đưa về
định dạng mà các công cụ phân lớp có thể chấp nhận. Trong bài toán
này,

chúng

tôi

phải

xử

lý

2

dạng

dữ

liệu

hoàn



hậu

tố,

rút

gọn

các

từ

về

từ

nguyên
gốc

(chúng

tôi

đã

thử

nghiệm


được:

WordList

của

trường
Cornell

có

2133

từ,

trường

Texas

có

1756

từ,

Trường
Washington

có



web (đây

là

mô

hình

Boolean

–
chúng tôi đã thử nghiệm các mô hình Tần suất như TF,
TF-IDF nhưng cho kết quả không tốt bằng) ;
o Đưa

dữ

liệu

vector

của

tất

cả

các


của 4 trường Đại học là: CornellContent.arff,
TexasContent.arff, WashingtonContent.arff và
WisconsinContent.arff.


Với dữ liệu dạng Link, ta cần tìm ra liên kết giữa các trang web,
tính trọng số cho chúng và lưu vào tệp tin .rn có định dạng đúng
với quy định của Netkit-SRL.Các bước tiến hành như sau :
o Tìm các siêu liên kết xuất hiện trong từng trang web và
kiểm tra xem nó có chỉ tới một trang web khác trong bộ
dữ liệu gốc không ;
o Nếu tìm thấy hai trang web có liên kết (dạng Direct link)
với nhau, tính trọng số bằng cách đếm số lần xuất hiện
liên kết ;
o Đưa tất cả các liên kết cùng trọng số tìm thấy trong mỗi
website

vào

một

tệp

tin rn,

ta

được

4


các

liên

kết

và

trọng

số
dạng

Cocite

và

đưa

vào

4

tệp

tin

CornellCocite.rn,
TexasCocite.rn, WashingtonCocite.rn,


xử

lý

dữ

liệu

chúng

tôi

phát

hiện

ra

việc
dùng dữ liệu dạng Direct link trong bài toán phân loại trang web sẽ
cho

kết

quả

kém

chính


chúng

tôi

thử

nghiệm

học

và

phân

lớp

tập

hợp

kết
hợp

bộ

phân

lớp



0.5

Naïve Bayes (Content)
wvRN (Cocite)
wvRN.RL (Cocite)
Naïve Bayes + wvRN.RL
(Content+Cocite)

Cornell Texas Washington Wisconsin Trung bình

Hình

3.1.

Biểu

đồ

so

sánh

độ

chính

xác

của

trong

4

phương
pháp phân lớp thì

độ chính xác của phương pháp phân lớp tập hợp
kết hợp Naïve Bayes – wvRN –RL là cao hơn cả. Trong phần lớn các
trường hợp, độ chính xác của phương pháp này là cao nhất. Không
có trường hợp nào phương pháp này cho kết quả kém nhất. Ngoài ra,
biểu đồ này còn cho ta thấy rằng phương pháp phân lớp tập hợp đã
giúp nâng độ chính xác so 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. Độ chính xác trung bình trên dữ liệu của
cả 4 trường đại học đều thể hiện điều này.

0.7
0.65
0.6
Dùng

riêng

lẻ
0.55

0.5
0.45
0.4
0.35

xác

áp

dụng

3

thuật

toán

wvRN,

cdRN

và

nLB

-23-

Hình 3.2 là kết quả so sánh độ chính xác của 4 thuật toán phân
lớp liên kết đã được trình bày trong chương 2. Mỗi thuật toán này đi
cùng với 3 phương pháp thực hiện là: thực hiện đơn lẻ; kết hợp với
phương thức suy luận tập hợp RL; kết hợp với thuật toán phân lợp
cục bộ Naïve Bayes và phương thức suy luận tập hợp RL. Độ chính
xác trong hình là độ chính xác trung bình trên dữ liệu của cả 4 trường
đại



chính

xác

cao

nhất.

Hiệu

quả

phân

lớp

của

cả

4
thuật toán phân lớp liên kết đều được nâng cao khi gắn với phương
thức suy luận tập hợp (RL) và được nâng cao một lần nữa khi tiếp
tục kết hợp với bộ phân lớp cục bộ (Naïve Bayes).