TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
──────── * ───────
ĐỒ ÁN
TỐT NGHIỆP ĐẠI HỌC
NGÀNH CÔNG NGHỆ THÔNG TIN
NỚI LỎNG TRUY VẤN SỬ DỤNG KĨ
THUẬT KHÁM PHÁ TRI THỨC
Sinh viên thực hiện : Nguyễn Chí Thanh
Lớp HTTT – K50
Giáo viên hướng dẫn: PGS. TS Nguyễn Kim Anh
HÀ NỘI 6-2010
PHIẾU GIAO NHIỆM VỤ ĐỒ ÁN TỐT NGHIỆP
1. Thông tin về sinh viên
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 1
Họ và tên sinh viên: Nguyễn Chí Thanh
Điện thoại liên lạc: 0986703698 Email:
Lớp: HTTT B – K50 Hệ đào tạo: Đại học chính quy
Đồ án tốt nghiệp được thực hiện tại: Bộ môn Hệ thống thông tin, Viện CNTT & Truyền
thông, Trường Đại học Bách khoa Hà nội
Thời gian làm ĐATN: Từ ngày 05 / 01 /2010 đến 28 / 05 /2010
2. Mục đích nội dung của ĐATN
Chứng minh được một giải pháp cho bài toán nới lỏng truy vấn sử dụng tri thức học online
và cài đặt hệ thống thử nghiệm.
3. Các nhiệm vụ cụ thể của ĐATN
- Tìm hiểu bài toán nới lỏng truy vấn và thực trạng nới lỏng truy vấn dựa trên cách các
tiếp cận đã có.
- Tìm hiểu các kĩ thuật khám phá tri thức và nghiên cứu khả năng áp dụng cho bài toán nới
lỏng truy vấn.
- Chứng minh giải pháp nới lỏng truy vấn sử dụng kĩ thuật khám phá tri thức.
- Cài đặt hệ thống thử nghiệm.

lớp trong chương trình và CSDL thử nghiệm. Phần cuối chương đưa ra một số kết quả
minh họa hoạt động của hệ thống.
Phần kết luận và hướng phát triển
Phần này tổng kết lại những kết quả đồ án đã đạt được và những vấn đề còn tồn đọng,
đồng thời đưa ra một số phương án phát triển đề tài lên mức cao hơn.
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 3
Mục lục
Mục lục 4
LỜI CẢM ƠN 5
DANH MỤC CÁC HÌNH VẼ 6
DANH MỤC CÁC BẢNG 7
DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ 8
Mở đầu 9
Chương I. Tổng quan về nới lỏng truy vấn 10
1.1 Định nghĩa 10
1.2 Vị trí của nới lỏng 10
11
1.3 Một số cách tiếp cận nới lỏng 11
Chương II. Kĩ thuật khai phá dữ liệu và bài toán học phân loại 13
2.1 Khai phá tri thức 13
15
17
2.2 Mô hình học, dự đoán của bài toán phân loại 17
2.3 Mô hình học cây quyết định 20
2.3 Học cây quyết định cho bài toán nới lỏng truy vấn 31
2.4 Sơ nét về thư viện lập trình học máy của Weka 32
Chương III. Nới lỏng theo tiếp cận của học cây quyết định 33
Chương IV. Chương trình cài đặt thử nghiệm 42
Chương V. Kết luận và hướng phát triển 53
5.1 Các kết luận 53

Hình 1: Vị trí của nới lỏng 11
Hình 2: Thuận lợi của khám phá tri thức 14
Hình 3: Tiến trình khai phá tri thức 15
Hình 4: Ứng dụng của KDD 17
Hình 5: Mô hình học 18
Hình 6: Mô hình thử 19
Hình 7: Mô hình sử dụng (phân loại) 19
Hình 8: Ví dụ về cây quyết định 22
Hình 9: Lượng thông tin đạt được khi phân chia tập ví dụ trên thuộc tính Huminity 26
Hình 10: Lượng thông tin đạt được khi phân chia tập ví dụ trên trên thuộc tính Wind 26
Hình 11: Lượng thông tin đạt được khi phân chia tập ví dụ trên trên thuộc tính Outlook 27
Hình 12: Phân chia trên thuộc tính số 28
Hình 13: Chia lớp theo chỉ số Gini 29
Hình 14: Quá trình thử phân chia và tính chỉ số Gini 30
Hình 15: Cây quyết định thu được sau khi đã phân chia tập ví dụ 31
Hình 16: Giải thuật nới lỏng 37
Hình 17: Trích xuất tri thức về miền giá trị 38
Hình 18: Nới lỏng tập ràng buộc 40
Hình 19: Ví dụ về cây điều kiện 43
Hình 20: Ví dụ về cây điều kiện (2) 44
Hình 21: Cây điều kiện thu được sau phép biến đổi 44
Hình 22: Kiến trúc của hệ thống thử nghiệm 45
Hình 23: Lược đồ CSDL thử nghiệm 48
Hình 24: Giao diện của hệ thống 50
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 6
DANH MỤC CÁC BẢNG
Bảng 1: Dữ liệu thống kê chơi golf 22
Bảng 2: Bảng ví dụ 30
Bảng 3: Bảng dữ liệu thử 34
Bảng 4: Bảng dữ liệu Di 34

