Luận văn tốt nghiệp

Phương pháp lọc thư rác dựa trên CBR 1
Tóm tắt nội dung khóa luận
Khóa luận trình bày một số nội dung cơ bản nhất về thư rác (khái niệm, tác hại, các
hình thức phát tán thư rác ), tập trung định hướng tới các phương pháp lọc thư rác, đặc
biệt là phương pháp lọc dựa trên nội dung.
Trong các phương pháp lọc theo nội dung, khóa luận quan tâm mô tả, phân tích hệ
thống hệ thống Email Classification Using Examples (ECUE), một phương pháp lọc spam
dựa trên nội dung do Delany và Cunningham đề xuất năm 2004 [4]. Khóa luận mô tả kiến

nội dung dựa trên việc phân tích nội dung của email để phân biệt spam email và nonspam
email.
Tuy đã có nhiều biện pháp ngăn chặn thư rác nhưng số
lượng thư rác vẫn càng
ngày càng nhiều, tác hại gây ra càng lớn, cấu trúc nội dung của thư càng ngày càng thay
đổi tinh vi hơn để vượt qua các bộ lọc vì vậy cần có một hệ thống lọc có khả năng giải
quyết được vấn đề thư rác ngày càng tăng, nội dung, cấu trúc của thư ngày càng phức tạp
tinh vi hơn (concept drift).
Đã có nhiều hệ thống học máy lọc thư rác sử dụng các thuật toán Naïve bayes,
phân l
ớp dựa trên thống kê (Lewis and Ringuette 1994, Lewis 1998), Support Vector
Machines (Joachims 1998, Dumais et al. 1998) các phương pháp này đều cho kết quả lọc
khá tốt[17]. Tuy nhiên các mô hình này chưa giải quyết được vấn đề concept drift . Một
mô hình mới đã được Delany(2006) đề xuất, dựa trên hệ thống học máy sử dụng phương
3
pháp Case-Based Reasoning (CBR)(Riesbeck and Shank 1989)[17] có khả năng giải
quyết được concept drift. Phương pháp CBR, sử dụng các vấn đề trước đây đã được giải
quyết để đưa ra giải pháp cho vấn đề mới. Các vấn đề đã được giải quyết được lưu vào tập
dữ liệu dùng để huấn luyện gọi là case-base. Các case được biểu diễn dưới dạng véc tơ n
chiều, mỗi thành phần là một token đã
được trích chọn từ việc phân tích cú pháp, phân
tích từ tố của tài liệu (email). Các vector cũng chứa thêm một thành phần nữa chỉ lớp mà
tài liệu đó được phân (nonspam, spam).
Trong việc ứng dụng CBR để lọc thư rác có hai vấn đề chính là: làm thế nào để
quản lý được tập dữ liệu huấn luyện(case-base), chứa một số lượng lớn email của người
dùng. Thứ hai là làm thế nào để điều khiể
n được vấn đề concept drift. Để quản lý được dữ
liệu huấn luyện CBR áp dụng các luật để điều chỉnh case-base(case-base Editing), nhằm
đưa ra tập case-base chứa các case có khả năng dự đoán cao nhất cho việc phân lớp case
mới. Để giải quyết được concept drift CBR thực hiện việc lựa chọn lại các đặc trưng và

khó chịu cho người dùng, làm giảm tốc độ truyền internet và tốc độ xử lý của email
server, gây thiệt hại rất lớn về kinh tế. Chương này sẽ khái quát các vấn đề về khái niệm
thư
rác, ảnh hưởng của thư rác trong cuộc sống của chúng ta và các phương pháp ngăn
chặn thư rác.
1.1 Một số khái niệm cơ bản
1.1.1 Định nghĩa thư rác.
Hiện nay vẫn chưa có một định nghĩa hoàn chỉnh, chặt chẽ về thư rác. Có quan
điểm coi thư rác là những thư quảng cáo không được yêu cầu (Unsolicited Commercial
Email-UCE), có quan điểm rộng hơn cho rằng thư rác bao gồm thư qu
ảng cáo, thư quấy
rối, và những thư có nội dung không lành mạnh (Unsolicited Bulk Emai -UBE). Sau đây
sẽ đưa ra một định nghĩa thông dụng nhất về thư rác và giải thích các đặc điểm của nó để
phân biệt thư rác với thư thông thường [18,19]:
Thư rác (spam mail) là những bức thư điện tử không yêu cầu, không mong muốn
và được gửi hàng loạt tới người nhận.
5
Một bức thư nếu gửi không theo yêu cầu có thể đó là thư làm quen hoặc thư được
gửi lần đầu tiên, còn nếu thư được gửi hàng loạt thì nó có thể là thư gửi cho khách hàng
của các công ty, các nhà cung cấp dịch vụ. Vì thế một bức thư bị coi là rác khi nó không
được yêu cầu, và được gửi hàng loạt.
Tuy nhiên yếu tố quan trọng nhất để phân biệt thư rác với thư thông thường là nội
dung th
ư. Khi một người nhận được thư rác, người đó không thể xác định được thư đó
được gửi hàng loạt hay không nhưng có thể xác định được đó là thư rác sau khi đọc nội
dung thư. Đặc điểm này chính là cơ sở cho giải pháp phân loại thư rác bằng cách phân
tích nội dung thư.
1.1.2 Phân loại thư rác
Có rất nhiều cách phân loại thư rác[18] .
- Dựa trên kiểu phát tán thư rác: Tính tớ

