Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
Bộ giáo dục và đào tạo
Trờng đại học bách khoa Hà nội
Trang 1
Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
Luận văn tốt nghiệp cao
học
ngành: Công nghệ thông tin
Tên đề tài
Khai phá dữ liệu và Phát hiện luật kết hợp trong cơ sở dữ liệu lớn
Ngời hớng dẫn: Tiến sỹ Nguyễn Thanh Thuỷ
Khoa Công nghệ Thông tin, ĐHBKHN

Ngời thực hiện: nguyễn An Nhân
Hà nội - 2001
Trang 2
Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
Lời nói đầu
Một tổ chức thơng mại có thể sản sinh ra dữ liệu trong hoạt động kinh doanh mà để ghi
chép lại có thể phải mất cả đời ngời. Tình trạng này càng tăng lên kể từ khi xuất hiện
mạng toàn cầu Internet. Mỗi ngày có hàng trăm megabyte, thậm chí nhiều hơn thế dữ
liệu đợc đa lên Internet. Trong tình trạng bội thực về dữ liệu nh vậy, chúng ta phải đối
mặt với nghịch lý mới về khai thác dữ liệu: càng nhiều dữ liệu, càng ít thông tin. Hiện
nay, cũng nh trong tơng lai, các nhà kinh doanh, nhà khoa học hoặc tổ chức thơng mại
không thể đủ thời gian và khả năng đọc và diễn giải theo cách cổ điển tất cả các dữ liệu
sang những thông tin cần thiết. Tuy nhiên, yêu cầu về thông tin không vì thế giảm đi,
mà ngày càng trở nên cần thiết hơn bao giờ hết đã buộc chúng ta phải đề ra và thực hiện
các chiến lợc và phơng pháp chọn, lọc và diễn giải dữ liệu thành các thông tin hữu ích.
Nh thế, các tổ chức bị ngập chìm trong đống dữ liệu khổng lồ, đặc biệt trong một số
lĩnh vực tài chính, ngân hàng, thị trờng chứng khoán và kinh doanh thơng mại, sẽ có cơ
hội khai thác dữ liệu hiệu quả để phát triển.

Trang 3
Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
Lời cảm ơn
Trớc hết , tôi xin chân thành cảm ơn Trờng Đại học Bách khoa Hà nội,
Trung tâm Đào tạo và Bồi dỡng sau đại học và cơ quan nơi tôi đang công
tác đã tạo điều kiện thuận lợi cho tôi trong suốt thời gian học và làm luận
văn cao học.
Tôi xin bày tỏ sự biết ơn sâu sắc đến Thầy giáo, Tiến sỹ Nguyễn Thanh
Thuỷ, ngời đã tận tình hớng dẫn động viên trong suốt quá trình học và đặc
biệt trong thời gian hoàn thành luận văn này.
Tôi xin trân trọng cảm ơn các thầy giáo đã quan tâm, góp ý và nhận xét
cho bản luận văn của tôi.
Tôi cũng xin gửi lời cám ơn đến các thày, cô giáo đã giảng dạy cho tôi trong
suốt thời gian qua.
Nguyễn An Nhân
Trang 4
Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
Chơng 1. Mở đầu
1.1 Học máy
Luận văn nghiên cứu về lĩnh vực khai phá dữ liệu, liên quan đến kỹ thuật học của máy
tính để phát hiện ra các thông tin mới và có ý nghĩa. ý tởng về học máy xuất phát từ mô
phỏng các cơ thể sống, từ các cây cối hay con amip đến cơ thể sống phát triển nhất là
con ngời. Cây học cách thu nhận ánh sáng tối đa bằng cách hớng các chiếc lá của
mình về phía mặt trời, nhằm tự thích nghi với môi trờng sống. ở mức cao hơn, con ngời
sản sinh ra ngôn ngữ để khai thác các qui luật của thế giới tự nhiên và xã hội. Lý thuyết
về sự tiến hoá chỉ ra rằng các loài sống sót đợc sau quá trình tồn tại là những loài tự
thích nghi tốt nhất với môi trờng sống. Học là một dạng thích nghi và là một đặc tính
trung tâm của cuộc sống thực tế.
Tuy nhiên, một câu hỏi đặt ra liệu các hệ thống máy tính có thể học đợc không và nếu
học đợc, thì có thể thông minh ở mức nào. Có thể xem sẽ không có trí tuệ nhân tạo

