ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG
________________
BÁO CÁO THU HOẠCH MÔN HỌC
KHAI PHÁ DỮ LIỆU
Đề tài: Các kỹ thuật trong khai phá dữ
liệu và các chương trình demo
Giáo viên hướng dẫn: PGS.TS Đỗ Phúc
Sinh viên thực hiện: Du Chí Hào
Mã số sinh viên: CH1101083
Tp. HCM 2012
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Lời nói đầu
Với việc phát triển và phân bố ngày càng rộng rãi của các công ty, xí
nghiệp, dữ liệu là rất lớn và vẫn chưa khác thác hết để tìm thấy những tính chất,
quy luật, điểm mạnh và điểm yếu. Do đó, việc khai thác dữ liệu đóng vai trò rất
lớn hiện nay trong việc tìm kiếm, khám phá các tri thức mới và các tri thức ở
dạng tiềm năng trong các nguồn dữ liệu đã có.
Trong bài thu hoạch chuyên đề này sẽ giới thiệu về ba kỹ thuật trong
khai phá dữ liệu gồm luật kết hợp, phân lớp dữ liệu và gom cụm dữ liệu. Dựa
vào những kỹ thuật đó, em đã xây dựng các chương trình demo kèm theo bài
thu hoạch này để mô tả thực tế về cách thức hoạt động của việc khai phá dữ liệu
bao gồm các bài toán sau:
• Tìm tập phổ biến và tập phổ biến tối đại, từ đó rút trích ra các luật kết
hợp.
• Phân lớp Bayes dựa trên các mẫu chưa gặp.
• Rút gọn lớp tương đương.
• Dựa trên thuật toán rút gọn lớp tương đương để tìm độ chính xác xấp
xỉ của tất cả các phân hoạch.

• Rút gọn ma trận phân biệt và rút gọn hàm phân biệt.
• Gom cụm dữ liệu dựa trên thuật toán K-Means.
Theo đó, em có thể ứng dụng vào các công việc thực tiễn.
Em xin chân thành cám ơn thầy PGS.TS Đỗ Phúc đã truyền đạt những
kiến thức quý báu cho em về bộ môn “Khai phá dữ liệu” để em có thể hoàn
thành bài thu hoạch này.
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Mục lục
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
PHẦN I : TỔNG QUAN
I. Khai phá dữ liệu
Khai phá dữ liệu – Data Mining (KPDL) là tiến trình khám phá tri thức
tiềm ẩn trong các CSDL. Cụ thể hơn, đó là tiến trình trích lọc, sản sinh những
tri thức hoặc các mẫu tiềm ẩn, chưa biết nhưng hữu ích từ các CSDL lớn.
KPDL là tiến trình khai thác các sự kiện rời rạc trong dữ liệu thành các
tri thức mang tính khái quát, tính quy luật hỗ trợ tích cực cho các tiến trình ra
quyết định.
Có thể chia khai phá dữ liệu thành hai dạng chính: khai phá dữ liệu theo
hướng kiểm tra va khai phá dữ liệu theo hướng khám phá. Trong khai phá dữ
liệu theo hướng kiểm tra, người dùng đề xuất giả thiết, hệ thống kiểm tra tính
đúng đắn của giả thiết. Khai phá dữ liệu theo hướng kiểm tra bao gồm: truy vấn,
báo cáo, phân tích đa chiều, phân tích thống kê… Ngược lại, khai phá dữ liệu
theo hướng khám phá sẽ tìm kiếm các tri thức tiềm ẩn trong CSDL bằng cách
tiến hành xem xét tất cả các giả thiết khả dĩ. Do không gian tìm kiếm lớn, nên
rất nhiều heuristic đã được đề xuất nhằm nâng cao hiệu suất của các giải thuật
tìm kiếm.

Tri thức được rút ra có thể được dùng để:
Giải thích dữ liệu:
• Cung cấp sự hiểu biết sâu sắc và rất hữu ích về hành vi của các đối
tượng, giúp cho các doanh nghiệp hiểu rõ hơn những khách hàng của
họ.
Dự báo: dự đoán giá trị của những đối tượng mới.
• Khuynh hướng mua hàng của khách hàng.
• Xác định rủi ro tín dụng đối với một khách hàng.
• Định hướng tập trung nguồn lực của doanh nghiệp.
KPDL là một công đoạn trong tiến trình lớn hơn là khám phá tri thức từ
CSDL. KPDL mang tính trực giác, cho phép thu được những hiểu biết rõ ràng
và sâu sắc hơn, vượt xa kho dữ liệu. Kho dữ liệu điển hình trong những doanh
nghiệp cho phép người dùng hỏi và trả lời những câu hỏi như “Doanh số bán ra
là bao nhiêu tính theo khu vực, theo nhân viên bán hàng trong khoảng thời gian
nào đó?”. Trong khi đó, KPDL cho phép người ra quyết định kinh doanh hỏi và
trả lời cho những câu hỏi như: “Ai là khách hàng chính yếu của công ty đối với
một mặt hàng cụ thể?” hoặc “Dòng sản phẩm nào sẽ bán trong khu vực này và
ai sẽ mua chúng?”. Vị trí của KPDL được thể hiện qua sơ đồ:
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
KPDL là cần thiết đối với người dùng vì những lý do sau:
• Ngày càng có nhiều dữ liệu được lưu trữ trong các CSDL, kho dữ
liệu và hình thành “một mỏ vàng dữ liệu” chứa đầy các thông tin
chiến lược mà các hệ quản trị CSDL thông thường không thể phát
hiển và quản trị được chúng.
• CSDL phát triển rất nhanh cả về kích thước lẫn số lượng. Không xét
những thông tin mang tính sự kiện được lưu trữ trong CSDL, những
thông tin được suy diễn từ nó cũng hết sức lý thú. Tuy nhiên, với các
quan hệ có số lượng khổng lồ, các bản ghi và có quá nhiều trường tin,