kết luận của nhóm hợp tác chống thư rác gồm các công ty AOL, Bell Canada, Cigular
Wireless, EarthLink, France Telecom, Microsoft, Verizon, và Yahoo. Microsoft và AOL
cho biết hai hãng này trung bình mỗi ngày chặn gần 5 tỷ thư rác. Ước tính, cứ 9 trong 10
email sử dụng dịch vụ MSN Hotmail của Microsoft là thư rác[18].
Tại Việt Nam, tình hình thư rác cũng đang rất phức t
ạp. Công ty Điện toán và
Truyền số liệu (VDC) - ISP lớn nhất Việt Nam - cho biết, thư rác hiện nay chiếm phần
lớn lưu lượng email qua hệ thống máy chủ thư của ISP này.
Các thư phàn nàn gửi đến ISP nếu không giải quyết, các khách hàng của ISP đó có
thể bị liệt vào danh sách đen, không gửi được email ra địa chỉ nước ngoài. Một số ISP cho
biết, cuối năm ngoái, khách hàng của nhiều ISP ở Việt Nam th
ường xuyên bị tê liệt do bị
liệt vào danh sách đen. Mỗi lần thoát ra khỏi danh sách này ISP phải mất khoảng 40 USD.
Tại trang web Spamhaus.org (tổ chức theo dõi các nguồn gửi thư rác), có lần vnn.vn đã có
trong danh sách top 10 ISP cung cấp nhiều rác nhất.
Không chỉ gây thiệt hại về tiền bạc, thư rác còn làm giảm hiệu quả làm việc, gây
stress, tiêu tốn thời gian của nhân viên Những điều này cũng đồng nghĩa với việc, năng
suất lao
động giảm, ảnh hưởng tới tình hình kinh doanh và doanh thu của công ty.
Một số lời khuyên cho người dùng thư điện tử:
 Yêu cầu và đòi hỏi nhà chức trách phải đưa ra những luật lệ nghiêm cấm thư
rác và có hình phạt đích đáng cho kẻ cố tình gửi thư rác.
 Mỗi người dùng nên tạo nhiều địa chỉ email, với mục đích khác nhau nên
dùng địa chỉ email khác nhau.
 Hạn chế
việc đăng kí các dịch vụ vô ích: nên tìm hiểu kĩ thông tin về dịch
vụ trước khi cung cấp địa chỉ email của mình.
 Kích hoạt các dịch vụ chống thư rác của ISP.
 Cài đặt một số chương trình xử lý thư trong máy tính cá nhân để xóa thư rác
ngay khi chuyển về máy.