bước thực hiện đã là một công việc gây mất thời gian, buồn tẻ, và chán ngắt. Trong
trường hợp xấu nhất họ phải xét đến một hàm số mũ của các khả năng nới lỏng có
thể (các khả năng nới lỏng ở đây lả các cách thử kết hợp khác nhau dựa trên giá trị
đối với mỗi tập các thuộc tính).
Trong tình huống tệ hơn, sự nới lỏng quá mức đối với một truy vấn (đôi khi phá
vỡ cả các ràng buộc để có nhiều bộ thỏa mãn) có thể đưa ra cái giá không ngờ tới
trong khía cạnh băng thông và phí phải trả cho mỗi bộ các kết quả có được.
Trước tình hình đó, yêu cầu đặt ra với các hệ tìm kiếm thông tin hiện đại là phải
sử dụng nguồn tri thức bổ sung để giải quyết ngày càng nhiều hơn những vấn đề
đau đầu nói trên. Vai trò của tri thức không chỉ đem lại trả lời thỏa đáng cho người
dùng mà còn có nhiều khả năng đáng kinh ngạc: giải thích thông minh, cung cấp
thêm hiểu biết và lựa chọn cho người dùng nhờ các tư vấn ngày càng nhanh chóng
và chính xác. Vậy nguồn tri thức này lấy từ đâu?
Khái niệm tri thức chỉ thông tin được tích lũy, bao gồm các nhân tố và mối quan
hệ giữa chúng, được nhận ra, nghiên cứu và được học bởi các hệ thống thông minh,
hay những “hình ảnh mô phỏng của bộ não con người”. Tri thức có thể được coi là
dữ liệu ở mức khái quát và trừu tượng cao.
Kĩ thuật khai phá dữ liệu (KDD) và học máy (Machine learning) mở rộng khả
năng tìm kiếm thông tin. Khả năng học là một trong những thành tố quan trọng của
hành vi thông minh.
Để giải quyết thành công các bài toán khai phá dữ liệu cần có sự phối hợp và nỗ
lực vượt bậc của các chuyên gia và người sử dụng cuối. Nhà chuyên gia cần nắm
vững các kỹ thuật, hiểu được các yêu cầu thực tế, vận dụng kỹ thuật để giải quyết
các bài toán và giải thích kết quả bằng ngôn ngữ thực tế cho người sử dụng. Và
người sử dụng cần nhận ra những bài toán thiết thực, nắm bắt các kết quả đạt được
và vận dụng chúng một cách hiệu quả trong thực tế.
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 9
Chương I. Tổng quan về nới lỏng truy vấn
1.1 Định nghĩa
Như đã giới thiệu, nới lỏng truy vấn là phương pháp được sử dụng trong các hệ