việc duyệt hàng triệu bản ghi hay hàng trăm trường tin để tìm ra các
mẫu và các quy luật là một thách thức và trở ngại thật sự đối với các
nhà phân tích dữ liệu.
• Không phải người nào cũng là nhà thống kê hay nhà phân tích dữ liệu
chuyên nghiệp.
• Sử dụng cho các trường hợp tìm kiếm nhưng chưa xác lập rõ hoặc
chưa mô tả được các điều kiện tìm kiếm. Nếu người dùng biết họ
đang tìm kiếm gì thì dùng SQL, nhưng nếu người dùng chỉ có một ý
tưởng không rõ rang, hoặc một cảm nhận nào đó thì họ không nên
dùng KPDL.
KPDL là một công cụ hiệu quả trong các lĩnh vực:
Sử dụng dữ liệu để xây dựng các mô hình dự báo:
• Khả năng dự báo tiềm ẩn trong dữ liệu.
• Gợi ý các chiều và các nhóm dữ liệu có khả năng chứa các tri thức
hữu ích.
Tạo tóm tắt và báo cáo rõ ràng:
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
• Tự động tìm những phân đoạn trong dữ liệu
• Tìm ra những phân đoạn mà nhà phân tích chưa biết hoặc có hiểu biết
chưa rõ ràng.
Cung cấp cơ chế hỗ trợ ra quyết định:
• Dự báo.
• Mô hình hóa.
II. Các công đoạn khám phá tri thức từ CSDL
Tiến trình khám phá tri thức từ CSDL bao gồm ba công đoạn:
1.Chuẩn bị dữ liệu:
Chọn lọc dữ liệu:
Đây là giai đoạn chọn lọc, rút trích các dữ liệu cần thiết từ CSDL tác

nghiệp vào một CSDL riêng. Chúng ta chỉ chọn ra những dữ liệu cần thiết cho
các giai đoạn sau. Tuy nhiên, công việc thu gom dữ liệu vào một CSDL thường
rất khó khăn vì dữ liệu nằm rải rác khắp nơi trong cơ quan, tổ chức cùng một
loại thông tin, nhưng được tạo lập theo các dạng thứ khác nhau, chất lượng dữ
liệu các nơi cũng không giống nhau.
Làm sạch dữ liệu:
• Chống trùng lặp: Dạng lỗi thứ nhất khá quan trọng trong thao tác
xóa bỏ dữ liệu đó là xóa bỏ thông tin trùng các các bản ghi. Thao tác
này diễn ra khi có những thông tin bị trùng do có sai sót trong phần
nhập dữ liệu, hoặc thông tin không được cập nhật kịp thời hoặc thông
tin được cung cấp bị sai.
• Giới hạn vùng giá trị: Dạng lỗi thứ hai thường hay xãy ra là giá trị
nằm ngoài miền giá trị cho phép, nghĩa là các thông tin chứa các giá
trị không hợp lệ theo một quy tắc nào đó. Dạng lỗi này gây tác hại
khá lớn vì rất khó phát hiện ra nó, nhưng lại ảnh hưởng lớn đến dạng
thức của các mẫu cần tìm khi thực hiện KPDL trên các bảng dữ liệu
này.
Làm giàu dữ liệu:
Mục đích của giai đoạn là bổ sung thêm nhiều loại thông tin có liên quan
vào CSDL gốc. Để làm điều này, chúng ta phải có các CSDL khác ở bên ngoài
có liên quan đến CSDL gốc ban đầu. Ta tiến hành bổ sung những thông tin cần
thiết, làm tăng khả năng khám phá tri thức từ CSDL.
Vấn đề đặt ra là làm thế nào để kết hợp thông tin giữa dữ liệu gốc và dữ
liệu được bổ sung. Bên cạnh đó, cúng ta cần chú ý đến vấn đề khôi phục các
quan hệ trong CSDL sau khi đã được làm giàu thông tin.
Mã hóa dữ liệu:
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Mục đích của giai đoạn mã hóa là chuyển đổi kiểu dữ liệu về những dạng

thuận tiện để tiến hành các thuật toán khám phá dữ liệu. Có nhiều cách mã hóa
dữ liệu theo từng loại dữ liệu:
• Phân vùng: với dữ liệu là giá trị chuỗi, nằm trong tập các chuỗi cố
định.
• Biến đổi giá trị năm thành con số nguyên là số năm đã trôi qua so với
năm hiện hành.
• Chia giá trị số theo một hệ số để tập các giá trị nằm trong vùng nhỏ
hơn.
• Chuyển đổi yes-no thành 0-1.
2.Khai phá dữ liệu
KPDL là tiến trình "điều chỉnh đúng" các mô hình dữ liệu. Chức năng
biến đổi dữ liệu được đưa vào bước này với mục đích để trình diễn dữ liệu.
3.Trình diễn dữ liệu
Trình diễn dữ liệu là quá trình giải thích và hiển thị trực quan các kết quả
KPDL để hỗ trợ việc định giá chất lượng dữ liệu, đánh giá mô hình dữ liệu
được lựa có phù hợp hay không, và thể hiện mô hình. Mỗi bước (trừ lưu trữ dữ
liệu) cho phép tương tác người dùng, và một số bước (ví dụ như lựa chọn tài
nguyên) có thể được thực hiện hoàn toàn thủ công.
III. Khái quát các kỹ thuật KPDL
1 Khai thác tập phổ biến và luật kết hợp
Là tiến trình khám phá các tập giá trị thuộc tính xuất hiện phổ biến trong
các đối tượng dữ liệu. Từ tập phổ biến có thể tạo ra các luật kết hợp giữa các giá
trị thuộc tính nhằm phản ánh khả năng xuất hiện đồng thời các giá trị thuộc tính
trong tập các đối tượng. Một luật kết hợp X → Y phản ánh sự xuất hiện của tập
X dẫn đến sự xuất hiện đồng thời tập Y.
4.Phân lớp dữ liệu
Là tiến trình khám phá các luật phân loại hay đặc trưng cho các tập dữ
liệu đã được xếp lớp. Tập dữ liệu học bao gồm tập đối tượng đã được xác định
lớp sẽ được dùng để tạo mô hình phân lớp dựa trên đặc trưng của đối tượng
trong tập dữ liệu học. Các luật phân lớp được sử dụng để xây dựng bộ phân lớp

