MỤC LỤC
1.2 Những thách thức trong Khai phá dữ liệu 9
1.3 Những vấn đề được chú trọng trong Khai phá dữ liệu 11
CHƯƠNG II: PHÂN LỚP DỮ LIỆU 12
2.1 Bài toán phân lớp 12
2.1.1 Phát biểu bài toán 12
2.1.2 Một số ứng dụng của bài toán phân lớp 12
2.2 Các kỹ thuật phân lớp 13
2.2.1 Kỹ thuật sử dụng khoảng cách 13
2.2.2 Kỹ thuật phân lớp theo tiếp cận thống kê xác xuất 17
2.2.3 Cây quyết định 30
2.2.4 Mạng neural 40
2.2.5 Các kỹ thuật khác 54
Bảng từ viết tắt
Từ hoặc cụm từ Từ viết tắt Từ tiếng Anh
Cơ sở dữ liệu CSDL Database
Khai phá dữ liệu KPDL Data Mining
1
LỜI NÓI ĐẦU
Trong thời đại ngày nay, Internet phát triển rộng lớn khắp toàn cầu,
cùng với sự bùng nổ của ngành Công nghệ thông tin và những điều kiện
phát triển của nó, các công nghệ lưu trữ dữ liệu và phục hồi dữ liệu ngày
càng phát triển nhanh chóng tạo điều kiện cho các đơn vị thu thập dữ liệu
nhiều hơn và tốt hơn. Chính vì lý do này mà cơ sở dữ liệu ở các cơ quan,
doanh nghiệp, đơn vị, trường học ngày càng nhiều thông tin tiềm ẩn, phong
phú và đa dạng; đặc biệt trong việc học tập các môn học của học viên, các
nhà trường đã nhận thức được tầm quan trọng của việc nắm bắt và xử lý
thông tin, sử dụng những tri thức được chiết xuất từ cơ sở dữ liệu để phục
vụ cho việc dự đoán phân loại học viên trong các môn học tiếp theo trong
quá trình học tập của học viên tại nhà trường.
Trước những điều kiện và yêu cầu đặt ra của nhiệm vụ đào tạo, đòi

Discovery in Databases – KDD). Khai phá dữ liệu là giai đoạn quan trọng
nhất trong tiến trình khám phá tri thức từ cơ sở dữ liệu, các tri thức này có
rất nhiều ý nghĩa, là cơ sở hỗ trợ trong việc ra quyết định trong khoa học và
kinh doanh.
Các bước trong quá trình khám phá tri thức:
- Làm sạch dữ liệu (Data cleaning): loại bỏ dữ liệu nhiễu hoặc dữ
liệu không thích hợp.
- Tích hợp dữ liệu (Data Intergration): Tích hợp dữ liệu từ các nguồn
khác nhau như CSDL, kho dữ liệu, file text,
- Trích chọn dữ liệu (data selection): trích chọn những tập dữ liệu
cần được khai phá từ các tập dữ liệu lớn ban đầu (database, data
warehouses,…) theo một số tiêu chí nhất định.
- Biến đổi dữ liệu (data transformation): chuẩn hoá và làm mịn dữ
liệu, đưa dữ liệu về dạng thuận lợi nhất, phù hợp cho việc khai phá bằng
cách thực hiện các thao tác nhóm hoặc tập hợp.
- Khai phá dữ liệu (data mining): là giai đoạn thiết yếu, đây là bước
quan trọng và tốn nhiều thời gian nhất của toàn bộ quá trình khám phá tri
thức, đây là bước áp dụng những kỹ thuật khai phá để khai thác, trích xuất
thông tin có ích, những mẫu điển hình, những mối liên hệ đặc biệt có nhiều
giá trị, mang nhiều ý nghĩa từ dữ liệu.
- Đánh giá mẫu (Pattern Evaluation): đánh giá sự hữu ích của các
mẫu biểu diễn tri thức dựa vào một số phép đo.
4
- Trình diễn dữ liệu (knowledge presentation): sử dụng các kỹ thuật
trình diễn và trực quan hoá dữ liệu để biểu diễn tri thức khai phá được cho
người sử dụng.
Hình 1.1 Các bước trong quá trình khám phá trí thức.
Khai phá dữ liệu là một lĩnh vực liên quan tới rất nhiều ngành học khác
như: hệ Cơ sở dữ liệu, thống kê, trực quan hoá. Tuỳ vào cách tiếp cận được
sử dụng, khai phá dữ liệu còn có thể áp dụng một số kỹ thuật như mạng