Các kĩ thuật thu thập và biểu diễn tri thức đóng vai trò quan trọng trong việc
phát hiện và mô tả mối quan hệ giữa các giá trị “thô” trong CSDL (là các giá trị
thuộc miền giá trị của thuộc tính nào đó) và các khái niệm ở mức trừu tượng cao
hơn. Các tri thức này là cơ sở cho quá trình nới lỏng truy vấn. Mỗi phương pháp thu
thập và biển diễn tri thức khác nhau đem đến một hướng tiếp cận khác nhau tới nới
lỏng. Có thể kể tên một vài hướng tiếp cận trong số đó, bao gồm: Tiếp cận dựa trên
tập mờ, tiếp cận dựa trên khoảng cách ngữ nghĩa và tiếp cận dựa trên phương pháp
gom nhóm khái niệm, tiếp cận phân cấp trừu trượng tri thức.
Tiếp cận mờ gán cho mỗi đối tượng dữ liệu một độ thuộc vào một miền nào đó.
Độ thuộc này có giá trị từ 0 tới 1. Thông tin trong cơ sở tri thức là những thông tin
“mờ”, tương đương với những giá trị ngôn ngữ được gán độ thuộc đối với miền.
Các câu truy vấn xấp xỉ được thực hiện một cách tự nhiên trên những khoảng mờ.
Tiếp cận khoảng cách ngữ nghĩa định nghĩa số đo khoảng cách giữa một cặp
đối tượng dữ liệu, là độ đo chỉ ra mức độ “gần” nhau về ngữ nghĩa giữa chúng.
Miền giá trị của thuộc tính được biểu diễn bằng một ma trận có trọng số. Cách tiếp
cận này khá dễ dàng và tỏ ra hiệu quả trong việc phát triển các thuật toán nới lỏng
nếu khoảng cách giữa các đối tượng dễ tính toán. Tuy nhiên, tiếp cận khoảng cách
ngữ nghĩa bị hạn chế trong việc biến đổi các đối tượng định lượng và định tính về
cùng một thước đo định lượng. Hơn nữa, không có tiêu chuẩn chung nào trong việc
đánh giá mức độ tương tự về mặt ngữ nghĩa giữa các đối tượng dữ liệu.
Tiếp cận gom nhóm khái niệm áp dụng các phương pháp trừu tượng hóa cho
dữ liệu. Một nhóm các khái niệm tương tự nhau được gom lại thành một khái niệm
duy nhất đại diện cho nhóm đó. Sự gom nhóm khái niệm tạo ra một cấu trúc phân
cấp hình cây gọi là phân cấp khái niệm. Các phân cấp khái niệm là cơ sở tri thức sử
dụng trong nới lỏng. Hướng tiếp cận này chấp nhận những câu truy vấn ngữ nghĩa
dựa trên các khái niệm trừu tượng. Nó tỏ ra có ưu điểm đặc biệt khi các đối tượng
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 11
dữ liệu là định tính và có khả năng phân loại tốt. Tuy nhiên, nó cũng có một số giới
hạn do bị phụ thuộc vào tính đa dạng của các câu truy vấn và vào độ mềm dẻo của
các phân cấp. Hơn nữa, thường xảy ra nhập nhằng giữa các giá trị do sự thiếu vắng

