Đại Học Quốc Gia Tp. Hồ Chí Minh
TRƯỜNG ĐẠI HỌC BÁCH KHOA

NGUYỄN NGỌC BÌNH PHƯƠNG

XÂY DỰNG GIẢI THUẬT XÁC ĐỊNH
ĐỘ TƯƠNG TỰ GIỮA HAI TÌNH HUỐNG
DỰA VÀO BỘ THUỘC TÍNH ĐỘNG
Chun ngành:

Khoa học Máy tính

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 06 năm 2008


CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC BÁCH KHOA
ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH

Cán bộ hướng dẫn khoa học: TS. Võ Văn Huy

Cán bộ chấm nhận xét 1: PGS. TS. Dương Tuấn Anh

Cán bộ chấm nhận xét 2: TS. Vũ Thanh Nguyên

Luận văn thạc sĩ được bảo vệ tại:

HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ
TRƯỜNG ĐẠI HỌC BÁCH KHOA

Ngày 06 tháng 09 năm 2008

ii


ĐẠI HỌC QUỐC GIA TP. HCM

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM

TRƯỜNG ĐẠI HỌC BÁCH KHOA

Độc Lập - Tự Do - Hạnh Phúc

----------------

---oOo--Tp. HCM, ngày 09 tháng 09 năm 2008

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên: Nguyễn Ngọc Bình Phương

Giới tính: Nam

Ngày, tháng, năm sinh: 17/02/1981

Nơi sinh: Tiền Giang

Chun ngành: Khoa học Máy tính

Khóa: K15


1. TÊN ĐỀ TÀI: Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa
vào bộ thuộc tính động
2. NHIỆM VỤ LUẬN VĂN:
− Sử dụng phương pháp CBR (Case-Based Reasoning) xây dựng giải thuật xác
định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động. Độ tương
tự phải được tổng hợp từ các kiểu biến khác nhau.
− Hiện thực một chương trình minh họa.
3. NGÀY GIAO NHIỆM VỤ: 15/01/2007
4. NGÀY HOÀN THÀNH NHIỆM VỤ: 30/06/2008
5. HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN: TS. Võ Văn Huy
Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thông qua.
CÁN BỘ HƯỚNG DẪN

CHỦ NHIỆM BỘ MÔN
QUẢN LÝ CHUYÊN NGÀNH

TS. Võ Văn Huy

TS. Đinh Đức Anh Vũ

iii


LỜI CẢM ƠN
Xin được gửi lời cảm ơn chân thành đến:
9 Thầy Võ Văn Huy đã tận tình hướng dẫn trong suốt thời gian thực
hiện luận văn;
9 Các thầy cô trong khoa Công nghệ Thông tin, trường Đại học Bách
Khoa TP. Hồ Chí Minh đã cung cấp những kiến thức quý báu;

9 Các bạn đồng nghiệp đã gánh vác một phần cơng việc hằng ngày;
9 Gia đình và bạn bè thân thiết đã ln quan tâm, động viên khích lệ
và sẵn sàng giúp đỡ.
Nguyễn Ngọc Bình Phương

iv


TÓM TẮT
CBR là phương pháp lập luận mạnh được ứng dụng rộng rãi trong
nhiều lĩnh vực công nghiệp, quản lý, y học, v.v... CBR lập luận dựa
vào độ đo tương tự giữa các tình huống, thơng thường là một hàm của
bộ thuộc tính mơ tả đặc trưng tình huống. Trong các lĩnh vực như tư
vấn quản lý, các tình huống có bộ thuộc tính đặc trưng khó có thể xác
định chính xác một lần, phương pháp CBR dựa vào bộ thuộc tính tĩnh
bị hạn chế trong việc thể hiện đặc trưng của tình huống. Luận văn này
nghiên cứu một độ đo tương tự linh hoạt, có khả năng diễn tả được các
thuộc tính động cho các tình huống phức tạp. Cơ sở của giải pháp là
nguyên lý “cục bộ-toàn cục” với sự hỗ trợ của bộ trọng số, hàm gộp,
và độ đo tương tự cho các kiểu thuộc tính đặc thù như thuộc tính dạng
tập hợp, dạng mờ, dạng thơ (so với thuộc tính dạng số hay dạng ký
hiệu truyền thống). Luận văn cũng đã hiện thực bài toán CBR dựa vào
bộ thuộc tính động trên mơi trường web. Thử nghiệm chương trình
được thực hiện với bài tốn tư vấn ước lượng chi phí phần mềm và kết
quả cho thấy giải thuật hoạt động tương đối hiệu quả. Bài toán đã được
giải ở mức tiếp cận, có thể được phát triển hơn trong tương lai.
Từ khóa: CBR, lập luận dựa theo tình huống, độ tương tự, bộ thuộc
tính động

v



DANH MỤC HÌNH
Hình 1.1 Kiểu giải quyết vấn đề dựa theo tình huống ......................................................................... 4
Hình 2.1 Hệ thống CBR ....................................................................................................................... 9
Hình 2.2 Chu trình CBR với bốn “RE” [Aamodt & Plaza, 1994]..................................................... 10
Hình 2.3 Chu trình CBR với năm “RE” [Finnie & Sun, 2003] ......................................................... 11
Hình 2.4 Chu trình CBR với sáu “RE” [Watson, 2001] .................................................................... 12
Hình 2.5 Chu trình CBR với sáu “RE” [Berghofer & Iglezakis, 2001] ............................................ 12
Hình 2.6 Bản ghi tình huống tư vấn cho một doanh nghiệp.............................................................. 18
Hình 2.7 Q trình trích lục tình huống [Pal & Shiu, 2004] ............................................................. 20
Hình 2.8 Cách tìm láng giềng gần nhất của tình huống mới ............................................................. 22
Hình 2.9 Cây quyết định hồn chỉnh.................................................................................................. 23
Hình 2.10 Q trình tinh chỉnh tình huống [Pal & Shiu, 2004]......................................................... 24
Hình 2.11 Một số lĩnh vực ứng dụng CBR [Leake, 1996] ................................................................ 27
Hình 2.12 Hình chóp kiến thức [Bergmann, 2002] ........................................................................... 27
Hình 2.13 So sánh nỗ lực cho các cách tiếp cận CBR khác nhau [Bergmann et al., 2003].............. 30
Hình 2.14 Một ví dụ về lối biểu diễn tình huống dựa trên “thuộc tính-giá trị”................................. 30
Hình 3.1 Kết quả của một truy vấn dải cho đối tượng truy vấn q ..................................................... 48
Hình 3.2 Kết quả của một truy vấn láng giềng gần nhất cho đối tượng truy vấn q........................... 49
Hình 3.3 Kết quả của một truy vấn k-láng giềng gần nhất cho đối tượng truy vấn q và k = 5 ......... 50
Hình 3.4 Bốn bộ chứa kiến thức trong một hệ thống CBR [Richter, 1995]...................................... 57
Hình 3.5 Phép biến đổi CBR.............................................................................................................. 58
Hình 3.6 Ngữ cảnh học phép đo độ tương tự của Stahl [2001; 2003]............................................... 59
Hình 4.1 Sơ đồ hệ thống quản lý các tình huống tư vấn.................................................................... 63
Hình 4.2 (Quy trình 1) Quy trình đưa một tình huống mới vào kho (được thực hiện bởi người quản
trị hệ thống với sự trợ giúp của chuyên gia lĩnh vực)......................................................................... 65
Hình 4.3 (Quy trình 2) Quy trình tạo một tình huống truy vấn (được thực hiện bởi người dùng) ... 67
Hình 4.4 Phân loại kiểu thuộc tính..................................................................................................... 68
Hình 4.5 Một ví dụ về thuộc tính dạng ký hiệu phân cấp.................................................................. 71

