TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
TP.HỒ CHÍ MINH
CÔNG NGHỆ TRI THỨC VÀ ỨNG DỤNG
Đề tài: TÌM HIỂU VỀ KHAI PHÁ DỮ LIỆU
VÀ CÁC THUẬT TOÁN SỬ DỤNG TRONG KHAI PHÁ DỮ LIỆU

GVHD: GS TSKH Hoàng Kiếm
HVTH: Nguyễn Hồng Thái
LỚP: CH-CNTTQM K6
Mã HV: CH1101040
11
Tp HCM, tháng 05 năm 2012
Nhận xét của giáo viên:
………….……
………….……
………….……
………….……
………….……
………….……
………….……
………….……
………….……
………….……
………….……
………….……
………….……
………….……
………….……
………….……
………….……
………….……

Lĩnh vực khai phá dữ liệu (data mining) chuyên nghiên cứu về những vấn đề
này.
2. Định nghĩa
Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để tự động
khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập
hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm ẩn
trong tập dữ liệu đó.
3. Các chức năng chính
Khai phá dữ liệu được chia nhỏ thành một số hướng chính như sau:
- 4 -
Đồ án môn học: Công nghệ trí thức và ứng dụng
1) Tìm luật kết hợp (association rules)
Là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Ví dụ: “60 % nam
giới vào siêu thị nếu mua bia thì có tới 80% trong số họ sẽ mua thêm thịt bò
khô”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kính doanh, y học, tin-
sinh, tài chính & thị trường chứng khoán, .v.v.
2) Phân lớp và dự đoán (classification & prediction)
Xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ: phân
lớp vùng địa lý theo dữ liệu thời tiết. Hướng tiếp cận này thường sử dụng một
số kỹ thuật của machine learning như cây quyết định (decision tree), mạng nơ
ron nhân tạo (neural network), .v.v. Người ta còn gọi phân lớp là học có giám
sát (học có thầy).
3) Phân cụm (clustering)
Xếp các đối tượng theo từng cụm (số lượng cũng như tên của cụm chưa
được biết trước. Người ta còn gọi phân cụm là học không giám sát (học không
thầy).
Khai phá chuỗi (sequential/temporal patterns): tương tự như khai phá luật
kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được
ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính
dự báo cao.

nhãn là tên các thuộc tính, các cạnh được gán các giá trị có thể của các thuộc
tính, các lá miêu tả các lớp khác nhau. Các đối tượng được phân lớp theo các
đường đi trên cây, qua các cạnh tương ứng với giá trị của thuộc tính của đối
tượng tới lá.
- 6 -
Đồ án môn học: Công nghệ trí thức và ứng dụng
Figure 1: Mẫu kết với phương pháp cây quyết định
- Tạo luật: Các luật được tạo ra nhằm suy diễn một số mẫu dữ liệu có ý
nghĩa về mặt thống kê. Các luật có dạng Nếu P thì Q với P là mệnh đề đúng với phần
dữ liệu trong cơ sở dữ liệu, Q là mệnh đề dự đoán.
- Cây quyết định và luật có ưu điểm là hình thức miêu tả đơn giản, mô
hình suy diễn khá dễ hiểu đối với người sử dụng. Tuy nhiên, giới hạn của nó là miêu tả
cây và luật chỉ có thể biểu diễn được một số dạng chức năng và vì vậy giới hạn cả về
độ chính xác của mô hình
3) Phân lớp và hồi quy phi tuyến:
Các phương pháp này bao gồm một họ các kỹ thuật dự đoán để làm cho
các kết hợp tuyến tính và phi tuyến của các hàm cơ bản (hàm sygmoid, hàm
spine, hàm đa thức) phù hợp với các kết hợp của các giá trị biến vào.
4) Phân nhóm và phân đoạn:
Kỹ thuật phân nhóm và phân đoạn là những kỹ thuật phân chia dữ liệu sao
cho mỗi phần hoặc mỗi nhóm giống nhau theo một tiêu chuẩn nào đó. Mối quan
hệ thành viên của các nhóm có thể dựa trên mức độ giống nhau của các thành
viên và từ đó xây dựng nên các luật ràng buộc giữa các thành viên trong nhóm.
- 7 -
Có tham
gia thi
Không tham
gia thi
Không qua môn
Điểm >= 5Điểm < 5

