TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Khoa Công nghệ Thông tin
BÁO CÁO NIÊN LUẬN
Tên đề tài:
GIẢI PHÁP GOM NHÓM ĐẶC TRƯNG ĐỒNG NGHĨA
TIẾNG VIỆT TRONG ĐÁNH GIÁ SẢN PHẨM
DỰA TRÊN PHÂN LỚP BÁN GIÁM SÁT SVM-KNN VÀ
PHÂN CỤM HAC
Sinh viên thực hiện:
Phạm Huyền Trang – K52CHTTT
Giáo viên hướng dẫn:
PGS.TS Hà Quang Thụy
Ths Trần Mai Vũ
Hà Nội, 05/2011
1
MỤC LỤC
I. Đặt vấn đề 3
II. Phát biểu bài toán 4
III. Tóm tắt cơ sở lý thuyết 4
III.1. Một số nội dung cơ bản về phân lớp bán giám sát 4
III.1.1. Học bán giám sát 4
III.1.2. Phân lớp bán giám sát 5
III.1.3. Các phương pháp phân lớp bán giám sát điển hình 5
III.2. Phương pháp luận SVM-KNN dựa trên học bán giám sát 6
III.2.1. Thuật toán máy vector hỗ trợ (SVM) 6
III.2.2. Thuật toán K người láng giềng gần nhất (kNN) 8
III.2.3. Phương pháp phân lớp bán giám sát SVM-kNN 9
IV. Phương pháp đề xuất 11
IV.1. Phương pháp đề xuất 11
IV.2. Mô hình 12
IV.3. Dự kiến kết quả đạt được 13

Trong [16], chúng tôi đề xuất một mô hình khai phá quan điểm dựa trên đặc trưng
đối với các đánh giá sản phẩm điện thoại bằng tiếng Việt. Công trình nói trên đã đề cập
tới một giải pháp đơn giản để nhóm các đặc trưng “đồng nghĩa” – đó là sử dụng một bộ
từ điển đặc trưng đồng nghĩa xây dựng bằng tay để giải quyết bài toán. Từ điển này chứa
các đặc trưng đồng nghĩa trên miền sản phẩm “điện thoại”. Tuy nhiên, giải pháp này còn
3
gặp nhiều điểm hạn chế như khi chuyển sang miền sản phẩm mới hoặc khi xuất hiện một
từ mới không có trong từ điển, thì giải pháp vẫn chưa giải quyết được.
Trong công trình này chúng tôi đề xuất một giải pháp gom nhóm đặc trưng đồng
nghĩa cũng dựa trên phân lớp bán giám sát. Tuy nhiên, so với [17], mô hình của chúng tôi
có các điểm khác biệt: Thứ nhất, chúng tôi không tạo một tập huấn luyện bằng tay để tạo
ra một bộ phân lớp như [17], mà thay vào đó, tập huấn luyện này được tạo một cách tự
động nhờ áp dụng thuật toán phân cụm HAC. Thứ hai, chúng tôi không sử dụng từ điển
đồng nghĩa, mà thay vào đó là một từ điển Việt-Việt cùng các đánh giá của khách hàng
để tạo tập huấn luyện. Thứ ba, phương pháp phân lớp bán giám sát mà chúng tôi sử dụng
là SVM-kNN, trong khi phương pháp được sử dụng trong [17] là EM.
II. Phát biểu bài toán
Nếu gọi nhóm đặc trưng là tên của một đặc trưng được đưa ra bởi người dùng, và
thể hiện đặc trưng của một đặc trưng là một từ hoặc cụm từ xuất hiện thực sự trong các
đánh giá để thể hiện đặc trưng đó, thì bài toán được phát biểu như sau:
Đầu vào:
- Tập các thể hiện đặc trưng
- Tập các đánh giá của khách hàng S
-
Ngưỡng α > 0
Đầu ra:
- Tập các thể hiện đặc trưng cùng với nhóm đặc trưng tương ứng
Phát biểu bài toán: Coi mỗi thể hiện đặc trưng là một mẫu dữ liệu, mỗi nhóm đặc
trưng là một lớp. Cần xây dựng một bộ phân lớp SVM-kNN để phân lớp các mẫu dữ liệu
này vào các lớp khác nhau, thỏa mãn mỗi mẫu chỉ thuộc về một lớp nhưng một lớp có thể