(2000), “Luật Khống chế thư rác truyền qua đường điện thoại vô tuyến” (2000) , “Luật
Chống thư rác” (2001).
Mười năm gần đây, Liên minh Châu Âu cũng đã ban hành một số chỉ lệnh, đưa ra
các quy phạm và chỉ dẫn đối với các vấn đề thương mại điện tử, thông tin điện t
ử, bảo hộ
dữ liệu.
Trong các chỉ lệnh nói trên, có không ít các qui định có liên quan mật thiết, thậm
chí là trực tiếp với phục vụ và sử dụng thư điện tử như “Chỉ lệnh Bảo vệ dữ liệu cá nhân ở
Châu Âu”, “Chỉ lệnh về thông tin điện tử và bảo mật dữ liệu” Ngày 12 tháng 7 năm
2002, Nghị Viện Liên minh Châu Âu đã thông qua “Chỉ lệnh Bảo mật riêng t
ư và Thông
tin điện tử trong Liên minh Châu Âu”. Chỉ lệnh quy định: Từ 31 tháng 10 năm 2003,
trong phạm vi Liên minh Châu Âu, nếu chưa được người nhận đồng ý trước, không được
gửi thư điện tử thương mại hay nhằm mục đích tuyên truyền cho cá nhân. Tiếp theo sau
8
khi Liên minh Châu Âu đưa ra các qui định về phục vụ và sử dụng thư điện tử, các nước
thành viên Liên minh Châu Âu, như Italia, Anh, Đan Mạch, Tây Ban Nha đều đã ban
hành quy phạm pháp luật trong nước quy định hành vi cung cấp và sử dụng thư điện tử,
ngăn chặn sự tràn ngập của thư rác.
Tại Việt Nam vấn đề thư rác bắt đầu nhận được sự quan tâm từ phía các cơ quan có
trách nhiệm. Bộ
Thương mại đang soạn thảo Thông tư quản lý hoạt động quảng cáo
thương mại trên các phương tiện điện tử. Trên trang báo điện tử của bộ viễn thông, Bà Lại
Việt Anh, Trưởng Phòng chính sách, Vụ Thương mại điện tử, Bộ Thương mại, nhận xét:
mục tiêu của Thông tư này trước mắt tập trung quản lý ba hình thức quảng cáo đang bức
xúc: thư
điện tử, tin nhắn điện thoại di động và quảng cáo trên trang thông tin điện tử.
1.2.2 Lọc thư rác dựa trên địa chỉ IP
Phương pháp lọc thư rác thông qua địa chỉ IP là phương pháp đơn giản và được sử
dụng sớm nhất trong công cuộc chống thư rác. Dựa vào địa chỉ IP của người gửi để xác

1.2.3 Lọc dựa trên chuỗi hỏi/đáp (Challenge/Response filters)
Đặc trưng của phương pháp này là khả năng tự động gửi thư hồi đáp cho người gửi
để yêu cầu mộ
t số hành động chắc chắn về việc gửi thư của họ. Chương trình kiểm tra này
được đặt tên là “Turing Test” sau một vài kiểm tra được nghĩ ra bởi nhà toán học người
anh tên là Alan Turing.
Trong một vài năm gần đây xuất hiện của một vài dịch vụ Internet tự động xử lý
hàm Challenge/Response này cho người dùng, chương trình yêu cầu người gửi thư phải
vào website của họ và trả lời một số câu hỏi
để chắc chắn về e-mail mà người này đã
gửi.Việc này chỉ được yêu cầu trong lần gửi thư đầu tiên.
Đối với một số người dùng có lượng thư trao đổi thấp, hệ thống đơn lẻ này có thể
chấp nhận được như một phương pháp hoàn hảo để loại trừ hoàn toàn thư rác từ hòm thư
của họ.
1.2.4 Phương pháp lọc dựa trên mạ
ng xã hội.
Các nghiên cứu gần đây đã bắt đầu khai thác thông tin từ mạng xã hội cho việc xác
định thư rác bằng cách xây dựng một đồ thị (các đỉnh là địa chỉ email, cung được thêm
vào giữa 2 node A và B nếu giữa A và B có sự trao đổi thư qua lại). Người ta đã sử dụng
một số tính chất đặc trưng của mạng xã hội để xây dựng một công cụ lọc thư rác [18].
Đầ
u tiên, người ta phân đồ thị thành các thành phần con rồi tính độ phân cụm cho
từng thành phần này. Mỗi thành phần con là một đồ thị mạng xã hội của một node, bao
gồm tất cả các node xung quanh là “node hàng xóm” (các node có cung liên kết với node
này) và những cung liên kết giữa các node hàng xóm này với nhau. Nếu thành phần nào
có độ phân cụm thấp thì node tương ứng với thành phần đó là một địa chỉ gửi thư rác.
Trong thành phần mạng xã hội của những node g
ửi thư rác, những node hàng xóm của nó
thường là những node rất ngẫu nhiên, không có mối quan hệ (không có sự trao đổi email
qua lại với nhau) nên độ phân cụm của mạng xã hội của những node này rất thấp. Ngược

