BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------DƢƠNG XUÂN PHÚC

NGHIÊN CỨU HỆ THỐNG GỢI Ý

CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN

LUẬN VĂN THẠC SĨ KỸ THUẬT
CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC :
TS. Đinh Viết Sang

Hà Nội – Năm 2016


LỜI CAM ĐOAN
Tôi Dƣơng Xuân Phúc, cam đoan Luận văn tốt nghiệp là công trình nghiên
cứu của bản thân dƣới sự hƣớng dẫn của TS. Đinh Viết Sang.
Kết quả luận văn là trung thực, không sao chép toàn văn của bất kì công trình
nào khác.

Hà Nội, ngày

tháng

năm 2016

Tác giả

Dƣơng Xuân Phúc

Xác nhận của giáo viên hƣớng dẫn về mức độ hoàn thành của Luận văn tốt
nghiệp và cho phép bảo vệ:
..................................................................................................................................
..................................................................................................................................
..................................................................................................................................
..................................................................................................................................
Hà Nội, ngày 21 tháng 10 năm 2016
Giáo viên hƣớng dẫn

TS. Đinh Viết Sang

2


MỤC LỤC
MỤC LỤC ...................................................................................................................3
DANH MỤC HÌNH ẢNH ..........................................................................................5
DANH MỤC CÁC BẢNG..........................................................................................6
DANH MỤC CÁC TỪ VIẾT TẮT ............................................................................7
CHƢƠNG 1: TỔNG QUAN VỀ HỆ THỐNG GỢI Ý ...............................................8
1.1 Hệ thống gợi ý ...................................................................................................8
1.2 Ứng dụng thực tiễn ............................................................................................8
1.3 Phát biểu toán học .............................................................................................9
CHƢƠNG II. CƠ SỞ LÝ THUYẾT .........................................................................10
2.1 Ma trận ............................................................................................................10
2.2.1 Định nghĩa ................................................................................................10
2.1.2 Các phép tính cơ bản ................................................................................10
2.1.3 Định thức của ma trận ..............................................................................11

2.1.4 Ma trận nghịch đảo...................................................................................11
2.1.5 Hạng của Ma trận .....................................................................................12
2.1.6 Ma trận unitary .........................................................................................12
2.1.7 Giá trị riêng của ma trận và vec-tơ riêng .................................................12
2.1.8 Ma trận giả nghịch đảo.............................................................................12
2.1.9 Ma trận trực giao ......................................................................................13
2.2 Cơ bản về học máy ..........................................................................................13
2.2.1 Học có giám sát và học không giám sát ...................................................13
2.2.2 Phân lớp và hồi quy..................................................................................14
2.2.3 Overfitting và Underfitting ......................................................................15
2.2.4 Tập huấn luyện, tập validation và tập kiểm tra ........................................16
2.2.5 Bias và variance .......................................................................................17
2.2.6 Các phƣơng pháp chống overfitting .........................................................19
2.2.7 Lựa chọn mô hình ....................................................................................20

3


2.3. Trung bình bình phƣơng tối thiểu ..................................................................21
CHƢƠNG III: CÁC KĨ THUẬT ÁP DỤNG TRONG HỆ GỢI Ý ..........................22
3.1 Điểm TF.IDF ...................................................................................................22
3.2 Chỉ số tƣơng đồng Jaccard ..............................................................................23
3.3 Độ tƣơng đồng cosine .....................................................................................24
3.4 Phƣơng pháp giảm số chiều không gian .........................................................25
3.4.1 Giới thiệu..................................................................................................25
3.4.2 Phƣơng pháp phân rã ma trận SVD .........................................................27
3.4.3 Phƣơng pháp giảm số chiều không gian ..................................................29
3.5 Các phƣơng pháp giảm giá trị hàm gradient descent ....................................30
3.5.1 Gradient Descent (GD) ............................................................................30
3.5.2 Stochastic Gradient Descent (SGD) .........................................................31

CHƢƠNG IV: CÁC MÔ HÌNH GỢI Ý ...................................................................33
4.1 Dữ liệu .............................................................................................................33
4.2 Cách đánh giá độ tốt của một mô hình............................................................33
4.3 Các mô hình ....................................................................................................34
4.3.1 Phƣơng pháp Content Base (CB) .............................................................34
4.3.2 Phƣơng pháp Collaborative Filtering (CF) ..............................................38
4.3.3 Phƣơng pháp hỗn hợp ..............................................................................45
4.3.4 Đánh giá giá trị Global Baseline ..............................................................45
4.3.5 Phƣơng pháp Latent Factor (LF) ..............................................................46
CHƢƠNG V: THỬ NGHIỆM CÁC MÔ HÌNH GỢI Ý ..........................................54
5.1 Mô tả dữ liệu ...................................................................................................54
5.2 Các mô hình và kết quả thử nghiệm................................................................58
5.3 So sánh và đánh giá các phƣơng pháp ............................................................64
KẾT LUẬN ...............................................................................................................66
TÀI LIỆU THAM KHẢO .........................................................................................67

4