1.2 Phát hiện tri thức và Khai phá dữ liệu
Tuy nhiên, một xu hớng khác trong nghiên cứu học máy ngoài ứng dụng trong các hệ
chuyên gia xuất phát từ sự bùng nổ thông tin trong xã hội hiện đại. Hầu hết các tổ chức
đều hình thành các kho dữ liệu lớn có khả năng truy cập đợc. Nhng trên thực tế rất khó
có thể tìm ra các thông tin mong muốn và hữu ích, giống nh việc tìm một cái kim trong
đống sắt vụn càng ngày càng lớn dần. Công việc một hệ máy tính tự động tìm đợc các
mẩu kim cơng thông tin trong số hàng tấn mảnh vụn dữ liệu lu trong cơ sở dữ liệu
(CSDL) dẫn đến một lĩnh vực nghiên cứu mới. Đó là khai phá dữ liệu (Data Mining) và
phát hiện tri thức trong CSDL (Knowledge Discovery in Databases). Về mặt ngữ nghiã,
hai thuật ngữ này có ý nghĩa phân biệt đôi chút. Phát hiện tri thức trong CSDL chỉ toàn
bộ quá trình kết xuất tri thức từ dữ liệu. Theo ngữ cảnh này, tri thức có nghĩa là mối
quan hệ và các mẫu giữa các phần tử dữ liệu. Khai phá dữ liệu đợc dùng để mô tả giai
đoạn phát hiện của quá trình phát hiện tri thức trong CSDL. Việc phát hiện tri thức trong
CSDL không chỉ là một kỹ thuật mà còn là lĩnh vực nghiên cứu đa chủ đề: Học máy,
Thống kê, công nghệ CSDL, Kho dữ liệu và Hệ chuyên gia.
1.3 Khai phá dữ liệu và các công cụ SQL
Các CSDL lớn của các tổ chức có thể ví nh các mỏ dữ liệu bao gồm nhiều gigabytes dữ
liệu với các thông tin tiềm ẩn bên trong không thể dễ dàng tìm ra đợc bằng công cụ SQL
hoặc các công cụ truy vấn khác. Các thuật toán và công cụ khai phá dữ liệu có thể chia
nhóm tối u hoặc các luật nào đó từ các dữ liệu trong CSDL, trong khi SQL chỉ là công
cụ truy vấn, giúp tìm ra các dữ liệu dới các ràng buộc đã biết. Các thuật toán và công cụ
khai phá dữ liệu có thể quan tâm đến toàn bộ hoặc một phần CSDL, có thể sử dụng lặp
đi lặp lại các câu truy vấn SQL và lu kết quả trung gian trong quá trình phát hiện tri
thức.
Tuy nhiên, các công cụ khai phá dữ liệu và công cụ SQL có những bổ trợ lẫn nhau.
Công cụ khai phá dữ liệu không thể thay thế công cụ truy vấn, nhng làm tăng khả năng
khai thác dữ liệu của ngời dùng. Sau đây là một ví dụ đơn giản minh hoạ việc sử dụng
kết hợp các công cụ truy vấn truyền thống và công cụ khai phá dữ liệu. Giả sử một tổ
chức có một kho dữ liệu hàng triệu bản ghi về việc mua sắm của khách hàng trong mời
năm gần đây. Có vô vàn các câu truy vấn thông thờng hay sử dụng từ kho dữ liệu này,

Chọn lọc dữ liệu
Làm sạch
Làm giàu
Mã hoá
Khai phá dữ liệu
Kết xuất báo cáo.
Khai phá dữ liệu chỉ là một giai đoạn của quá trình phát hiện tri thức trong
CSDL. Mặc dù có 6 giai đoạn, nhng quá trình xây dựng và hoàn chỉnh việc phát
hiện tri thức không chỉ qua 6 bớc mà theo chu trình liên tục kiểu xoáy trôn ốc,
trong đó các giai đoạn đợc lặp đi lặp lại, lần sau hoàn chỉnh hơn lần trớc và theo
kiểu thác nớc, trong đó giai đoạn sau dựa trên các kết quả đã đạt đợc của giai
đoạn trớc. Đây là quá trình phát triển biện chứng mang tính triết học của lĩnh vực
phát hiện tri thức và là phơng pháp luận trong việc xây dựng các hệ thống phát
hiện tri thức. Một lu ý nữa là 6 giai đoạn này có thể có các phần công việc liên
quan chặt chẽ đến các quá trình xây dựng một Kho dữ liệu (Data Warehouse).
Chúng ta sẽ thấy rõ hơn khi khảo sát về Kho dữ đợc đề cập ở chơng 4. Có thể có
cùng một việc cần làm nhng đợc nhìn ở góc độ của Kho dữ liệu hay góc độ phát
hiện tri thức trong CSDL.
Chọn lọc dữ liệu
Đây là bớc chọn lọc dữ liệu liên quan trong các nguồn dữ liệu. Chẳng hạn, trong CSDL
về bán hàng, ta chọn ra các dữ liệu về các khách hàng, đặt hàng và hoá đơn. Cụ thể hơn,
dữ liệu chọn ra chính là các bản ghi bao gồm số hiệu khách hàng, tên, địa chỉ, ngày
mua, số lợng và loại hàng.
Làm sạch
Thông thờng, quá trình chọn lọc và làm sạch dữ liệu kết hợp chặt chẽ với nhau và có thể
rất phức tạp nếu dữ liệu đầu vào đợc lấy từ nhiều nguồn không đồng nhất và phải tính
đến việc phải biến đổi và di chuyển dữ liệu về một kho dữ liệu riêng dùng cho khai phá.
Có thể có một vài kiểu làm sạch dữ liệu. Do dữ liệu đầu vào từ nhiều nguồn và có thể
không nhất quán nên cần phải điều hoà (reconcile) các dữ liệu, bao gồm khử các trờng
hợp lặp dữ liệu, thống nhất cách ký hiệu. Một khách hàng có thể có nhiều bản ghi do