- Kỹ thuật khai phá dữ liệu dự đoán: đưa ra các dự đoán dựa vào các
suy diễn trên dữ liệu hiện thời, các kỹ thuật này gồm có: phân lớp
(classification), hồi quy (regression),…
Các bài toán chính trong khai phá dữ liệu: 3 bài toán thông dụng và
phổ biến nhất là:
- Bài toán phân lớp dữ liệu và hồi quy: Mục tiêu của phương pháp
phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu. Quá trình phân
lớp dữ liệu thường gồm 2 bước: xây dựng mô hình và sử dụng mô hình để
phân lớp.
6
+ Xây dựng mô hình: một mô hình sẽ được xây dựng trên việc phân
tích các mẫu dữ liệu sẵn có. Mỗi mẫu tương ứng với một lớp, được quyết
định bởi một thuộc tính gọi là thuộc tính lớp. Các mẫu dữ liệu này còn
được gọi là tập dữ liệu huấn luyện. Các nhãn lớp của tập dữ liệu huấn luyện
đều phải được xác định trước khi xây dựng mô hình, vì vậy phương pháp
này còn được gọi là học có giám sát, khác với phân cụm dữ liệu là học
không có giám sát.
+ Sử dụng mô hình để phân lớp dữ liệu: trước hết ta tính toán độ
chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ
được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương
lai.
Phương pháp hồi quy khác với phân lớp dữ liệu ở chỗ, hồi quy dùng
để dự đoán về các giá trị liên tục còn phân lớp dữ liệu thì chỉ dùng để dự
đoán về các giá trị rời rạc.
- Bài toán phân cụm (clustering/segmentation): Mục tiêu chính của
phương pháp phân cụm dữ liệu là nhóm các đối tượng tương tự nhau trong
tập dữ liệu vào các cụm sao cho các đối tượng thuộc cùng một lớp là tương
đồng còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng.
Phân cụm dữ liệu là một ví dụ của phương pháp học không giám sát.
Không giống như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải

- Bài toán mô tả khái niệm (concept description & summarization):
tập trung vào việc mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn
bản, mô tả khái niệm,…
Những công cụ khai phá dữ liệu có thể dự đoán những xu hướng
trong tương lai và do đó cho phép doanh nghiệp ra những quyết định kịp
thời được định hướng bởi tri thức mà khai phá dữ liệu mang lại.
8
Những ứng dụng điển hình của khai phá dữ liệu:
 Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis and decision
support)
 Text mining & Webmining: phân lớp văn bản và các trang Web, tóm
tắt văn bản, tìm kiếm thông tin,…
 Tin – sinh: tìm kiếm, đối sánh các quan hệ gen và thông tin di
truyền, mối liên hệ giữa một số hệ gen và một số bệnh di truyền,…
 Điều trị y học: (medical treatment): mối liên hệ giữa triệu chứng,
chẩn đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc men,
…)
 Tài chính và thị trường chứng khoán (finance & stock market): phân