Hình 4.6 Ví dụ về số mờ và khoảng mờ ............................................................................................ 74
Hình 4.7 Ví dụ về thuộc tính dạng ngơn ngữ mờ .............................................................................. 75
Hình 4.8 Các tiêu chí được so sánh từng cặp theo độ ưu tiên ........................................................... 78
vi


Hình 4.9 Trọng số của các tiêu chí sau khi tính tốn......................................................................... 78
Hình 4.10 (Quy trình 3) Quy trình đánh lại bộ trọng số để cải thiện kết quả trích lục (được thực hiện
bởi người quản trị hệ thống) ............................................................................................................... 82
Hình 4.11 Ý tưởng sử dụng giải thuật suy giảm độ dốc để tối ưu bộ trọng số [Stahl, 2003] ........... 84
Hình 5.1 Thiết kế mơ hình tình huống với phần mềm CBR-Works.................................................. 87
Hình 5.2 Thiết kế mơ hình tình huống tĩnh bằng cơ sở dữ liệu quan hệ (SQL Server 2000) ........... 87
Hình 5.3 Một kiến trúc điển hình cho hệ thống CBR dựa trên web [Hayes et al., 1998] ................. 88
Hình 5.4 Lược đồ cơ sở dữ liệu quan hệ: phần quản lý tình huống .................................................. 89
Hình 5.5 Giao diện web thiết kế mơ hình tình huống cho bài tốn tư vấn ước lượng chi phí phần
mềm..................................................................................................................................................... 92
Hình 5.6 Giao diện thử nghiệm các phép đo cục bộ mặc định .......................................................... 93
Hình 5.7 Năm dạng của hai khoảng mờ x và y .................................................................................. 95
Hình 5.8 Lược đồ cơ sở dữ liệu quan hệ: phần quản lý bộ từ khóa đặc thù lĩnh vực........................ 97
Hình 5.9 Giao diện trích lục các tình huống tương tự đối với một tình huống truy vấn................... 98
Hình 5.10 Kết quả trích lục gồm các tình huống với độ tương tự được sắp theo thứ hạng giảm dần
............................................................................................................................................................. 99
Hình 5.11 Xây dựng bộ trọng số ban đầu bằng phương pháp AHP .................................................. 99
Hình 5.12 Xấp xỉ độ hữu dụng theo độ tương tự phần giải pháp .................................................... 100
Hình 5.13 Sai lệch về độ tương tự giảm xuống sau khi tối ưu bộ trọng số ..................................... 101
Hình 6.1 So sánh độ tương tự dựa trên thuộc tính (a) và khơng dựa trên thuộc tính (b) ................ 104

vii



DANH MỤC BẢNG BIỂU
Bảng 1.1 So sánh các kỹ thuật/phương pháp giải quyết vấn đề [Watson, 1997] ................................ 3
Bảng 2.1 So sánh CBR, RBR, và MBR [Conradie, 2000]................................................................. 14
Bảng 2.2 Bốn tình huống cho vay ...................................................................................................... 22
Bảng 2.3 Tình huống cho vay mới ..................................................................................................... 22
Bảng 2.4 So sánh trích lục láng giềng gần nhất và trích lục quy nạp [Watson, 1997]...................... 23
Bảng 3.1 Các phép đo khoảng cách kinh điển [Belanche, 2000] ...................................................... 41
Bảng 3.2 Độ tương tự cho dữ liệu nhị phân [Pękalska & Duin, 2005].............................................. 51
Bảng 3.3 Độ không tương tự cho dữ liệu nhị phân [Pękalska & Duin, 2005] .................................. 52
Bảng 3.4 Độ không tương tự cho dữ liệu dạng số thực [Pękalska & Duin, 2005]............................ 53
Bảng 4.1 Giá trị thuộc tính của các tình huống trong kho tình huống và các tình huống truy vấn... 62
Bảng 4.2 Một số cơng thức tính độ tương tự giữa hai số................................................................... 69
Bảng 4.3 Bảng độ ưu tiên chuẩn trong AHP...................................................................................... 77
Bảng 4.4 Các tiêu chí được so sánh từng cặp theo độ ưu tiên (do chuyên gia thiết lập)................... 77
Bảng 5.1 Mơ hình tình huống của bài tốn tư vấn ước lượng chi phí phần mềm ............................. 86
Bảng 5.2 Bảng tbl_LinhVuc............................................................................................................... 90
Bảng 5.3 Bảng tbl_CongViec............................................................................................................. 90
Bảng 5.4 Bảng tbl_KieuThuocTinh ................................................................................................... 90
Bảng 5.5 Bảng tbl_ThuocTinh ........................................................................................................... 90
Bảng 5.6 Bảng tbl_TinhHuong .......................................................................................................... 91
Bảng 5.7 Bảng tbl_GiaTriThuocTinh ................................................................................................ 91
Bảng 5.8 Bảng tbl_stopword .............................................................................................................. 96
Bảng 5.9 Bảng tbl_keyword............................................................................................................... 96

viii


MỤC LỤC
LỜI CẢM ƠN..................................................................................................................................... iv
TĨM TẮT ............................................................................................................................................ v

DANH MỤC HÌNH............................................................................................................................ vi
DANH MỤC BẢNG BIỂU.............................................................................................................. viii
MỤC LỤC........................................................................................................................................... ix
Chương 1. GIỚI THIỆU ĐỀ TÀI ..................................................................................................... 1
1.1 Cơ sở hình thành đề tài...........................................................................................................1
1.2 Mục tiêu và phương pháp thực hiện.......................................................................................2
1.3 Bố cục của đề tài ....................................................................................................................5
Chương 2. TỔNG QUAN VỀ CBR................................................................................................... 6
2.1 Đôi nét về lịch sử và các nghiên cứu liên quan......................................................................6
2.2 Định nghĩa CBR .....................................................................................................................7
2.3 Chu trình CBR........................................................................................................................9
2.4 So sánh CBR với các cách tiếp cận khác .............................................................................13
2.4.1 So sánh CBR và lập luận dựa theo luật, lập luận dựa theo mơ hình ..........................13
2.4.2 So sánh CBR và lập luận của con người ....................................................................14
2.4.3 Lợi ích của việc sử dụng CBR....................................................................................15
2.5 Các kỹ thuật cơ bản khi xây dựng một hệ thống CBR ........................................................17
2.5.1 Biểu diễn tình huống và đánh chỉ mục tình huống.....................................................17
2.5.1.1 Biểu diễn tình huống .........................................................................................17
2.5.1.2 Đánh chỉ mục tình huống ..................................................................................19
2.5.2 Đối sánh và trích lục tình huống.................................................................................20
2.5.2.1 Trích lục láng giềng gần nhất ............................................................................21
2.5.2.2 Trích lục quy nạp...............................................................................................22
2.5.2.3 So sánh và phối hợp các kỹ thuật trích lục........................................................23
2.5.3 Tinh chỉnh tình huống.................................................................................................24
2.5.4 Bảo trì kho tình huống ................................................................................................25
2.6 Khả năng ứng dụng của CBR...............................................................................................25
2.7 Những định nghĩa và quy ước cơ bản về CBR trong đề tài này ..........................................27
2.7.1 Một số định nghĩa nền tảng.........................................................................................27
ix