DANH MỤC HÌNH ẢNH
Hình 1 - Mô tả kết quả đạt đƣợc bằng hai mô hình phân loại và hồi quy [11] ........14
Hình 2 - Mô hình underfitting, fitting và overfitting với dữ liệu [23] .....................16
Hình 3 - Sự thay đổi của giá trị bias và variance theo mức độ học dữ liệu huấn
luyện của mô hình [22] .............................................................................................18
Hình 4 - Giá trị của hàm mục tiêu trên tập huấn luyện [16] ....................................20
Hình 5 - Dữ liệu trong không gian ba chiều đƣợc biểu diễn bởi mặt phẳng hai chiều
[8] ..............................................................................................................................25
Hình 6 - Dữ liệu nhìn thấy biểu diễn xung quanh đƣờng thẳng [8] .........................26
Hình 7 - Phân rã SVD của một ma trận [9] ..............................................................29
Hình 8 - Cách làm giảm số chiều bằng phân rã SVD [9]........................................29

Hình 9 - Ma trận nhận đƣợc sau khi thực hiện giảm số chiều [9]...........................30
Hình 10 - Sự di chuyển của hàm mục tiêu theo hai phƣơng pháp Gradient Descent
và Stochastic Gradient Descent [5] ...........................................................................31
Hình 11 - Ma trận đánh giá của hệ gợi ý và cách lấy tập dữ liệu kiểm tra [10] .....33
Hình 12 - Biểu đồ thể hiện quá trình hoạt động của CB [3] ...................................37
Hình 13 - Mô tả cơ bản về quá trình gợi ý của CF [7] ............................................38
Hình 14 - Tác động của ma trận

khi cập nhật tại

...............................51

Hình 15 - Ví dụ về một bản ghi dữ liệu trong tập tin "users.dat" ...........................54
Hình 16 - Ví dụ về một bản ghi dữ liệu trong tập tin “movies.dat” ........................56
Hình 17 - Ví dụ về một bản ghi trong tập tin “ratings.dat”.....................................58
Hình 18 - Cập nhật Stochastic Gradient Descent với (0.001, 0.002), k=1 .............64

5


DANH MỤC CÁC BẢNG

Bảng 1: Kết quả của mô hình CB..............................................................................61
Bảng 2: Kết quả cho mô hình ngƣời dùng- ngƣời dùng CF .....................................62
Bảng 3: Kết quả của mô hình sản phẩm-sản phẩm CF .............................................62
Bảng 4: Kết quả chọn mô hình của mô hình LF .......................................................64

6



DANH MỤC CÁC TỪ VIẾT TẮT

Từ viết tắt
TF
IDF

Tên đầy đủ
Term Frequency
Inverse Document Frequency

SVD

Singular Value Decomposition

CB

Content-based

CF

Collaborative Filtering

LF

Latent Factor

GD

Gradient Descent


SGD

Stochastic Gradient Descent

7


CHƢƠNG 1: TỔNG QUAN VỀ HỆ THỐNG GỢI Ý
1.1 Hệ thống gợi ý
Hệ thống gợi ý (Recommender Systems - RS) là một dạng của hệ thống lọc
thông tin (information filtering), nó đƣợc sử dụng để dự đoán sở thích (preference)
hay xếp hạng (rating) mà ngƣời dùng có thể dành cho một mục thông tin (item)
nào đó mà họ chƣa xem xét tới trong quá khứ (item có thể là bài báo, bộ phim,
đoạn video clip, sách,..) [11] nhằm gợi ý các mục thông tin “có thể đƣợc quan tâm”
bởi ngƣời dùng. Hệ thống gợi ý sẽ đƣa ra các gợi ý dựa trên quá trình thu thập, xử
lý và phân tích dữ liệu từ ngƣời dùng. Dữ liệu đó đƣợc chia làm 2 loại là tường
minh (explicit) bằng cách yêu cầu ngƣời dùng phản hồi trực tiếp và tiềm ẩn
(implicit) bằng cách tự động suy luận dựa trên những tƣơng tác của ngƣời dùng
với hệ thống nhƣ: số lần nhấp chuột, thời gian quan sát... Trong hầu hết các trƣờng
hợp, bài toán gợi ý đƣợc coi là bài toán dự đoán việc xếp hạng (rating) của các
sản phẩm (phim, sản phẩm tiêu dùng, sách, nhạc…) chƣa đƣợc ngƣời dùng biết
đến. Việc dự đoán này thƣờng dựa trên những đánh giá đã có của chính ngƣời dùng
đó hoặc những ngƣời dùng khác. Ví dụ, những bộ phim đƣợc dự đoán là sẽ có xếp
hạng cao nhất sẽ đƣợc dùng để gợi ý. Có khá nhiều ứng dụng nổi tiếng về hệ thống
gợi ý nhƣ: gợi ý sản phẩm của Amazon và Ebay, hệ thống gợi ý phim của NetFlix và
Youtube,..
Hệ thống gợi ý đã chứng minh đƣợc ý nghĩa to lớn: giúp cho ngƣời sử dụng
trực tuyến đối phó với tình trạng quá tải thông tin. Hệ thống gợi ý trở thành một
trong những công cụ mạnh mẽ và phổ biến trong thƣơng mại điện tử. Mục đích
của hệ thống gợi ý là dựa vào hành vi từ thói quen, nhu cầu... trong quá khứ của