dữ liệu. Phân lớp dữ liệu có vai trò quan trọng trong tiến trình dự báo các
khuynh hướng, quy luật phát triển.
5.Khai thác cụm
Là tiến trình nhận diện các cụm tiềm ẩn trong tập các đối tượng chưa
được xếp lớp. Tiến trình khai thác cụm dựa trên mức độ tương tự giữa các đối
tượng. Các đối tượng được gom cụm sao cho mức độ tương tự giữa các đối
tượng trong cùng một cụm là cực đại và mức độ tương tự giữa các đối tượng
nằm trong các cụm khác nhau là cực tiểu. Các cụm được đặc trưng bằng các
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
tính chất chung của tất cả các đối tượng trong cụm. Do vậy, khao sát các cụm sẽ
giúp khái quát, tổng kết nhanh chóng nội dung của khối dữ liệu lớn.
PHẦN II : TẬP PHỔ BIẾN VÀ LUẬT KẾT HỢP
I Mở đầu
Các công ty bán lẻ hiện nay phải lưu một số lượng dữ liệu bán hàng
khổng lồ. Một bản ghi trong CSDL này phải chứa các thông tin về ngày mua
bán, hàng mua bán Từ CSDL bán hàng, chúng ta có thể tìm ra các mối quan
hệ giữa các cặp thuộc tính - giá trị thuộc tính. Một luật kết hợp tiêu biểu:
Có 78% khách hàng mua sữa hộp Vinamilk thì mua trà Lipton.
Các công ty thành công thường tìm kiếm những luật như vậy để biết
được xu hướng của thị trường, từ đó đưa ra những chương trình và chiến lược
nhập hàng, bố trí mặt hàng cho phù hợp.
IV. Bài toán khai thác tập phổ biến
1.Các khái niệm cơ bản
Cho tập O là tập hữu hạn khác rỗng các hóa đơn và I là tập hữu hạn khác
rỗng các mặt hàng, R là một quan hệ hai ngôi O và I sao cho với o ∈ O và i ∈ I,
(o, i) ∈ R ⇔ hóa đơn o có chứa mặt hàng i. Ngữ cảnh KPDL là bộ ba (O, I, R).
Ma trận ngữ cảnh KPDL:
Quan hệ hai ngôi R được biểu diễn bằng một ma trận nhị phân trong đó

dòng thứ i ứng với hóa đơn o
i
và cột thứ j ứng với mặt hàng i
j
. Ma trận này được
gọi là ma trận biểu diễn ngữ cảnh KPDL.
i
1
i
2
i
3
i
4
o
1
1 1 1 0
o
2
1 0 0 0
o
3
0 1 1 1
o
4
1 1 1 0
o
5
0 0 1 1
Bảng 1.1: Ma trận nhị phân biểu diễn ngữ cảnh KPDL

Tập phổ biến:
Cho ngữ cảnh KPDL (O,I,R) và S ⊂ I, độ phổ biến của S được định
nghĩa là tỉ số giữa các hóa đơn có chứa S và số lượng hóa đơn trong O. Độ phổ
biến của S ký hiệu SP(S) và được tính như sau:
SP(S) = |ρ(S)| / |O|
với |.| là lực lượng của tập hợp.
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Cho S ⊂ I và minsupp ∈ (0,1] là ngưỡng phổ biến tối thiểu, S là một tập
phổ biến theo ngưỡng minsupp nếu và chỉ nếu SP(S) ≥ minsupp.
Ký hiệu FS(O, I, R, minsupp) là tập hợp các tập phổ biến theo ngưỡng
minsupp hay FS(O, I, R, minsupp) = { S ∈ P(I) | SP(S) ≥ minsupp }.
Dàn các tập mặt hàng:
Cho (O,I,R), xét P(I) là tập các tập hợp con của tập mặt hàng I và quan
hệ thứ tự "⊆", thì (P(I), ⊆) là một dàn, Do I là tập mặt hàng nên dàn (P(I), ⊆)
được gọi là dàn các tập mặt hàng. Dàn (P(I), ⊆) xác định không gian tìm kiếm
lời giải của bài toán.
Hình 1.1: Vi dụ về dàn các tập mặt hàng
2.Thuật toán tìm tập phổ biến
Tập phổ biến được tìm dựa trên các tập phần tử có độ support tối thiểu.
Thuật toán Apriori dựa trên nguyên tắc "Những tập con của tập phổ biến cũng
là tập phổ biến", ví dụ như nếu {AB} là một tập phổ biến thì cả {A} và {B} đều
là những tập phổ biến.
Thuật toán Apriori:
Bước kết hợp: Ck được tạo bằng cách kết Lk-1 với chính nó
Bước rút gọn: Những tập kích thước (k-1) không phổ biến không thể là
tập con của tập phổ biến kích thước k
Mã giả:
Ck: Tập ứng viên có kích thước k; Lk : Tập phổ biến có kích thước k

L1 = {các phần tử phổ biến};
for (k = 1; Lk !=∅; k++) do begin
Ck+1 = {các ứng viên được tạo từ Lk };
for each giao tác t trong database do
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Tăng số đếm của tất cả các ứng viên trong Ck+1
mà được chứa trong t
Lk+1 = {các ứng viên trong Ck+1 có độ ủng hộ tối tiểu}
end
return ∪k Lk;
Ví dụ minh họa cho thuật toán:
Cho ngữ cảnh KPDL (O, I, R) trong bảng 1.1 và minsupp = 0,4. Các
bước thực hiện thuật toán như sau:
F1 = { {i1}, {i2}, {i3}, {i4} }
• {i1}, v({i1}) = (1,0,0,1,0)
SP({i1}) = SPV(v({i1})) = 2/5 = 0,4 Tập phổ biến
• {i2}, v({i2}) = (1,1,1,1,0)
SP({i2}) = SPV(v({i2})) = 4/5 = 0,8 Tập phổ biến
• {i3}, v({i3}) = (1,1,1,1,1)
SP({i3}) = SPV(v({i3})) = 4/5 = 1,0 Tập phổ biến
• {i4}, v({i4}) = (0,1,1,0,1)
SP({i4}) = SPV(v({i4})) = 3/5 = 0,6 Tập phổ biến
F2 = { {i1, i2}, {i1, i3}, {i2, i3}, {i2, i4}, {i3, i4} }
• {i1, i2}, v({i1, i2}) = (1,0,0,1,0)
SP({i1,i2}) = SPV(v({i1, i2})) = 2/5 = 0,4 Tập phổ biến
• {i1, i3}, v({i1, i3}) = (1,0,0,1,0)
SP({i1,i3}) = SPV(v({i1, i3})) = 2/5 = 0,4 Tập phổ biến
• {i1, i4}, v({i1, i4}) = (0,0,0,0,0)