2.7.2 Lối biểu diễn dựa trên “thuộc tính-giá trị” .................................................................29
2.7.3 Thuộc tính và kiểu thuộc tính .....................................................................................31
2.7.4 Mơ hình tình huống.....................................................................................................32
2.7.5 Trọng số thuộc tính .....................................................................................................34
2.7.6 Bộ thuộc tính động......................................................................................................35
2.8 Kết chương ...........................................................................................................................36
Chương 3. TỔNG QUAN VỀ ĐỘ TƯƠNG TỰ ............................................................................ 37
3.1 Giới thiệu..............................................................................................................................37
3.2 Cơ sở toán học về độ tương tự .............................................................................................39
3.2.1 Phép đo khoảng cách ..................................................................................................39
3.2.2 Độ tương tự, độ không tương tự .................................................................................43
3.2.3 Gộp các độ tương tự....................................................................................................44
3.2.4 Độ tương tự cho các kiểu biến thông thường .............................................................46
3.2.4.1 Biến định danh...................................................................................................46
3.2.4.2 Biến có thứ tự ....................................................................................................46
3.2.4.3 Biến liên tục.......................................................................................................47
3.2.4.4 Biến tập hợp.......................................................................................................47
3.3 Các kiểu truy vấn dựa vào độ tương tự ................................................................................48
3.3.1 Truy vấn dải ................................................................................................................48
3.3.2 Truy vấn láng giềng gần nhất .....................................................................................49
3.3.3 Truy vấn k-láng giềng gần nhất ..................................................................................49
3.3.4 Truy vấn xếp hạng ......................................................................................................50
3.4 Độ tương tự trong CBR........................................................................................................50
3.4.1 Định nghĩa độ tương tự trong CBR ............................................................................51
3.4.2 Các phép đo truyền thống ...........................................................................................51
3.4.3 Nguyên lý “cục bộ-toàn cục”......................................................................................54
3.4.3.1 Độ tương tự cục bộ ............................................................................................54
3.4.3.2 Độ tương tự toàn cục .........................................................................................55
3.4.4 Vấn đề học phép đo độ tương tự.................................................................................56

3.4.4.1 Kiến thức trong các hệ thống CBR ...................................................................56
3.4.4.2 Các nghiên cứu liên quan ..................................................................................57
3.5 Kết chương ...........................................................................................................................59
Chương 4. BÀI TỐN XÁC ĐỊNH ĐỘ TƯƠNG TỰ GIỮA HAI TÌNH HUỐNG DỰA VÀO
BỘ THUỘC TÍNH ĐỘNG............................................................................................................... 61
4.1 Tìm lĩnh vực cho tình huống dạng văn bản .........................................................................63
x


4.2 Ý tưởng xây dựng kho tình huống .......................................................................................64
4.2.1 Quy trình đưa một tình huống mới vào kho ...............................................................65
4.2.2 Quy trình tạo một tình huống truy vấn .......................................................................66
4.3 Xây dựng cơng thức tính định độ tương tự giữa hai tình huống .........................................68
4.3.1 Độ tương tự cục bộ cho một số kiểu thuộc tính..........................................................68
4.3.1.1 Thuộc tính dạng số ............................................................................................68
4.3.1.2 Thuộc tính dạng ký hiệu ....................................................................................69
4.3.1.3 Thuộc tính dạng tập hợp....................................................................................71
4.3.1.4 Thuộc tính dạng mờ...........................................................................................72
4.3.1.5 Thuộc tính dạng thơ...........................................................................................75
4.3.1.6 Thuộc tính dạng văn bản ...................................................................................76
4.3.2 Ý tưởng xây dựng bộ trọng số ban đầu.......................................................................77
4.3.3 Độ tương tự toàn cục...................................................................................................78
4.3.4 Vấn đề thiếu hụt giá trị thuộc tính ..............................................................................80
4.4 Vấn đề đánh lại bộ trọng số để cải thiện kết quả trích lục...................................................82
4.4.1 Định nghĩa hàm sai lệch..............................................................................................83
4.4.2 Mô tả giải thuật ...........................................................................................................84
4.5 Kết chương ...........................................................................................................................85
Chương 5. HIỆN THỰC HỆ THỐNG CBR VỚI BỘ THUỘC TÍNH ĐỘNG .......................... 86
5.1 Chọn mơi trường hiện thực ..................................................................................................87
5.1.1 Vấn đề chọn cách thức lưu trữ dữ liệu tình huống .....................................................87

5.1.2 Vấn đề chọn kiểu ứng dụng ........................................................................................88
5.2 Hiện thực hệ thống CBR với bộ thuộc tính động ................................................................89
5.2.1 Thiết kế cơ sở dữ liệu..................................................................................................89
5.2.2 Độ tương tự cục bộ mặc định cho một số kiểu thuộc tính..........................................92
5.2.2.2 BINARY ............................................................................................................93
5.2.2.3 NUMBER ..........................................................................................................93
5.2.2.4 NUMBER_SET .................................................................................................94
5.2.2.5 SYMBOL...........................................................................................................94
5.2.2.6 SYMBOL_SET .................................................................................................94
5.2.2.7 ROUGH_NUMBER..........................................................................................95
5.2.2.8 FUZZY_INTERVAL ........................................................................................95
5.2.2.9 TEXT .................................................................................................................96
5.2.3 Độ tương tự toàn cục...................................................................................................98
5.2.4 Vấn đề đánh trọng số thuộc tính .................................................................................99
xi


5.3 Kết chương .........................................................................................................................101
Chương 6. KẾT LUẬN................................................................................................................... 102
6.1 Đánh giá..............................................................................................................................102
6.2 Hướng phát triển.................................................................................................................103
6.3 Lời kết.................................................................................................................................105
CÀI ĐẶT ỨNG DỤNG MINH HỌA ............................................................................................ 106
THUẬT NGỮ ANH-VIỆT ............................................................................................................. 107
QUY ƯỚC VỀ KÝ HIỆU............................................................................................................... 110
TÀI LIỆU THAM KHẢO .............................................................................................................. 112

xii



Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động

Chương 1.

GIỚI THIỆU ĐỀ TÀI

1.1 Cơ sở hình thành đề tài
Tư vấn là hoạt động trong đó các chuyên gia tiến hành chọn lọc và cung cấp các thông tin, kiến
thức, giải pháp hoặc phương án hành động được lựa chọn và xử lý thích hợp để giúp ích cho từng
trường hợp cụ thể [MOI, 2004]. Một cách tương đối, tư vấn được chia làm nhiều loại: tư vấn kỹ
thuật, tư vấn quản trị, tư vấn tài chính, tư vấn pháp luật, tư vấn xây dựng, tư vấn đầu tư,...
Hoạt động tư vấn hiện thu hút hàng triệu chuyên gia trên khắp thế giới với những cơng ty có doanh
thu hàng tỷ đô la. Trong 20 năm gần đây, tốc độ phát triển bình quân đạt 15%/năm và được báo cáo
là một trong 10 lĩnh vực phát triển nhanh nhất trong thế kỷ 21. Tại Việt Nam, nhu cầu tư vấn cũng
tăng nhanh, nhưng đáp ứng nhu cầu thì cịn hạn chế. Ngoài các viện, trường đại học, các hội khoa
học kỹ thuật cũng cung ứng dịch vụ tư vấn một cách khiêm tốn. Nhìn chung, ngành dịch vụ tư vấn ở
Việt Nam còn rất non trẻ so với các ngành dịch vụ khác. Tuy vậy, ngành tư vấn với các dịch vụ liên
quan đến hỗ trợ doanh nghiệp được xác định là ngành thâm dụng tri thức và là ngành mũi nhọn [Võ
et al., 2004].
Tư vấn quản trị cũng giống như bác sĩ chẩn đoán cho bệnh nhân, ở đây các nhà tư vấn sẽ “chẩn
đốn” các khó khăn của doanh nghiệp. Những nhà tư vấn với kinh nghiệm và kiến thức phong phú
sử dụng phương pháp khoa học để nghiên cứu doanh nghiệp, tìm ra các vấn đề trong việc vận hành
và quản trị kinh doanh. Bằng các phương tiện như phép phân tích lý thuyết, kinh nghiệm chun
mơn, nghiên cứu hình huống, dự báo có tính khoa học và các phương cách khác, họ xác định các
nguyên nhân gây ra rắc rối và “kê toa” một kế sách cải tiến có tính khả thi để đưa vào hoạt động,
chủ doanh nghiệp và các nhà quản trị có thể sử dụng các phương cách mới để kiểm sốt cơng việc
của họ hiệu quả hơn, và tác động lại nhu cầu khách hàng và dịch chuyển thị trường.
Thời gian giải quyết các tình huống tư vấn thường khơng kịp thời nếu một đơn vị nào đó đảm nhận
giải quyết trong nhiều lĩnh vực. Khối lượng tư vấn khổng lồ đòi hỏi sử dụng lại các giải pháp của
các tình huống tương tự. Cho nên nhu cầu đặt ra là cần có một nơi tập trung xử lý, lưu lại các tình