ngƣời sử dụng để dự đoán sở thích trong tƣơng lai của họ.
1.2 Ứng dụng thực tiễn
Hệ gợi ý có thể đƣợc triển khai trên hầu hết các hệ thống có tƣơng tác với
ngƣời dùng. Phổ biến nhất là các hệ thống trên nền web. Phổ biến nhất là các hệ
thống về phim ảnh, nhạc, sách báo,… và nhiều sản phẩm nói chung khác. Không

8


những vậy, hệ gợi ý còn đƣợc áp dụng cho các chuyên gia, nhà nghiên cứu, nhà
hàng, hệ thống tài chính, bảo hiểm,…
Ta có thể nhận thấy các hệ gợi ý xung quanh chúng ta có rất nhiều. Các trang web nhƣ
Youtube, Google, Facebook,… đều áp dụng những hệ thống nhƣ vậy để luôn luôn giúp
ngƣời dùng tìm kiếm thông tin, sản phẩm một cách nhanh chóng nhất có thể.
Với những ứng dụng nhƣ vậy, hệ gợi ý đã mang đến nhiều lợi ích to lớn cho
cả ngƣời dùng và hệ thống áp dụng nó. Với ngƣời dùng, chúng ta luôn có thể nhanh
chóng tiếp cận đƣợc những nguồn thông tin phù hợp, chính xác. Tiết kiệm đƣợc
thời gian một cách đáng kể. Với các nếu áp dụng tốt các hệ gợi ý sẽ đƣợc ngƣời
dùng ƣa thích và đánh giá cao. Ví dụ điển hình nhất là các trang web nhƣ Youtube
hay Google.
1.3 Phát biểu toán học
Các hệ thống gợi ý có thể áp dụng cho nhiều lĩnh vực khác nhau. Tuy nhiên,
bài toán có thể đƣợc phát biểu dƣới dạng toán học nhƣ sau:
U là tập ngƣời dùng trong hệ thống.
I là tập các sản phẩm của hệ thống đó.
là đánh giá của ngƣời dùng i (

) cho sản phẩm j(

).


Bằng các mô hình của hệ gợi ý, ta cần đƣa ra các dự đoán cho đánh giá của
một ngƣời dùng bất kì trong hệ thống cho một sản phẩm bất kì mà ngƣời dùng đó
chƣa đánh giá. Và trong thực tế, các sản phẩm đƣợc hệ gợi ý dự đoán ngƣời dùng
đó sẽ đánh giá cao, sẽ đƣợc đƣa lên để gợi ý cho ngƣời dùng đó trải nghiệm.

9


CHƢƠNG II. CƠ SỞ LÝ THUYẾT
2.1 Ma trận
2.2.1 Định nghĩa
Ta có định nghĩa ma trận:
[

]=[

]

Trong đó: n là số hàng, m là số cột.
Ma trận có n=m là ma trận vuông.
Phần tử

là phần tử nằm tại hàng thứ I và cột thứ j;

có thể là số thực hoặc số

phức. Trong khuôn khổ của luân văn tốt nghiệp này, chúng ta sẽ chỉ xét các ma trận
thực.
2.1.2 Các phép tính cơ bản

 Phép cộng hai ma trận:
Ta có hai ma trận:

có tổng đƣợc định nghĩa là:

và

[

]

[

]

 Phép nhân vô hƣớng:
Phép nhân của ma trận

với số thực α đƣợc định nghĩa là:
[

]

[

]

 Phép nhân hai ma trận:
Phép nhân của hai ma trận
Tronng đó:


và

đƣợc định nghĩa là:

∑

Phép nhân hai ma trận chỉ đƣợc xác định khi số cột của ma trận thứ nhất
bằng số hàng của ma trận thứ hai.
Chú ý: Phép nhân hai ma trận không có tính giao hoán.

10


 Chuyển vị:
Ta có định nghĩa phép chuyển vị ma trận:
[

]

[

]

2.1.3 Định thức của ma trận
Ma trận con hàng i, cột j của ma trận

là ma trận A sau khi bỏ đi các

, khi đó:


phần tử của hàng i và cột j. Kí hiệu là

[

]

Khi đó ta sẽ có công thức tính định thức của ma trận nhƣ sau:
∑
Với j tùy ý và
Ví dụ với ma trận vuông cấp 3:
[

]

Ta có:
Hoặc:
Hoặc:
Định thức của ma trận chỉ tồn tại khi ma trận đó là ma trận vuông.
2.1.4 Ma trận nghịch đảo
Ma trận nghịch đảo của ma trận vuông là ma trận đƣợc kí hiệu là

Với

: sao cho:

là ma trận đơn vị cấp .

Ma trận vuông cấp tồn tại ma trận nghịch đảo khi và chỉ khi:


11


2.1.5 Hạng của Ma trận
Với ma trận

hạng của ma trận A là số tự nhiên

thỏa

mãn các điều kiện:
- Tồn tại ít nhất một định thức con cấp r của ma trận A khác 0.
- Mọi định thức con cấp lớn hơn r (nếu có) của ma trận A đều bằng 0.
Nói cách khác, hạng của ma trận chính là cấp cao nhất của các định thức con khác 0
của ma trận
Bên cạnh đó, hạng của ma trận còn là số cột (hoặc hàng) độc lập tuyến tính
của ma trận.
2.1.6 Ma trận unitary
Ma trận unitary là ma trận vuông với tính chất chuyển vị của ma trận liên
hợp phức với ma trận đó là ma trận nghịch đảo. Với ma trận thực (thành phần ảo
bằng không) thì ma trận chuyển vị là ma trận nghịch đảo.
Khi đó, xét ma trận thực U. Ta có:
2.1.7 Giá trị riêng của ma trận và vec-tơ riêng
Với ma trận vuông