bằng khóa bí mật. Chữ ký được thêm vào trường Domainkey_signature.
Ví dụ:
DomainKey-Signature: a=rsa-sha1 s=brisbane;
d=example.net;c=simple; q=dns; b=dzdVyOfAKCd…ZHRNiYzR;
Hình vẽ dưới đây (hình1) mô tả hệ thống gửi và nhận thư, ch
ỉ ra vị trí sử dụng
domainkeys.

Hình 1.1 Khung ID người gửi được thi hành trên MTA [6]
11
Domainkeys yêu cầu cả bên gửi Mail Transfer Agent(MTA) và bên nhận MTA
thực hiện domainkey. Việc xác minh của Domainkeys_signature có thể cũng được thực
hiện tại Domainkeys_enabled của Mail User Agent (MUA).
Khi server nhận được tên của domain từ mail gốc (string-domainkey) thì bộ
selector thực hiện tra cứu DNS. Dữ liệu trả về chứa khóa công khai của domain đó. Người
nhận có thể giải mã giá trị băm chứa trong trường tiêu đề và đồng thời tính lại giá trị băm
cho phần thân của mail nh
ận được. sau đó so sánh hai giá trị này nếu giống nhau chứng tỏ
mail được gửi là thật, đảm bảo tin cậy nếu không là mail không đáng tin.
Ưu điểm:

- xác định nguồn gốc domain của email một cách rõ ràng, sẽ hiệu quả hơn nếu kết
hợp với sử dụng danh sách đen và danh sách trắng. Giúp dễ dàng phát hiện ra sự tấn công
phising.
- Loại bỏ những email giả mạo tại phần mềm email người dùng cuối (mail user
agents) hoặc bởi ISP’s mail transfer agents.
- Theo dõi việc lạm dụng domain của những cá nhân một cách dễ dàng hơn.
Khả năng tươ
ng thích:
Domainkeys tương thích với cấu trúc hiện tại của email. Trong trường hợp đặc

t dựa trên xác định tính đúng đắn của IP. IBM không cố gắng đạt tới
hệ thống FairUCE hoàn hảo, nhưng là một cơ cấu đơn giản hiệu quả để xác định tính
đúng đắn.
Tất cả những kỹ thuật nêu ra ở trên nhằm cải tiến vấn đề an toàn cho giao thức
SMTP. Kỹ thuật nổi bật là Domainkeys và Identified Internet Mail. IIM hiện tại chỉ
được đưa ra với phiên bản alpha. Domainkeys đã đượ
c đưa vào sử dụng, nhưng chỉ được
thực hiện bởi 2 nhà sản xuất. Vì thế tỉ lệ chấp nhận của những đề xuất này là rất thấp. Tuy
nhiên một chuẩn mới Domainkeys Identified Mail, sự kết hợp của hai kỹ thuật
Domainkeys và IIM đang được phát triển làm thay khả năng chấp nhận của chúng được
tăng lên
1.2.6 Phương pháp lọc nội dung
Phương pháp lọc n
ội dung để phân loại thư rác đã và đang được quan tâm, nghiên
cứu và ứng dụng nhiều nhất. Phương pháp này dựa vào nội dung và chủ đề bức thư để
phân biệt thư rác và thư hợp lệ. Phương pháp này có ưu điểm đó là chúng ta có thể dễ
dàng thay đổi bộ lọc để nó có thể lọc các loại thư rác cho phù hợp. Nhược điểm của
phương pháp này là: do biết được cách thứ
c lọc nội dung nên các spammer luôn luôn thay
đổi hình thức nội dung của thư rác.
Phần dưới đây trình bày những nét cơ bản nhất về các phương pháp lọc nội dung
thông dụng [18,19].
Lọc dựa trên các dấu hiệu nhận biết

Trước tiên, tạo ra các địa chỉ email để bẫy thư rác, gọi là honeypots, phương pháp
này được nghiên cứu phát triển nhiều vào năm 2003. Honeypots chứa các địa chỉ sao cho
không bao giờ thư bình thường có thể gửi đến. Do đó thư gửi đến bẫy địa chỉ này ta có thể
coi đó là thư rác.
Sau đó hệ thống so sánh thư mới đến với thư đã được bẫy. Sự so sánh dựa trên dấu
hi