1


Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động

huống đã phát sinh giúp cho việc tìm kiếm các tình huống tư vấn tương tự được nhanh chóng [Lâm
& Nguyễn, 2005]. Cơng việc này địi hỏi tập hợp nhiều chun gia thuộc nhiều lĩnh vực ở nhiều nơi
và sự hợp tác của khách hàng.
Xây dựng một hệ thống quản lý các tình huống tư vấn là một lựa chọn để đáp ứng nhu cầu này.
Những lợi ích của một website tư vấn được liệt kê trong [Trần, 2005]. Đây là một hệ thống quản lý
kiến thức đồ sộ, đòi hỏi sự tổng qt hóa cao, áp dụng nhiều quy trình nghiệp vụ phức tạp. Đã có
nhiều nỗ lực xây dựng hệ thống như thế tại Việt Nam, chẳng hạn như dự án Chợ Tư vấn1 của Trung
tâm Thông tin Khoa học và Cơng nghệ TP. Hồ Chí Minh [CESTI, 2007], dự án Bệnh viện Tư vấn2
của Trung tâm Nghiên cứu và Hỗ trợ Đào tạo Quản trị Doanh nghiệp, thuộc khoa Quản lý Công
nghiệp, trường Đại học Bách khoa TP. Hồ Chí Minh [BR&T, 2006]. Tuy nhiên, các tình huống chủ
yếu được mơ tả bằng văn bản (khơng có cấu trúc), vì thế chức năng tìm kiếm tình huống trong các
hệ thống này cịn nhiều hạn chế, chủ yếu tìm kiếm dựa trên từ khóa và các truy vấn SQL đơn giản.
Luận văn này khơng có ý xây dựng một hệ thống như thế, cũng như không bàn về lĩnh vực tư vấn;
mà đứng ở góc độ kỹ thuật, tập trung vào một bài toán nhỏ trong hệ thống đồ sộ đó: xây dựng một
giải thuật hiệu quả để xác định độ tương tự giữa hai tình huống tư vấn.

1.2 Mục tiêu và phương pháp thực hiện
Hệ chuyên gia là một hệ thống sử dụng kiến thức của con người, đưa kiến thức vào máy tính để giải
quyết một số vấn đề đòi hỏi đến kiến thức của người chuyên gia. Đây là những hệ thống được thiết
kế hoàn chỉnh, bắt chước quá trình suy luận mà chuyên gia dùng để giải quyết vấn đề đặc thù. Các
chuyên gia có thể sử dụng những hệ thống như thế thay cho các trợ lý chuyên môn. Hệ chuyên gia
được sử dụng để quảng bá nguồn kiến thức hiếm hoi nhằm mang lại kết quả được nâng cao và bền
vững. Suy cho cùng, những hệ thống như thế có thể hoạt động tốt hơn bất kỳ một chuyên gia đơn
độc nào trong việc thực hiện các thẩm định trong lĩnh vực chuyên ngành khá hẹp. Khả năng này có
thể có tác dụng đáng kể đến các nghề nghiệp có tính chất tư vấn. Nhu cầu của hệ chuyên gia được

thúc đẩy do trong một số lĩnh vực cần đến kiến thức của một chuyên gia. Do đó nếu xây dựng được
hệ chuyên gia thì có thể thay thế được vai trị của chun gia và có thể nhân bản được kiến thức.
Mục tiêu của đề tài này là xây dựng một cơ sở lý thuyết vững chắc nhằm xây dựng một giải thuật
(hay công thức) xác định độ tương tự (hay khoảng cách) giữa hai tình huống tư vấn ở mức tổng quát
nhất (độc lập lĩnh vực và dựa vào bộ thuộc tính động). Mục tiêu cụ thể như sau:
9 So sánh và chọn phương pháp luận xây dựng hệ thống quản lý các tình huống tư vấn;
9 Tìm hiểu cơ sở tốn học về độ tương tự, tổng hợp các phép đo độ tương tự cho các kiểu biến
khác nhau đã được nghiên cứu, và ứng dụng vào bài toán quản lý tình huống tư vấn;
9 Xây dựng một giải thuật hiệu quả để xác định độ tương tự giữa hai tình huống dựa vào bộ
thuộc tính động;
9 Hiện thực một chương trình để minh họa, kiểm thử với một số dữ liệu mẫu.

1

;

2

;

2


Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động

Phương pháp được đề nghị để xây dựng hệ thống quản lý các tình huống tư vấn là CBR. CBR (viết
tắt của Case-Based Reasoning―tạm dịch là “lập luận dựa theo tình huống”1) là quy trình giải quyết
vấn đề mới dựa trên giải pháp của các vấn đề tương tự đã gặp. CBR không chỉ là một phương pháp
mạnh cho lập luận máy tính mà cịn là một hành vi phổ biến của con người trong cuộc sống hằng
ngày khi giải quyết vấn đề. Hay nói cách khác, mọi lập luận đều dựa trên các tình huống trong quá

khứ (mà đã được trải nghiệm hoặc chấp nhận bằng cách chủ động thực hiện chọn lựa). Bảng 1.1 so
sánh CBR với các kỹ thuật/phương pháp giải quyết vấn đề khác.
Bảng 1.1 So sánh các kỹ thuật/phương pháp giải quyết vấn đề [Watson, 1997]
Kỹ thuật/Phương pháp

Có thể áp dụng

Khơng thể áp dụng

Database (cơ sở dữ liệu)

Dữ liệu được chuẩn hóa, có cấu
trúc tốt và cần các truy vấn
chính xác, đơn giản

Dữ liệu phức tạp, có cấu trúc
nghèo nàn và cần các truy vấn mờ

Information Retrieval
(trích lục thông tin)

Lượng lớn dữ liệu dạng văn bản

Các kiểu dữ liệu phức tạp phi văn
bản, kiến thức nền

Statistics (thống kê)

Lượng lớn dữ liệu được hiểu rõ
với một giả thuyết được định rõ


Phân tích thăm dị dữ liệu với biến
phụ thuộc

Rule-Based System (hệ
thống dựa theo luật)

Miền bài toán được hiểu rõ, ổn
định, chặt chẽ và sự canh chỉnh
bởi truy vết luật (rule-trace) là
được chấp nhận

Miền bài toán được hiểu kém, liên
tục thay đổi

Machine Learning (học
máy)

Luật tổng quát hóa (generalized
rule) là bắt buộc từ một tập huấn
luyện lớn và sự canh chỉnh bởi
truy vết luật (rule-trace) là được
chấp nhận

Các luật là không bắt buộc và sự
canh chỉnh bởi truy vết luật (ruletrace) là không được chấp nhận

Neural Network (mạng
nơ-ron nhân tạo)


Dữ liệu dạng số nhiễu đối với
nhận dạng mẫu hay xử lý tín
hiệu

Dữ liệu dạng ký hiệu phức tạp
hoặc khi cần có sự canh chỉnh

Case-Based Reasoning
(lập luận dựa theo tình
huống)

