




KHAI PHÁ DỮ LIỆU VÀ NHÀ KHO DỮ LIỆU
 !"#$%&'($#
$%
Giảng viên hướng dẫn : P) )*+,
Học viên thực hiện: -.//0//12
Lớp 03
TP. Hồ Chí Minh, tháng 11 năm 2012
Lời mở đầu
Với môn cơ sở dữ liệu truyền thống, ta thấy các lợi ích mà nó mang lại là
không thể phủ nhận trong việc giải quyết các vấn đề thông dụng như tìm kiếm thông
tin, thống kê, kết xuất Tuy nhiên với nhiều năm lưu trữ và tích luỹ một lượng rất lớn
dữ liệu và giá trị của nguồn dữ liệu này là một tài sản vô giá thì còn tìm ẩn. Để có thể
khai thác và xử lý hiệu quả nguồn “tài nguyên- khoáng sản” này, các chuyên gia công
nghệ thông tin đã có rất nhiều công trình nghiên cứu và từ đó hình thành lĩnh vực
riêng về đề tài này, cụ thể là “Kỹ thuật phát hiện tri thức và khai phá dữ liệu” (KDD -
Knowledge Discovery and Data Mining) đã ra đời và đã được ứng dụng rộng rãi vào
thực tế.
Về mặt thực tiễn, khai phá dữ liệu hiện đang được áp dụng một cách rộng rãi
trong nhiều lĩnh vực kinh doanh và đời sống khác nhau như: marketing, tài chính,
ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet, … rất nhiều tổ chức và công
ty lớn trên thế giới đã áp dụng kỹ thuật khai phá dữ liệu vào các hoạt động sản xuất
kinh doanh. Các công ty phần mềm lớn trên thế giới cũng rất quan tâm và chú trọng
tới việc nghiên cứu và phát triển kỹ thuật khai phá dữ liệu: hãng Oracle tích hợp các
công cụ khai phá dữ liệu vào bộ Oracle9i, hãng Microsoft thì tích hợp các công cụ và
SQL 2005, IBM đã đi tiên phong trong việc phát triển các ứng dụng khai phá dữ liệu
với các ứng dụng như Intelligence Miner,…