, đa thức đặc trƣng đƣợc định nghĩa:
[

]


Khi đó, nghiệm của phƣơng trình:
Đƣợc gọi là giá trị riêng của ma trận A.
2.1.8 Ma trận giả nghịch đảo
Nhƣ đã nêu ở trên, một ma trận chỉ có thể nghịch đảo đƣợc khi ma trận đó là
ma trận vuông và có

. Tuy nhiên, các ma trận chữ nhật n x m vẫn có tồn

tại một ma trận chữ nhật m x n sao cho:

12


khi đó ma trận

đƣợc gọi là ma trận giả nghịch đảo của ma trận

.

2.1.9 Ma trận trực giao
đƣợc gọi là ma trận trực giao khi:

Ma trận

∑
Trong đó:

và

Và:



nếu



nếu

2.2 Cơ bản về học máy
Học máy là một lĩnh vực nghiên cứu của trí tuệ nhân tạo. Sau quá trình đƣợc
huấn luyện, máy móc có thể giải quyết một số công việc cụ thể. Ví dụ: máy có thể
học đƣợc cách phân loại thƣ rác và tự động xếp các thƣ này vào đúng phân loại của
chúng.
Trong khuôn khổ luận văn này, tác giả không tìm hiểu sâu về học máy. Sẽ chỉ
tìm hiểu về các đặc trƣng cũng nhƣ một số phƣơng pháp phổ biến đƣợc áp dụng
trong học máy.
2.2.1 Học có giám sát và học không giám sát


Học có giám sát
Học có giám sát là quá trình mô hình học máy sẽ đƣợc huấn luyện trên một tập

dữ liệu đầu vào đã đƣợc dán nhãn hoặc đƣợc gán giá trị đầu ra mong muốn.
Mục đích của quá trình học là đƣa ra đƣợc một giả thiết (có thể là một phân
lóp hoặc một hàm mục tiêu,…) phù hợp với tập dữ liệu huấn luyện đầu vào.
Từ giả thiết học đƣợc ở trên, mô hình sẽ áp dụng giả thiết đó cho các dữ liệu
chƣa đƣợc dán nhãn.
Ví dụ: trong bài toán nhận diện chữ viết, trong quá trình huấn luyện, mô hình
sẽ đƣợc nhận diện các ảnh là các chữ viết với nhãn cụ thể. Sau quá trình huấn luyện,
khi đƣa một chữ viết bất kì vào thì mô hình sẽ đƣa ra kết quả là một trong các nhãn

mô hình đã đƣợc học, chính là nhận diện chữ viết đó là gì.

13




Học không giám sát
Trái ngƣợc với phƣơng pháp học có giám sát, học không giám sát sẽ đƣợc

huấn luyện trên tập dữ liệu mà mỗi dữ liệu đầu vào không có thông tin về nhãn hay
giá trị đầu ra mong muốn.
Mục đích của quá trình học không giám sát là tìm ra các cụm dữ liệu hoặc phát
hiện ra các cấu trúc, quan hệ tồn tại trong tập dữ liệu đó.
Mô hình cũng sẽ đƣợc áp dụng cho các dữ liệu khác. Kết quả cũng là phân
cụm dữ liệu mới vào các cụm đã đƣợc phân ra từ khi huấn luyện hoặc tìm ra cấu
trúc hoặc quan hệ trong dữ liệu mới này.
2.2.2 Phân lớp và hồi quy
Mô hình học máy đƣa ra kết quả đƣợc quy về bài toán phân lớp hay bài toán
hồi quy phụ thuộc vào dữ liệu đầu ra của mô hình sau khi đạt đƣợc giả thiết.
Nếu mô hình học đƣợc đƣa ra kết quả là một hàm liên tục thì đó là bài toán
hồi quy. Trong trƣờng hợp đầu ra là các giá trị rời rạc thì đó là bài toán phân lớp.

Hình 1 - Mô tả kết quả đạt được bằng hai mô hình phân loại và hồi quy [11]
Qua hình vẽ, ta thấy, kết quả của bài toán phân lớp là ta chia dữ liệu đầu vào
thành hai nhóm dữ liệu. Còn trong bài toán hồi quy, ta sẽ tìm đƣợc một hàm liên tục
(trong trƣờng hợp này là đƣờng thẳng) dựa trên các dữ liệu đầu vào thỏa mãn một
hàm mục tiêu nào đó.

14