Miền bài tốn được hiểu kém
với dữ liệu có cấu trúc phức tạp,
thay đổi chậm theo thời gian và
cần có sự canh chỉnh

Khi khơng có sẵn dữ liệu tình
huống, hoặc khi cần những tinh
chỉnh phức tạp, hoặc khi cần một
câu trả lời tối ưu, chính xác

1

Có một số tranh cãi về nghĩa tiếng Việt của “reasoning” trong CBR, xem chi tiết tại />luận:Lập luận theo tình huống. Trong một số tài liệu tiếng Việt, “case” được dịch là “trường hợp” [Võ & Trần, 2006],
“ca lập luận” [Phan et al., 2005], hay “kinh nghiệm” [Đỗ et al., 2005].

3


Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động


Vấn đề mới

tìm tương tự

Vấn đề cũ

?
Giải pháp
chưa biết
Tình huống hiện
tại

tinh chỉnh

Giải pháp
đã biết
Tình huống

Kho tình huống

Hình 1.1 Kiểu giải quyết vấn đề dựa theo tình huống
Khái niệm CBR có lịch sử tương đối trẻ, nghiên cứu ban đầu liên quan đến CBR là của Schank và
Abelson tại đại học Yale vào năm 1977. Họ đề xuất CBR là một công cụ cho tổ chức bộ nhớ, lưu
trữ các hồn cảnh (tình huống) trước đó nhằm mục đích học và giải quyết vấn đề [Schank, 1982].
Kể từ đó, các hoạt động CBR phát triển khơng chỉ ở mức nghiên cứu mà cịn ở những ứng dụng
trong các lĩnh vực khác nhau. Aamodt và Plaza [1994] đưa ra một nền tảng triết học cho phương
pháp luận CBR.
CYRUS là hệ thống CBR đầu tiên [Kolodner, 1984], được sử dụng để lưu trữ và trích lục các sự
kiện trong cuộc đời của Cyrus Vance (Ngoại trưởng Mỹ). Sau đó, nhiều hệ thống CBR đã được phát

triển cho nhiều ứng dụng khác nhau. Chẳng hạn, HYPO được phát triển cho lĩnh vực luật [Ashley &
Rissland, 1988]. CASEY [Koton, 1988] và PROTOS [Bareiss, 1988] lần lượt là các hệ thống CBR
khác được sử dụng trong lĩnh vực y khoa và điều trị thính giác. Những hệ thống CBR đầu tiên khác
có thể được tìm thấy trong [Kolodner, 1993]. Bất chấp hệ thống nào được sử dụng, CBR có thể
được sử dụng trong nhiều ứng dụng khác nhau, đa số cho các lĩnh vực yếu hay lý thuyết mở1.
Nghiên cứu CBR được lan rộng trên khắp thế giới, nhiều hội thảo về CBR được tổ chức ở châu Âu,
chẳng hạn như EWCBR. Các hoạt động CBR tương tự ở các nước châu Á cũng chạy theo với các
cách tiếp cận khác nhau như ở Ấn Độ [Venkatamaran et al., 1993; Bogaerts & Leake, 2005] và Nhật
[Kitano, 1993; Wahono & Far, 2000]. Hiện tại, các hoạt động CBR trải rộng khắp thế giới và có xu
hướng tăng cường ứng dụng của CBR. Có thể nói CBR là một trong những ứng dụng kỹ thuật trí
tuệ nhân tạo thành cơng nhất trong những năm gần đây trên thế giới.
Tại Việt Nam, CBR vẫn cịn khá mới mẻ, có thể kể đến ứng dụng CBR để chẩn đoán y học [Lê &
Phan, 2002], thu hẹp khơng gian tìm kiếm lời giải trong các hệ lập luận dựa theo luật [Nguyễn et al.,
2004; Nguyễn & Phạm, 2005], ước lượng chi phí phần mềm [Phạm et al., 2005], đánh giá sơ đồ
biểu diễn giải thuật [Phan et al., 2005]. Hy vọng luận văn này có thể đóng góp phần nào vào xu
hướng nghiên cứu CBR tại Việt Nam.

1

Một lĩnh vực mở là lĩnh vực mà khơng thể được mơ hình hóa như thực tế, và một lĩnh vực lý thuyết yếu là lĩnh vực có
sự khơng chắc chắn giữa các khái niệm quan trọng trong lĩnh vực [Aamodt, 1994]

4


Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động

1.3 Bố cục của đề tài
Luận văn này được tổ chức thành 6 chương:
•


Chương 1: Giới thiệu đề tài. Chương này trình bày nguyên nhân hình thành đề tài, mục
tiêu và phương pháp thực hiện đề tài.

•

Chương 2: Tổng quan về CBR. Chương này tìm hiểu về phương pháp luận CBR và quy
trình xây dựng một hệ thống CBR. Chương này cũng điểm qua lợi ích của việc sử dụng
CBR, so sánh nó với các phép lập luận khác. Theo đó, CBR là một chọn lựa hồn hảo cho
bài tốn quản lý các tình huống tư vấn. Cuối chương là những quy ước về CBR được sử
dụng trong luận văn.

•

Chương 3: Tổng quan về độ tương tự. Trước hết, chương này trình bày cơ sở toán học về
độ tương tự và các phép đo độ tương tự cho các kiểu biến thông thường. Tiếp theo, khái
niệm độ tương tự trong CBR được bàn đến, tập trung vào việc áp dụng nguyên lý “cục bộtoàn cục” để xây dựng phép đo độ tương tự giữa hai tình huống. Các kỹ thuật học phép đo
độ tương tự trong CBR cũng được bàn ở đây.

•

Chương 4: Bài toán xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính
động. Trước hết, chương này phát biểu bài tốn một cách hình thức. Tiếp theo, từng vấn đề
nhỏ trong bài toán sẽ được giải quyết, dựa trên những khái niệm và ý tưởng đã được trình
bày trong các chương trước.

•

Chương 5: Hiện thực hệ thống CBR với bộ thuộc tính động. Chương này trình bày ý
tưởng thiết kế và hiện thực ứng dụng minh họa giải thuật xác định độ tương tự giữa hai tình

huống. Vấn đề chọn cơng nghệ nào để hiện thực hệ thống cũng được bàn ở đây. Đề tài chọn
công nghệ ASP.NET (cụ thể là Microsoft .NET Framework 1.1 và Microsoft SQL Server
2000), bộ dữ liệu kiểm thử là các tình huống tư vấn ước lượng chi phí phần mềm.

•

Chương 6: Kết luận. Chương cuối cùng này đánh giá những kết quả đã đạt được, và nêu
những hướng phát triển luận văn.

5


Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động

Chương 2.

TỔNG QUAN VỀ CBR

C

hương này trình bày cơ sở lý thuyết về quá trình xây dựng một hệ thống CBR phục vụ cho
mục đích quản lý các tình huống tư vấn. Trong đó, tập trung vào bước trích lục tình huống
với giải thuật xác định độ tương tự giữa hai tình huống.

2.1 Đôi nét về lịch sử và các nghiên cứu liên quan
CBR phát sinh từ việc nghiên cứu khoa học nhận thức, là một lĩnh vực có lịch sử tương đối trẻ.
Những công bố đầu tiên về lĩnh vực này là do Roger Schank và các đồng sự của ông tại trường Đại
học Yale [Schank, 1982]. Việc nghiên cứu CBR được đánh giá là một mơ hình cao cấp đáng tin cậy
trong việc xử lý nhận thức. Nó được quan tâm nhiều ở các vấn đề như làm cách nào con người học
được một kỹ năng mới và làm cách nào con người tạo ra giả thuyết về các trạng thái mới dựa trên