tích tình hình tài chính và dự báo giá của các loại cổ phiếu trong thị
trường chứng khoán,…
Những ứng dụng thực tế:
+ Ngành bảo hiểm y tế Australia đã dựa vào việc chẩn đoán bệnh
trong y tế dựa trên kết quả xét nghiệm và đã phát hiện ra nhiều trường hợp
xét nghiệm không hợp lý, tiết kiệm được 1 triệu USD/năm.
+ Trang Web mua bán qua mạng Amazon.com cũng tăng doanh thu
nhờ áp dụng khái phá dữ liệu trong việc phân tích sở thích mua bán của
khách hàng.
+ Bitish Telecom đã phát hiện ra những nhóm người thường xuyên
gọi cho nhau bằng mobile và thu lợi hàng triệu USD.
1.2 Những thách thức trong Khai phá dữ liệu

10
• Khả năng tích hợp với các hệ thống khác: Hệ thống để đạt được
hiệu quả và khả năng cao nhất thì phải được tích hợp với các hệ
thống khác, ví dụ như các hệ sensor đầu thu dữ liệu, các công cụ
bảng tính, trực quan dữ liệu.
1.3 Những vấn đề được chú trọng trong Khai phá dữ liệu
KPDL là một lĩnh vực mới, do đó đang còn rất nhiều vấn đề chưa đuợc
nghiên cứu một cách trọn vẹn. Sau đây là một số hướng nghiên cứu đã và
đang thu hút được sự chú ý của các nhà tin học.
• OLAM (OnLine Analytical Mining) - Sự tích hợp giữa CSDL, kho
dữ liệu, và KPDL. Hiện nay một số hệ quản trị CSDL như Oracle,
MS SQL Server, DB2 đã tích hợp tính năng xây dựng kho dữ liệu và
phân tích trực tuyến (OLAP). Những nhà nghiên cứu trong lĩnh vực
CSDL mong muốn có một sự tích hợp giữa CSDL, kho dữ liệu và
KPDL.
• Khám phá được nhiều dạng tri thức khác nhau từ nhiều kiểu dữ liệu.
• Tính hiệu quả, tính chính xác, độ phức tạp tính toán, khả năng mở
rộng và tích hợp, xử lý nhiễu và dữ liệu không đầy đủ, tính hữu
dụng (ý nghĩa) của tri thức.
• Kết hợp KPDL với tri thức cơ sở.
• Vấn đề song song hóa và phân tán quá trình KPDL.
• Ngôn ngữ truy vấn trong KPDL (Data Mining Query Language –
DMQL): cung cấp cho người sử dụng một ngôn ngữ hỏi thuận tiện
tương tự như SQL đối với CSDL quan hệ.
• Biểu diễn và trực quan hóa tri thức khai phá được sao cho gần gũi
với người sử dụng. Tri thức có thể biểu diễn đa chiều, đa tầng để sử
dụng tri thức hiệu quả hơn.
11
CHƯƠNG II: PHÂN LỚP DỮ LIỆU
2.1 Bài toán phân lớp

Chuỗi AND.
Chuỗi Protein
Các dạng gen
protein đã biết
Y học Xác định ung thư Hình ảnh tế bào
Kết luận có ung thư
hay không?
Phân loại văn
bản
Tìm kiếm thông
tin trên Internet
Dữ liệu văn bản Phân loại văn bản
Tự động hoá
công nghiệp
Kiểm tra mẫu các
sản phẩm
Ảnh cường độ
sáng của các sản
phẩm
Sản phẩm có bị lỗi
hay không?
Nhận dạng
tiếng nói
Các thao tác tự
động (bán vé máy
bay, đặt chỗ…)
Tín hiệu dạng
số
Các từ, câu lệnh
Bảng 2.1 Một số ứng dụng của bài toán phân lớp