— Cơ sở dữ liệu về đặc trưng chỉ được nạp khi các từ nằm trong danh sách
đen hoặc trắng. Nếu nằm trong danh sách đen thì đặt là -1, trong danh sách
trắng là +1, các trường hợp còn lại đặt là 0.
— Luật tổ hợp là : “Điểm mới = Điểm cũ + trọng số đặc trưng”
— Ngưỡng lọc cuối cùng là : Nếu Điểm mới > 0 là thư hợ
p pháp, nếu < 0 là
thư rác.
Như vậy bộ lọc thực hiện chấm điểm các từ trong danh sách đen và các từ trong
danh sách trắng bằng nhau. Một số cải biên của phương pháp này là đánh trọng số cho các
từ trong danh sách đen cao hơn trong danh sách trắng hoặc ngược lại.
Lọc thư rác dựa vào phương pháp heuristic.

Cách thức hoạt động của phương pháp này là dựa trên việc xác định những từ đặc
trưng thuộc về thư rác, từ đặc trưng thuộc về thư hợp pháp, sau đó phát hiện những đặc
trưng đó trong thư mới nhận để đưa ra kết luận thư đó là thư rác hay thư hợp lệ.
Người ta đánh trọng số cho các đặc trưng trên bằng tay ho
ặc bằng thuật toán và lập
một ngưỡng để phân loại thư. Nếu bức thư có trọng số lớn hơn ngưỡng quy định sẽ bị coi
là thư rác.
Các chương trình lọc thư rác sử dụng phương pháp này có hiệu suất khác nhau. Vì
mỗi chương trình sử dụng một luật lọc khác nhau.
Một số chương trình lọc theo phương pháp này như hệ thống chấm điểm cho email
sử
dụng phương pháp hueristic của mail server Mdaemon, SpamAssassin hay SpamGuard
của Yahoo.
Phương pháp này có ưu điểm là dễ cài đặt và hiệu suất chặn thư rác khá cao khi
xây dựng được hệ thống luật tốt. Nhược điểm chính của phương pháp này là tỉ lệ chặn
nhầm thư hợp pháp cũng khá lớn 0.5%. Phương pháp này không linh hoạt do các luật
được xây dựng luôn chậm hơn sao với sự biến đổi của từ ngữ trong thư rác.
Phương pháp này thường được áp dụng cho các bộ lọc thư ở server.

ng lọc thư rác ECUE mới do Delany đề xuất và đã xây dựng
thử nghiệm thành công.
Lọc thư rác dựa trên thuật toán bayes
[8,15]:
Coi mỗi email được biểu diễn bởi một vectơ thuộc tính đặc trưng
x
r
= (x
1
, x
2
,…,x
n
). với (x
1
, x
2
,…,x
n
) là các giá trị thuộc tính X
1
, X
2
, …, X
n
tương
ứng trong không gian đặc trưng (space model) . Ta sử dụng giá trị nhị phân 0 và 1 để mô
tả email đó có đặc điểm X
i
hay không, giả xử nếu email đó có đặc điểm X

kCxXPkCP
cCxXPcCP
xXcCP
r
r
r
r
r
r
r
(1)
Để đơn giản khi tính P(
CX |
r
) ta phải giả sử X
1
, X
2
,…,X
n
là độc lập. Khi đó biểu
thức (1) tương đương với biểu thức sau:
16
∑
∏
∏
∈
=
=
===