những kinh nghiệm mà họ đã trải qua. Mục tiêu của những việc nghiên cứu dựa trên nhận thức này
là nhằm xây dựng các hệ hỗ trợ quyết định để giúp con người học tập. Nhiều hệ thống CBR mẫu đã
được xây dựng như: CYRUS [Kolodner, 1984], HYPO [Ashley & Rissland, 1988], CASEY [Koton,
1988], PROTOS [Bareiss, 1988],…
Dưới đây là một số hệ thống CBR có liên quan đến tư vấn luật:
•

FINDER là hệ chuyên gia về luật bồi thường tài sản được phát triển bởi Tyree [1985].
FINDER lưu trữ mỗi tình huống trong một vectơ gồm các giá trị thuộc tính, thuộc tính là
“yes” hay “no” ứng với những câu hỏi về các sự kiện được xác định là hợp pháp. FINDER
đưa ra lý lẽ dựa trên tình huống gần nhất (sử dụng phép phân tích láng giềng gần nhất).

•

Popple [1993] dựa trên cách tiếp cận này và xây dựng nên SHYSTER tại Đại học Quốc gia
Úc. SHYSTER cũng là một hệ chuyên gia tư vấn luật CBR (gồm 4 nhóm luật cụ thể, bao
gồm cả nhóm luật của FINDER). SHYSTER lưu trữ các tình huống ở dạng vectơ sự kiện,
mỗi sự kiện được biểu diễn bởi giá trị “yes”, “no” hay “unknown”. Khi người dùng tương
tác với SHYSTER, nó sẽ đưa ra các câu hỏi để thiết lập giá trị cho các sự kiện trong vectơ.
Sau đó, SHYSTER so sánh vectơ sự kiện của hình huống hiện tại với các tình huống đã
được giải quyết trong kho tình huống. Phép so sánh này được thực hiện bởi phép phân tích
cận gần nhất trong khơng gian n chiều chứa vectơ sự kiện. Điều này nghĩa là phương pháp
lập luận luật mà SHYSTER sử dụng là tính tương tự.
6


Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động

•


SHYSTER-MYCIN là hệ chuyên gia tư vấn luật được phát triển bởi O’Callaghan et al.
[2003]. SHYSTER-MYCIN kết hợp cả RBR và CBR: phần MYCIN sử dụng một hệ thống
các quy luật để lập luận với các luật quốc hội; phần SHYSTER sử dụng tính tương tự để lập
luận với các tình huống giảng giải các khái niệm có kết cấu mở.

Hiện nay, có một số phần mềm với vai trị là một framework (bộ khung) dùng để xây dựng các hệ
thống CBR, có thể kể đến như CBR-Works [Schulz, 1999], jCOLIBRI [García & Agudo, 2004],
IUCBRF [Bogaerts & Leake, 2005], myCBR [Zilles, 2007],…
CBR là một phương pháp luận dùng để giải quyết vấn đề 1, tìm ra các giải pháp cho các vấn đề mới
bằng cách phân tích các vấn đề đã được giải quyết trước đó, được gọi là các hình huống (case).
Trọng tâm của một hệ thống CBR là tập hợp các hình huống đã được giải quyết, được gọi là một
kho tình huống (case base). Cho trước một vấn đề mới cần được giải quyết, những vấn đề gần giống
(tương tự) nhất từ kho tình huống sẽ được thu lấy. Các giải pháp này có thể được áp dụng trực tiếp
vào vấn đề mới, mặc dù một vài tinh chỉnh cho các giải pháp này có thể là cần thiết để phù hợp tốt
hơn với vấn đề mới. Kế đó, giải pháp được đề xuất có thể được xem xét, và nếu được phê chuẩn, nó
sẽ được lưu trữ trong kho tình huống và được sử dụng để giải quyết các vấn đề trong tương lai.
Nhìn chung, các hệ thống CBR (cả các hệ thống được xây dựng từ framework) đều được sử dụng
cho một lĩnh vực cụ thể và rõ ràng. Điều đó có nghĩa: có thể xác định một bộ thuộc tính cụ thể cho
một tình huống. Bài tốn tư vấn là khơng có cấu trúc, xác định một bộ thuộc tính cho một tình
huống là điều khơng khả thi. Đề tài này sẽ ứng dụng CBR với bộ thuộc tính động vào bài tốn tư
vấn.

2.2 Định nghĩa CBR
Chúng ta hãy xem như một hệ thống chẩn đoán y học là một ví dụ điển hình của việc sử dụng CBR,
trong đó các phép chẩn đốn cho các bệnh nhân mới được dựa trên kinh nghiệm đã qua của thầy
thuốc. Trong trường hợp này, một tình huống có thể tương ứng với các triệu chứng của một bệnh
nhân cùng với các phương pháp điều trị. Khi đối diện với một bệnh nhân mới, bác sĩ so sánh các
triệu chứng hiện tại của bệnh nhân với các triệu chứng của những bệnh nhân trước đó, những người
có các triệu chứng tương tự. Phương pháp điều trị cho các bệnh nhân đó được sử dụng và sửa đổi
(nếu cần) cho thích hợp với bệnh nhân mới. Trong cuộc sống thực, có rất nhiều các trường hợp

tương tự sử dụng mơ hình CBR để xây dựng các hệ thống lập luận, ví dụ như việc lấy các tình
huống pháp luật có trước để đưa ra các lý lẽ hợp pháp, việc định giá một căn nhà dựa trên các thông
tin tương tự từ những tài sản thực khác, việc dự báo thời tiết dựa trên những ghi chép về thời tiết
trước đó, và việc tổng hợp một lịch trình sản xuất cụ thể từ những kế hoạch trước đó.
Định nghĩa 2.1 (CBR): Dưới đây là một số định nghĩa về CBR:
9 Một bộ lập luận dựa theo tình huống (case-based reasoner) giải quyết các vấn đề mới bằng
cách sử dụng hoặc tinh chỉnh các giải pháp đã được sử dụng để giải quyết các vấn đề trước
đó [Riesbeck & Schank, 1989].

1

Bằng cách khảo sát bốn ứng dụng CBR khác nhau, Watson [1998] đã chứng minh rằng: CBR chỉ mô tả một phương
pháp luận cho việc giải quyết vấn đề chứ không kê ra một kỹ thuật cụ thể. Ông chỉ ra rằng: các kỹ thuật khác nhau có
thể được sử dụng và áp dụng trong các pha thuộc vòng đời CBR.

7


Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động