Khai phá dữ liệu:
-Nhóm cụm
-Luật kết hợp
-Dự báo
Phân tích
Báo cáo
Di
chuyển
Hình 4.1 Quá trình KDD
Làm giàu
Các nguồn dữ liệu cung cấp cho hệ thống khai phá dữ liệu bao gồm từ các hệ thống dữ
liệu điều hành hàng ngày trong nội bộ một tổ chức, nhng cũng có thể cần các dữ liệu lấy
từ các nguồn bên ngoài khác. Chẳng hạn, dữ liệu về khách hàng đã bao gồm các thông
tin về ngày sinh, thu nhập, số d tài khoản thậm chí có sở hữu các tài sản nh nhà cửa và
xe máy. Tuy nhiên, ta cũng có thể rất cần các thông tin khác về thị trờng, chính sách của
nhà nớc, và ngay cả các số liệu thống kê về dân số học, thu nhập bình quân đầu ngời,
vv... Quá trình này cũng đợc mô tả kỹ khi xây dựng một Kho dữ liệu. Các dữ liệu sẽ đợc
biến đổi và di chuyển dựa trên một số phơng pháp, chẳng hạn dùng cổng kết nối
(gateway), tiện ích (utilities) và lập trình.
Một vấn đề thờng xảy ra khi thu thập dữ liệu từ nhiều nguồn khác nhau là sự không đầy
đủ của dữ liệu. Chẳng hạn, dữ liệu về khách hàng lấy từ một nguồn bên ngoài không có
hoặc có không đầy đủ thông tin về thu nhập. Nếu thông tin về thu nhập là quan trọng
trong việc khai phá dữ liệu để phân tích hành vi khách hàng, rõ ràng là ta không chấp
nhận đa dữ liệu thiếu vào đợc.
Trang 8
Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
Các dữ liệu ở các khuôn dạng khác nhau cũng cần đợc qui đổi và tính toán lại để đa về
một kiểu thống nhất tiện cho quá trình phân tích, chẳng hạn qui đổi đơn vị tiền tệ, tuổi
hay ngày sinh, địa chỉ chi tiết hay chia theo vùng, vv...
Dữ liệu thay đổi theo thời gian và đa yếu tố thời gian vào dữ liệu cũng là một vấn đề lớn

nhiệm vụ phát hiện tri thức trong CSDL là vấn đề đáng quan tâm nhằm tạo ra một hệ
thống phát hiện tri thức trong CSDL hiệu ích.
Trong chơng này, chúng ta mô tả mời kiểu nhiệm vụ phát hiện tri thức trong CSDL
chính và đa ra một vài so sánh giữa chúng.
2.1 Phát hiện các luật tối u truy vấn ngữ nghĩa (Semantic Query Optimization
- SQO Rules)
Các luật tối u truy vấn CSDL thông thờng thực hiện một phép biến đổi cú pháp, hay sắp
xếp lại thứ tự của các phép toán quan hệ trong một truy vấn và sản sinh ra một truy vấn
hiệu quả hơn. Các phép biến đổi này thờng dựa trên lý thuyết đại số quan hệ. Các luật
đợc biến đổi trả lại cùng một câu trả lời nh câu truy vấn ban đầu ở bất kỳ trạng thái nào
của CSDL. Ngợc lại, luật tối u truy vấn ngữ nghĩa biến đổi các câu truy vấn ban đầu
thành một truy vấn mới bằng cách thêm vào hoặc xoá đi các mối liên kết, bằng việc sử
dụng tri thức CSDL ngữ nghĩa bao gồm các ràng buộc về tính toàn vẹn và sự phụ thuộc
hàm để sản sinh ra câu truy vấn hiệu quả hơn. Nh vậy câu truy vấn đã biến đổi cũng trả
lại cùng câu trả lời giống nh câu truy vấn ban đầu trong bất kỳ trạng thái nào của CSDL
thoả mãn kiến thức về ngữ nghĩa đợc sử dụng trong phép biến đổi.
Các hệ thống phát hiện luật SQO có thể đợc chia thành 3 lớp:
Các hệ thống hớng truy vấn (hệ thống báo cáo) trong đó thuật toán phát hiện tri
thức trong CSDL nhằm phục vụ các truy vấn CSDL thực của ngời dùng;
Các hệ thống hớng dữ liệu (hệ thống tác nghiệp) trong đó thuật toán phát hiện tri
thức trong CSDL chủ yếu phục vụ sự phân bố dữ liệu trong trạng thái hiện thời
của CSDL;
Các hệ thống lai kết hợp các đặc tính của cả hệ thống hớng truy vấn và hớng dữ
liệu.
Một đặc tính quan trọng của các luật SQO, khác với các kiểu phát hiện tri thức khác, là
việc chọn các thuộc tính để tổng hợp một SQO cần phải tính toán đến chi phí liên quan
nh dùng phơng pháp truy cập nào và sơ đồ chỉ số trong HQT CSDL. Việc này là cần
thiết để tiết kiệm thời gian xử lý truy vấn. Một thuật toán phát hiện tri thức trong CSDL
loại này đòi hỏi phải xem xét tối u chi phí.
Trang 10