Những ví dụ về bài toán phân lớp nhƣ:
- Nhận diện chữ số viết tay: sau khi đƣợc huấn luyện, mô hình sẽ phân nhóm
thành 10 nhóm. Mỗi nhóm tƣơng ứng với một nhãn là một số từ 0 đến 9. Sau khi
đƣa một hình ảnh mới vào để nhận diện, máy phải cho biết ảnh đó thuộc vào nhóm
nào trong 10 nhóm đã đƣợc phân loại.
- Phân loại thƣ điện tử: mô hình sẽ đƣợc huấn luyện xem thƣ thế nào đƣợc cho
là thƣ rác hoặc không. Khi nhận một thƣ điện tử mới thì mô hình phải cho biết thƣ
đó là thƣ thuộc nhóm nào.
Ví dụ về bài toán hồi quy:
- Dự đoán giá cổ phiếu trên thị trƣờng dựa trên lịch sự và các nhân tố ảnh
hƣởng đến nó. Kết quả sẽ là một hàm liên tục theo thời gian. Để dự đoán giá cổ
phiếu tại thời gian ta chỉ cần lấy giá trị hàm đó tại thời điểm là đƣợc.
- Dự đoán tuổi của một ngƣời dựa theo ảnh của ngƣời đó.
2.2.3 Overfitting và Underfitting
Trƣớc hết ta phải biết thế nào là một mô hình “fitting” với dữ liệu. Sau khi
đƣợc huấn luyện thì học máy sẽ sinh ra đƣợc một mô hình. Mô hình đó đƣợc gọi là
“fitting” với dữ liệu khi mà nó có thể đoán nhận tốt đƣợc với những dữ liệu mới.
Đây là trạng thái mà chúng ta mong muốn mô hình đạt đƣợc.


Overfitting
Hiện tƣợng này xảy ra khi mô hình quá phức tạp và thay vì mô tả chính xác dữ

liệu, mô hình đã mô tả cả nhiễu và sai số ngẫu nhiên trong dữ liệu. Mô hình bị
overfitting khi số tham số của mô hình vƣợt qua số biến cần quan sát của dữ liệu.
Lúc này, mô hình sẽ chỉ “fitting” với tập dữ liệu huấn luyện mà không có khả năng
đƣa ra dự đoán chính xác cho các dữ liệu ngoài tập này.
Hiện tƣợng overfitting sẽ xảy ra khi tập huấn luyện không đủ khả năng biểu

diễn đầy đủ mô hình. Trong khi đó, mô hình chỉ đƣợc huấn luyện trên các tập này.
Nó dễ bị dẫn đến việc mô hình bắt đầu “ghi nhớ” dữ liệu từ tập huấn luyện hơn là
“học” từ nó để sinh ra các hƣớng phát triển mới.

15




Underfitting
Underfitting là hiện tƣợng ngƣợc lại với hiện tƣợng overfitting. Mô hình học

đƣợc từ tập huấn luyện quá đơn giản so với thực tế. Khi đó, mô hình không nắm bắt
đƣợc hết các biến đƣợc biểu diễn bởi tập huấn luyện. Và tất nhiên, khi áp dụng vào
việc dự đoán các dữ liệu mới thì mô hình hoàn toàn không có khả năng. Do ngay cả
tập huấn luyện mô hình còn chƣa biểu diễn đƣợc hết các nhân tố trong đó.

Hình 2 - Mô hình underfitting, fitting và overfitting với dữ liệu [23]
Hình 2 là một mô tả về các trạng thái underfitting, fitting và overfitting của
một mô hình. Ta thấy, Trong hình thứ nhất, mô hình hồi quy đƣợc một đƣờng
thẳng. Rõ ràng, mô hình này quá đơn giản so với dữ liệu. Trong khi đó, hình bên
phải thì mô hình học đƣợc quá sát những dữ liệu huấn luyện mà không tập trung thể
hiện đƣợc mô hình. Hình ở giữa cho thấy hàm hồi quy nhận đƣợc từ mô hình đã tiếp
cận tốt với dữ liệu thực tế. Mô hình này có thể dự đoán tốt những dữ liệu mới.
2.2.4 Tập huấn luyện, tập validation và tập kiểm tra
Trong học máy, với các bộ tham số khác nhau ta sẽ sinh ra đƣợc một mô hình
khác nhau. Vì vậy, cần có một phƣơng pháp để đánh giá xem liệu mô hình nào tốt
hơn mô hình nào. Ở đây, chúng ta không nói về cách đánh giá mô hình, mà chỉ xem
xét về mặt dữ liệu.
Các bƣớc của quá trình học máy đƣợc chia ra nhƣ sau:

- Với bộ dữ liệu đầu vào, áp dụng phƣơng pháp “học” để sinh ra mô hình với
một bộ tham số. Ở đây, bộ dữ liệu đầu vào chính là tập huấn luyện.

16


- Đánh giá mô hình nhận đƣợc ở bƣớc một bằng một tập dữ liệu khác. So sánh
đánh giá đó giữa các mô hình khác nhau. Mô hình nào cho đánh giá ở bƣớc này
thấp nhất sẽ đƣợc coi là mô hình tốt nhất. Tập dữ liệu đƣợc sử dụng ở đây chính là
tập validation.
- Để ƣớc lƣợng độ tốt của mô hình, ta sẽ vẫn áp dụng phƣơng pháp đánh giá ở
trên nhƣng với một tập dữ liệu khác. Ở đây, ta chỉ đánh giá cho mô hình đạt kết quả
tốt nhất ở bƣớc trên. Tập dữ liệu đƣợc sử dụng ở bƣơc sày gợi là tập kiểm tra.
Vậy, tại sao cần tập validation và tập kiểm tra tách biệt nhau? Lý do đƣợc
đƣa ra là: khi đánh giá mô hình trên tập validation để chọn lựa ra mô hình tốt nhất,
thì tập validation này cũng đã ảnh hƣởng đến mô hình đƣợc chọn lựa. Nhƣ vậy, mô
hình cũng đã phần nào “ghi nhớ” những thông tin của tập validation này. Nếu
trƣờng hợp mô hình bị overfitting và sử dụng trực tiếp tập validation này cho việc
ƣớc lƣợng mô hình, thì sẽ không thể phản ánh đúng bản chất của dữ liệu. Do đó, ta
cần một bộ dữ liệu hoàn toàn độc lập để có thể đƣa ra ƣớc lƣợng cho mô hình học
đƣợc. Từ đó mới quyết định xem có sử dụng đƣợc mô hình này không.
2.2.5 Bias và variance