9 CBR là phương cách con người sử dụng các tình huống để giải quyết các vấn đề và là
phương cách chúng ta làm cho máy tính sử dụng chúng [Kolodner, 1993].
9 CBR là một cách tiếp cận học và giải quyết vấn đề [Aamodt & Plaza, 1994].
9 CBR là lập luận bằng việc ghi nhớ [Leake, 1996].
9 CBR được dựa trên một mơ hình nhận thức của con người, làm việc với kiến thức ở dạng
các mẫu từng trải cụ thể (kinh nghiệm) [Wangenheim, 2000].
Nhìn chung, CBR là:
9 Một quá trình ra quyết định tập trung vào sự tương tự của vấn đề hiện tại với một hay nhiều
vấn đề đã được giải quyết trong q khứ.
9 Một q trình khơng cậy vào các phép đo theo khuynh hướng trung tâm (chẳng hạn như

trung bình, trung vị, độ lệch chuẩn).
9 Một q trình thơng báo cho người ra quyết định bằng cách khảo sát ngữ cảnh (context) và
sự phong phú (richness) của các tình huống riêng lẻ từ quá khứ.
9 Một quá trình gần giống với phương pháp ra quyết định theo trực giác thông thường của con
người trong cuộc sống hàng ngày.
CBR bao hàm sự lập luận từ các mẫu có trước: giữ lại ký ức về các vấn đề trước đó cùng các giải
pháp của chúng và giải quyết các vấn đề mới bằng cách tham khảo đến sự nhận biết đó. Nói chung,
một bộ lập luận dựa theo tình huống sẽ được đưa ra, bởi một người dùng hoặc bởi một chương trình
hoặc hệ thống, cùng với một vấn đề. Sau đó, bộ lập luận dựa theo tình huống sẽ tìm kiếm trong bộ
nhớ của nó về những tình huống đã qua (được gọi là kho tình huống) và cố gắng tìm một tình huống
có sự chỉ định vấn đề tương tự như tình huống đang phân tích. Nếu bộ lập luận khơng tìm thấy một
tình huống đúng nào trong kho tình huống của nó, nó sẽ cố gắng tìm một tình huống hoặc một tập
các tình huống gần giống nhất với tình huống hiện tại.
Trong các trường hợp một tình huống đúng được trích lục, giả sử giải pháp của nó đã thành cơng,
nó có thể được cung cấp như một giải pháp cho vấn đề hiện tại. Trong trường hợp tình huống trích
lục khơng giống hồn tồn với tình huống hiện tại, pha tinh chỉnh sẽ diễn ra. Trong suốt quá trình
tinh chỉnh, sự khác biệt giữa tình huống hiện tại với tình huống trích lục được nhận biết trước tiên
và từ đó giải pháp cho tình huống trích lục sẽ được sửa đổi, ghi lại những sự khác biệt vào bản kê
khai. Giải pháp trả về cho vấn đề hiện hành có thể được thử nghiệm trong lĩnh vực phù hợp.
Cấu trúc của một hệ thống CBR được đặt ra theo kiểu phản ánh các trạng thái riêng biệt, ví dụ như:
việc trích lục và tinh chỉnh được trình bày ở trên. Tuy nhiên, ở cấp độ cao nhất của khái niệm trừu
tượng, một hệ thống CBR có thể được xem như một hộp đen (Hình 2.1) kết hợp chặt chẽ cơ chế lập
luận và các yếu tố sau:
9 Sự chỉ định dữ liệu nhập hay tình huống vấn đề.
9 Dữ liệu xuất định nghĩa một giải pháp đề nghị cho vấn đề cần giải quyết.
9 Bộ nhớ cho những tình huống đã qua (kho tình huống) được tham khảo bởi cơ chế lập luận.

8



Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động

Kho tình huống

Vấn đề

Cơ chế lập luận
dựa theo tình huống

Giải pháp

Hình 2.1 Hệ thống CBR
Trong hầu hết các hệ thống CBR, cơ chế lập luận dựa theo tình huống (được coi là một bộ lập luận
hoặc bộ tìm giải pháp cho vấn đề) có cấu trúc bên trong được chia thành hai phần lớn: bộ trích lục
tình huống (case retriever) và bộ lập luận tình huống (case reasoner). Nhiệm vụ của bộ trích lục tình
huống là tìm những tình huống thích hợp trong kho tình huống, trong khi bộ lập luận tình huống sử
dụng những tình huống được trích lục để tìm một giải pháp cho những mô tả về vấn đề được đưa ra.
Quá trình lập luận này bao gồm việc xác định sự khác nhau giữa những tình huống trích lục và tình
huống hiện tại, sửa đổi giải pháp để phản ánh những khác biệt này một cách thích hợp. Q trình
lập luận có thể bao gồm hoặc khơng bao gồm việc lấy thêm các tình huống hoặc các phần của tình
huống từ kho tình huống.

2.3 Chu trình CBR
Theo [Aamodt & Plaza, 1994], CBR là một quá trình bao gồm bốn bước cơ bản (gọi là bốn “RE”
hay R4) sau đây1:
1. RETRIEVE: Trích lục các tình huống tương tự nhất. Trong quá trình này, bộ lập luận tìm
trong cơ sở dữ liệu tình huống gần giống với hồn cảnh hiện tại nhất.
2. REUSE: Sử dụng lại các tình huống nhằm giải quyết vấn đề. Quá trình này bao gồm sử
dụng tình huống được trích lục và tinh chỉnh nó với hồn cảnh mới. Cuối q trình này, bộ
lập luận có thể đề xuất một giải pháp.

3. REVISE: Duyệt lại giải pháp được đề xuất nếu thấy cần thiết. Vì giải pháp được đề xuất có
thể khơng thỏa đáng, q trình này có thể hiệu chỉnh giải pháp được đề xuất đầu tiên.
4. RETAIN: Giữ lại giải pháp mới một khi nó đã được cơng nhận hoặc thơng qua (là một
phần của tình huống mới). Quá trình này cho phép CBR học và tạo một giải pháp mới và
một tình huống mới (sẽ được thêm vào kho tình huống).
Trong nhiều ứng dụng thực tế, các bước sử dụng lại và chỉnh sửa đơi khi rất khó phân biệt, các nhà
nghiên cứu sử dụng một bước tinh chỉnh duy nhất để thay thế và kết hợp chúng. Tuy nhiên, sự tinh
chỉnh trong các hệ thống CBR vẫn còn là một câu hỏi mở bởi vì nó là một q trình phức tạp để cố

1

Khi nói đến mơ hình CBR, người ta thường hay nhắc đến mơ hình R4 của Aamodt và Plaza [1994]. Thật ra, tồn tại một
số mơ hình CBR khác như mơ hình của Kolodner [1993], mơ hình của Allen [1994], mơ hình của Hunt [1995].

9


Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động

gắng vận dụng bằng tay các giải pháp tình huống. Thơng thường, việc này địi hỏi sự pháp triển của
một mơ hình quan hệ nhân quả giữa không gian vấn đề (chẳng hạn sự định rõ vấn đề) và không gian
giải pháp (chẳng hạn các điểm đặc trưng của giải pháp) của các tình huống có liên quan.
Vấn đề mới

Tình huống mới
Các tình huống
thu hồi được

REUSE (SỬ DỤNG LẠI)


RETRIEVE (TRÍCH LỤC)
Tình huống mới

RETAIN (GIỮ LẠI)

Tình huống
học được

Tình huống được
kiểm tra/hiệu chỉnh

Giải pháp được thẩm định

Các
tình
huống
cũ

Kiến thức lĩnh vực

REVISE (SỬA LẠI)

Tình huống được
giải quyết

Giải pháp được đề xuất

Hình 2.2 Chu trình CBR với bốn “RE” [Aamodt & Plaza, 1994]
Trong hình trên, các tình huống lưu trữ trong kho tình huống được bổ sung bởi kiến thức chung
thường lệ thuộc vào lĩnh vực. Sự hỗ trợ này nằm trong khoảng từ rất yếu đến rất mạnh tùy thuộc

vào kiểu của phương pháp CBR. Ví dụ, khi sử dụng các hồ sơ bệnh nhân trước đó vào việc chẩn
đốn y học, một mơ hình nhân quả của bệnh lý và phẫu thuật có thể tạo thành kiến thức chung được
sử dụng bởi hệ thống CBR. Kiến thức này có thể ở dạng một tập các quy luật NẾU-THÌ hoặc một
số điều kiện trong việc sử dụng các tình huống.
Cần lưu ý rằng q trình trích lục trong CBR không giống như trong cơ sở dữ liệu. Nếu muốn truy
vấn dữ liệu, cơ sở dữ liệu chỉ trích lục dữ liệu bằng phép đối sánh chính xác, trong khi CBR có thể
trích lục dữ liệu bằng phép đối sánh xấp xỉ.
Chu trình CBR bắt đầu với mơ tả một vấn đề mới, mà có thể được giải quyết bằng cách trích lục các
tình huống trước đó và sử dụng lại các tình huống đã được giải quyết nếu có thể, đưa ra một giải
pháp đề xuất hoặc sửa lại giải pháp, giữ lại tình huống được tu sửa và sáp nhập nó vào kho tình
huống. Tuy nhiên, chu trình này hiếm khi xảy ra mà khơng có sự can thiệp của con người (thường là
trong trong pha RETAIN). Nhiều công cụ và hệ thống ứng dụng đóng vai trị là một hệ thống trích
lục tình huống, chẳng hạn một số hệ thống help desk và hệ thống hỗ trợ khách hàng.