===
},{},1,0{
)()(
),(
log),(
legitimatespamcx
cXPxXP
cCxXP
cCxXPMI

Một email được coi là spam nếu:

λ
>
==
==
)|(
)|(
xXlegitimateCP
xXspamCP
r
r
r
r
(2)
Giả sử các thuộc tính X
i
là độc lập khi đó ta có:
P(C=spam|
xX

CASE-BASED REASONING

Đã có nhiều hệ thống học máy lọc thư rác sử dụng các thuật toán Naïve bayes,
phân lớp dựa trên thống kê (Lewis and Ringuette 1994, Lewis 1998), Support Vector
Machines (Joachims 1998, Dumais et al. 1998) các phương pháp này đều cho kết quả lọc
khá tốt[4]. Tuy nhiên các mô hình này chưa giải quyết được vấn đề concept drift . Một mô
hình mới đã được Delany(2006) đề xuất, dựa trên hệ thống học máy sử dụng phương pháp
Case-Based Reasoning (CBR)(Riesbeck and Shank 1989)[17] có khả năng giải quyết
được concept drift. Phương pháp CBR, sử dụng các vấ
n đề trước đây đã được giải quyết
để đưa ra giải pháp cho vấn đề mới. Các vấn đề đã được giải quyết được lưu vào tập dữ
liệu dùng để huấn luyện gọi là case-base. Các case được biểu diễn dưới dạng véc tơ n
chiều, mỗi thành phần là một token đã được trích chọn từ việc phân tích cú pháp, phân
tích từ tố của tài liệu (email). Các vector cũng chứ
a thêm một thành phần nữa chỉ lớp mà
tài liệu đó được phân (nonspam, spam). Trình bày về cấu trúc Case-based
Reasoning(CBR), chu trình thực hiện của CBR Retrieve, Reuse, Revise, Retain; sự biểu
diễn case; việc trích chọn các đặc trưng, biểu diễn đặc trưng; Và đưa ra ưu điểm của CBR
trong việc giải quyết vấn đề concept; ứng dụng CBR trong lĩnh vực phân lớp Textual
CBR.
2.1 Case-based Reasoning.
Case-Base Reasoning(CBR) (Smyth và McKenna 1998) là phương pháp kĩ thuật
giải quyết vấ
n đề, thực hiện giải quyết các vấn đề mới bằng việc sử dụng lại những giải
pháp đã có của những vấn đề trước. Những vấn đề trước đây được mã hóa gọi là các case,
mỗi case chứa những thuộc tính đặc trưng của vấn đề đó và giải pháp cho nó. Một tập các
case được gọi là case-base, là kiến thức nền tảng đã qua trả
i nghiệm, case-base được sử
dụng cho quá trình đưa giải pháp cho vấn đề mới[17].
CBR thực hiện theo một chu trình gồm các tiến trình sau (theo Aamodt and Plaza


Hình 2.2: Tiến trình của CBR (Cunningham, 1994)[17]
Thông thường mô tả của một case chứa một tập các đặc trưng. Những đặc trưng
này được xác định qua một quá trình kiểm tra kiến thức: hệ chuyên gia phỏng vấn trong
lĩnh vực mà nó liên quan đến, việc đưa ra những yêu cầu và việc sử dụng các phương
pháp kĩ thuật tập hợp dữ liệu. Ví dụ như một vấn đề về một chương trình quản lý quỹ tín
d
ụng. Một khách hàng tiếp cận với ngân hàng và yêu cầu vay tiền. Người quàn lý ngân
hàng sẽ quyết định có nên cho vay hay không như thế nào? Vấn đề này được thực hiện
bằng cách sử dụng hệ thống các tri thức hay hệ thống dựa trên các luật (còn gọi là hệ
chuyên gia). Trong trường hợp cho ứng dụng này case biểu diễn một sự trải nghiệm, nó
nên biểu diễn những đặc trưng của ứng dụng đẻ
xác định nên hay không nên cho khách
hàng vay tiền. Trong case sẽ phải chứa số lượng tiền mà khách hàng muốn vay, thời hạn
trả tiền, giới tính của khách hàng, tình trạng hôn nhân, tuổi, tình trạng và những chi tiết
20
mô tả việc làm như tiền lương, vị trí đảm trách…mục đich vay tiền làm gì, và có thể thêm
một vài đặc trưng khác nữa.

Bảng 2.1: Biểu diễn các case, người vay tiền ngân hàng.[17]
2.1.2 Case Retrieval
Quá trình lấy các case gồm việc tìm kiếm các case có độ tương đồng cao nhất với
case hiện tại, những case này có tiềm năng cao cho việc dự đoán cho case mới.
Kolodner(1992) khẳng định việc tìm các case phù hợp chính là phần quan trọng nhất của
case-base reasoning[17].
Trong CBR có hai phương thức chính để lấy các case có độ tương đồng cao với
case mới từ case-base, đó là sử dụng thuật toán cây quy
ết định và thuật toán k-Nearnest
Neighbour(k-NN). Thuật toán cây quyết định (Wess et al .1994) thực hiện phân tích các
đặc trưng để tìm ra đặc trưng nào là tốt nhất cho việc so sánh các case với nhau. Các đặc

thể hiện độ quan trọng của IE.
- Similarity Arcs kết nối với các IE cùng tham chiếu đến một số các thuộc tính, và
được đánh trọng số dựa vào độ tương đồng giữa các IE nối với nhau. Hình 2.3: Mô hình CRR[17]

22
Hoạt động của CRR:
Các case mới được kích hoạt bằng cách kết nối nó vào mạng qua một tập các
Relevance Arc và sự kích hoạt này sẽ được lan rộng khắp mạng. Mỗi một case node có
điểm số kích hoạt tương ứng với độ tương đồng của nó với case mới. Những case node có
điểm số kích hoạt cao sẽ là những case có độ tương đồng cao với case mới. CRNs khai
thác được lợi ích của sự dư thừa
đặc trưng và chúng có thể bỏ qua các giá trị đặc trưng bị
lỗi hoặc vắng mặt.
2.1.3 Reuse
Trong trường hợp mà ở đó các case đã được lấy về giống hệt case mới, khi đó giải
pháp của các case lấy về sẽ áp dụng cho case mới. Trong các trường hợp khác, giải pháp
cũ cần được thay thế để tương ứng với case mới, tiến trình thực hiện sự thay th
ế được gọi
là adaptation. Một vài kĩ thuật adaptation được sử dụng trong CBR được mô tả theo hình
2.4 Hình 2.4: Quy trình Adaptation(Wilke and Bergmann 1998, Wilke et al. 1998)[17]
- Đơn giản nhất là null adaptation: Không cần adaption, giải pháp đưa ra được áp
dụng trực tiếp cho case mới, trường hợp này thường gặp trong bài toán phân lớp.
- Transformational adaptation: Sử dụng một tập các luật để điều chỉnh những giải
pháp đã thu được trên cơ sở sự khác nhau giữa những đặc trưng của case mới và case lấy

base.(Smyth and Cunningham 1996). Vì vậy việc điều chỉnh case-base cho thích hợp là
r
ất cần thiết, tôi sẽ mô tả chi tiết trong phần 3.3 dưới đây. Điểm quan trọng trong việc
điều chỉnh case-base (case-base editing) là giảm bớt kích cỡ của case-base trong khi đó
phải duy trì được hiệu suất thực hiện.
2.1.5 Những ưu điểm của CBR
Case-based reasoning có nhiều ưu điểm hơn so với những phương pháp kĩ thuật
học máy khác. CBR là một phương pháp học máy do Aha phát triển nă
m 1997. Phương
pháp này có ưu điểm đó là những mẫu huấn luyện mới có thể được thêm vào một cách rất
dễ dàng. Sự hạn chế của việc học này là tất cả các mẫu được sử dụng cần phải lưu trữ và
hệ thống có thể truy cập được mỗi khi có yêu cầu. Để thực hiện các tiến trình xử lý khi có
yêu cầu đòi hỏi tính toán nhiều. Tuy nhiên tốc
độ phát triển của phần cứng máy tính rất
nhanh do đó sự hạn chế này dễ dàng khắc phục được.
2.1.6 Ứng dụng phương pháp CBR vào việc phân lớp văn bản (Textual CBR)
Một lĩnh vực trong nghiên cứu CBR đó là lọc spam Textual Case-Based
Reasoning(TCBR)(Lenz et 1998). TCBR là một lĩnh vực thuộc CBR với các case là tài
liệu dạng text. Có rất nhiều lĩnh vực ứng dụng TCBR như: trợ giúp trên bàn giấy (hepl
desks) (Lenz 1998, Lenz 1998), hỗ trợ khách hàng (customer support) (Gupta and Aha
24
2004), người dạy học thông minh (intelligent tutoring) (Ashley and Aleven 1991) and
luật sư (law ) (Bruninghaus and Ashley 2001, 2003).
TCBR dựa trên ưu điểm của việc trích chọn thông tin (IR- Information Retrieval)
(Baeza-Yates and Ribeiro-Neto 1999). IR lấy một tập các mục (đó là các từ thông
thường) nằm trong tập tài liệu thu được và dựa trên thống kê để đánh chỉ số cho mục đó,
ví dụ như: xác suất hay tần suất xuất hiện của từ đó trong tài liệu. Tần suất xuất hiện của
mục đó trong tài liệu cũng được sử dụng để xác định độ quan trọng của nó và độ quan
trọng này được sử dụng để tính toán độ tương đồng giữa các tài liệu với nhau. Ý tưởng
này đã được áp dụng trong TCBR. Trong TCBR, những case phải được trích ra từ những