Định nghĩa
Bias là giá trị sai khác giữa các giá trị dự đoán do mô hình đƣa ra so với giá trị

thực của dữ liệu. Nhƣ vậy, nếu khoảng cách từ giá trị thực đến giá trị dự đoán của
mô hình càng lớn thì càng làm tăng bias của mô hình, và ngƣợc lại nếu giá trị thực
càng gần giá trị dự đoán thì mô hình càng đoán đúng dữ liệu. Ta luôn hi vọng mô

hình có giá trị bias nhỏ nhất có thể.
Về giá trị variance, giả sử ta có một mô hình đƣợc huấn luyện trện một tập dữ
liệu huấn luyện nào đó và đƣa ra dự đoán cho một dữ liệu . Sau đó, ta bổ sung thêm
cho tập huấn luyện và ta huấn luyện thêm cho mô hình đó và sau đó lại đƣa ra dự
đoán cho dữ liệu . Khi đó, sự sai khác giữa hai giá trị dự đoán của hai mô hình với
dữ liệu đƣợc gọi là variance. Nhƣ vậy, ta cũng mong giá trị variance này càng nhỏ
càng tốt. Càng nhỏ, chứng tỏ mô hình đã học đƣợc rất gần với dữ liệu thực tế nên
khi thêm dữ liệu huấn luyện mới không làm thay đổi quá nhiều mô hình hiện có.

17




Bias-variance trade-off
Ta thấy, học máy luôn hi vọng giá trị bias và variance càng nhỏ càng tốt. Tuy

nhiên, nếu máy càng “học” trên một bộ dữ liệu huấn luyện thì giá trị bias sẽ càng
lúc càng giảm, nhƣng giá trị variance sẽ càng lúc càng tăng. Vấn đề này đƣợc giải
thích thông qua hình vẽ:

Hình 3 - Sự thay đổi của giá trị bias và variance theo mức độ học dữ liệu huấn
luyện của mô hình [22]
Ban đầu khi mới “học” dữ liệu huấn luyện thì mô hình sẽ có bias lớn, do mô
hình chƣa học đƣợc hết các biến của mô hình. Mô hình đang bị underfitting. Khi đó
dự đoán bị sai lệch nhiều nên mô hình sẽ có sai số dự đoán cao. Cũng trong lúc này,
do mô hình còn quá đơn giản nên mỗi lần cập nhật mới không làm thay đổi quá
nhiều hàm kết quả mô hình. Điều đó làm cho variance của mô hình nhỏ.
Mô hình càng “học” thì càng “nắm bắt” đƣợc nhiều thông tin về mô hình hơn.
Tuy nhiên, càng học thì mô hình có xu hƣớng bị overfitting. Điều này dẫn đến bias

của mô hình sẽ càng ngày càng nhỏ. Do mô hình có xu hƣớng trở thành hàm biểu
diễn dữ liệu huấn luyện. Trong khi đó, hàm hội tụ của mô hình có số biến quá
nhiều, một tác động nhỏ cũng làm thay đổi hoàn toàn cấu trúc của hàm này. Dẫn
đến variance của mô hình càng lúc càng tăng.
Thông qua hình 3 ta thấy, để có đƣợc một mô hình tốt thì cần phải có một sự
đánh đổi giữa giá trị bias và giá trị variance. Bias và variance cân bằng sẽ giúp cho

18


mô hình tìm ra đƣợc những quy luật của dữ liệu cũng nhƣ giúp cho mô hình không
quá phức tạp.
2.2.6 Các phƣơng pháp chống overfitting
Qua những phân tích lý thuyết trên, ta thấy mô hình bị overfitting là điều
không mong muốn với học máy. Để tránh đƣợc hiện tƣợng trên, trong thực tế
phƣơng pháp phổ biến thƣờng đƣợc dùng đó là regularization.


L2 regularization

Thông thƣờng ta có hàm đánh giá mô hình là:
∑

̂

Để tránh overfitting thì phƣơng pháp
trên độ “phức tạp” của hàm

̂


regularization sẽ thêm vào hàm đánh giá

. Khi đó ta có hàm mục tiêu đánh giá mới:
∑

̂

̂

‖ ‖

trong đó:
‖ ‖ là chuẩn Frobenius.
là giá trị điều khiển mức độ “quan trọng” của thành phần regularization
trong hàm mục tiêu đánh giá nà


Dừng sớm (early stopping)
Khi bắt đầu bị overfitting, giá trị của hàm mục tiêu trên tập huấn luyện thì

ngày càng nhỏ dần, nhƣng giá trị này đối với tập validation bắt đầu tăng lên. Lý do
đƣợc đƣa ra là mô hình thay vì mô tả đúng dữ liệu thật, nó bắt đầu có xu hƣớng chỉ
mô tả dữ liệu trong tập huấn luyện.