10


Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động

Finnie và Sun [2003] cho rằng chu trình CBR bao gồm năm “RE” (thêm pha REPARTITION) với ý
tưởng rằng việc xây dựng kho tình huống là một tác vụ quan trọng của CBR và kho tình huống có
thể được xây dựng dựa trên việc phân hoạch lại không gian các vấn đề và giải pháp.
Các tình huống
trích lục được

RETRIEVE
(TRÍCH LỤC)

Vấn đề mới


REUSE
(SỬ DỤNG LẠI)
Kho
tình
huống

REPARTITION
(PHÂN LẠI)

Tình huống
học được

Tình huống
được giải quyết

RETAIN
(GIỮ LẠI)

Wp

REVISE
(SỬA LẠI)

Tình huống
được sửa lại

Ws

Hình 2.3 Chu trình CBR với năm “RE” [Finnie & Sun, 2003]
Watson [2001] cho rằng chu trình CBR không phải gồm bốn “RE” mà là sáu “RE” và tương ứng

với các hoạt động của hệ quản lý kiến thức. Trong đó, hai “RE” mới là:
9 REVIEW: Xem lại cặp “vấn đề-giải pháp” có thể được sử dụng làm một tình huống mới
hay khơng.
9 REFINE: Cải thiện các chỉ mục trong kho tình huống và các trọng số thuộc tính nếu điều
này là cần thiết.

11


Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động
Vấn đề mới

Tình huống mới

RETRIEVE (TRÍCH LỤC)

REUSE
REFINE
(TINH LỌC)

RETAIN
(GIỮ LẠI)

REVIEW

Giải pháp
tiềm năng

(SỬA LẠI)


Tình huống
được giải quyết

REVISE

Kho
tình
huống

(SỬ DỤNG LẠI)

Các tình huống
thu hồi được

Tình huống mới

Tình huống được
kiểm tra/hiệu chỉnh

Tình huống mới

(XEM LẠI)

Giải pháp mới

Hình 2.4 Chu trình CBR với sáu “RE” [Watson, 2001]
Nhằm hướng đến một phương pháp luận bảo trì các hệ thống CBR, Berghofer và Iglezakis [2001]
đề xuất mơ hình sáu bước như sau:
Cơng đoạn bảo trì


Cơng đoạn ứng dụng
kiến thức

các bộ
chứa kiến
thức

vấn đề

các bộ
chứa kiến
thức

Hình 2.5 Chu trình CBR với sáu “RE” [Berghofer & Iglezakis, 2001]

12


Xây dựng giải thuật xác định độ tương tự giữa hai tình huống dựa vào bộ thuộc tính động

2.4 So sánh CBR với các cách tiếp cận khác
Bảng 1.1 đã so sánh CBR với các phương pháp/kỹ thuật giải quyết vấn đề: Database (cơ sở dữ liệu),
Information Retrieval (trích lục thông tin), Statistics (thống kê), Rule-Based System (hệ thống dựa
theo luật), Machine Learning (học máy), Neural Network (mạng nơ-ron nhân tạo). Trong phần này,
chúng ta sẽ so sánh kỹ hơn CBR với RBR và MBR. Chúng ta cũng so sánh CBR và sự lập luận của
con người trong cuộc sống hàng ngày. Sau cùng, danh sách các thuận lợi của CBR sẽ được liệt kê.
Tham khảo thêm [Althoff et al., 1995; Watson, 1997; Pal & Shiu, 2004].
2.4.1 So sánh CBR và lập luận dựa theo luật, lập luận dựa theo mơ hình
Sự tiếp cận của CBR có thể được đối chiếu với sự tiếp cận của các hệ thống dựa trên kiến thức khác
như các hệ thống dựa theo luật (rule-based system) hoặc các hệ thống dựa theo cơ chế phối hợp luật

& khung (combined frame-rule-based system). Trong các hệ thống dựa theo luật, một bộ phận có
một cơ sở luật bao gồm một tập các luật cho trước, các luật này có dạng: NẾU A THÌ B, với A là
một điều kiện và B là một hành động. Nếu điều kiện A là đúng, hành động B sẽ được thực hiện.
Điều kiện A có thể là một điều kiện phức hợp, bao gồm sự kết hợp của các điều kiện A1, A2,…, An.
Hơn nữa, một hệ thống dựa theo luật có một bộ máy suy luận làm nhiệm vụ so sánh dữ liệu có trong
bộ nhớ đang hoạt động với các phần của các luật để xác định xem những luật nào được sử dụng.
Ngoài các luật, các hệ thống dựa theo cơ chế phối hợp luật & khung cũng sử dụng các bộ khung để
nắm bắt kiến thức rập khn. Các bộ khung bao gồm nhiều mặt có các giá trị mặc định, giá trị thực
tế hoặc các giá trị ảo được gán vào. Các bộ khung sử dụng một thủ tục hoặc một tập luật để xác
định những giá trị cần thiết khi chúng được kích hoạt. Đơi khi một hệ thống sử dụng một mơ hình
của một vấn đề làm cơ sở lập luận cho một trạng thái mà ở đó mơ hình có thể là định tính hay định
lượng. Những hệ thống này được gọi là những hệ thống dựa theo mơ hình (model-based system).
Trong nhiều trường hợp, các hệ thống CBR là một sự lựa chọn cho các hệ thống dựa theo luật.
Trong nhiều lĩnh vực và quá trình, việc xem các tình huống như một phương tiện lập luận có thể là
một thuận lợi do trạng thái tự nhiên của kiểu giải quyết vấn đề này. Một trong những khía cạnh tốn
nhiều thời gian nhất khi phát triển một hệ thống dựa theo luật là tác vụ thu nhận kiến thức. Thu
nhận được thông tin đặc trưng của một lĩnh vực và chuyển nó thành một số hình thức biểu diễn nào
đó có thể là một tác vụ khổng lồ và trong một số trường hợp, đặc biệt là những trường hợp thuộc
các lĩnh vực chưa được hiểu biết rõ ràng, kiến thức không thể được chuyển đổi hết được. Các hệ
thống dựa theo tình huống thường địi hỏi rất ít sự thu nhận kiến thức bởi vì nó bao hàm việc thu
thập một tập hợp những kinh nghiệm đã gặp mà không cần trích thêm một mơ hình lĩnh vực từ các
tình huống này. Trong nhiều lĩnh vực, có nhiều tình huống khiếm khuyết để trích một mơ hình lĩnh
vực, đây là một lợi ích khác của CBR: Một hệ thống có thể được tạo ra với một lượng kinh nghiệm
nhỏ hoặc có giới hạn, sau đó được phát triển tăng dần, nạp thêm các tình huống vào kho tình huống
khi chúng trở nên có giá trị.
Conradie [2000] đã so sánh các phép lập luận: dựa theo tình huống, dựa theo luật, và dựa theo mơ
hình trong Bảng 2.1. Những khác biệt này dẫn đến những khác biệt trong việc trích lục kiến thức.
Trong RBR, kiến thức được trích xuất từ các chun gia và được mã hóa thành những luật. Thơng
thường, khó đạt được điều này. Trong CBR, hầu hết (khơng phải tất cả) kiến thức ở dạng các tình
huống. CBR cần những luật tinh chỉnh, không gian tương tự và nhiều kiểu kiến thức hơn nữa,

nhưng dễ dàng trích lục kiến thức hơn. Cả MBR và CBR đều đã được khai triển thành các phương

13