SP({i1,i4}) = SPV(v({i1, i4})) = 0/5 = 0,0 Không phải tập phổ biến
• {i2, i3}, v({i2, i3}) = (1,1,1,1,0)
SP({i2,i3}) = SPV(v({i2, i3})) = 4/5 = 0,8 Tập phổ biến
• {i2, i4}, v({i2, i4}) = (1,1,1,0,0)
SP({i2,i4}) = SPV(v({i2, i4})) = 2/5 = 0,4 Tập phổ biến
• {i3, i4}, v({i3, i4}) = (0,1,1,0,1)
SP({i3,i4}) = SPV(v({i3, i4})) = 3/5 = 0,6 Tập phổ biến
F3 = { {i1, i2, i3}, {i2, i3, i4} }
• {i1, i2, i3}, v({i1, i2, i3}) = (1,0,0,1,0)
SP({i1,i2, i3}) = SPV(v({i1, i2, i3})) = 2/5 = 0,4 Tập phổ biến
• {i1, i2, i4}, v({i1, i2, i4}) = (0,0,0,0,0)
SP({i1,i2, i4}) = SPV(v({i1, i2, i4})) = 0/5 = 0,0 Không phải tập phổ
biến
• {i1, i3, i4}, v({i1, i3, i4}) = (0,0,0,0,0)
SP({i1,i3, i4}) = SPV(v({i1, i3, i4})) = 0/5 = 0,0 Không phải tập phổ
biến
• {i2, i3, i4}, v({i2, i3, i4}) = (0,1,1,0,0)
SP({i2,i3, i4}) = SPV(v({i2, i3, i4})) = 2/5 = 0,4 Tập phổ biến
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
F4 = { {i1, i2, i3, i4 }
• {i1, i2, i3, i4}, v({i1, i2, i3,i4}) = (0,0,0,0,0)
SP({i1,i2, i3,i4}) = SPV(v({i1, i2, i3, i4})) = 0/5 = 0,0 Không phải tập
phổ biến
Kết thúc thuật toán. Kết quả FS(O,I,R, minsupp) = { {i1}, {i2}, {i3},
{i4}, {i1, i2}, {i1, i3}, {i2, i3}, {i2, i4}, {i3, i4}, {i1, i2, i3}, {i2, i3, i4} }
3.Tập phổ biến tối đại
Cho M ∈ FS(O,I,R, minsupp), M được gọi là tập phổ biến tối đại nếu
không tồn tại S ∈ FS(O,I,R, minsupp) M ≠ S, M ⊂ S.

Ký hiệu MS(O,I,R,minsupp) là tập hợp các tập phổ tối đại của ngữ cảnh
KPDL (O,I,R) theo ngưỡng minsupp.
Ví dụ: Với ngữ cảnh KPDL theo bảng 1.1 và ngưỡng phổ biến tối thiểu
minsupp = 0,4 sẽ có các tập phổ biến tối đại {i1, i2, i3} và {i2, i3, i4}.
4.Bài toán tìm luật kết hợp
Luật kết hợp
Cho ngữ cảnh KPDL (O,I,R) và ngưỡng minsupp ∈ (0,1]. Với một S ∈
FS(O,I,R,minsupp), gọi X và Y là các tập con khác rỗng của S sao cho S = X ∪
Y và X ∩ Y = φ. Luật kết hợp X với Y có dạng X → Y phản ánh khả năng xuất
hiện Y khi cho trước X. Độ phổ biến của luật kết hợp X → Y với S = X ∪ Y và
SP(S). Độ tin cậy của luật kết hợp X → Y là tỉ số giữa SP(S) và SP(X). Độ tin
cậy của luật kết hợp X → Y được ký hiệu là CF(X → Y) và được tính bằng:
CF(X → Y) = SP(S) / SP(X)
Mã giả tìm luật kết hợp
for mỗi tập phổ biến l
tạo tất cả các tập con khác rỗng s of l
for mỗi tập con khác rỗng s of l
cho ra luật "s ⇒ (l-s)" nếu support(l)/support(s)
≥

min_conf", trong đó min_conf là ngưỡng độ tin cậy tối thiểu.
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
PHẦN III : PHÂN LỚP DỮ LIỆU
I Mở đầu
Phân lớp dữ liệu là xếp đố tượng dữ liệu vào một trong các lớp đã được
xác định trước. Phân lớp dữ liệu gồm hai bước là xây dựng mô hình và vận
hành mô hình.
1.Xây dựng mô hình:

Nhằm mục tiêu mô tả một tập những lớp đã được định nghĩa trước trong
đó mỗi bộ hoặc mẫu sẽ được gán về một lớp đã xác định trước bởi thuộc tính
nhãn lớp. Tập hợp những bộ được dùng để xây dựng mô hình được gọi là tập dữ
liệu học (dưới đây sẽ gọi tắt là tập học). Mô hình được biểu diễn dưới dạng luật
phân lớp, cây quyết định hoặc công thức toán học
2.Vận hành mô hình:
Nhằm mục đích xác định lớp của dữ liệu trong tương lai hoặc phân lớp
những đối tượng chưa biết. Trước khi vận hành mô hình cần đánh giá độ chính
xác của mô hình trong đó các mẫu kiểm tra (đã biết được lớp) được đem so
sánh với kết quả phân lớp của mô hình. Lưu ý tập kiểm tra và tập học là hai tập
độc lập với nhau.
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
3.Các phương pháp phân lớp:
• Phân lớp bằng phương pháp quy nạp dựa trên cây quyết định.
• Phương pháp phân lớp Bayes
• Phân lớp bằng mạng Nơron lan truyền ngược
• Phân lớp dựa trên luật kết hợp
• Thuật giải di truyền
• Tiếp cận tập thô
Sau đây, em sẽ trình bày hai phương pháp phân lớp là phân lớp dựa trên
cây quyết định và phân lớp Bayes.
V. Phân lớp quy nạp trên cây quyết định
Cây quyết định gồm các nút trong biểu diễn giá trị thuộc tính, các nhánh
biểu diễn đầu ra của kiểm tra, nút lá biểu diễn nhãn lớp. Cây quyết định được
tạo theo hai giai đoạn là tạo cây và tỉa nhánh.
Trong giai đoạn tạo cây. lúc bắt đầu tất cả mẫu học đều nằm ở nút gốc,
sau đó các mẫu học được phân chia một cách đệ quy dựa trên thuộc tính được
chọn. Bước tỉa nhánh nhằm tìm và xóa những nhánh có phần tử không thể xếp

vào lớp nào cả.
Bước vận hành nhằm kiểm tra những giá trị thuộc tính của mẫu đối với
các giá trị trên nhánh của cây quyết định.
Thuật toán tạo cây quyết định bao gồm các bước sau:
• Bước 1: Cây được xây dựng đệ quy từ trên xuống vào theo cách chia
để trị.
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
• Bước 2: Ban đầu tất cả các mẫu học đều nằm ở gốc.
• Bước 3: Thuộc tính được phân loại (nếu là giá trị liên tục được rời rạc
hóa)
• Bước 4: Các mẫu học được phân chia đệ quy dựa trên thuộc tính chọn
lựa
• Bước 5: Kiểm tra những thuộc tính được chọn lựa trên heristic hoặc
một tiêu chuẩn thống kê.
Điều kiện để dừng phân chia học tập:
• Tất cả những mẫu học đối với một nút cho trước đều cùng lớp
• Không còn thuộc tính nào để phân chia tiếp
• Không còn mẫu học
Độ lợi thông tin là đại lượng được dùng để chọn thuộc tính nhằm phân
chia tập học. Thuộc tính được chọn là thuộc tính có độ lợi thông tin lớn nhất.
Cho hai lớp P và N và học tập S.Lớp P có p phần tử và lớp N có n phần
tử. Khối lượng thông tin cần để quyết định các mẫu trong S thuộc về lớp P hay
lớp N được xác định bởi:
np
n
np
n
np

p
np
p
npI
++
−
++
−=
22
loglog),(
Giả sử thuộc tính A được chọn để phân hoạch S thành các tập hợp {S
1
,
S
2, ,
S
v
}. Nếu S
1
chứa p
i
mẫu của lớp P và n
i
mẫu của lớp N thì entropy, hay
thông tin mong muốn cần thiết để phân lớp các đối tượng trong tất cả các cây
con S
i
là:
∑
=

+
+
=
ν
1
),()(
i
ii
ii
npI
np
np
AE
Độ lợi thông tin của nhánh A là:
)(),()( AEnpIAGain −=
Thuật toán ID3 là một thuật toán học trên cây quyết định được phát triển
bởi Ross Quinlan (1983). Ý tưởng cơ bản của thuật toán ID3 là tạo cây quyết
định bằng việc sữ dụng cách tìm kiếm từ trên xuống theo tập học. Độ lợi thông
tin được sử dụng để chọn thuộc tính có khả năng phân loại tốt nhất.
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
VI. Bộ phân lớp Bayes
1 Định lý Bayes
Cho X là mẫu dữ liệu chưa biết nhãn lớp, H là giả thuyết ví dụ như mẫu
dữ liệu X thuộc về lớp C. Đối với các bài toán phân loại, ta cần xác định P(H|X)
là xác suất xảy ra giả thuyết H trên mẫu dữ liệu X.
P(H|X) là xác suất hậu nghiệm của H với điều kiện X. Ví dụ, giả sử các
mẫu dữ liệu trong tập hoa quả được mô tả bởi màu sắc và hình dạng của chúng.
Giả sử X là đỏ và tròn, H là giả thuyết X là quả táo. Thì P(H|X) phản ánh độ tin

cậy rằng X là một quả táo với việc đã nhìn thấy X là đỏ và tròn. Ngược lại, P(H)
là xác suất tiên nghiệm của H. Như ví dụ, đây là xác suất một mẫu dữ liệu bất kì
cho trước là quả táo bất kể nó trông như thế nào. Xác suất hậu nghiệm P(H|X)
dựa trên nhiều thông tin (như nền tảng tri thức) hơn xác suất tiên nghiệm P(H),
nó độc lập với X. Tương tự như vậy, P(X|H) là xác suất hậu nghiệm của X với
điều kiện H. Đó là xác suất để X là đỏ và tròn, ta đã biết sự thật là X là một quả
táo. P(X) là tiên nghiệm của X. Theo ví dụ trên, nó là xác suất để cho một mẫu
dữ liệu từ tập hoa quả là đỏ và tròn.
P(X), P(H), P(X|H) được đánh giá từ dữ liệu cho trước. Định lý Bayes
thực sự có ích bởi nó cung cấp cách thức tính toán xác suất hậu nghiệm P(H|X)
từ P(X), P(H) và P(X|H). Định lý Bayes như sau:
Trong mục tiếp theo ta sẽ xem định lý Bayes được dùng như thế nào
trong phân lớp Bayes.
4.Phân lớp Bayes
Mỗi mẫu dữ liệu được đại diện bởi một vector đặc trưng n-chiều,
X=(x
1
,x
2
, ,x
n
), mô tả n phép đo có được trên mẫu từ n thuộc tính tương ứng A
1
,
A
2
, , A
n
.
Giả sử rằng có m lớp C

1
,C
2
, C
m
. Cho trước một mẫu dữ liệu chưa biết
nhãn lớp X, classifier sẽ dự đoán X thuộc về lớp có xác suất hậu nghiệm cao
nhất, với điều kiện trên X. Phân lớp Bayes ấn định một mẫu không biết X vào
một lớp C
i
khi và chỉ khi:
Do vậy cần tìm P(C
i
|X) lớn nhất. Theo định lý Bayes:
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
P(X) không đổi với mọi lớp, P(C
i
)=s
i
/s (s
i
là số lượng các mẫu huấn
luyện của lớp C
i
và s là tổng số các mẫu huấn luyện), P(X|C
i
)P(C
i

) cần được cực
đại.
Cho trước các tập dữ liệu với nhiều thuộc tính, việc tính P(X|C
i
) sẽ rất
tốn kém. Để giảm tính toán khi đánh giá P(X|C
i
), giả định của độc lập có điều
kiện lớp được thiết lập. Điều này làm cho giá trị của các thuộc tính là độc lập có
điều kiện với nhau, cho trước nhãn lớp của mẫu, tức là không có mối quan hệ
độc lập giữa các thuộc tính. Vì thế,
P(x
1
|C
i
), P(x
2
|C
i
), , P(x
n
|C
i
) được đánh giá từ các mẫu huấn luyện với:
• Nếu A
k
là xác thực thì P(x
k
|C
i

)=s
ik
/s
i
với s
ik
là số lượng các mẫu huấn
luyện của lớp C
i
có giá trị xk tại A
k
và s
i
là số lượng các mẫu huấn
luyện thuộc về C
i
.
• Nếu A
k
là giá trị liên tục thì thuộc tính được giả định có phân phối
Gaussian. Bởi vậy,
với g(x
k
,μC
i
,σC
i
) là hàm mật độ (thông thường) Gaussian của thuộc tính
A
k

, với μC
i
,σC
i
đại diện cho các giá trị trung bình và độ lệch chuẩn của thuộc
tính A
k
đối với các mẫu huấn luyện của lớp C
i
.
Để phân loại một mẫu chưa biết X, với P(X|C
i
)P(C
i
) được đánh giá cho
lớp C
i
. Mẫu X được ấn định vào lớp C
i
khi và chỉ khi:
Hay nói cách khác, nó được ấn định tới lớp C
i
mà tại đó P(X|C
i
)P(C
i
) cực
đại.
Ví dụ minh họa cho phân lớp Bayes:
Ta có tập huấn luyện "Chơi tennis" theo bảng sau:

Thời tiết Nhiệt độ Độ ẩm Gió Lớp
nắng nóng cao không N
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
nắng nóng cao không N
u ám nóng cao không P
mưa ấm áp cao không P
mưa mát vừa không P
mưa mát vừa có N
u ám mát vừa có P
nắng ấm áp cao không N
nắng mát vừa không P
mưa ấm áp vừa không P
nắng ấm áp vừa có P
u ám ấm áp cao có P
u ám nóng vừa không P
mưa ấm áp cao có N
Dựa theo tập huấn luyện trên, ta có thể tính được các xác suất sau:
P(
p
p) = 9/14; P(n) = 5/14
Thời tiết
P(nắng | p) = 2/9 P(nắng | n) = 3/5
P(u ám | p) = 4/9 P(u ám | n) = 0
P(mưa | p) = 3/9 P(mưa | n) = 2/5
Nhiệt độ
P(nóng | p) = 2/9 P(nóng | n) = 2/5
P(ấm áp | p) = 4/9 P(ấm áp | n) = 2/5
P(mát | p) = 3/9 P(mát | n) = 1/5

Độ ẩm
P(cao | p) = 3/9 P(cao | n) = 4/5
P(vừa | p) = 6/9 P(vừa | n) = 1/5
Gió
P(có | p) = 3/9 P(có | n) = 3/5
P(không | p) = 6/9 P(fkhông | n) = 2/5
Cho một mẫu chưa thấy như sau X = < mưa, nóng, cao, không >
Phân lớp X:
• Một mẫu chưa thấy X = <mưa, nóng, cao, không>
• P(X|p)·P(p) =
P(mưa|p)·P(nóng|p)·P(cao|p)·P(không|p)·P(p) = 3/9·2/9·3/9·6/9·9/14
= 0.010582
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
• P(X|n)·P(n) =
P(mưa|n)·P(nóng|n)·P(cao|n)·P(không|n)·P(n) = 2/5·2/5·4/5·2/5·5/14
= 0.018286
• Mẫu X được phân vào lớp n (không chơi tennis)
PHẦN IV : LÝ THUYẾT TẬP THÔ
I Mở đầu
Lý thuyết tập thô được Z. Pawlak phát triển vào đầu thập niên 1980. Lý
thuyết tập thô rất hiệu quả trong KPDL, tìm kiếm thông tin, hỗ trợ quyết định,
máy học, các hệ cơ sở tri thức. Rất nhiều ứng dụng sử dụng ý tưởng của lý
thuyết tập thô như phân tích dữ liệu y khoa, lượng giá điều phối hàng không, xử
lý ảnh, nhận dạng
VII. Các hệ thông tin
1.Hệ thông tin
Hệ thông tin là tập hợp dữ liệu được biểu diễn dưới dạng bảng, trong đó
mỗi dòng biểu diễn một trường hợp, một sự kiện, một khách hàng hoặc đơn

giản một đối tượng. Mỗi cột biểu diễn một thuộc tính và có thể đo đạc với từng
đối tượng.
Một cách hình thức, hệ thông tin là cặp A = (U, A), trong đó U là tập hữu
hạn khác rỗng các đối tượng và A là tập hữu hạn khác rỗng các thuộc tính sao
cho a: U → V
a
với mỗi thuộc tính a ∈ A. Tập V
a
được gọi là tập giá trị của
thuộc tính a.
2.Hệ quyết định
Trong nhiều ứng dụng, ta thấy có một sự phân loại kết quả. Đó là sự mô
tả tri thức bởi một thuộc tính đặc trưng phân biệt được gọi là thuộc tính quyết
định. Hệ thống này là một hình thức học có giám sát. Các hệ thông tin theo loại
này được gọi là các hệ quyết định. Một hệ quyết định là một hệ thông tin có
dạng (U;A∪{d}) trong đó d không thuộc A là thuộc tính quyết định. Các thành
phần thuộc tính của A được gọi là các thuộc tính điều kiện hoặc gọi đơn giản là
các thuộc tính. Thuộc tính quyết định có thể có nhiều hơn hai giá trị mặc dù
thường gặp là thuộc tính nhị phân.
Ví dụ 4.1: Bảng 4.1 là một bảng quyết định đơn giản.
Độ tuổi Số buổi Thi đậu
x1 16-30 50 Có
x2 16-30 0 Không
x3 31-45 1-25 Không
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
x4 31-45 1-25 Có
x5 46-60 26-49 Không
x6 16-30 26-49 Có

x7 46-60 26-49 Không
VIII. Quan hệ bất khả phân biệt
Cho một hệ thông tin S = (U,A), với tập thuộc tính B ⊆ A có quan hệ
tương đương ứng IND
S
(B):
IND
S
(B) = {(u;v) ∈ U
2
| ∀a ∈ B, a(u) = a(v)}
IND
S
(B) được gọi là quan hệ bất khả phân biệt theo B. Nếu (u, v) ∈
IND
S
(B), thì các đối tượng u và v là không thể phân biệt lẫn nhau qua tập thuộc
tính B. Các lớp tương đương của quan hệ bất khả phân biệt theo B được ký hiệu
|x|
B
.
Ví dụ 4.2: Quan hệ bất khả phân biệt được định nghĩa với bảng quyết
định 4.1.
Các tập con khác rỗng của thuộc tính điều kiện là{Age}, {LEMS},
và{Age, LEMS}.
IND({Độ tuổi}) = {{x1,x2,x6}, {x3,x4}, {x5,x7}}
IND({Số buổi}) = {{x1}, {x2}, {x3,x4}, {x5,x6,x7}}
IND({Độ tuổi, Số buổi }) = {{x1}, {x2}, {x3,x4}, {x5,x7}, {x6}}.
IX. Xấp xỉ tập hợp
Cho hệ thông tin IS = (U;A) và cho B ⊆ A và X ⊆ U. Ta có thể xấp xỉ

tập đối tượng X chỉ với thông tin chứa trong tập thuộc tính B bằng cách xây
dựng các xấp dựng các xấp xỉ B-dưới và B-trên của tập X, ký hiệu tương ứng là
X và X, trong đó:
X = { x | [x]
B
⊆ X} và
X = { x | [x]
B
∩ X

≠ φ}
Tập BN
B
(X) = X - X được gọi là vùng biên của tập X, và vì có thể chứa
các đối tượng mà ta không thể phân lớp chắc chắn vào X theo tập B.
Tập U - X được gọi là vùng B-ngoài của X và chứa các đối tượng phân
lớp chắc chắn là không thuộc về tập X.
Một tập hợp được gọi là thô nếu vùng biên là khác rỗng. Ngược lại, một
tập hợp được gọi là rõ nếu vùng biên là rỗng.
Ví dụ:
Gọi W = {x | Thi đậu(x) = Có}={x1,x4,x6}.
A={Độ tuổi, Số buổi} theo bảng 4.1. Ta có vùng xấp xỉ:
• W = {x1, x6}
• W = {x1, x3, x4, x6}
• BN
B
(X) = {x3, x4} và U - X = {x2, x5, x7}
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG

Như vậy lớp quyết định Thi đậu là thô vì vùng biên khác rỗng.
Độ chính xác của xấp xỉ:
Tập thô còn có thể đặc trưng hóa dưới hình thức số bằng hệ số phản ánh
độ chính xác của xấp xỉ:
Trong đó |X| biểu diễn lực lượng của tập X ≠ φ.
Rõ ràng ta có 0 <= αB(X) <= 1
Nếu αB(X) = 1, X là rõ theo B, ngược lại, nếu αB(X) < 1, X là thô theo
B.
X. Rút gọn
Các phần trước đã nghiên cứu một hướng rút gọn dữ liệu bằng cách xác
định các lớp tương đương. Việc rút gọn có thể thực hiện được vì chỉ cần một
phần tử của lớp tương đương là đủ để biểu diễn toàn bộ lớp đó. Một hướng rút
gọn khác là chỉ giữ lại các thuộc tính bảo toàn quan hệ bất khả phân biệt và do
vậy bảo toàn xấp xỉ tập hợp. Các thuộc tính được loại bỏ là dư thừa vì việc loại
bỏ chúng không làm xấu đi sự phân lớp. Thường có một vài tập thuộc tính con
như vậy và nếu chúng là tối tiểu thì được gọi là các rút gọn. Việc tính toán lớp
tương đương là tương đối dễ dàng. Nhưng việc tìm kiếm một rút gọn tối tiểu là
một bài toán NP khó. Điều này có nghĩa là việc tính toán các rút gọn là một bài
toán không tầm thường. Tuy vậy hiện có nhiều thuật toán tốt cho phép tìm một
cách hiệu quả các rút gọn trong thời gian chấp nhận được, ngoại trừ trường hợp
số lượng thuộc tính quá lớn.
Định nghĩa rút gọn
Một rút gọn của hệ thông tin IS là một tập tối tiểu của các thuộc tính B ⊆
A sao cho IND
S
(B) = IND
S
(A).
Ma trận phân biệt
Với S là hệ thông tin với n đối tượng, ma trận phân biệt của S là một ma

trận đối xứng n x n với các giá trị c
ij
được định nghĩa như sau:
c
ij
= {a ∈ A | a(x
i
) ≠ a(x
j
)} với i, j = 1 n
Mỗi dòng bao gồm tập giá trị các thuộc tính khác nhau với các đối tượng
x
i
và x
j
.
Hàm phân biệt
Hàm phân biệt f
S
của hệ thông tin IS là một hàm bool của m biến bool
a*
1
a*
m
và được định nghĩa như sau:
f
S
(a*
1
a*

m
) = Λ {Vc
ij
*/1 <= j <= i < n, c
ij
≠ φ}
Tập các đơn thức của f
S
xác định tập rút gọn của IS.
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Ví dụ:
f
S
(d,e,f,r) = (evr)(dvevr)(dvevr)(dvr)(dve)(evfvr)(dvevf)
= (dvr)(dve)(dve)(dvevr)(evfvr)(dvfvr)
= (dvevr)(dvevr)(dvevr)(dvevf)(fvr)
= (e)(r)(dvfvr)(dvevfvr)
= (evr)(dvevfvr)(dvevfvr)
= (dvfvr)(dvevf) = (dvevr)
PHẦN V : GOM CỤM DỮ LIỆU
I Mở đầu
Gom cụm là hình thức học không giám sát trong đó các mẫu học chưa
gán nhãn. Mục đích của gom cụm dữ liệu là tìm các mẫu đại diện hoặc gom dữ
liệu tương tự nhau. Các điểm dữ liệu trong các cụm khác nhau có độ tương tự
thấp hơn các điểm nằm trong cùng một cụm. Một số ứng dụng tiêu biểu của
gom cụm như:
• Xem xét phân bố dữ liệu
• Tiền xử lý cho các thuật toán

• Khám phá thói quen và nhu cầu của khách hàng để có phương pháp
tiếp thị thích hợp.
• Phân loại nhà theo vị trí, giá trị.
• Phân loại bệnh nhân.
•
Một phương pháp gom cụm tốt nếu đạt được các tính chất sau:
• Có độ tương tự cao trong từng cụm.
• Có độ tương tự thấp trong giữa cụm.
• Có khả năng phân biệt mẫu ẩn.
• Có khả năng làm việc hiệu quả với dữ liệu lớn, nhiều loại dữ liệu
khác nhau.
• Có khả năng khám phá các cụm có phân bố theo các dạng khác nhau.
• Có khả năng làm việc với nhiễu và mẫu cá biệt
• Không ảnh hưởng thứ tự nhập của dữ liệu
• Làm việc tốt trên CSDL có số chiều cao.
• Chấp nhận các ràng buộc do user quy định.
• Có thể hiểu và sử dụng kết quả gom cụm.
Dựa trên cách tiếp cận và thuật toán sử dụng, người ta phân thuật toán
gom cụm theo các phương pháp chính sau:
• Các phương pháp phân hoạch.
• Các phương pháp phân cấp.
• Các phương pháp dựa trên mật độ.
• Các phương pháp dựa trên mô hình.
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
• Các phương pháp dựa trên lưới.
XI. Thuật toán gom cụm k-means
1.Giới thiệu
Một phương pháp phân hoạch là xác định trước số cụm cần có. Chẳng

hạn là k, sau đó xếp từng điển dữ liệu vào một trong k cụm sao cho độ phân biệt
trong các cụm là thấp nhất. Vấn đề đặt ra là đối với một không gian với số chiều
và số phần tử lớn thì thời gian thực hiện tăng rất nhanh theo quy luật bùng nổ tổ
hợp. Với k cho trước có thể có (kn-(k-1)n 1) khả năng phân hoạch khác
nhau. Đây là con số quá lớn nếu k là khá lớn do đó hầu như không thể thực hiện
được. Vì vậy, gom cụm phân hoạch là những thuật toán nhanh và sử dụng
euristic để đạt được giải pháp gom cụm đủ tốt. Thuật toán k-means là một trong
số những thuật toán như vậy.
2.Thuật toán k-means
Cho k là số cụm sau khi phân hoạch (1 <= k <= n, với n là số điểm)
Thuật toán gồm 4 bước:
1) Phân hoạch đối tượng thành k tập con/cụm khác rỗng
2) Tính các điểm hạt giống làm centroid (trung bình của các đối
tượng của cụm) cho từng cụm trong cụm hiện hành
3) Gán từng đối tượng vào cụm có centroid gần nhất
4) Quay về bước 2, chất dứt khi không còn phép gán mới
Minh họa với k = 2:
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
3.Ưu và nhược điểm của thuật toán
Ưu điểm
Tương đối nhanh. Độ phức tâp thuật toán là O(tkn), trong đó:
• n: số điểm trong không gian dữ liệu
• k: số cụm cần phân hoạch
• t:số lần lặp
K-means phù hợp với các cụm có dạng hình cầu
Khuyết điểm
Có thể áp dụng chỉ khi xác định được trị trung bình của các đối tượng
Cần chỉ định trức k, số các cụm