19


Hình 4 - Giá trị của hàm mục tiêu trên tập huấn luyện [16]
Để chống bị overfitting thì mô hình sẽ dừng lại ngay khi giá trị hàm mục tiêu
có xu hƣớng tăng lên. Phƣơng pháp này rất thích hợp cho quá trình học cần thực

hiện các vòng lặp trên tập huấn luyện. Sau mỗi lần lặp (mô hình học trên hết tập
huấn luyện), mô hình tính lại giá trị của hàm mục tiêu trên tập huấn luyện và trên
tập validation. Nếu giá trị trên tập validation không tăng lên thì tiếp tục “học” trên
tập huấn luyện đó.
2.2.7 Lựa chọn mô hình
Lựa chọn mô hình ở đây có nghĩa là chúng ta sẽ tìm ra các tham số để sau quá
trình huấn luyện ta đƣợc mô hình tốt nhất.


Phƣơng pháp k-fold cross validation
Theo phƣơng pháp này, tập dữ liệu sẽ đƣợc chia ra làm tập con có số lƣợng

phần tử xấp xỉ nhau. Nhƣ vậy, các tập này không bị trùng lặp nhau phần tử nào cả.
Mỗi lần đánh giá mô hình sẽ sử dụng k-1 tập làm dữ liệu huấn luyện, còn tập con
còn lại sẽ làm tập validation. Lặp lần lƣợt lần để mỗi tập con đều là tập validation.
Sau khi huấn luyện ra mô hình, tính giá trị hàm mục tiêu đánh giá trên tập
validation (một trong k tập). Trung bình giá trị sai số k của tập validation sẽ đƣợc
coi là giá trị của hàm đánh giá mục tiêu của mô hình đang xét.

20


Với mỗi bộ tham số ta đều đánh giá bằng cách trên. Sau đó chọn mô hình với
bộ tham số có giá trị hàm mục tiêu đánh giá thấp nhất làm mô hình để thực hiện dự
đoán trên tập kiểm tra.
Thông thƣờng, tập dữ liệu sẽ đƣợc chia ra 80% cho tập huấn luyện và
validation, 20% cho tập kiểm tra. Sau đó, chia 80% dữ liệu làm 4 phần. Mỗi lần
huấn luyện trên 3 phần dữ liệu này. Phần còn lại đƣợc chọn là tập validation.



Holdout validation
Holdout validation là một trƣờng hợp đặc biệt của k-fold cross validation với k

= 2. Chia dữ liệu làm 2 phần bằng nhau
là tập validation. Sau đó đổi ngƣợc lại

và

. Ban đầu,

là tập huấn luyện còn

là tập validation còn

là tập huấn

luyện. Đánh giá sai số cho hai tập dự liệu rồi tính trung bình để đƣợc giá trị sai số
cho mô hình đó. Phƣơng pháp này thƣờng đƣợc sử dụng cho các tập dữ liệu đủ lớn.


Leave-one-out cross validation
Phƣơng pháp này cũng là một trƣờng hợp đặc biệt của k-fold cross validation

với bằng số dữ liệu của tập dữ liệu. Phƣơng pháp này thích hợp cho những tập dữ
liệu nhỏ.
2.3. Trung bình bình phƣơng tối thiểu
Đây là một phƣơng pháp tối ƣu hóa, nhằm đạt đến giá trị nhỏ nhất bình phƣơng sai
số của các giá trị dự đoán với giá trị thực tế. Ở đây, sai số dƣợc xem là đại lƣợng
ngẫu nhiên.
Giả sử ta có:

Khi đó mục tiêu của phƣơng pháp là tối thiểu hóa hàm mục tiêu:
∑

21


CHƢƠNG III: CÁC KĨ THUẬT ÁP DỤNG TRONG HỆ GỢI Ý
3.1 Điểm TF.IDF
TF.IDF là phƣơng pháp xác định tần suất xuất hiện của một từ khóa trong một
văn bản trong tất cả các văn bản khác nhau. Để từ đó, đƣa ra đƣợc những từ khóa
đặc trƣng cho văn bản đó. Các từ khóa đặc trƣng cho văn bản là những từ khóa có
điểm TF.IDF cao nhất.
Khi đánh giá bằng điểm TF.IDF cho một văn bản, thì văn bản đó sẽ đƣợc ánh
xạ với một vec-tơ trong không gian chiều. Mỗi chiều sẽ đƣợc đại diện cho một từ
khóa nào đó. Không gian chiều bao gồm từ khóa.
Mỗi giá trị trong vec-tơ sẽ thể hiện mức độ liên kết giữa văn bản đó với từ
khóa tƣơng ứng. Giá trị này đƣợc gọi là “khối lƣợng” của văn bản với một từ khóa.
Khi “khối lƣợng” càng lớn thì từ khóa đó càng quan trọng với văn bản đó.
Giả sử:
- Tập các văn bản:
{

}

{

}

Tập các từ khóa:
khi đó, mỗi văn bản sẽ đƣợc biểu diễn bởi một vec-tơ chiều:

{
mà ở đó,

là “khối lƣợng” của từ khóa

}
đối với văn bản

.