rời rạc, thậm chí liên tục. Chẳng hạn, các tác giả Srikant và Agrawal đa ra cách giải
quyết bài toán về CSDL khách hàng nhng mỗi mục đợc phân loại theo các mức độ khác
nhau.
2.5 Mô hình hoá sự phụ thuộc (Dependence Modeling)
Nhiệm vụ này liên quan đến việc phát hiện sự phục thuộc trong số các thuộc tính.
Những phụ thuộc này thờng đợc biểu thị dới dạng theo luật nếu-thì: nếu (tiền đề là
đúng) thì (kết luận là đúng). Về nguyên tắc, cả tiền đề và kết luận của luật đều có thể
là sự kết hợp lôgic của các giá trị thuộc tính. Trên thực tế, tiền đề thờng là nhóm các giá
trị thuộc tính và kết luận chỉ là một giá trị thuộc tính. Lu ý là những luật này không phải
hoàn toàn giống với sự phụ thuộc CSDL đợc nêu ở phần 2.2. Hơn nữa, hệ thống có thể
Trang 11
Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
phát hiện các luật với nhiều thuộc tính trong phần kết luận của luật. Điều này khác với
luật phân lớp trong đó tất cả các luật cần phải có cùng một thuộc tính do ngời dùng chỉ
ra trong kết luận.
Quan hệ phụ thuộc cũng có thể biểu diễn dới dạng mạng tin cậy Bayes. Đó là một đồ thị
có hớng, không chu trình. Các nút biểu diễn thuộc tính và trọng số của liên kết giữa hai
nút biểu diễn độ mạnh của sự phụ thuộc giữa các nút đó.
2.6 Mô hình hoá nhân quả (Causation Modeling)
Nhiệm vụ này liên quan đến việc phát hiện mối quan hệ nhân quả trong các thuộc tính.
Các luật nhân quả cũng là các luật nếu-thì giống với luật phụ thuộc, nhng luật nhân
quả mạnh hơn luật phụ thuộc. Luật phụ thuộc đơn giản chỉ ra một mối tơng hỗ giữa tiền
đề và kết luận của luật, nhng không có ý nghĩa nhân quả trong quan hệ này. Do vậy, cả
tiền đề và kết luận có thể quan hệ do ảnh hởng của một biến thứ ba, tức là một thuộc
tính hoặc có mặt ở trong tiền đề hoặc trong kết luận. Luật nhân quả không chỉ chỉ ra
mối tơng quan giữa tiền đề và kết luận mà còn cho biết rằng tiền đề thực sự gây ra kết
luận và mối quan hệ giữa hai thành phần này là trực tiếp. Tập các mối quan hệ nhân quả
có thể đợc biểu diễn bởi đồ thị nhân quả.
Thuật toán phát hiện luật nhân quả CAUDISCO áp dụng các phép kiểm tra sự độc lập
thống kê của từng cặp thuộc tính. Sau đó đối với các thuộc tính phụ thuộc lẫn nhau,

ra trong kết luận.
2.9 Hồi qui (Regression)
Về khái niệm, nhiệm vụ hồi qui tơng tự nh phân lớp. Điểm khác nhau chính là ở chỗ
thuộc tính để dự báo là liên tục chứ không phải rời rạc. Việc dự báo các giá trị số thờng
đợc làm bởi các phơng pháp thống kê cổ điển, chẳng hạn nh hồi qui tuyến tính. Tuy
nhiên, các phơng pháp mô hình hoá cũng đợc sử dụng chẳng hạn cây quyết định trong
đó nút lá là một mô hình tuyến tính phát sinh từ các giỏ học thuộc về nút đó. Thuật toán
liên quan đến cây quyết định sẽ phát sinh tập các lớp giả (pseudo-class) có giá trị thuộc
tính đích tơng tự nhau, sau đó sử dụng phơng pháp qui nạp luật thay thế các lớp giả
trong luật qui nạp bằng tổ hợp các giá trị của thuộc tính lớp cho các giỏ theo luật.
2.10 Tổng hợp (Sumarization)
Nhiệm vụ tổng hợp chính là sản sinh ra các mô tả đặc trng cho một lớp. Mô tả này là
một kiểu tổng hợp, tóm tắt mô tả các đặc tính có chung của tất cả (hoặc hầu hết) các giỏ
thuộc một lớp. Các mô tả đặc trng thể hiện dới dạng luật có dạng sau: Nếu một giỏ
thuộc về lớp đã chỉ trong tiền đề thì giỏ có tất cả các thuộc tính đã nêu trong kết luận.
Chú ý là luật này có những đặc trng khác biệt so với luật phân lớp. Luật phát hiện đặc
trng cho một lớp chỉ sản sinh khi các giỏ đã thuộc về lớp đó.
2.11 So sánh các nhiệm vụ phát hiện tri thức
Điểm tơng tự và sự khác biệt giữa các nhiệm vụ phát hiện tri thức đợc tóm tắt trong
Bảng 2.1. Cột đầu tiên chỉ ra nhiệm vụ phát hiện tri thức. Cột thứ 2 chỉ ra kiểu tri thức
đợc phát hiện có thể là hớng Hệ quản trị cơ sở dữ liệu (HQT CSDL) nh luật SQO hoặc
phụ thuộc CSDL, hay mục đích chung (các nhiệm vụ phát hiện khác). Tri thức hớng
HQT CSDL thờng dùng trong thiết kế và giao dịch của một CSDL. Tuy nhiên, tri thức
hớng HQT CSDL cũng có thể dùng cho việc kiểm tra các luật tối u truy vấn ngữ nghĩa
để cải thiện việc hiểu lĩnh vực ứng dụng. Trong khi tri thức theo kiểu mục đích chung có
thể sử dụng mục đích tuỳ thuộc nhu cầu của ngời dùng trong nghĩa mở. Tri thức theo
mục đích chung có thể sử dụng hiệu quả trong HQT CSDL. Tuy vậy, điểm khác biệt
quan trọng là tri thức hớng HQT CSDL yêu cầu độ chính xác cao hơn so với tri thức
theo mục đích chung.
Bảng 2.1: So sánh các nhiệm vụ phát hiện tri thức trong CSDL