Không thể xử lý dữ liệu chuỗi và outliers
Không phù hợp để khám phá các cụm với dạng khong lồi hay cụm có
kích thước khác nhau.
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
PHẦN VI : CHƯƠNG TRÌNH DEMO KHAI PHÁ DỮ LIỆU
I Mở đầu
Chương trình Demo giới thiệu các thuật toán và phương pháp khai phá
dữ liệu được trình bày trên phần cơ sở lý thuyết. Bao gồm các phần sau:
• Luật kết hợp: Tìm tất cả các tập phổ biến theo minsupp và tìm tập
luật kết hợp dựa trên minconf. Chương trình còn hỗ trợ tìm tập luật
tối đại và phát sinh luật kết hợp theo tập tối đại. Trong chương trình,
còn có phần “Chi tiết thuật toán” để theo dõi các bước thực hiện các
thuật giải.
• Phân lớp Bayes: Người dùng có thể tìm các phân lớp bayes dựa trên
các mẫu thử. Chương trình còn hỗ trợ tự động tìm các mẫu thử chưa
tồn tại trên CSDL để phân lớp trên các mẫu đó. Trong chương trình,
còn có phần “Chi tiết thuật toán” để theo dõi các bước tính toán và ra
kết luận.
• Rút gọn lớp tương đương: Giúp xác định được vùng xấp xỉ B-Trên
và B-Dưới của phân hoạch được chọn với tất cả tập đối tượng.
• Độ chính xác xấp xỉ: được mở rộng dựa trên demo “Rút gọn lớp
tương đương”. Chương trình tự động tìm ra tất cả các phân hoạch.
Sau đó, sẽ tính độ chính xác xấp xỉ của từng đối tượng X theo các tập
phân hoạch. Cuối cùng, chương trình sẽ xác định tập hợp xấp xỉ tối
đại. Trong chương trình, còn có phần “Chi tiết thuật toán” để theo dõi
các bước thực hiện việc tính toán và kết luận các thuật giải.
• Rút gọn ma trân phân biệt: Chương trình hỗ trợ tạo ma trận phân
biệt dựa trên CSDL cho trước và sinh ra hàm phân biệt. Chương trình

sẽ tự động rút gọn hàm phân biệt dựa trên luật hấp thụ và hiển thị quá
trình hấp thụ trên chương trình.
• Thuật toán K-means: Chương trình dựa trên thuật toán K-means để
gom cụm dữ liệu. Chương trình hỗ trợ tính ra các cụm theo ma trận
phân biệt hay cho trước vector trọng tâm. Trong chương trình, còn có
phần “Chi tiết thuật toán” để theo dõi các bước thực hiện việc tính
toán ra ma trận phân hoạch, vector trọng tâm và khoảng cách Euclide.
MÔN HỌC : KHAI PHÁ DỮ LIỆU
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
CHƯƠNG TRÌNH ĐẠO TẠO THẠC SĨ CNTT QUA MẠNG
Giao diện chương trình: Giao diện chương trình gồm có hai phần làm
việc:
• Phần 1: Dùng để chọn các ứng dụng demo.
• Phần 2: Vùng làm việc dùng để xử lý các bài toán tương ứng với ứng
dụng demo đã chọn.
Chương trình được phát triển trên .Net Framework 4.0 và Visual Studio
2010.
MÔN HỌC : KHAI PHÁ DỮ LIỆU