; và u ví dụ chưa gán nhãn . Trong phân lớp bán
giám sát, số lượng dữ liệu chưa gán nhãn là lớn hơn nhiều so với dữ liệu đã gán nhãn,
tức là u >> l. Mục tiêu của phân lớp bán giám sát là huấn luyện một bộ phân lớp f từ l và
u; trong khi đó, phân lớp giám sát lại tạo ra một bộ phân lớp chỉ từ những dữ liệu đã gãn
nhãn. Trong quá trình học, việc phân lớp bán giám sát sẽ tận dụng được những thông tin
phong phú của dữ liệu chưa gãn nhãn, mà chỉ yêu cầu một số lượng rất nhỏ các dữ liệu đã
gãn nhãn.
III.1.3. Các phương pháp phân lớp bán giám sát điển hình
Các thuật toán bán giám sát đã và đang được phát triển một cách nhanh chóng
trong những năm gần đây. Hiện nay, có rất nhiều phương pháp học bán giám sát như:
self-learning và self-labeling – là hai trong số những phương pháp phân lớp bán giám sát
sớm nhất, chúng vẫn được sử dụng rộng rãi trong lĩnh vực xử lý ngôn ngữ tự nhiên; hoặc
phương pháp SSSVM (SVM bán giám sát) với ý tưởng tìm một biên quyết định trong các
5
vùng mật độ thấp; hay phương pháp dựa trên đồ thị - phương pháp này xây dựng một đồ
thị có trọng số trên những ví dụ đã gán nhãn và ví dụ chưa gán nhãn và giả thiết rằng giữa
hai ví dụ có một kết nối mạnh thì có khuynh hướng có cùng nhãn và giải quyết bài toán
tối ưu hóa; một phương pháp phân lớp bán giám sát khác là sử dụng mô hình sinh, hỗn
hợp phân bố Gaussian trong thuật toán EM [13].
Hiệu quả của những thuật toán phân lớp bán giám sát phụ thuộc vào chất lượng
của các ví dụ gán nhãn được thêm vào ở mỗi vòng lặp và được đánh giá dựa trên hai tiêu
chí [3]:
- Các ví dụ được thêm vào phải được gán nhãn một cách chính xác.
- Các ví dụ được thêm vào phải mang lại thông tin hữu ích cho bộ phân lớp (
hoặc dữ liệu huấn luyện).
III.2. Phương pháp luận SVM-KNN dựa trên học bán giám sát
Niên luận này tập trung nghiên cứu việc nhóm các đặc trưng đồng nghĩa dựa trên
phân lớp bán giám sát SVM-kNN. Phương pháp phân lớp bán giám sát SVM-kNN tỏ ra
rất hiệu quả trong bài toán phân lớp nếu chọn các tham số phù hợp. Phương pháp này có
độ chính xác cao hơn so với thuật toán phân lớp SVM bởi vì nó thực hiện việc cải tiến độ

năng lỗi xảy ra là tối thiểu.
a.Trường hợp khả tách tuyến tính
Trong trường hợp này, bộ phân lớp SVM là mặt siêu phẳng phân tách các mẫu
dương khỏi các mẫu âm với lề cực đại, được xác định bằng khoảng cách giữa các mẫu
dương và các mẫu âm gần mặt siêu phẳng lề tối ưu nhất (hình 1). Các mặt siêu phẳng
trong không gian đối tượng có phương trình là w
T
x + b = 0, trong đó w là vector pháp
6
tuyến, b là tham số mô hình phân lớp.
Hình 1: Mặt siêu phẳng tách các mẫu dương khỏi các mẫu âm
Bộ phân lớp SVM được định nghĩa như sau: f(x) = sign(w
T
x + b) (1.1), trong đó:
sign(z) = +1 nếu z ≥ 0 và sign(z) = −1 nếu z < 0. Nếu f(x) = +1 thì x thuộc về lớp
dương, và ngược lại, nếu f(x) = −1 thì x thuộc về lớp âm. Mục tiêu của phương pháp
SVM là ước lượng w và b để cực đại hóa lề giữa các lớp dữ liệu dương và âm. Các giá trị
khác nhau của lề cho ta các họ mặt siêu phẳng khác nhau, và lề càng lớn thì lỗi tổng quát
hóa của bộ phân lớp càng giảm.
Hai mặt siêu phẳng có phương trình là w
T
x + b = ±1 được gọi là các mặt siêu
phẳng hỗ trợ (các đường nét đứt trên hình 1). Để xây dựng một mặt siêu phẳng lề tối ưu
thì:
- Vector w sẽ được tính:
w = (1.2)
- Tham số b được xác định sử dụng điều kiện Karush–Kuhn–Tucker(KKT)
như sau:
α
i