Độ chính xác
tuyệt đối
Phát hiện sự
sai khác
Mục đích
chung
Xác định trội Không có học Ngời dùng xác
định ý nghĩa
Phát hiện liên
kết
Mục đích
chung
Dự báo, Xác
định trội
nhiều-nhiều
(học)
Ngời dùng xác
định độ chính
xác và tần suất
Sự phụ thuộc Mục đích
chung
Dự báo, mô tả nhiều-nhiều
(không có
học)
Độ chính xác
cao
Nhân quả Mục đích
chung
Dự báo, mô tả nhiều-nhiều
(không có

tinh lọc từ cột thứ hai. Mục đích chính của tri thức hớng CSDL hoàn toàn cụ thể: tối u
câu truy vấn (nh trờng hợp luật SQO) và thiết kế và duy trì CSDL (nh trong trờng hợp sự
phụ thuộc CSDL). Tri thức kiểu này thờng đợc dùng cho một sự kết hợp các mục đích
dự báo, mô tả và xác định trội.
Dự báo liên quan đến xác định giá trị của các thuộc tính trên cơ sở các giá trị của các
thuộc tính khác. Kỹ thuật đặc trng là Phân lớp và Hồi qui. Tuy nhiên, dự báo cũng dựa
trên quan hệ Nhân quả và mô hình hoá sự phụ thuộc cũng nh phát hiện luật liên kết.
Mô tả liên quan đến việc phát hiện tri thức trừu tợng nhng hiểu đợc bởi ngời dùng. Mô
tả thờng gắn với tổng hợp, thông tin gộp. Do vậy, mô tả là mục tiêu chính của nhiệm vụ
Tổng hợp và Phân cụm. Đối với cả Tổng hợp và Phân cụm, việc mô tả các thuộc tính
chung nhau bởi các tập hợp dữ liệu đợc quan tâm. Hơn nữa, việc mô tả cũng khá quan
trọng trong các nhiệm vụ xác định phụ thuộc và quan hệ Nhân quả. Chú ý là mục tiêu
chính của phát hiện tri thức phụ thuộc vào dạng mà tri thức biểu diễn. Chẳng hạn, mạng
nhân quả thích hợp hơn cho mục tiêu mô tả hơn là Luật về sự phụ thuộc.
Trang 14
Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
Ta sử dụng thuật ngữ xác định trội (highlighting) để xác định các mẫu, những qui luật
hay những bất thờng đặc biệt trong dữ liệu. Tính chất cơ bản của các mẫu đặc biệt này
là chúng có một giá trị bất ngờ hoặc một tần suất tơng đối không mong đợi. Hơn nữa,
khác với tri thức đợc phát hiện cho các mục đích mô tả, các mẫu này không cần thiêt
thể hiện dới dạng trừu tợng. Ví dụ điển hình là thăm dò sự sai khác với thông tin đợc
phát hiện chỉ đơn giản là danh sách các điểm dữ liệu lệch ra ngoài. Nhiệm vụ phát hiện
luật liên kết có thể đợc xem là một dạng xác định trội, bởi lẽ một trong các đòi hỏi rõ
ràng của luật liên kết là tần suất tơng đối tối thiểu (giá trị support) trong dữ liệu.
Cột thứ t chỉ ra loại dự báo liên quan đến từng nhiệm vụ phát hiện tri thức. Mặc dù các
nhiệm vụ SQO và Sự phụ thuộc CSDL phát hiện tri thức hớng CSDL và theo mục tiêu cụ
thể, nhng cũng có các nhiệm vụ dự báo liên quan đến kiểu này. Nói chung, các nhiệm
vụ SQO, Sự phụ thuộc CSDL, Liên kết, Nhân quả, Sự phụ thuộc và Phân cụm có kiểu dự
báo nhiều-nhiều trong đó giá trị của một vài thuộc tính có thể dùng để dự báo giá trị của
các thuộc tính khác. Một cách nhìn khác về quan hệ nhiều-nhiều là xem xét các nhiệm

Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
Chơng 3. Các kỹ thuật Khai phá dữ liệu
Khai phá dữ liệu là bớc tiếp theo của quá trình phát hiện tri thức và là giai đoạn quan
trọng nhất. Chúng ta sẽ khảo sát một số thuật toán nhận dạng và học máy một cách tổng
quan và sau đó sẽ đi sâu vào một số phần ở các chơng sau.
Vì tri thức có nhiều dạng thể hiện khác nhau nên việc phát hiện tri thức cũng đa dạng và
cần nhiều kỹ thuật và phơng pháp để sử dụng. Chúng ta sẽ quan tâm đến các kỹ thuật
sau:
Các công cụ truy vấn, các kỹ thuật thống kê, hiển thị
Công cụ phân tích trực tuyến (OLAP)
Học dựa trên trờng hợp (k ngời láng giềng gần nhất)
Cây quyết định
Luật kết hợp
Mạng nơron
Thuật toán di truyền
3.1 Các công cụ truy vấn, các kỹ thuật thống kê, hiển thị
Hiện nay, phần lớn các hệ thống CSDL điều hành, CSDL báo cáo và kho dữ liệu vẫn
dùng chủ yếu những công cụ truy vấn SQL cho việc khai thác dữ liệu đầu ra. Với các
công cụ truy vấn này, nguời dùng sẽ đạt đợc các thông tin chính xác. Với một số công
cụ phân tích SQL tốt, ngời lãnh đạo, nhà phân tích, ngời quản lý có thể kết xuất dữ liệu
ra theo cách tuỳ biến (ad-hoc), đáp ứng yêu cầu hỗ trợ quyết định đến khoảng 80 %.
Phần còn lại, ớc tính 20%, là các thông tin tiềm ẩn, đòi hỏi phải có kỹ thuật cao hơn và
thờng dùng cho các tổ chức lớn có kho dữ liệu lớn. 20% có thể là thông tin vô cùng
quan trọng quyết định sự thành công trong môi trờng cạnh tranh.
Chúng ta sẽ sử dụng một ví dụ minh hoạ trong cả chơng để biểu diễn quá trình phát
hiện tri thức trong CSDL. Một nhà sách có CSDL về các khách hàng mua sách theo các
chủ đề về thiếu nhi, thể thao, âm nhạc và kỹ thuật. Mục tiêu của quá trình khai phá dữ
liệu là tìm ra các nhóm khách hàng có đặc tính chung để thực hiện các hoạt động tiếp
thị. Do đó, chúng ta quan tâm đến các câu hỏi chẳng hạn nh Hồ sơ điển hình của một
độc giả về sách thiếu nhi là gì? hoặc Có mối tơng quan nào giữa sự quan tâm đến

khai thác trực tiếp. Ngoài ra, có các công cụ nhiều chiều đợc gọi là công cụ phân tích
trực tuyến kiểu quan hệ (ROLAP) bao gồm một cơ cấu đa chiều có kết nối đến dữ liệu
thực sự lu dới dạng mô hình quan hệ. Đây là mô hình lai cho phép lu dữ liệu hai chiều
và phân tích đa chiều.
Điểm khác biệt giữa các công cụ phân tích trực tuyến và khai phá dữ liệu là công cụ
phân tích trực tuyến không học, chúng không tạo ra tri thức mới mà chỉ thể hiện và tổng
hợp các dữ liệu chính xác ở nhiều góc độ nhìn khác nhau. Các thuật toán khai phá dữ
liệu thông minh hơn và chúng không cần dạng lu trữ đặc biệt nào mà thờng dựa ngay
vào các CSDL quan hệ.
3.3 K ng ời láng giềng gần nhất
Khi chúng ta biểu diễn bản ghi dữ liệu nh một phần tử trong không gian nhiều chiều, thì
chúng ta có thể xác định khái niệm láng giềng. Giả thiết chúng ta muốn dự báo hành vi
của một tập khách hàng với một CSDL mô tả về các khách hàng đó. Giả định cơ bản đòi
hỏi để làm dự báo nh vậy là khách hàng cùng một kiểu sẽ có cùng một hành động.
Trong hình dung về không gian dữ liệu, một kiểu không gì khác hơn là một vùng dữ
liệu. Nói cách khác, bản ghi có cùng kiểu sẽ phân bố ở gần nhau trong không gian dữ
liệu và chúng sẽ là hàng xóm của nhau. Dựa trên ý tởng này, chúng ta có thể phát
triển một thuật toán học rất đơn giản nhng hiệu quả k ngời láng giềng gần nhất. Luận
đề của k ngời láng giềng gần nhất là làm nh láng giềng làm. Nếu chúng ta muốn dự
báo hành vi của một cá nhân nào đó, chúng ta bắt đầu nhìn vào hành vi của chẳng hạn
10 cá nhân gần với anh ta nhất trong không gian dữ liệu. Và giá trị trung bình của các
hành vi của các hàng xóm này sẽ là dự báo cho hành vi của anh ta. Số k trong k láng
giềng gần nhất chỉ số láng giềng đợc xem xét.
K láng giềng gần nhất đơn giản cha phải là một kỹ thuật học, mà gần nh là một phơng
pháp tìm kiếm. Nếu nó dự báo cho từng phần tử trong tập dữ liệu có n bản ghi thì chíng
ta phải so sánh từng bản ghi với tất cả các bản ghi còn lại và nh thế độ phức tạp sẽ là
bậc 2
n
và không đáp ứng cho tập dữ liệu lớn. Nếu chúng ta muốn phân tích k láng giềng
Trang 17

nhờ cây quyết định đợc trình bày kỹ ở trong chơng 5 và chơng 8.
3.5 Luật kết hợp
Trong thực tế, những chuyên gia về kinh doanh và tiếp thị rất thích các luật đại thể nh:
90% phụ nữ có xe máy đỏ và đeo đồng hồ Thuỵ sỹ thì dùng nớc hoa hiệu Chanel.
Những thông tin nh vậy rất hữu ích cho việc định hớng cho các hoạt động tiếp thị và
kinh doanh. Vấn đề là liệu có thể tìm đợc các kiểu luật nh vậy nhờ các công cụ khai phá
dữ liệu hay không. Câu trả lời là có và trong lĩnh vực khai phá dữ liệu, đó chính là
nhiệm vụ phát hiện luật kêt hợp. Giả sử ta có một CSDL về các khách hàng với các
thông tin nh màu và kiểu xe máy, kiểu đồng hồ yêu thích và một số sản phẩm mà họ
muốn mua, lúc đó ta có thể phát hiện các luật tơng tự nh trên.
Việc phát triển một thuật toán phát hiện luật này trong một CSDL lớn không khó. Tuy
nhiên, vấn đề là ở chỗ có thể có rất nhiều luật kiểu này và ta chỉ biết một tập hợp nhỏ dữ
liệu trong CSDL lớn. Chẳng hạn, chỉ có một số không nhiều phụ nữ có xe máy đỏ và
đeo đồng hồ Thuỵ sỹ. Số lợng các luật kết hợp trong một CSDL lớn gần nh vô hạn.
Thuật toán sẽ không thể phát hiện hết các luật và không phân biệt đợc luật nào là thông
tin thực sự có giá trị và thú vị.
Trang 18
Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
Vậy luật kết hợp nào là thực sự có giá trị và thú vị? Chẳng hạn ta có luật: Âm nhạc, Thể
thao => Thiếu nhi, nghĩa là những ngời mua sách Âm nhạc và Thể thao thì cũng mua
sách về Thiếu nhi. Lúc đó ta quan tâm đến số lợng trờng hợp khách hàng thoả mãn luật
này hay độ hỗ trợ (support) cho luật này. Giá trị support cho luật chính là: phần trăm số
bản ghi có cả Âm nhạc, Thể thao, Thiếu nhi hay tất cả những ngời thích cả 3 loại sách.
Tuy nhiên, giá trị support là không đủ. Có thể có trờng hợp ta có một nhóm tơng đối
những ngời đọc cả ba loại sách nhng lại có một nhóm lớn hơn nhiều những ngời đọc cả
sách âm nhạc, thể thao nhng không thích sách thiếu nhi. Trong trờng hợp này tính kết
hợp rất yếu, mặc dù support tơng đối cao. Nh vậy, chúng ta cần thêm một độ đo phụ. Đó
là độ tin cậy (confidence). Trong trờng hợp này, confidence chính là phần trăm các bản
ghi có sách thiếu nhi trong số các bản ghi có sách âm nhạc và Thể thao.
Thực tế, luật kết hợp chỉ hữu ích trong khai phá dữ liệu nếu chúng ta đã có một ý tởng

Perceptrons
Mạng lan truyền ngợc (Back propagation networks)
Mạng tự tổ chức Kohonen (Kohonen Self-organized Map)
Perceptron là dạng tổ chức sơ khai của mạng nơron lần đầu tiên đa ra bởi Frank
Rosenblatt năm 1958. Một perceptron là một mạng đơn giản gồm hai lớp với các đơn
vị đầu vào gọi là điểm thu nhận ảnh, các đơn vị trung gian gọi là các điểm kết hợp và
Trang 19
Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
các điểm ra gọi là điểm đáp ứng. Perceptron có thể học các luật đơn giản và nh vậy có
thể đợc dùng để thực hiện các nhiệm vụ phân lớp đơn giản. Tuy nhiên, ngời ta đã chỉ ra
rằng lớp các bài toán có thể giải đợc bằng một máy có kiến trúc perceptron rất hạn chế.
Trong hai chục năm trở lại đây, mạng nơron nhân tạo đã đợc nghiên cứu nhiều với các
kiến trúc phức tạp hơn có thể giải quyết nhiều bài toán phức tạp hơn. Một trong các phát
triển chính đó là các lớp ẩn và từ đó dẫn đến khái niệm mạng lan truyền ngợc.
Mạng lan truyền ngợc không chỉ có các nút đầu vào và đầu ra mà còn có một tập các
lớp trung gian với các nút ẩn. Trong giai đoạn ban đầu, một mạng lan truyền ngợc có
các trọng số ngẫu nhiên cho các khớp thần kinh (hay liên kết) của nó. Khi chúng ta dạy
mạng học, chúng ta cho một tập các dữ liệu học chạy qua mạng. Với mỗi lần học, giá trị
đầu ra thực sự của mạng lại đợc so sánh với giá trị ra đòi hỏi thực tế. Nếu có sự khác
nhau giữa câu trả lời của mạng và câu trả lời thực tế thì các trọng số của các nút và khớp
thần kinh mạng đợc điều chỉnh. Quá trình này lặp đi lặp lại cho đến khi kết quả tính
toán của mạng đạt đợc độ chính xác cần thiết. Khi cấu trúc của mạng đã xác định sau
quá trình học, có thể dùng mạng để phân lớp các đối tợng cha biết.
Mạng lan truyền ngợc đã có sự cải thiện hơn về khả năng so với kiến trúc perceptron.
Tuy nhiên, chúng cũng có các bất lợi. Mạng nơron lan truyền ngợc cần một tập dữ liệu
học rất lớn. Một vấn đề khác là mặc dù nói rằng mạng nơron học nhng chúng không
cho chúng ta một hình dung rõ ràng về chúng đã học cái gì, mà chỉ là những hộp đen, đ-
a ra câu trả lời nhng không cung cấp cho chúng ta một suy luận làm thế nào để đa ra
câu trả lời đó.
Kohonen đã đa ra một phiên bản khác hoàn toàn về mạng nơron mà hiện nay đợc gọi là

quan đến rất nhiều các cơ thể sống qua nhiều thời gian và hoạt động của sinh vật sống.
Một bất lợi khác là việc tiến hoá loài sinh vật phụ thuộc vào các cơ hội. Các loài sinh
vật tiến hoá nhờ vào sự đột biến ngẫu nhiên của gen, nhng cơ hội mà một đột biến nh
vậy thực sự dẫn tới cái gì đó có ý nghĩa thật hiếm hoi.
Trang 21
Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
Chơng 4. kho dữ liệu
Kho dữ liệu (DataWarehouse) là một hớng công nghệ áp dụng cho các ứng dụng công
nghệ tin học trong các doanh nghiệp và tổ chức. Thuật ngữ này gợi nên hình ảnh của
nhà băng dữ liệu rộng lớn đợc bắt nguồn từ các hệ thống trên khắp thế giới, với đông
đảo các nhà phân tích của công ty khai thác những thông tin quí giá giúp công ty của họ
thu đợc nhiều lợi nhuận hơn.
Một cách cơ bản, kho dữ liệu cung cấp dữ liệu lịch sử cho các ứng dụng hỗ trợ quyết
định. Những ứng dụng nh vậy bao gồm báo cáo, xử lý phân tích trực tuyến (Online
Analysis Procesing - OLAP), hệ thống thông tin điều hành (Executive Information
System - EIS) và khai thác dữ liệu.
Kho dữ liệu chứa các thông tin tập trung hoá và thống nhất. Thống nhất ở đây nghĩa là
đã đợc làm sạch, hợp nhất và thiết kế lại, có thể ít nhiều phức tạp tuỳ thuộc vào việc có
bao nhiêu hệ thống cung cấp thông tin cho một kho và khác nhau trong việc xử lý cùng
một thông tin nh thế nào.
- Kho dữ liệu khác với cơ sở dữ liệu tác nghiệp hoặc hệ thống xử lý giao tác trực
tuyến (OLTP) ở mục đích và thiết kế của chúng. Một hệ thống xử lý giao tác trực
tuyến đợc thiết kế và tối u với dữ liệu đa vào và các cập nhật. Trong khi kho dữ
liệu đợc tối u hoá cho mục đích báo cáo và khôi phục dữ liệu và thờng là một hệ
thống chỉ - đọc. Một hệ thống xử lý giao tác trực tuyến chứa các dữ liệu cần thiết
để điều hành kinh doanh hàng ngày, nhng kho dữ liệu chứa các dữ liệu đợc sử
dụng để phân tích kinh doanh. Dữ liệu trong một hệ thống xử lý giao tác trực
tuyến đợc cập nhật thờng xuyên và có độ linh hoạt cao với những phần tử dữ liệu
có thể cha hoàn chỉnh hoặc không biết ở thời điểm vào. Kho dữ liệu chứa những
dữ liệu lu trữ, ổn định, các lỗi giao tác đã đợc điều chỉnh. Do mục đích của chúng

nghiệp
nghiệp
Kho
Kho
Dữ
Dữ
liệu
liệu
Đ. T.T. Hà
Đ. T.T. Hà
Đỗ
Đỗ
Thanh
Thanh
Hà
Hà
Đỗ
Đỗ
Thị Thanh
Thị Thanh
Hà
Hà
Hà, Đỗ
Hà, Đỗ
Thanh
Thanh
Đỗ
Đỗ
Thị Thanh
Thị Thanh

CSDL A
CSDL B
CSDL C
CSDL D
Hình 4.1 Đa dữ liệu vào kho dữ liệu một cách thống nhất
-Không bị phá huỷ: Không nh trong hệ tác nghiệp, dữ liệu trong kho dữ liệu không đợc
sửa đổi. Định nghĩa này chỉ mang tính nguyên tắc. Thực tế có rất nhiều kho dữ liệu cho
phép thay đổi dữ liệu trong kho. Tuy nhiên, việc này dẫn đến các vấn đề nghiêm trọng
khác, sẽ đợc giải thích sau đây.
Trang 23
Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
Cập nhật
Cập nhật
Xoá
Xoá
Th
Th
êm
êm
Tra cứu
Tra cứu
Truy vấn
Truy vấn
Các
Các
hệ thống
hệ thống
tác
tác
nghiệp

-Một trong những kiểu đơn giản nhất của kho dữ liệu, là kho dữ liệu điều hành
(Operational Data System - ODS). Đó là một cơ sở dữ liệu nghiệp vụ đã đợc sao chép và
điều chỉnh lỗi. Kho dữ liệu điều hành thờng đợc sử dụng chính để hình thành những báo
cáo điều hành định kỳ và thực hiện các giao tác cụ thể cho các phân tích mang tính tổng
hợp.
- Tuỳ thuộc vào yêu cầu tổng hợp của một tổ chức hoặc công ty, một kho dữ liệu
điều hành có thể đợc cập nhật hàng tháng, hàng tuần, hay thờng xuyên hơn. Lợi
ích chủ yếu là tăng cờng việc thực thi trong hệ thống tác nghiệp, do các chức năng
Trang 24
Luận văn tốt nghiệp cao học ngành CNTT, ĐHBKHN
báo cáo và truy vấn đợc tải từ hệ thống xử lý xử lý giao tác trực tuyến sang kho dữ
liệu điều hành.
-
Kho dữ liệu
(xí nghiệp)
Chợ dữ liệu
(phòng ban)
công cụ
truy vấn,
OLAP
ứng dụng
Dữ liệu tài sản (legacy)
Dữ liệu
tác nghiệp
Kho dữ liệu
(xí nghiệp)
Chợ dữ liệu
(phòng ban)
Khai phá
Dữ liệu