ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Phan Thị Thơm
LÀM GIÀU VÀ LỰA CHỌN ĐẶC TRƯNG
TRONG PHÂN LỚP ĐA NHÃN VÀ ÁP DỤNG
TRONG QUẢN LÝ DANH TIẾNG KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành:Công nghệ thông tin
HÀ NỘI - 2012
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Thom Phan Thi FEATURES ENRICHING AND SELECTING
IN MULTI-LABEL CLASSIFICATION
IN REPUTATION MANAGEMENT
Major: Information of Technology Supervisor:Assoc. Prof. Thuy Ha Quang
Co-Supervisor:MSC. Vu Tran Mai HA NOI, 2012 Lời cảm ơn
Trước tiên, em xin bày tỏ lòng biết ơn chân thành và sâu sắc tới Thầy giáo,
PGS.TS Hà Quang Thụy và Thạc sỹ Trần Mai Vũ đã tận tình chỉ bảo, hướng dẫn,
động viên và giúp đỡ em trong suốt quá trình thực hiện đề tài khóa luận.
Em xin gửi lời cảm ơn sâu sắc tới các Thầy Cô trong Khoa Công nghệ thông tin
đã truyền đạt kiến thức quý báu cho em trong bốn năm học vừa qua.
Em cũng xin gửi lời cảm ơn tới các thầy cô, các anh chị, các bạn và các em sinh
viên trong phòng thí nghiệm KT-Sislab đã giúp em rất nhiều trong việc hỗ trợ kiến
ty sản phNm nên chúng là những dữ liệu đa nhãn. Vì vậy, một trong các vấn đề trọng tâm của
hệ thống quản lý danh tiếng là việc xử lý dữ liệu đa nhãn.
Bài toán phân lớp dữ liệu đa nhãn có đặc điểm là số lượng đặc trưng lớn [2]. Việc tạo
lập và lựa chọn tập đặc trưng dữ liệu có ý nghĩa rất quan trọng trong việc nâng cao hiệu quả
của thuật toán phân lớp đa nhãn. Khóa luận đề xuất một mô hình kết hợp việc tạo lập đặc
trưng dựa theo mô hình chủ đề Nn với giải pháp lựa chọn đặc trưng của Gomez-Verdejo và
Michel Verleysen, 2007 [3].
Khóa luận thi hành thực nghiệm trên miền dữ liệu là tập nhận xét của người dùng về
1000 khách sạn ở Việt Nam ở website ( ). Kết quả thu được cho thấy giải
pháp kết hợp đặc trưng đã cải thiện kết quả phân lớp đa nhãn.
Từ khóa : reputation management, multi-label, classification, feature selection.FEATURES ENRICHING AND SELECTINGIN MULTI-LABEL
CLASSIFICATION IN REPUTATION MANAGEMENT
Thom Phan Thi
QH-2008-I/CQ course, information technology faculty
Abtract thesis:
From the late 20
th
century, the reputation systems have been commonly adopted by
Internet companies. For each companies or products, the reputation management crawled
customer’s reviews. Then they found the opinion customers in there and constructed the
report about opinion customers in features products or features companies. However, some
customer review may belong to more than one class, almost them is multi-label data. So the
importation problem in reputation management is classification multi-label.
According to Guyon and Elisseeff, 2003 [2], feature selection is an important task in
classification multi-label, as it can improve the interpretability of the problems, together with
performances and learning time of prediction algorithms. Based on the methodology of
Mục lục
MỞ ĐẦU 1
CHƯƠNG 1. GIỚI THIỆU CHUNG VỀ QUẢN LÝ DANH TIẾNG 3
1.1. Danh tiếng và các khái niệm liên quan 3
1.2. Giới thiệu chung về hệ thống quản lý danh tiếng 4
1.2.1. Sơ bộ về hệ thống quản lý danh tiếng 4
1.2.3. Tầm quan trọng của hệ thống quản lý danh tiếng 6
1.3. Phân lớp dữ liệu đa nhãn và bài toán lựa chọn đặc trưng 7
Kết luận chương một 9
CHƯƠNG 2. PHƯƠNG PHÁP LỰA CHỌN ĐẶC TRƯNG TRONG PHÂN LỚP ĐA
NHÃN VÀ MÔ HÌNH CHỦ ĐỀ ẨN LDA 10
2.1. Phương pháp lựa chọn đặc trưng sử dụng độ tương hỗ (MI) 10
2.1.1. Bài toán lựa chọn đặc trưng 10
2.1.2. Phương pháp lựa chọn đặc trưng dựa vào độ tương hỗ (MI) 11
2.1.2.1. Độ tương hỗ MI 11
2.1.2.2. Phương pháp thực hiện 11
2.1.2.3. Cách đánh giá 12
2.2. Mô hình chủ đề Nn 12
2.2.1. Mô hình sinh trong LDA 14
2.2.2. Ước lượng tham số và suy luận 15
Kết luận chương hai 16
CHƯƠNG 3. PHƯƠNG PHÁP LÀM GIÀU VÀ LỰA CHỌN ĐẶC TRƯNG TRONG
PHÂN LỚP ĐA NHÃN 17
3.1. Mô tả phương pháp 17
3.2. Mô hình đề xuất 18
3.3. Pha 1. Huấn luyện mô hình 19
3.3.1. Xây dựng tập đặc trưng bổ xung từ mô hình chủ đề n LDA 19
3.3.2. Xây dựng vector đặc trưng 20
3.3.3. Lựa chọn đặc trưng 21
Hình 4.1: So sánh kết quả thực nghiệm 1 và thực nghiệm 2 33
Hình 4.2: So sánh 4 thực nghiệm 34
Danh sách bảng biểu
Bảng 3.1: Ví dụ về kết quả của mô hình chủ đề Nn cho tài liệu t 19
Bảng 3.2: Bảng ký hiệu 25
Bảng 4.1. Cấu hình hệ thống thử nghiệm 27
Bảng 4.2: Công cụ phần mềm sử dụng 28
Bảng 4.3 : Tập dữ liệu thực nghiệm 29
Bảng 4.4: Tập dữ liệu huấn luyện 29
Bảng 4.5: Tập dữ liệu cho mô hình chủ đề Nn 30
Bảng 4.6: Kết quả của thực nghiệm 1 31
Bảng 4.7: Kết quả thực nghiệm 2 với số chủ đề là 15 32
Bảng 4.8: Kết quả thực nghiệm 2 với số chủ đề là 20 32
Bảng 4.9: Kết quả thực nghiệm 2 với số chủ đề là 25 32
Bảng 4.10: Kết quả thực nghiệm 3 33
Bảng 4.11: Kết quả thực nghiệm 4 34
Danh sách các từ viết tắt
BR Binary Relevance
IDF Inverse Document Frequency
MI Mutual Information
LDA Latent Dirichlet Allocation
LP Label Powerset
tiếng và tầm quan trọng của hệ thống này trong thực tế. Sau đó, khóa luận còn trình
bày về tầm quan trọng của việc xử lý dữ liệu đa nhãn trong hệ thống quản lý danh
tiếng, tầm quan trọng của việc lựa chọn đặc trưng.
Chương 2 : Trình bày về bài toán lựa chọn đặc trưng trong việc phân lớp dữ liệu
đa nhãn cùng một số nghiên cứu liên quan. Ngoài ra, khóa luận còn trình bày về
phương pháp mô hình chủ đề Nn LDA và giải pháp do khóa luận đề xuất.
Chương 3 : Khóa luận đề xuất phương pháp xây dựng tập đặc trưng dựa vào việc
bổ xung đặc trưng thu được từ mô hình chủ đề Nn LDA kết hợp với phương pháp
lựachọn đặc trưng dựa vào độ tưng hỗ(MI) trên miền dữ liệu Tiếng Việt. Đồng thời,
khóa luận cũng trình bày chi tiết các pha cũng như các bước trong mô hình.
2
Chương 4 : Khóa luận trình bày một số thực nghiệm trong việc áp dụng phương
pháp xây dựng tập đặc trưng mà khóa luận đề xuất. Từ đó, khóa luận sử dụng để đánh
giá danh tiếng cho 1000 khách sạn ở Việt Nam.
Phần kết luận : Tóm lược kết quả đạt được của khóa luận và định hướng phát
triển tương lai.
3
CHƯƠNG 1. GIỚI THIỆU CHUNG VỀ QUẢN LÝ DANH TIẾNG
1.1. Danh tiếng và các khái niệm liên quan
Theo như Từ điển Oxford(1992) thì danh tiếng được định nghĩa “là các ước
lượng chung của con người về các phương diện đặc tính hoặc phm chất ; nó gần như
là sự yêu quý hay tin tưởng vào một người hay một tổ chức”.
Danh tiếng được coi như là một đặc tính hoặc một thuộc tính của con người hay
một tổ chức được hình thành nhờ hành vi trong quá khứ. Theo Lik Mui, 2002 [5], danh
tiếng được phân loại dựa vào nguồn gốc xây dựng như sơ đồ sau:
Hình 1.1 : Sơ đồ phân loại danh tiếng
sản phNm, … Sau đó tổ
ng h
dùng khác có thể sử dụ
ng thông tin mà h
tài liệu tham khảo để
đưa ra quy
(a)
4
ng thu đư
ợc từ những thông tin gián tiế
p như : s
nhóm mà cá nhân đó tham gia, các thông tin thu th
ậ
p t
u chung
về hệ thống quản lý danh tiếng
th
ống quản lý danh tiếng
i th
ế lớn nhất mà Internet mang lạ
i cho ngư
i gian công s
ức trong việc tìm kiếm, thu thậ
p thông tin. Hàng ngày,
, Internet luôn có hàng tri
ệu người giao tiếp và chia sẻ
các ý ki
ời. Mọi người
ng mang l
ại như một 5
(c) (d)
Hình 1.2: (a) Hệ thống Vật giá, (b) Hệ thống Swooti;
(c,d) Hệ thống zoominfo: Giao diện (c); kiến trúc thành phần hệ thống (d)
1.2.2. Mô hình của hệ thống quản lý danh tiếng
Theo Liu Ling (2011, [4]), mô hình hệ thống quản lý danh tiếng được xây dựng
từ mô hình hệ thống thông tin song đi theo hai hướng tiếp cận có hoặc không có thành
phần phản hồi J. Laudon và K. Laudon (2007, [13]), Stair và cộng sự (2010, [14]) đề
nghị hệ thống quản lý danh tiếng được xây dựng như một hệ thống thông tin bao gồm
bốn thành phần: Đầu vào, Xử lý, Đầu ra và Phản hồi người dùng như hình 3(a). Trong
khi đó, Hoffman và cộng sự (2009, [15]), Zheng và Jin (2009, [16]), Swamynathan và
cộng sự (2010, [24]) coi rằng hệ thống danh tiếng bao gồm ba thành phần: Thu thập
thông tin, Xử lý thông tin và Hiển thị kết quả người dùng như hình 3(b).
(a) Mô hình kiểu Hệ thống thông tin [4]
(b) Mô hình kiểu ba thành phần [4]
6
(c) Một mô hình năm thành phần [25]
Hình 1.3 : Hai kiểu mô hình hệ thống quản lý danh tiếng [4, 25]
Thành phần Phản hồi người dùng là rất quan trọng trong hệ thống danh tiếng,
chỉ trong chốc nát. Công ty Enron, ngành công nghiệp kế toán kiểm toán sau vụ
Andersen, Wall Street,… là những ví dụ nổi bật. Với danh tiếng tốt của doanh nghiệp
sẽ thu hút khách hàng, nhà đầu tư và các nhân viên tài năng, dẫn đến lợi nhuận cao.
Sự thành công của eBay [5], một trang web bán hàng rất phổ biến đã là ví dụ
điển hình cho thấy tầm quan trọng to lớn của danh tiếng, các giá trị uy tín của người
bán và người mua được đo và xếp hạng theo điểm số (tích cực, tiêu cực và trung lập).
Nghiên cứu của Resnich và Zeckhauser [6] đã chỉ ra rằng trên eBay 89% trong số
168.680 giao dịch xảy ra giữa người bán và người mua gặp nhau lần đầu tiên. Và hầu
như tất cả (98.9%) xảy ra giữa những người đã tiến hành giao dịch không quá bốn lần.
Các thống kê trên chỉ ra rằng, hầu hết giao dịch trên eBay là giao dịch giữa những
người không quen biết và danh tiếng là yếu tố quyết định của những giao dịch này.
Như đã nói ở trên, quản lý danh tiếng là làm nhiệm vụ thu thập ý kiến của người
dùng về sản phNm và các sự kiện, thông tin về uy tín của sản phNm, … sau đó tổng hợp
thông tin này và công bố với mọi người. Như vậy, quản lý danh tiếng được coi là tầng
trên của khai phá quan điểm và bài toán phân lớp quan điểm được coi là bài toán trọng
tâm của quản lý danh tiếng.
1.3. Phân lớp dữ liệu đa nhãn và bài toán lựa chọn đặc trưng
Hầu hết các ứng dụng của phân lớp phân cấp văn bản là bài toán đa nhãn, có
nghĩa là một văn bản hay câu có thể được gán vào nhiều hơn một lớp. Ví dụ, một câu
8
quan điểm của khách hàng nhận xét về khách sạn như “Khách sạn rất đẹp, thoáng và
có nhiều đồ ăn ngon” có thể thuộc lớp “Chất lượng phòng, khách sạn” hoặc “Chất
lượng đồ ăn”. Phân lớp dữ liệu đa nhãn là nhiệm vụ phân loại tài liệu trong đó mỗi tài
liệu có thể đồng thời thuộc vào nhiều nhãn khác nhau. Dữ liệu đa nhãn thường được
gặp trong thực tế hơn dữ liệu đơn nhãn vì dữ liệu đơn nhãn được quy định chỉ thuộc
vào một nhãn cố định. Xét một ví dụ về phân lớp dữ liệu văn bản như : một bài báo về
nghị định Kyoto, bài báo này có thể được gán nhãn là chính trị hoặc môi trường. Một
ví dụ khác như, một bức ảnh có thể thuộc về nhiều nhãn khác nhau như bãi biển, núi,
du lịch, Do tầm quan trọng của dữ liệu đa nhãn, bài toán phân lớp dữ liệu đa nhãn đã
Chương tiếp theo, khóa luận sẽ đi sâu vào phân tích bài toán lựa chọn đặc trưng
trong miền dữ liệu đa nhãn, giới thiệu các nghiên cứu liên quan, phương pháp bổ xung
đặc trưng bằng mô hình chủ đề Nn LDA. Từ những tìm hiểu đó, khóa luận đề xuất giải
pháp xây dựng tập đặc trưng hiệu quả cho hệ thống quản lý danh tiếng.
10
CHƯƠNG 2. PHƯƠNG PHÁP LỰA CHỌN ĐẶC TRƯNG TRONG PHÂN LỚP
ĐA NHÃN VÀ MÔ HÌNH CHỦ ĐỀ ẨN LDA
2.1. Phương pháp lựa chọn đặc trưng sử dụng độ tương hỗ (MI)
2.1.1. Bài toán lựa chọn đặc trưng
Lựa chọn đặc trưng là việc lựa chọn từ một tập hợp các đặc trưng đầu vào để đưa
ra một tập nhỏ các đặc trưng có giá trị nhất. Xét với một vector đặc trưng đầu vào ngẫu
nhiên X={X
1
,…, X
d
} và Y là giá trị đầu ra có thể dự đoán từ vector đặc trưng X.
Nhiệm vụ lựa chọn đặc trưng chính là việc tìm ra các đặc trưng X
i
có liên quan nhất
đến dự đoán giá trị Y.
Lựa chọn đặc trưng có tầm quan rất lớn trong thực tế, đặc biệt là trong các
phương pháp K-láng giềng gần nhất, học máy vector hỗ trợ (SVM). Những phương
pháp này bị ảnh hưởng rất lớn vào yếu tố đầu vào, khả năng phân lớp của thuật toán có
xu hướng giảm khi các biến không có giá trị được thêm vào.
Khi dữ liệu có số lượng đặc trưng lớn, việc tìm kiếm tập các đặc trưng tối ưu là
rất khó. Theo các nghiên cứu trước đây, có một số phương pháp tìm kiếm tập đặc
trưng tối ưu bằng cách làm ngược lại với thông thường, tức là loại bỏ các đặc trưng
(y) và xác
suất cận biên của X, Y là p
x,y
(x,y) thì MI được định nghĩa là :
ܫ
ሺ
ܺ,ܻ
ሻ
=
නන
௫,௬
ሺݔ,ݕሻ݈݃
௫,௬
ሺݔ,ݕሻ
௫
ሺ
ݔ
ሻ
௬
ሺݕሻ2.1.2.2. Phương pháp thực hiện
Có rất nhiều cách thức để lựa chọn ra một tập nhỏ đặc trưng từ tập lớn ban đầu.
Theo Vanessa Gomez-Verdejo và cộng sự [3], thì phương pháp Forward-Backward là
phương pháp hiệu quả trong việc lựa chọn đặc trưng cho phân lớp dữ liệu. Phương
, đặc trưng tiếp theo được lựa
chọn ܺ
௧
௦
phải thỏa mãn điều kiện sau :
ܺ
௧
௦
= ܽݎ݃݉ܽݔ
ೕ
ܫ
መ
ሺ
൛
ܺ
ଵ
௦
,…,ܺ
௧ିଵ
௦
,ܺ
ൟ
,ܻሻ
1 ≤ ݆ ≤ ܰ
12
ܺ
௦
,ܺ
ାଵ
௦
,…,ܺ
௧
௦
ൟ
,ܻሻ1 ≤ ݆ ≤ ݐ
Nếu : ܫ
መ
൫
൛
ܺ
ଵ
௦
,…,ܺ
ିଵ
௦
,ܺ
ାଵ
௦
,…,ܺ
௧
௦
ൟ
,ܻ൯ > ܫ
መ
ሺ
ሼ
1
|
ܥ
|
|
ெ
|
ୀଵ
หܻ
∆ܻ
ห
Trong đó ∆ là biểu thị của phép lấy giá trị khác nhau giữa hai tập, |C| là số lượng
các nhãn dương.
Độ chính xác được định nghĩa như sau :
ܣܿܿݑݎܽܿݕ
ሺ
ℎ,ܯ
ሻ
=
1
|
ܯ
|
หܻ
nhau, với những phân phối khác nhau. Tiếp đó, để sinh các từ cho tài liệu ta có thể lựa
chọn ngẫu nhiên các từ dựa vào phân phối xác suất của các từ trên các chủ đề.
Một cách hoàn toàn ngược lại, cho một tập các tài liệu, có thể xác định một tập
các chủ đề Nn cho mỗi tài liệu và phân phối xác suất của các từ trên từng chủ đề. Hai ví
dụ về phân tích chủ đề sử dụng mô hình Nn là Probabilistic Latent Semantic Analysis
(pLSA) và Latent Dirichlet Allocation (LDA)
PLSA là một kỹ thuật thống kê nhằm phân tích những dữ liệu xuất hiện đồng thời
[18]. Phương pháp này được phát triển dựa trên LSA và các cộng sự (2003) [17], mặc
dù LPSA là một bước quan trọng trong việc mô hình hóa dữ liệu văn bản, tuy nhiên nó
vẫn còn chưa hoàn thiện ở chỗ chưa xây dựng được một mô hình xác suất tốt ở mức độ
tài liệu. Điều đó dẫn đến vấn đề gặp phải khi phân phối xác suất cho một tài liệu nằm
ngoài tập dữ liệu học, ngoài ra số lượng các tham số có thể tăng lên một cách tuyến
tính khi kích thước của tập dữ liệu tăng.
LDA là một mô hình hoàn thiện hơn so với PLSA và có thể khắc phục được
những nhược điểm ở trên. Mô hình chủ đề Nn này sẽ được sử dụng trong việc xây dựng
hệ thống của khóa luận.
LDA là một mô hình sinh xác suất cho tập dữ liệu rời rạc. LDA được xây dựng
dựa trên ý tưởng : mỗi tài liệu là sự trộn lẫn của nhiều chủ đề (topic). Về bản chất,
LDA là một mô hình Bayes phân cấp 3 mức (mức kho ngữ liệu, mức tài liệu và mức từ
ngữ). Mỗi tài liệu trong tập hợp được coi là một hỗn hợp xác định trên tập cơ bản các
chủ đề. Mỗi chủ đề là một hỗn hợp không xác định trên tập cơ bản các xác suất chủ đề.
Về khía cạnh mô hình hóa văn bản, các xác suất chủ đề là một biểu diễn cụ thể, rõ ràng
cho một tài liệu.
Copyright: Tài liệu đại học ©