n
)
và Y = (y
1
, y
2
, …, y
n
) trong không gian Enclid n chiều được định nghĩa:
13
d (X,Y) =
∑
=
−=
n
i
ii
yxYXd
1
2
)(),(
(2-1)
Mẫu kiểm tra sẽ thuộc vào lớp thông dụng nhất trong số k mẫu có khoảng
cách gần nhất với mẫu kiểm tra.
Phân lớp/nhóm n đối tượng thành k lớp dựa trên đặc tính/thuộc tính
của đối tượng (k ≤ n nguyên, dương).
Mỗi đối tượng được coi là 1 véc tơ m chiều (m - số thuộc tính của
đối tượng). Việc phân lớp được thực hiện dựa trên khoảng cách Euclidean
nhỏ nhất giữa đối tượng đến phần tử trung tâm của các lớp. Phần tử trung
tâm của lớp được xác định bằng giá trị trung bình các phần tử trong lớp.

c
t
s
sj
ij
∑
=
=
1
(2-3)
15
- Khởi tạo ci i=1 k ngẫu nhiên
- Lặp
B1: Xác định khoảng cách Euclidean δ giữa aj j=1 n và ci i=1 k
theo công thức (2-2).
B2: Nhóm đối tượng vào cluster dựa δ nhỏ nhất.
B3: Tính ci của mỗi nhóm theo công thức (2-3).
- Đến khi không còn đối tượng nào di chuyển từ lớp này sang lớp
khác.
Bảng 2.2 Thuật toán k - means
c) Đánh giá ưu nhược điểm
Nhược điểm
 Việc khởi tạo phần tử trung tâm của lớp ban đầu ảnh hưởng đến sự
phân chia đối tượng vào lớp trong trường hợp dữ liệu không lớn.
 Số lớp k luôn phải được xác định trước.
 Không xác định được rõ ràng vùng của lớp, cùng 1 đối tượng, nó có
thể được đưa vào nhóm này hoặc nhóm khác khi dung lượng dữ liệu
thay đổi.
 Điều kiện khởi tạo có ảnh hưởng lớn đến kết quả. Điều kiện khởi tạo
khác nhau có thể cho ra kết quả phân vùng nhóm khác nhau.

• Giá trị của các xác suất đều nằm trong khoảng từ 0 đến 1. 0≤P(A)≤1.
• Các mục tiêu tất yếu đúng có xác suất là 1, các mục tiêu tất yếu sai
có xác suất là 0. P(True)=1 P(False)=0
• Xác suất của các sự kiện tách rời được tính theo công thức:
P(A∪B) = P(A) + P(B) – P(A ∩ B)
Sự phân bố xác suất chung (The joint probability distribution)
Một mô hình xác suất của một lĩnh vực gồm một tập hợp các biến
ngẫu nhiên mà chúng có thể lấy các giá trị đặc biệt với xác suất nào đó. Đặt
các biến là X
1
X
n
. Một sự kiện nguyên tử là việc phân bổ các giá trị riêng
biệt tới tất cả các biến, nói cách khác là xác định trạng thái cụ thể của một
vùng.
17
Sự phân bố xác suất chung P(X
1
,….,X
n
) gán xác suất cho các sự kiện
có thể. P(X
i
) là một vectơ có kích thước là 1 đối với không gian xác suất
các giá trị có thể của biến X
i
. Khi đó một bảng có kích thước n ô với giá trị
trong mỗi ô là xác suất của một trạng thái xác định.
Ví dụ: Đây là sự phân bố xác suất chung cho vùng y học chung bao gồm 2
biến logic Toothache và Cavitry