Đồ án môn học: Công nghệ trí thức và ứng dụng
nghiên cứu mô hình học của hệ thống thần kinh con người. Mạng neuron có thể
đưa ra ý nghĩa từ các dữ liệu phức tạp hoặc không chính xác và có thể được sử
dụng để chiết xuất các mẫu và phát hiện ra các xu hướng quá phức tạp mà con
người cũng như các kỹ thuật máy tính khác không thể phát hiện được.
Khi đề cập đến khai thác dữ liệu, người ta thường đề cập nhiều đến mạng
neuron. Tuy mạng neuron có một số hạn chế gây khó khăn trong việc áp dụng
và triển khai nhưng nó cũng có những ưu điểm đáng kể. Một trong số những ưu
điểm phải kể đến của mạng neuron là khả năng tạo ra các mô hình dự đoán có
độ chính xác cao, có thể áp dụng được cho rất nhiều loại bài toán khác nhau đáp
ứng được các nhiệm vụ đặt ra của khai phá dữ liệu như phân lớp, phân nhóm,
mô hình hoá, dự báo các sự kiện phụ thuộc vào thời gian,…
Đặc điểm của mạng neuron là không cần gia công dữ liệu nhiều trước khi
bắt đầu quá trình học như các phương pháp khác. Tuy nhiên, để có thể sử dụng
mạng neuron có hiệu quả cần phải xác định các yếu tố khi thiết kế mạng như:
- Mô hình mạng là gì?
- Mạng cần có bao nhiêu nút?
- Khi nào thì việc học dừng để tránh bị “học quá”?
- …
Ngoài ra còn có rất nhiều bước quan trọng cần phải làm để tiền xử lý dữ
liệu trước khi đưa vào mạng neuron để mạng có thể hiểu được (ví dụ như việc
chuẩn hoá dữ liệu, đưa tất cả các tiêu chuẩn dự đoán về dạng số).
Mạng neuron được đóng gói với những thông tin trợ giúp của các chuyên
gia đáng tin cậy và được các chuyên gia đảm bảo các mô hình này làm việc tốt.
Sau khi học, mạng có thể được coi là một chuyên gia trong lĩnh vực thông tin
mà nó vừa được học.
8) Thuật giải di truyền:
Giải thuật di truyền, nói theo nghĩa rộng là mô phỏng lại hệ thống tiến
hoá trong tự nhiên, chính xác hơn đó là các giải thuật chỉ ra tập các cá thể được
- 9 -

Các thuật toán được đề cử bao gồm:
1. C4.5
2. K-means
3. SVM (Support Vector Machine)
4. Apriori
5. EM (Epectation Maximization)
6. PageRank
7. AdaBoost
8. kNN (k-nearest neighbor classification)
9. Naive Bayes
10. CART
Trong phạm vi của bài thu hoạch này, em xin trình bày về 5 thuật toán C4.5,K-
means, Apiori, PageRank và Naïve Bayes
1. Thuật toán C45
Hệ thống khởi tạo các bộ phân lớp là một trong những bài toán thường gặp
trong khai phá dữ liệu. Mỗi hệ thống sẽ nhận vào một tập các trường hợp, được phân
bố trong một tập các lớp, trong đó mỗi lớp thường có một tập thuộc tính mang một tập
giá trị cố định nào đó. Đầu ra của hệ thống sẽ là một bộ phân lớp. Để khi xuất hiện một
trường hợp mới, từ bộ phân lớp này, ta có thể xác định được lớp mà trường hợp này
thuộc về, và từ đó xác định các thuộc tính tổng quát của trường hợp mới này.
Giống như những thuật toán khác trong khai phá dữ liệu, C45 sử dụng cây quyết
định để mô tả kết của mình.
1.2. Cây quyết định
Cho tập S là tập các mẫu, C4.5 sinh ra cây quyết định dựa theo thuật toán chia
để trị:
− Nếu tất cả các trường hợp trong S đều thuộc về cùng một lớp hoặc tập S nhỏ, thì
cây chỉ bao gồm một nút lá, được gán nhãn là lớp phổ biến nhất trong S.
- 11 -
Đồ án môn học: Công nghệ trí thức và ứng dụng
− Ngược lại, chọn một thuộc tính nhận 2 hay nhiều giá trị trong tập S. Tạo cây với

tiếp tục sử dụng công thức tính InfoGain như sau:
Với:
Tương tự ta tính được f(Wind) > 0 và f(Temp) > 0
Nên InfoGain(Sunny, Humidity) là lớn nhất. Ta dùng Humidity để phân lớp cho
Sunny.
Một cách tương tự, ta tính được Wind là thuộc tính để phân lớp cho Rain (Figure 1)
Vậy, ta được cây quyết định như sau:
Figure 3
- 14 -
Đồ án môn học: Công nghệ trí thức và ứng dụng
GainRatio:
GainRatio cung cấp một công thức khác để xác định thuộc tính được dùng trong cây
quyết định. Công thức như sau:
2. Thuật toán K-means:
- Tư tưởng của thuật toán là chia CSDL thành k nhóm (k do người dùng quyết định)
- Thuật toán thao tác trên một tập vector d-chiều D = { | i = 1, N}, với là điểm dữ
liệu thứ i. Thuật toán bắt đầu bằng việc chọn k điểm ngẫu nhiên làm trọng tâm, sau đó
gọi 2 bước sau cho đến khi hội tụ:
B1. Gán dữ liệu: Mỗi điểm được gán vào một nhóm nào đó gần nhất. Giai đoạn
này được gọi là phân chia dữ liệu.
B2. Tính lại trọng tâm: lấy trung bình các điểm trong nhóm để làm trọng tâm.
- Công thức tính khoảng cách giữa 2 đối tượng:
- Khoảng cách Minkowski:
d(i,j) =
trong đó () và () là 2 đối tượng dữ liệu trong không gian p chiều và q là
số nguyên dương.
Nếu q =1 là khoảng cách Manhattan
d(i,j) =
Nếu q=2 là khoảng cách Euclidean
d(i,j) =