, x
j
) = Φ(x
i
)
T
. Φ(x
j
) (1.6)
Nếu chọn một hàm nhân phù hợp, ta có thể xây dựng được nhiều bộ phân loại
khác nhau. Có một số hàm nhân cơ bản sau đây:
- Hàm nhân đa thức:
k(x
i
, x
j
) =
- Hàm vòng RBF (Radial Basic Function) :
- Hàm chữ S Sigmoid:
k(x
i
, x
j
) =
Hiện nay có khá nhiều mã nguồn để hỗ trợ cho việc thực thi thuật toán SVM
đã được mô tả trên, trong đó LibSVM [8] là một bộ thư viện được viết bằng ngôn ngữ
C++ và Java cho phép phân lớp vector hỗ trợ, hồi qui và ước lượng phân phối. Ngoài ra,
LibSVM còn có rất nhiều tính năng hữu ích như: phân lớp đa lớp, kiểm chức chéo cho
việc chọn mô hình, ước lượng xác suất, cho phép người dùng chọn hàm nhân,… Chính
vì vậy, chúng tôi chọn LibSVM làm công cụ cho việc thực thi thuật toán SVM trong bài

định đúng nếu có ít dữ liệu đã được gán nhãn.
Trong suốt quá trình quyết định của phương pháp KNN chỉ liên quan đến số lượng
nhỏ các hàng xóm gần nhất, do đó việc áp dụng phương pháp này có thể tránh được vấn
đề về sự cân bằng giữa các ví dụ. Mặt khác, KNN chủ yếu phụ thuộc vào số lượng giới
hạn các hàng xóm gần nhất không phải xung quanh một biên quyết định, vì vậy, nó phù
hợp với việc phân lớp trường hợp tập các ví dụ có biên giao nhau và trường hợp có sự
9
chồng chéo giữa các ví dụ.
Từ những ưu và nhược điểm của hai thuật toán SVM và kNN, H. Zhang và cộng
sự, 2006 [11] đã đề xuất một phương pháp kết hợp hai thuật toán trên. Công trình là một
trong những công trình điển hình sớm nhất về phương pháp SVM-kNN. Ý tưởng cơ bản
của phương pháp này là tìm các hàng xóm gần với mẫy truy vấn và huấn luyện một máy
vector hỗ trợ cục bộ. Máy vector hỗ trợ cục bộ này duy trì hàm khoảng cách trên tập các
hàng xóm. H. Zhuang và cộng sự đã chứng minh được rằng phương pháp này có thể áp
dụng với tập dữ liệu lớn và đa lớp với kết quả tốt hơn so với thuật toán SVM hay kNN.
Sau đó, Kunlun Li và cộng sự, 2010 [13] đã đề xuất một phương pháp phân lớp
SVM-KNN dựa trên học bán giám sát nhằm cải tiến thuật toán SVM bằng cách tận dụng
những ưu điểm của thuật toán kNN đã nêu ra ở trên. Phương pháp này hiệu quả hơn so
với phương pháp của H.Zhuang và cộng sự [11]. Do đó, trong khóa luận này, chúng tôi
tập trung nghiên cứu phương pháp phân lớp bán giám sát SVM-kNN do K.Li và cộng sự
đề xuất năm 2010.
Tư tưởng bán giám sát trong SVM-kNN:
Tư tưởng chính của phương pháp này dựa trên lý thuyết học bán giám sát, sử
dụng cả dữ liệu đã gán nhãn và dữ liệu chưa gán nhãn cho quá trình phân lớp. Cụ thể là
phương pháp sử dụng số ít các dữ liệu đã gán nhãn để huấn luyện một bộ phân lớp SVM
và sử dụng bộ phân lớp SVM này để dự đoán dữ liệu chưa được gán nhãn. Từ những
dữ liệu đã được gãn nhãn trong tập huấn luyện và những dữ liệu vừa được dự đoán bởi
SVM, chọn ra những vector biên, và sử dụng những vector biên này để cải tiến bộ phân
lớp SVM đó bằng cách sử dụng kNN. Việc sử dụng kNN để phân lớp không chỉ làm
giàu số lượng tập huấn luyện, mà còn làm cải tiến được chất lượng của những ví dụ huấn