Discovery in Databases - KDD) chỉ một tiến trình rất rộng nhằm tìm kiếm tri thức
trong dữ liệu, và nhấn mạnh các ứng dụng mức cao của các phương pháp khai phá
dữ liệu(Data mining) riêng biệt.
Chúng ta thường thấy dữ liệu ở dạng chuỗi các bít, hoặc các con số và kí hiệu,
hoặc các “đối tượng” mà chúng ta có thể thu thập được trong cuộc sống thường
ngày.
Khái niệm thông tin là dữ liệu được tối thiểu hóa dư thừa, và được cắt giảm tới
mức nhỏ nhất có thể để số hóa dữ liệu.
Khái niệm tri thức là các thông tin được tích hợp, bao gồm các sự kiện và mối
quan hệ giữa chúng, mà có thể được nhận biết, khám phá, hoặc được học từ các
“hình ảnh của bộ não con người”
Tri thức có thể được coi là dữ liệu ở mức trừu tượng và tổng quát quá cao.
Mục đích duy nhất của tiến trình khai phá tri thức là trích xuất tri thức từ dữ liệu
trong các cơ sở dữ liệu rất lớn.
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 13
Hình 2: Thuận lợi của khám phá tri thức
Nó thực hiện điều này bằng cách sử dụng các phương pháp khai phá dữ liệu(giải
thuật) để trích ra(định nghĩa) các tri thức tiềm ẩn, theo các đặc tả về độ đo và giá trị
ngưỡng, sử dụng một cơ sở dữ liệu (CSDL) với bất kì việc tiền xử lý, lấy mẫu, các
chuyển đổi nào được yêu cầu trên CSDL đó.
Tiến trình khai phá tri thức:
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 14
Hình 3: Tiến trình khai phá tri thức
Toàn bộ tiến trình tìm kiếm và hiểu được các mẫu từ dữ liệu bao gồm trong đó
chương trình lặp lại các bước:
• Xây dựng một kiến thức về:
o Miền ứng dụng
o Những thông tin về tính ưu tiên
o Mục đích của người sử dụng cuối
• Tạo ra một tập dữ liệu đích: chọn một tập dữ liệu đích, hoặc chú ý đến một tập

Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 16
Hình 4: Ứng dụng của KDD
Khai phá dữ liệu
Khai phá dữ liệu (Data Mining) là một thành phần cấu thành của tiến trình khám
phá tri thứ (KDD process).
Các nhiệm vụ chính của khai phá dữ liệu(Data Mining)
- Phân loại dữ liệu (Classification): tìm mô tả của một vài lớp đã được định
nghĩa và phân loại các đơn vị dữ liệu vào một trong các lớp ấy.
- Phân cụm dữ liệu (Clustering); định nghĩa một tập hữu hạn các tập hợp hoặc
cụm để mô tả dữ liệu.
- Hồi quy (Regression): ánh xạ một đơn vị dữ liệu tới một biến thực.
- Mô hình hóa sự phụ thuộc (Dependency Modeling): phát hiện một mô hình
mà mô tả các phụ thuộc quan trọng giữa các biến.
- Phát hiện độ lệch và sự thay đổi (Deviation and change detection): khám phá
các thay đổi quan trọng trong dữ liệu.
- Tóm tắt dữ liệu (Summarization): tìm các mô tả tóm tắt cho một tập dữ liệu.
Nội dung đồ án này sẽ phân tích khả năng ứng dụng các bài toán học phân loại
với nới lỏng truy vấn
2.2 Mô hình học, dự đoán của bài toán phân loại
Mục đích của phân loại dữ liệu là để tổ chức và sắp xếp dữ liệu vào trong các
lớp riêng biệt
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 17
- Một mô hình được tạo lần đầu dựa trên sự phân bố dữ liệu.
- Mô hình này sau đó được sử dụng để phân loại dữ liệu mới.
- Cho trước một mô hình, một lớp có thể được dự đoán đối với dữ liệu mới.
Tiến trình từ phân loại đến dự đoán dữ liệu mới gồm 3 bước – 3 mô hình con:
Mô hình học
Mỗi bản ghi (thực thể) được giả định thuộc về một lớp được định nghĩa sẵn,
được xác định bởi một trong số các thuộc tính, được gọi là nhãn lớp.
Tập tất cả các bản ghi được sử dụng để tạo mô hình được gọi là tập rèn luyện.

Amazon, eBay), y tế (MeSH), địa chất (ACORN), khai phá dữ liệu,
2.3 Mô hình học cây quyết định
2.3.1 Cây quyết định
Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo (predictive
model), nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết
luận về giá trị mục tiêu của sự vật/hiện tượng. Mỗi một nút trong (internal node)
tương ứng với một biến; đường nối giữa nó với nút con của nó thể hiện một giá trị
cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu, cho
trước các giá trị của các biến được biểu diễn bởi đường đi từ nút gốc tới nút lá đó.
Kỹ thuật học máy dùng trong cây quyết định được gọi là học bằng cây quyết định,
hay chỉ gọi với cái tên ngắn gọn là cây quyết định.
Học bằng cây quyết định cũng là một phương pháp thông dụng trong khai phá
dữ liệu. Khi đó, cây quyết định mô tả một cấu trúc cây, trong đó, các lá đại diện cho
các phân loại còn cành đại diện cho các kết hợp của các thuộc tính dẫn tới phân loại
đó. Một cây quyết định có thể được học bằng cách chia tập hợp nguồn thành các tập
con dựa theo một kiểm tra giá trị thuộc tính. Quá trình này được lặp lại một cách đệ
qui cho mỗi tập con dẫn xuất. Quá trình đệ qui hoàn thành khi không thể tiếp tục
thực hiện việc chia tách được nữa, hay khi một phân loại đơn có thể áp dụng cho
từng phần tử của tập con dẫn xuất. Một bộ phân loại rừng ngẫu nhiên (random
forest) sử dụng một số cây quyết định để có thể cải thiện tỉ lệ phân loại.
Cây quyết định cũng là một phương tiện có tính mô tả dành cho việc tính toán
các xác suất có điều kiện.
Cây quyết định có thể được mô tả như là sự kết hợp của các kỹ thuật toán học và
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 20
tính toán nhằm hỗ trợ việc mô tả, phân loại và tổng quát hóa một tập dữ liệu cho
trước.
Ta sẽ dùng một ví dụ để giải thích về cây quyết định:
David là quản lý của một câu lạc bộ đánh golf nổi tiếng. Anh ta đang có rắc rối
chuyện các thành viên đến hay không đến. Có ngày ai cũng muốn chơi golf nhưng
số nhân viên câu lạc bộ lại không đủ phục vụ. Có hôm, không hiểu vì lý do gì mà