………………………………………………………………………………….
………………………………………………………………………………….
………………………………………………………………………………….
………………………………………………………………………………….
3
………………………………………………………………………………….
………………………………………………………………………………….
………………………………………………………………………………….
………………………………………………………………………………….
………………………………………………………………………………….
………………………………………………………………………………….
………………………………………………………………………………….
………………………………………………………………………………….
………………………………………………………………………………….
………………………………………………………………………………….
………………………………………………………………………………….
………………………………………………………………………………….
……………………………………………………………………………….
………………………………………………………………………………….
…………………………………………………………………………………
4
67867
-/&9$%
I. -):;<
/*/* =>=?@=AB7@BCDEFG@HIJ@H?K=?@L7EMG@N=J@HOP8=AB
Nếu cho rằng, điện tử và truyền thông chính là bản chất của khoa học điện tử, thì
dữ liệu, thông tin, và tri thức hiện đang là tiêu điểm của một lĩnh vực mới để nghiên cứu
và ứng dụng, đó là khám phá tri thức và khai phá dữ liệu.
Thông thường, chúng ta coi dữ liệu như là một chuỗi các bits, hoặc các số và các
ký hiệu hay là các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một chương

Mô tả dữ liệu là tổng kết hoặc diễn tả những đặc điểm chung của những thuộc tính
dữ liệu trong kho dữ liệu mà con người có thể hiểu được.
Dự đoán là dựa trên những dữ liệu hiện thời để dự đoán những quy luật được phát
hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu trên cơ sở đó chiết xuất ra các
mẫu, dự đoán được những giá trị chưa biết hoặc những giá trị tương lai của các biến quan
tâm.
Quá trình KPDL bao gồm các bước chính được thể hiện như hình sau:
7
Hình 2: Quá trình Khai phá dữ liệu.
• Xác định nhiệm vụ
• Xác định các dữ liệu liên quan
• Thu thập và tiền xử lý dữ liệu
• Thuật toán khai phá dữ liệu
1 H7J@STCDJ@HJG@N=J@HOP8=AB
Với hai mục đích khai phá dữ liệu là Mô tả và Dự đoán, người ta thường sử dụng
các phương pháp sau cho khai phá dữ liệu:
• Luật kết hợp (association rules)
• Phân lớp (Classfication)
• Hồi qui (Regression)
• Trực quan hóa (Visualiztion)
• Gom cụm (Clustering)
• Tổng hợp (Summarization)
• Mô hình ràng buộc (Dependency modeling)
• Biểu diễn mô hình (Model Evaluation)
• Phân tích sự phát triển và độ lệch (Evolution and deviation analyst)
• Phương pháp tìm kiếm (Search Method)
Có nhiều phương pháp khai phá dữ liệu được nghiên cứu ở trên, trong đó có ba
phương pháp được các nhà nghiên cứu sử dụng nhiều nhất đó là: Luật kết hợp, Phân lớp
dữ liệu và Gom cụm dữ liệu.
U H78VC@EW7LCDO6CD?@W7?=XC7YN$

• Thay đổi dữ liệu và tri thức có thể làm cho các mẫu đã phát hiện không còn phù
hợp
• Quan hệ giữa các trường phức tạp
9
II. @cC76IOP8=ABd8Be?fK=CDg
R*/* @H=C=AIJ@cC76IOP8=AB
Gom cụm dữ liệu là vấn đề rất quan trọng, được dùng trong nhiều lĩnh vực. Mục
đích của gom cụm là xác định các cụm tồn tại bên trong một tập hợp dữ liệu không có nhãn
(không biết phần tử nào thuộc vào lớp nào) cho trước.
Gom cụm dữ liệu là một phương pháp học không giám sát (unsupervised learning).
Gom cụm dữ liệu là quá trình nhóm một tập 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 cụm 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. Gom cụm dữ liệu là một ví dụ
của phương pháp học không có thầy. Không giống như phân lớp dữ liệu, gom cụm dữ
liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi
gom cụm dữ liệu là một cách học bằng quan sát, trong khi phân lớp dữ liệu là học bằng ví
dụ… Ngoài ra gom cụm dữ liệu còn có thể được sử dụng như một bước tiền xử lí cho các
thuật toán khai phá dữ liệu khác như là phân loại và mô tả đặc điểm, có tác dụng trong
việc phát hiện ra các cụm.
Hình 3: Mô tả tập dữ liệu vay nợ đ
ư
ợc gom thành 3 cụm.
10
Gom cụm có ý nghĩa rất quan trọng trong hoạt động của con người. Ngay từ lúc
bé, con người đã học cách làm thế nào để phân biệt giữa mèo và chó, giữa động vật và
thực vật và liên tục đưa vào sơ đồ phân loại trong tiềm thức của mình. Gom cụm được sử
dụng rộng rãi trong nhiều ứng dụng, bao gồm nhận dạng mẫu, phân tích dữ liệu, xử lý
ảnh, nghiên cứu thị trường Với tư cách là một chức năng khai phá dữ liệu, phân tích
gom cụm có thể được sử dụng như một công cụ độc lập chuẩn để quan sát đặc trưng của
mỗi cụm thu được bên trong sự phân bố của dữ liệu và tập trung vào một tập riêng biệt