cụm nhỏ hơn ngưỡng này [3]. Do đó, những mẫu đã được đưa vào cụm có chất lượng tốt.
Nhờ vậy mà phân lớp SVM-kNN cũng sẽ có được kết quả cao.
Tư tưởng chính của giải pháp đề xuất như sau:
Các thể hiện đặc trưng sẽ được đưa vào các nhóm đặc trưng - cụm khác nhau, sao
cho một cụm có thể có nhiều thể hiện đặc trưng nhưng một thể hiện đặc trưng chỉ có
thể thuộc vào một nhóm đặc trưng. Ví dụ, cụm “kiểu dáng” có thể có nhiều thể hiện đặc
trưng như: “mẫu mã”, “thiết kế”, “kiểu cách”, “kiểu dáng”,… ; nhưng một thể hiện đặc
trưng “mẫu mã” chỉ thuộc vào một cụm “kiểu dáng”. Vì hiện nay, tại Việt Nam chưa có
bộ từ điển đồng nghĩa, do đó độ tương tự giữa 2 thể hiện đặc trưng dùng trong phân cụm
11
HAC được tính dựa trên độ tương tự về ngữ nghĩa và ngữ cảnh của 2 thể hiện đặc trưng
đó. Ngữ nghĩa của mỗi thể hiện đặc trưng được thể hiện thông qua bộ từ điển Việt-Việt.
Ngữ cảnh của mỗi thể hiện đặc trưng được xác định bằng cách xem xét các từ xuất hiện
xung quanh thể hiện đặc trưng trong các đánh giá của khách hàng. Vì kết quả phân cụm
có thể có sai sót, nên chúng tôi đưa ra một ngưỡng cho trước. Ngưỡng này được so sánh
với độ đo tương đồng giữa 2 thể hiện đặc trưng nhằm tạo ra một tập huấn luyện có độ
chính xác cao. Sau khi áp dụng thuật toán HAC, thu được các cụm chứa các thể hiện đặc
trưng. Với cụm có nhiều hơn một thể hiện đặc trưng, nếu coi các cụm là các nhãn lớp và
các thể hiện đặc trưng là các mẫu, thì các mẫu này được xem là những mẫu đã được gán
nhãn. Với cụm chỉ có 1 thể hiện đặc trưng thì coi các mẫu này là những mẫu chưa gán
nhãn. Sử dụng những mẫu gán nhãn và chưa gán nhãn cùng với ngữ cảnh của những mẫu
này để áp dụng phân lớp bán giám sát SVM-kNN
IV.2. Mô hình
Các công việc được thực hiện như sau:
Pha 1: Biểu diễn vector thể hiện đặc trưng
ü
Xác định ngữ nghĩa của các thể hiện đặc trưng
ü
Xác định ngữ cảnh của các thể hiện đặc trưng
ü

phân lớp văn bản. Khóa luận tốt nghiệp, Trường ĐHCN-ĐHQGHN.
2. Nguyễn Thị Hương Thảo (2006). Phân lớp phân cấp Taxonomy văn bản web và
ứng dụng, Khóa luận tốt nghiệp, Trường ĐHCN-ĐHQGHN.
3. Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn Thu
Trang, Nguyễn Cẩm Tú. Giáo trình khai phá dữ liệu Web, Nhà xuất bản giáo dục
Việt Nam, 2009, tr. 124-125
4. Andrew Brian Goldberg. New directions in semi-supervised learning.Doctor of
Philosophy, University of Wisconsin-Madison. 2010.
5. Bing Liu. Sentiment Analysis and Subjectivity. Invited Chapter for the Handbook
of Natural Language Processing, Second Edition. March, 2010.
6. Blum, A., and Mitchell, T. Combining labeled and unlabeled data with co-
training. In COLT, 92–100, 1998.
7. Carenini G., R. Ng and E. Zwart 2005. Extracting knowledge from evaluative text.
Proceedings of International Conference on Knowledge Capture.
8. C. Chang and C J. Lin (2010). LIBSVM: a library for support vector machines,
Technical Report, Initial version: 2001 Last updated: November 16, 2010, http://
www.csie.ntu.edu.tw/~cjlin/papers/libsvm.pdf, LIBSVM software library version
3.0 released on September 13, 2010, />9. Corinna Cortes, Vladimir Vapnik (1995). Support-Vector Networks, Machine
Learning, 20(3): 273-297.
10.Guo H., H. Zhu, Z. Guo, X. Zhang and Z. Su 2009. Product feature categorization
with multilevel latent semantic association. Proc. of CIKM.
11.Hao Zhang, Alexander C. Berg, Michael Maire, Jitendra Malik (2006). SVM-
KNN: Discriminative Nearest Neighbor Classification for Visual Category
Recognitionm, CVPR (2) 2006: 2126-2136.
12.T. Joachims (1997). Text categorization with Support Vector Machines: Learning
with many relevant features, Technical Report 23, LS VIII, University of
Dortmund, 1997, />13.Kunlun Li, Xuerong Luo and Ming Jin. Semi-supervised Learning for SVM-KNN.
Journal of computers, vol.5, No. 5. May 2010.
14.D. Marcu and A. Popescu. Extracting product features and opinions from reviews.
CICLing 2005: 88-99.

…………………………………………………………………………………………
…………………………………………………………………………………………
……………………
…………………………………………………………………
………………………
…………………………………………………………………
………………………
Điểm số: ……… Điểm chữ: ………
Hà Nội, ngày tháng năm 20…
Giáo viên đánh giá
(Ký và ghi rõ họ tên)
Xác nhận của Khoa CNTT
Chủ nhiệm Khoa
17