Xét C: d(C,M1) =
d(C,M2) =
 C thuộc nhóm 1
Xét D: d(D,M1) =
d(D,M2) =
 D thuộc nhóm 1
Xét E: d(E,M1) =
d(E,M2) =
- 17 -
Đồ án môn học: Công nghệ trí thức và ứng dụng
 E thuộc nhóm 1
Figure 6
Bước 3: Tính lại trọng tâm:
Bước 2: Tính toán lại nhóm cho các điểm:
Xét A: d(A,M1) =
d(A,M2) =
 A thuộc nhóm 2
Xét B: d(B,M1) =
d(B,M2) =
 B thuộc nhóm 2
Xét C: d(C,M1) =
d(C,M2) =
 C thuộc nhóm 1
Xét D: d(D,M1) =
d(D,M2) =
- 18 -
Đồ án môn học: Công nghệ trí thức và ứng dụng
 D thuộc nhóm 1
Xét E: d(E,M1) =
d(E,M2) =

Đồ án môn học: Công nghệ trí thức và ứng dụng
4. Thuật toán Page Rank
Thuật toán này được cho ra đời và trình bày Sergey Brin và Larry Page tại hội nghị
quốc tế WWW lần thứ 7, tháng 4 năm 1998. Đây là thuật toán xếp thứ hạng thống kê
để tìm kiếm dựa trên các đường dẫn web. Search engine nổi tiếng Google được dựa
trên thuật toán này và đã đạt được những thành công rực rỡ.
Thuật toán này tính toán giá trị thống kê của các trang dựa trên cấu trúc dạng offline
của trang đó và không phụ thuộc vào yêu cầu tìm kiếm, mà thông qua số lượng các
đường liên kết tới trang này. Ví dụ bên trong trang x chứa đường dẫn tới trang y, thì
trang y được thêm 1 điểm page rank bởi trang x.
Ví dụ về thuật toán tính page rank:
Giả sử ta có các lien kết như hình bên dưới:
Công thức tính page rank của một trang là:
PR(A) =
Trong đó Parent(A) là tập những trang web có link tới A, và N(V) là số liên kết tới ra
những trang khác trên V.
Chẳng hạn trong hình trên, ta tính được page rank của C là:
PR(C) =
Giải thuật tính pagerank:
PageRank-Iterate(G)
← e/n
- 21 -
Đồ án môn học: Công nghệ trí thức và ứng dụng
k ← 1
repeat
← (1-d)e + d;
k ← k + 1;
until || – ||1 < ε
return Pk
Trong đó d được gọi là damping factor, nhận giá trị từ 0

Lần 6:
PR(A)= 0.15 + 0.85*(1.338/1) = 1.2875
PR(B) = 0.15 + 0.85*(1.2875/2) = 0.6972
PR(C) = 0.15+ 0 85 *(1.2875/2+0.6972/1+0.15) = 1.490
Lần 7:
PR(A)= 0.15 + 0.85*(1.490/1) = 1.4165
PR(B) = 0.15 + 0.85*(1.4165/2) = 0.752
PR(C) = 0.15+ 0.85 *(1.4165/2+0.752/1+0.15) = 1.5178
Lần 8:
PR(A)= 0.15 + 0.85*(1.5178/1) = 1.4409
PR(B) = 0.15 + 0.85*(1.4409/2) = 0.7623
PR(C) = 0.15+ 0.85 *(1.4409/2+0.7623/1+0 15) = 1.5378
Chênh lệch giữa lần 7 và lần 8 là:
dA = 1.4409 – 1.4165 = 0.0244
dB = 0.0103
dC = 0.02
Các tính toán trên thõa mãn < ε = 0.03
Vậy giá trị PageRank của các page đã cho là: PR(A) = 1.4409, PR(B) = 0.7623, PR(C)
= 1.5378, PR(D) = 0.15
5. Thuật toán Native Bayes
Cho trước một tập đối tượng, và mỗi đối tượng thuộc về một lớp nào đó, và mỗi đối
tượng được đại diện bởi một vector. Mục tiêu là cần xây dựng tập luật, sao cho có thể
nhận biết được lớp của một đối tượng mới đưa vào tập hợp. Kỹ thuật này được gọi là
- 23 -
Đồ án môn học: Công nghệ trí thức và ứng dụng
phân lớp có giám sát, và đã có rất nhiều kỹ thuật làm việc này, một trong số đó là
Native Bayes.
Nguyên lí: Để đơn giản, giả sử rằng chỉ có 2 lớp 0 và 1. Mục tiêu là tìm một số sao cho
nếu lớn hơn số đó thì kết hợp với 1, nhỏ hơn thì kết hợp với 0.
Đặt P(i|x) là xác suất giá trị x thuộc về lớp i.