• WWW: Có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý nghĩa trong môi
trường Web. Các lớp tài liệu này trợ giúp cho việc KPTT từ dữ liệu.
1 H7ihB7jB7YNJ@cC76IOP8=AB
Gom cụm là một thách thức trong lĩnh vực nghiên cứu ở chỗ những ứng dụng tiềm
năng của chúng được đưa ra ngay chính trong những yêu cầu đặc biệt của chúng. Sau đây
là những yêu cầu cơ bản của gom cụm trong KPDL:
• Có khả năng mở rộng.
• Khả năng thích nghi với các kiểu thuộc tính khác nhau.
• Khám phá các cụm với hình dạng bất kỳ.
• Tối thiểu lượng tri thức cần cho xác định các tham số đầu vào.
• Khả năng thích nghi với dữ liệu nhiễu: Hầu hết những CSDL thực đều chứa đựng
dữ liệu ngoại lai, dữ liệu lỗi, dữ liệu chưa biết hoặc dữ liệu sai. Một số thuật toán
gom cụm nhạy cảm với dữ liệu như vậy và có thể dẫn đến chất lượng gom cụm
thấp.
• Ít nhạy cảm với thứ tự của các dữ liệu vào.
• Số chiều (thuộc tính) lớn.
• Gom cụm ràng buộc.
• Dễ hiểu và dễ sử dụng.
12
Với những yêu cầu đáng lưu ý này, nghiên cứu của ta về phân tích gom cụm diễn
ra như sau: Đầu tiên, ta nghiên cứu các kiểu dữ liệu khác và cách chúng có thể gây ảnh
hưởng tới các phương pháp gom cụm. Thứ hai, ta đưa ra một cách phân loại chung trong
các phương pháp gom cụm. Sau đó, ta nghiên cứu chi tiết mỗi phương pháp gom cụm,
bao gồm các phương pháp phân hoạch, phân cấp, dựa trên mật độ, Ta cũng khảo sát sự
gom cụm trong không gian đa chiều và các biến thể của các phương pháp khác.
U @PCDG_?@B\??=[J7\C?K`CDJ@cC76IOP8=AB
Các kỹ thuật gom cụm có rất nhiều cách tiếp cận và các ứng dụng trong thực tế,
nó đều h
ư
ớng tới hai mục tiêu chung đó là chất l

o Thuật toán PAM.
o Thuật toán CLARA.
o Thuật toán CLARANS.
• Các thuật toán gom cụm phân cấp:
o Thuật toán CURE.
o Thuật toán BIRCH.
o Thuật toán AGNES.
o Thuật toán DIANA.
o Thuật toán ROCK.
o Thuật toán CHANMELEON.
• Các thuật toán gom cụm dựa trên mật độ
o Thuật toán DBSCAN
o Thuật toán OPTICS.
o Thuật toán DENCLUE.
• Các thuật toán gom cụm dựa trên lưới
o Thuật toán STING
o Thuật toán CLIQUE.
• Các thuật toán gom cụm dựa trên mô hình
o Thuật toán EM
o Thuật toán COBWEB.
• Các thuật toán gom cụm có dữ liệu ràng buộc
o FCM.
o ɛFCM.
o FCM-Cải tiến.
16
-R !)
I -):;<
*/* @H=C=AI
K-means là thuật toán gom cụm theo phương pháp phân hoạch và đã được sử
dụngrộng rãi. Cho tập các đối tượng, mục tiêu gom cụm hay phân mảnh là chia tập

, C
2
, … , C
k
},sao cho mỗi điểm dữ liệu xi nằm
trong một cụm duy nhất. Đểbiết điểm dữ liệu thuộc cụm nào người ta gán cho nó
một mã cụm. Các điểm có cùngmã cụm thì ở cùng cụm, trong khi các điểm khác
mã cụm thì ở trong các cụm khácnhau. Một cụm có thể biểu thị bằng vec-tơ liên
thuộc cụm v có độ dài N, với vi là mãcụm của xi.
Giá trịk là đầu vào của thuật toán. Giá trịk dựa trên tiêu chuẩn tri thức trước đó.
Sẽ cóbao nhiêu cụm thực sự xuất hiện trong U, bao nhiêu cụm được đề nghị cho
ứng dụng hiện hành, hay các kiểu cụm được tìm thấy bằng cách dựa vào thực
nghiệm với nhiềugiá trịk khác nhau. Không cần thiết phải hiểu k được chọn như
thế nào khi k-meansphân mảnh tập dữ liệu U, việc chọn giá trịk như thế nào sẽ
được thảo luận trong phầnkế tiếp.
Trong các thuật toán gom cụm, các điểm được nhóm theo khái niệm “độ gần”
hay “độtương tự”. Với k-means, phép đo mặc định cho “độ tương tư” là khoảng
cách Euclide.Đặc biệt, có thể thấy k-means cố gắng cực tiểu hóa hàm giá trị không
âm sau:
18
Nói cách khác, k-means cố gắng cực tiểu khoảng cách Euclide tổng bình
phương giữamỗi điểm xi và thể hiện cụm gần nhất của nó Cj. Biểu thức trên
thường được xem làhàm mục tiêu k-means.
Thuật toán k-means, thay đổi giữa 2 bước: (1) gán lạimã cụm của tất cả điểm
trong U và (2) cập nhật các thể hiện cụm dựa trên các điểm dữliệu trong mỗi cụm.
Thuật toán làm việc như sau: đầu tiên, các thể hiện nhóm đượckhởi tạo bằng cách
chọn k điểm trong ℜd . Các kỹ thuật để chọn các hạt giống khởi tạobao gồm lấy
mẫu ngẫu nhiên từ tập dữ liệu, xem chúng như giải pháp gom cụm tậpcon nhỏ dữ
liệu, hay làm thay đổi giá trị trung bình toàn cục của k lần dữ liệu. Trongthuật toán
2.1, ta khởi tạo k điểm ngẫu nhiên. Sau đó thuật toán lặp 2 bước cho đến khihội tụ.

- Kết thúc ở điểm tối ưu cục bộ, có thể dùng thuật toán di truyền để tìm tối
ưu toàn cục.
*Z* k?el@pC7@[7YN?@B\??`HCG IfNCe
Sự hội tụ chỉ là tối ưu cục bộ và thuật toán khá nhạy cảm với các định vị tâm
khởi tạo.Nói cách khác, việc khởi tạo tâm các thể hiện cụm C khác nhau có thể
20
dẫn đến rấtnhiều cụm, thậm chí trên cùng tập dữ liệu U. Việc khởi tạo nghèo nàn
có thể dẫn đếncác cụm rất nghèo nàn.
Như đã đề cập, việc chọn giá trị tối ưu của k có thể khó. Nếu hiểu rõ về tập dữ
liệu,như là số mảnh tự nhiên có trong tập dữ liệu thì sự hiểu biết đó là cơ sở để
chọn k.Ngược lại, ta phải dùng một chuẩn khác để chọn k. Một giải pháp là thử
nhiều giá trịkhác nhau của k và chọn cụm mà nó cực tiểu hàm mục tiêu k-means.
Giá trị hàm mụctiêu không giống thông tin như mong muốn. Điều này làm bài
toán khó hơn khi dùnghàm mục tiêu cho (a) các giải pháp so sánh trực tiếp với
nhiều số cụm khác nhau và(b) tìm giá trị tối ưu của k. Vì vậy, nếu không biết được
giá trị k mong chờ, người ta sẽchạy k-means với các giá trị k khác nhau rồi chọn ra
một trong những giá trị tốt nhất.
Người ta có thể tăng dần số cụm, kết hợp với chuẩn dừng thích hợp. Chia k-
mean làm2, đầu tiên cho tất cả dữ liệu vào trong một cụm, sau đó chia một cách đệ
quy cụm ítbền vững nhất thành 2 cụm dùng 2-means. Thuật toán LBG dùng cho
lượng tử hóavec-tơ gấp đôi số cụm cho đến khi có kích thước hợp lý. Cả hai
hướng tiếp cận trênlàm nhẹ bớt nhu cầu biết trước k. Nhiều nhà nghiên cứu khác
vẫn tiếp tục nghiên cứuvấn đề này.
Với các giới hạn trên, k-means kém chất lượng do nhiều vấn đề khác. Đầu tiên
có thểđược hiểu bằng bài toán khớp dữ liệu dùng cách trộn k Gaussian với các ma
trận thốngkê Σ=σ 2 I (isotropic convariance matrices), với I là ma trận xác định,
các kết quảtrong phiên bản “mềm” của k-means. Chính xác hơn, nếu các phép gán
mềm của cácđiểm dữ liệu cho những thành phần trộn của một mô hình như vậy trở
nên khó, saocho mỗi điểm dữ liệu được định vị đơn độc cho thành phần giống
nhất, đó là thuật toánk-means. Từ đó có thể thấy, k-means sẽ gặp khó khăn bất cứ

22
II r!)!$!4d)g
*3* =>=?@=AB
Mô hình không gian vector được nếu như số lượng từ chỉ mục tăng rất lớn thì
kích thước của ma trận từ chỉ mục (term document) A cũng tăng theo rất lớn. Hơn
nữa độ đo Cosines giữa vector truy vấn và vector văn bản là phải khác Zero nếu và
chỉ nếu tồn tại ít nhất từ chỉ mục giữa 2 vector trên.
Latent Semantic Indexing (LSI ) là phương pháp tạo chỉ mục tự động dựa trên
khái niệm để khắc phục hai hạn chế tồn tại trong mô hình không gian vector chuẩn
về hai vấn đề synoymy và polysemy . Với synoymy, nhiều từ có thể được sử dụng
để biểu diễn một khái niệm, vì vậy hệ thống không thể trả về những văn bản liên
quan đến câu truy vấn của người dùng khi họ sử dụng những từ trong câu truy vấn
đồng nghĩa với những từ trong văn bản. Với polysemy, một từ có thể có nhiều
nghĩa, vì vậy hệ thống có thể trả về những văn bản không liên quan. Điều này thực
tế rất thường xảy ra bởi vì các văn bản trong tập văn bản được viết bởi rất nhiều
tác giả, với cách dùng từ rất khác nhau. Một cách tiếp cận tốt hơn cho phép người
dùng truy vấn văn bản dựa trên khái niệm (concept) hay nghĩa (meaning) của văn
bản.
Mô hình LSI cố gắng khắc phục hai hạn chế trên trong mô hình không gian
vector bằng cách chỉ mục khái niệm được tạo ra bởi phương pháp thống kê ( phân
tích SVD ma trận term – document A) thay cho việc sử dụng các từ chỉ mục đơn.
Mô hình LSI dựa trên giả thiết là có các ngữ nghĩa tiềm ẩn (latent semantic) trong
việc sử dụng từ: có nhiều từ biểu diễn cho một khái niệm và một khái niệm có thể
được biểu diễn bởi nhiều từ. Mô hình LSI sử dụng phân tích SVD (Singular Value
Decomposition) ma trận term – document A để phát hiện ra các quan hệ ngữ nghĩa
trong cách dùng từ trong toàn bộ văn bản .
23
*s* @cC?t7@)=CDB8NK&N8Bf$f7`IJ`e=?=`Cd)&$g7YNIN?K\C?u7@vI67
d?fKIO`7BIfC?g
Vấn đề cơ bản của mô hình LSI là phân tích SVD của ma trận term document











−
−
−−
−−−
−−
−−−
=
7071.006394.02774.00127.01182.0
001158.00838.08423.05198.0
7071.006394.02774.00127.01182.0
07071.02847.05308.02567.02670.0
000816.05249.03981.07479.0
07071.02847.05308.02567.02670.0
U







−−
−
−−−
−−
−−
=
7071.00577.03712.02815.05288.0
06571.05711.00346.04909.0
5000.01945.06247.03568.04412.0
5000.02760.00998.07549.03067.0
06715.03688.04717.04366.0
V
Ma trận xấp xỉ
T
kkkk
VUA Σ=
có hạng là k với k << r . Trong đó, các cột của U
k
là k cột đầu tiên của U, các cột của V
k
là k cột đầu tiên của của V và
k
Σ
là ma trận
đường chéo cấp k x k với các phần tử nằm trên đường chéo là k giá trị suy biến lớn
nhất của A.
Hình 2.2 Biểu diễn ma trận xấp xỉ A
k
có hạng là k
Ví dụ 2.2: cho k=3, Tìm ma trận xấp xỉ A