ToothacheCavryP
ToothacheCavtyP
b) Thuật toán phân lớp Bayesian
Như đã giải thích, điểm mấu chốt của các thuật toán phân lớp là phải
phân cụm các phần tử với nhau. Điều đó có nghĩa là xuất phát từ một tập
hợp các điểm, thuật toán sẽ cố gắng đưa ra một tập các tập con có thể phủ
18
kín toàn bộ không gian (hay còn gọi là phân hoạch) sao cho việc tạo các tập
con càng đơn giản càng tốt.
Một vấn đề đặt ra là làm thế nào để xác định một đối tượng thuộc
vào một lớp nào đó khi chỉ kiểm tra vectơ thuộc tính của nó là rất khó.
Thực tế là, sự khác biệt giữa vectơ thuộc tính của đối tượng và vectơ thuộc
tính của lớp để biết được đối tượng thuộc lớp nào, sự khác biệt này khiến
cho việc có được một biến cố chắc chắn là rất khó khăn. Đây chính là điểm
giải thích tại sao các phương pháp tiếp cận theo hướng thống kê lại được sử
dụng rộng rãi.
Thuật toán phân lớp Bayesian là một trong những thuật toán phân
lớp điển hình nhất trong khai thác dữ liệu và tri thức. Ý tưởng chính của
thuật toán là tính xác suất có điều kiện của sự kiện c thuộc lớp x theo sự
phân loại dựa trên xác suất có trước của sự kiện c thuộc lớp x trong điều
kiện T
∑
= )|(),|(),|( xTpTxcpxcp
τ
(2-6)
Gọi V là tập tất cả các từ vựng.
Giả sử có N lớp tài liệu: C
1,
C
2

li
DocF
DocFTF
j
CFPCP
CFPCP
DocCP
j
j
1
),(
),(
))|((*)(
)|(*)(
)|(
(2-7)
Với:
∑
=
+
+
=
n
i
ij
j
j
CFTFV
CFTF
CFP

Công thức F(F
i
| C) được tính sử dụng ước lượng xác suất Laplace.
Sở dĩ có số 1 trên tử số của công thức này để tránh trường hợp tần suất của
từ F
i
trong lớp C bằng 0, khi F
i
không xuất hiện trong lớp C.
Để giảm sự phức tạp trong tính toán và giảm thời gian tính toán,
chúng ta có nhận xét rằng, không phải tài liệu Doc đã cho đều chứa tất cả
các từ trong tập từ vựng V. Do đó, TF(F
i
| DOC) = 0 khi từ F
i
thuộc V
nhưng không thuộc tài liệu Doc, nên ta có (P(F
j
| C))
TF(Fj, Doc)
= 1. Như vậy
công thức (2-7) sẽ được viết lại như sau:
(2-9)
Với:
20
Như vậy trong quá trình phân lớp không dựa vào toàn bộ tập từ vựng
mà chỉ dựa vào các từ khóa xuất hiện trong tài liệu Doc.
c) Mạng tin cậy Bayesian
Trong phần trên, chúng ta đã thấy rằng sự phân bổ xác suất có thể
giải quyết trả lời bất kỳ câu hỏi nào về vùng, nhưng có thể trở nên rất phức

có thể được mô tả bằng giá trị của nút cha. Ví dụ, bảng điều kiện xác suất
cho biến chuông báo động ngẫu nhiên khi có trộm hoặc động đất có thể
được mô tả dưới đây:
Burg
lary
Earth
qake
P(Alarm|Burglary,
Earthqake)
True False
True True 0.950 0.050
True False 0.950 0.050
Fals
e
True 0.290 0.710
Fals
e
False 0.001 0.999
Mỗi dòng trong bảng phải có tổng bằng 1, bởi vì mỗi mục phải diễn
đạt hết các khả năng xảy ra. Ở đây chỉ có một trong hai trong mỗi dòng mô
tả độc lập các sự kiện. Một cách tổng quát, một bảng Boolean với các giá
trị logic với n giá trị Boolean chứa đựng 2
n
các biến cố độc lập. Một nút
không có cha chỉ có 1 dòng biểu diễn trật tự xác suất của các biến cố.
Ý nghĩa hình học của mạng tin cậy
Có hai cách để hiểu ý nghĩa của mạng tin cậy. Thứ nhất, xem mạng
như là sự trình bày sự phân bố xác suất. Thứ hai, xem mạng như một minh
hoạ tập hợp các trạng thái tình thái độc lập. Cả hai cách nhìn là tương
đương, nhưng cách thứ nhất đưa đến sự hướng dẫn dễ hiểu hơn về cấu trúc

=
=
(2-10)
Như vậy, mỗi mục vào trong mạng được đại diện bởi một giá trị
thích hợp của bảng phân bố xác suất trong mạng tin cậy. Bảng CPT, do đó,
cung cấp các phân tích trình diễn cho mạng.
Một phương pháp xây dựng mạng tin cậy
Đẳng thức (2-10) xác định ý nghĩa của mạng tin cậy. Tuy nhiên, nó
không giải thích cách xây dựng mạng tin cậy, do đó sự phân bố xác suất
cuối cùng là một sự biểu diễn khái niệm vùng tốt nhất. Bây giờ, chúng ta
xem xét đẳng thức 2-10 và chỉ ra mối quan hệ độc lập có điều kiện chắc
chắn có thể được sử dụng cho các kỹ sư xây dựng trong mô hình mạng.
Đầu tiên, chúng ta viết lại các xác suất điều kiện sử dụng định nghĩa xác
suất điều kiện:
P(x
1
,…,x
n
) = P(x
n
| x
n-1
,…,x
1
) P(x
n-1
,….,x
1
) (2-11)
Tiếp theo chúng ta lặp lại các thủ tục, giảm dần số lượng các biến cố xác

ii
xxxP
1
11
), ,|(
(2-12)
23
So sánh với đẳng thức (2-10) chúng ta thấy rằng sự đặc tả trong các
nút trong mạng là tương đương, do vậy ta có công thức:
P(X
i
| X
i-1
,…, X
1
) = P(X
i
/ Parents (X
i
)) (2-13)
Trong đó: Parents(X
i
) ⊆ {x
i-1
,….,x
1
}. Điều kiện cuối cùng này dễ
dàng được thoả mãn bởi việc gán nhãn thứ tự bất kỳ phù hợp với bộ phận
sắp đặt ẩn trong cấu trúc đồ thị.
Đẳng thức trên chỉ ra rằng mạng tin cậy trình diễn đúng vùng chỉ khi

trường hợp điều kiện có thể. Thực tế, đây là chuỗi sự kiện trường hợp xấu
nhất nơi quan hệ giữa các nút cha và nút con là hoàn toàn độc đoán. Thông
thường, như các quan hệ dẫn tới 1 nút của vài trường hợp có sự phù hợp
với phân bố tiêu chuẩn, nó làm thoả mãn vài trường hợp mẫu. Trong những
trường hợp này, để hoàn thành bảng cần phải đặc tả tên của các mẫu và có
lẽ cung cấp thêm một vài tham số.
Ví dụ đơn giản nhất là các nút tiền định. Một nút tiền định là nút có
giá trị được xác định chính xác bởi giá trị của các nút cha, những giá trị
chắc chắn. Quan hệ có thể là một logic - Ví dụ, quan hệ giữa các nút cha
Canadian, US, Mexican và nút con NorthAmerican là đơn nơi con tách rời
các cha. Quan hệ cũng có thể là số - Ví dụ, nếu các nút cha là giá của mô
hình cá biệt của ô tô ở các nhà bán buôn, và nút con là giá của người tiêu
dùng cuối cùng phải trả, thì nút con là giá trị nhỏ nhất của các giá trị nút
cha; hoặc nếu các nút cha dẫn đến (các con sông) các hồ chứa từ các hồ
khác và con là sự thay đổi của các loại hồ, thế thì con là sự khác nhau giữa
việc chảy đến và chảy đi của các nút cha.
Quan hệ không chắc chắn thường được đặc trưng bởi cách gọi là
quan hệ logic (noisy). Ví dụ chuẩn là cách gọi là quan hệ noisy-OR với đặc
tính chung của Logic OR. Mô hình noisy-OR thêm vài tính không chắc
chắn vào xấp xỉ logic chặt chẽ này. Mô hình tạo ra ba chấp nhận đúng. Thứ
nhất, nó chấp nhận rằng mỗi mệnh đề có một sự thay đổi độc lập với các
mệnh đề tác động. Thứ hai, nó chấp nhận rằng tất cả các mệnh đề có thể
được liệt kê. Thứ ba, nó chấp nhận rằng những hạn chế thậm chí xảy ra.
25

Trích đoạn Các kỹ thuật khác

---