Việc tính điểm TF.IDF cho các từ khóa trong một văn bản giúp ta mô tả dữ
liệu không có cấu trúc nhƣ văn bản thành dữ liệu có cấu trúc, vec-tơ “khối lƣợng”
các từ khóa. Bên cạnh đó, từ vec-tơ “khối lƣợng” này ta có thể tính độ tƣơng đồng
của hai văn bản bằng cách tính độ tƣơng đồng của hai vec-tơ.
TF là tần số xuất hiện của một cụm từ trong một văn bản
{

}

Trong đó:
f(t,d) là tần số xuất hiện của cụm từ t trong văn bản d .

22


{

} là tần số xuất hiện lớn nhất của cụm từ w bất kì nào đó.

IDF là tần số nghịch đảo tần số xuất hiện từ một cụm từ trong tập hợp các

văn bản có chứa cọm từ đó.
| |
}|

|{
trong đó:
| | là tổng số văn bản.

}| là số văn bản có xuất hiện cụm từ t.

|{

Điểm TF.IDF là tích của hai giá trị:

Từ giá trị này ta có thể thấy, một từ khóa xuất hiện nhiều trong duy nhất một
văn bản thì điểm TF.IDF của cụm từ này sẽ càng cao và có khả năng trở thành từ
khóa của văn bản đó.
Để đơn vị hóa vec-tơ “khối lƣợng” ta sử dụng công thức:
(
√∑|

|

)
(

)

3.2 Chỉ số tƣơng đồng Jaccard
Giả sử, đối tƣợng A gồm


phần tử, đối tƣợng B gồm

phần tử. Khi đó, giá trị

tƣơng đồng Jaccard đƣợc tính nhƣ sau:
|
|

|
|

trong đó:
|

| là số lƣợng phần tử chung của hai đối tƣợng A và B.

|

| là tổng số lƣợng phần tử khác nhau của hai đối tƣợng Avà B.

Chỉ số Jaccard này biểu diễn tốt cho dữ liệu dạng nhị phân khi chỉ có hai giá
trị A và B.

23


3.3 Độ tƣơng đồng cosine
Độ tƣơng đồng cosine đƣợc dùng để xác định mức độ tƣơng đồng của hai vectơ trong không gian bằng cách tính giá trị cosine của góc tạo bởi hai vec-tơ đó trong
không gian.

Theo công thức cosine cho hai vec-tơ, ta có:
̅̅̅̅̅

̅̅̅̅̅

∑
‖ ‖‖ ‖

∑

∑

Ta thấy, giá trị tƣơng đồng cosine này xem xét đến hƣớng của hai vec-tơ hơn
là độ lớn của chúng. Hai vec-tơ có cùng hƣớng sẽ có giá trị tƣơng đồng cosine là 1,
vuông góc thì giá trị này bằng 0 và nếu ngƣợc hƣớng thì sẽ là -1. Hoàn toàn không
phụ thuộc vào độ lớn vec-tơ.
Phƣơng pháp tính độ tƣơng đồng cosine này thƣờng đƣợc áp dụng trong
không gian nhiều chiều.
Ví dụ: Giả sử chúng ta nghiên cứu về việc phân loại các tài liệu văn bản. Tiêu
chí để phân loại là dựa vào tần suất xuất hiện của các cụm từ trong văn bản đó. Khi
đó, mỗi một cụm từ sẽ đại diện cho một hƣớng trong không gian. Có cụm từ thì mỗi
văn bản sẽ đƣợc ánh xạ vào một không gian n chiều. Sau khi có đƣợc vec-tơ đại
diện cho mỗi văn bản, ta có thể tìm ra các văn bản tƣơng đồng bằng cách tính độ
tƣơng đồng cosine giữa các văn bản. Các văn bản càng có nhiều từ giống nhau thì
(khả năng cao) độ tƣơng đồng của hai văn bản đó càng lớn.

24


3.4 Phƣơng pháp giảm số chiều không gian

3.4.1 Giới thiệu

Hình 5 - Dữ liệu trong không gian ba chiều được biểu diễn bởi mặt phẳng hai chiều [8]

Hình vẽ trên cho ta thấy sơ lƣợc mục đích của phƣơng pháp dimensionality
reduction. Dữ liệu đầu vào đƣợc cho dƣới dạng không gian ba chiều. Tuy nhiên, các
dữ liệu này đều nằm (hoặc gần) trên cùng một mặt phẳng. Nhƣ vậy, ta có thể biểu
diễn đầy đủ dữ liệu chỉ với việc biểu diễn mặt phẳng đó mà thôi.
Khi đó, nếu dữ liệu (hữu hạn) đƣợc cho trong không gian có số chiều là D, thì
ta có thể biểu diễn dữ liệu này dƣới dạng một ma trận có kích thƣớc D x D. Ta có
thể giảm số chiều của ma trận này bằng với giá trị hạng của ma trận đó. Vì hạng là
số hàng (cột) độc lập tuyến tính của ma trận. Tất cả các hàng (cột) khác đều có thể
biểu diễn thông quá các hàng (cột) độc lập tuyến tính này.
Ví dụ: Ta có các dữ liệu đƣợc cho trong không gian ba chiều và
đƣợc biểu diễn bởi ma trận:
|

|

Hiện tại, hệ cơ sở của ma trận trên là:
[

][

][

]

Tuy nhiên, ta nhận thấy:
[ ]


[ ]

[

]

25