12 Overcast Mild High Stron
g
Yes
13 Overcast Hot Normal Weak Yes
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 21
14 Rain Mild High Stron
g
No
Bảng 1: Dữ liệu thống kê chơi golf
Sau đó, để giải quyết bài toán của David, người ta đã đưa ra một mô hình cây
quyết định.
Hình 8: Ví dụ về cây quyết định
Cây quyết định là một mô hình dữ liệu mã hóa phân bố của nhãn lớp theo các
thuộc tính dùng để dự đoán. Đây là một đồ thị có hướng phi chu trình dưới dạng
một cây. Nút gốc (nút nằm trên đỉnh) đại diện cho toàn bộ dữ liệu. Thuật toán cây
phân loại phát hiện ra rằng cách tốt nhất để giải thích biến phụ thuộc, play (chơi), là
sử dụng biến Outlook. Phân loại theo các giá trị của biến Outlook, ta có ba nhóm
khác nhau: Nhóm người chơi golf khi trời nắng, nhóm chơi khi trời nhiều mây, và
nhóm chơi khi trời mưa.
Kết luận thứ nhất: nếu trời nhiều mây, người ta luôn luôn chơi golf. Và có một
số người ham mê đến mức chơi golf cả khi trời mưa.
Tiếp theo, ta lại chia nhóm trời nắng thành hai nhóm con. Ta thấy rằng khách
hàng không muốn chơi golf nếu độ ẩm lên quá 70%.
Cuối cùng, ta chia nhóm trời mưa thành hai và thấy rằng khách hàng sẽ không
chơi golf nếu trời nhiều gió.
Và đây là lời giải ngắn gọn cho bài toán mô tả bởi cây phân loại. David cho
phần lớn nhân viên nghỉ vào những ngày trời nắng và ẩm, hoặc những ngày mưa
gió. Vì hầu như sẽ chẳng có ai chơi golf trong những ngày đó. Vào những hôm
khác, khi nhiều người sẽ đến chơi golf, anh ta có thể thuê thêm nhân viên thời vụ để
phụ giúp công việc.

i
) là tập con mà có giá trị thuộc tính A là
v
i
 Nếu Tập_mẫu_luyện(v
i
) là rỗng
 Thì dưới nhánh mới này tạo một nút lá có nhãn = giá trị phổ
biến trong tập mẫu
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 23
 Ngược lại, dưới nhánh mới tạo cây con
ID3(Tập_mẫu_luyện(v
i
), Thuộc_tính_đích,
Danh_sách_thuộc_tính)
- Thuật toán kết thúc
- Trả về gốc của cây (root)
Thuật toán C4.5
C4.5 xây dựng cây quyết định từ một tập dữ liệu rèn luyện theo như cách của
ID3, sử dụng lý thuyết entropy thông tin. Dữ liệu rèn luyện S=s
1
s
2
là một tập các
mẫu đã được phân loại. Mỗi mẫu dữ liệu s
i
=x
1
x
2

ID3/C4.5 sử dụng độ đo để lựa chọn thuộc tính: Thuộc tính được chọn là thuộc tính
có lợi nhất cho quá trình phân lớp (tạo ra cây nhỏ nhất)
Có 2 độ đo thường dùng
- Độ đo định lượng thông tin (Information gain)
 Giả sử tất cả các thuộc tính dạng phi số
 Có thể biến đổi để áp dụng cho thuộc tính số
- Chỉ số Gini (Gini index)
 Giả sử tất cả các thuộc tính dạng số
 Giả sử tồn tại một vài giá trị có thể phân chia giá trị của từng
thuộc tính
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 24
 Có thể biến đổi để áp dụng cho thuộc tính phi số
Độ đo định lượng thông tin
Ta ký kiệu:
S: số lượng tập huấn luyện
S
i
: số các mẫu của S nằm trong lớp C
i
với i = {1, …, m}
- Thông tin cần biết để phân lớp một mẫu:
Thuộc tính A có các giá trị {a
1
, a
2
, …,a
n
}
Dùng thuộc tính A để phân chia tập huấn luyện thành n tập con {S
1

= 9, S
2
= 5
- Xét thuộc tính Huminity
Sinh viên thực hiện: Nguyễn Chí Thanh – K50 – Lớp HTTT B Trang 25