Đ Ạ I H Ọ C Q U Ố C G IA H À N Ộ I
K H O A C Ô N G N G H Ê
NGUYỄN THỊ THOA
VẤN ĐỂ PHÁT HIỆN LUẬT KẾT HỢP
• • •
TRONG Cơ SỞ Dữ LIỆU VÀ
K H A I PHÁ Dữ LIỆU
Chuyên ngành: Công nghệ thông tin
M ã số: 1.01.10
LUẬN VĂN THẠC s ĩ
NGƯỜI HƯỚNG DẨN KHOA HỌC
PGS TS ĐOÀN VĂN BAN
Hà Nội - 2003
r o Ặ n i ộ c " g u c x : g ;-\ h ả 'N Ọ I ỉ
I TRliNGTÁM THCHGTIN.Tilự VIỆNí
N" i - .L i U .U ?
1
Danh inục bảng biểu, hình vẽ 3
Các ký hiệu và từ viết tắt 4
VIỞ đ ầu 5
Chương 1. Tổng quan về khai phá dữ liệu 7
1.1. Khai phá dữ liệu 7
1.1.1. Định nghĩa 7
1.1.2. Các ứng dụng của khai phá dữ liệu 7
1.2. Các giai đoạn chính của quá trình phát hiện tri thức

8
1.3. Các bài toán trong khải phá dữ liệu 10
1.3.1. Phát hiện sự phụ thuộc dữ liệu 11
1.3.2. Phát hiện sự biến đổi và độ lệch 11
1.3.3. Phát hiện luật kết hợp 12

30
2.3.2. Ví dụ minh hoạ 32
2.3.3. Thuật toán phát hiện tập chỉ báo và các luật kết hợp m ờ

34
Chương 3. Một sô thuật toán phát hiện luật kết hợp

37
3.1. Thuật toán AIS 37
3.2. Thuật toán SETM

.

.

39
3.3. Thuật toán Apriori 42
3.4. Thuật toán AprioriTid 44
3.5. Thuật toán phân hoạch 46
3.6. Thuật toán CHARM
51
Chương 4. áp dung kỹ thuật khai phá dữ liệu vào bài toán bảo hiểm
.

58
5.1. Bài toán 58
5.2. Cài đặt chương trình 60
5.3. Kết quả chạy chương trình 61
5.4. Nhận xét kết quả


Bảng 3.11: Thuật toán phân hoạch 49
Bảng 3.12: Thủ tục gen_large_itemsets 49
Bảng 3.13: Thủ tục prune 50
Bảng 3.14: Thủ tục gen_final_count 51
Bảng 3.15: Thuật toán CHARM 54
Hình 3.1: CH ARM sắp xếp Iheo thứ tự từ điển 55
Hình 3.2: CHARM sắp xếp theo độ hỗ trợ tăng dần 56
Hình 4.1: Sơ đồ quan hệ 59
Hình 4.2: Cửa sổ giao diện chính của chương trình KDD on Insurance

72
CÂC KŸ HIÊU VÀ TÜ VIÉT TÂT
Kÿ hiêu,
tir viét tât
Tê'ng Anh
Tien g Viêt
conf confidence Dô tin cây
CSDL Database Ca sa du lieu
minconf
minimum confidence Dô tin cây toi thiëu
minsup
minimum support Dô hô tra toi thiëu
sup support
Dô hô tra
TID
Transacstion Identification Dinh danh giao dich
k-itemset
k-itemset Tâp gôm k mue
U
Tâp câc k-itemset pho bien.

Mục đích của luận văn là nghiên cứu, tổng hợp các kiến thức về khai phá dữ
liệu; tìm hiểu một số thuật toán khai phá luật kết hợp trong CSDL lớn và áp dụng
vào một bài toán trong thực tế.
M Ở Đ ẦU
6
Chương 1, trình bày tổng quát về khai phá dữ liệu, cụ thể là định nghĩa khai
phá dữ liệu và các ứng dụng của nó, các giai đoạn của quá trình phát hiện tri thức,
các bài toán trong khai phá dữ liệu. Cuối chương 1, luận văn trình bày các kỹ thuật
khai phá dữ liệu phổ biến hiện nay.
Chương 2, phát biểu bài toán phát hiện luật kết hợp, tiếp đến tìm hiểu hệ
thông tin nhị phân và hệ thông tin mờ cùng thuật toán phát hiện luật kết hợp trên hệ
thông tin nhị phân và thuật toán phát hiện luật kết hợp trên hệ thông tin mờ.
Chương 3, giới thiệu một số thuật toán được sử dụng để khai phá dữ liệu
như: AIS, SETM, Apriori, AprioriTid, phân hoạch, CHARM.
Chương 4, đề xuất áp dụng khai phá dữ liệu vào bài toán bảo hiểm và viết
chương trình thử nghiệm.
Cuối cùng là kết luận những kết quả đạt được của luận văn và hướng phát
triển trong tương lai.
Luận văn gồm các nội dung chính sau :
7
CHƯƠNG 1. TỔNG QUAN VỂ KHAI PHÁ DỮ LIỆU
1.1. Khai phá dữ liệu
11.1. Định nghĩa
Phát hiện tri thức trong CSDL là quá trình kết xuất tri thức từ dữ liệu. Khai
piá dữ liệu được dùng để mô tả giai đoạn phát hiện tri thức trong CSDL. Khai phá
dĩ liệu nhằm kết xuất ra những tri thức tiềm ẩn từ dữ liệu để giúp cho việc dự báo
tiong kinh doanh, .v.v. Khai.phá dữ liệu làm giảm chi phí về thời gian so với các
piương pháp truyền thống trước kia (bằng thống kê) rất mất thời gian.
Sau đây là một số định nghĩa mang tính mô tả mà Friedman đã lựa chọn từ
cíc bài giảng về khai phá dữ liệu [

thiết kế sản phẩm, chẳng hạn.như ỏtò.
- Chăm sóc sức klioẻ: các ứng dụng gồm phân tích hiệu qủa điều trị chắc
chắn; tối ưu quá thời gian điều trị (tối ưu thời gian nằm viện), dữ liệu liên quan đến
sức khoẻ bệnh nhân với chứng nhận của bác sỹ; và phân tích tác động của ma tuý,
•V.V.
- Tin-sinh học : Phát hiện các đoạn lặp trong trình tự ADN và protein,.v.v.
- Phân tích dữ liệu và hỗ trợ quyết địnli
- Giáo dục
- Phân loại vă n bản
- Khai phá Web
- .v.v.
1.2. Các giai đoạn chính của quá trình phát hiện tri thức
Trong mục này, chúng ta khảo sát quá trình, phân tích các giai đoạn phát
hiện tri thức. Có 5 giai đoạn chính trong quá trình phát hiện tri thức [4,7,8,18]:
- Trích chọn dữ liệu
- Tiền xử lý dữ liệu
9
- Biến đổi dữ liệu
- Khai phá dữ liệu
- Biểu diẽn và đánh giá tri thức
Trans
formation
Data
Target
Data
Preprocessed
Data
^ Data
Mining
Transformed

chuyển dữ liệu nhằm mục đích khai phá. Các chương trình có thể thực hiện các
công việc theo định kỳ để làm tươi dữ liệu cho phân tích.
Khai phá dữ liệu (data mining): bước khai phá dữ liệu bắt đầu khi hệ
thống dữ liệu được xây dựng và biến đổi. Các bước trước là công việc của người
thiết kế và lập trình. Bắt đầu từ bước này là công việc của các nhà phân tích và ra
quyết định. Đây là bước áp dụng các kỹ thuật khai phá để khai phá, trích chọn được
các mẫu thông tin, những mối quan hệ đặc biệt trong dữ liệu. Bước này được xem
là quan trọng và tốn nhiều thời gian nhất của quá trình khai phá tri thức.
Biểu diễn và đánh giá tri thức (knowlede representation & evolution):
Các kết quả khai phá dữ liệu cùng với các kết quả từ các công cụ phân tích khác có
thể được tổng hợp dưới dạng các báo cáo cho các mục đích hỗ trợ quyết định khác
nhau. Các mẫu thông tin và mối quan hệ trong dữ liệu khai phá được ở bước trên
được chuyển thành dạng gần gũi với người sử dụng như biểu đồ, cây, bảng biểu,
luật, .v.v. Đồng thời đánh giá những tri thức khám phá được theo những tiêu chí
nhất định.
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ó 5 giai đoạn, nhưng 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 5 bước mà theo chu trình liên tục kiểu xoáy ố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à các giai
đoạn sau dựa trên các kết quả đã đạt được của giai đoạn trước.
1.3. Các bài toán trong khai phá dữ liệu
Hai mục tiêu chính của khai phá dữ liệu trong thực tế cần đạt được là dự
đoán và mô tả. Dự đoán đòi hỏi sử dụng một số biến hoặc trường trong cơ sở dữ
liệu để dự đoán về các biến khác cần quan tâm mà chưa biết hoặc sẽ có giá trị trong
tương lai. Mô tả tập trung vào việc tìm ra các mẫu được biểu diễn bởi người mô tả
11
dữ liệu. Tầm quan trọng trong mối quan hệ dự báo và mô tả đối với các thuật toán
khai phá dữ liệu cụ thể riêng có thể được quan tâm khác nhau.
Do sự phát triển mạnh mẽ của các loại hệ thống phát hiện tri thức trong
CSDL theo yêu cầu nhằm đáp ứng những đòi hỏi trong nhiều lĩnh vực ứng dụng

thông qua công nghệ, ví dụ mã vạch trong các hoạt động kinh doanh siêu thị.
Cho một tập các giao dịch, trong đó mỗi giao dịch là một tập các mục, một
luật kết hợp là một biểu thức X => Y, trong đó X và Y là tập các mục. Phần trăm số
giao dịch trong CSDL mà chứa các mục trong X thì cũng chứa các mục trong Y
được gọi là độ tin cậy của luật. Độ hỗ trợ của luật X => Y là phần trăm số giao dịch
chứa cả X và Y. Bài toán phát hiện luật kết hợp là tìm tất cả các luật thoả mãn độ
hỗ trợ tối thiểu và độ tin cậy tối thiểu được xác định bởi người sử dụng [14, 12, 3,
4, 7].
1.3.4. Mô hình hoá sự phụ thuộc
Công việc này bao gồm việc tìm ra một mô hình mô tả sự phụ thuộc có ý
nghĩa giữa các biến, phát hiện sự phụ thuộc giữa các thuộc tính. Mô hình phụ thuộc
bao gồm hai mức [18, 4]: mức cấu trúc của mô hình mô tả (thường dưới dạng đồ
thị) trong đó các biến phụ thuộc bộ phận vào các biến khác, mức định lượng của
mô hình mô tả mức độ phụ thuộc. Những pnụ thuộc này thường được hiển 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 logic 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. Hơn nữa, hệ thống có thể 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ức độ phụ thuộc giữa các nút đó.
13
1.3.5. Phân lớp
Phân lớp là cách xác định ánh xạ ( hay phân loại ) mục dữ liệu vào một
trong một số lớp đã biết trước [18]. Mục tiêu của thuật toán phân lớp là tìm mối
quan hệ nào đó giữa các thuộc tính dự báo và thuộc tính phân lớp [4]. Như thế quá
trình phân lớp có thể sử dụng mối quan hệ này để dự báo cho các mục mới. Trong
trường hợp các kiến thức được phát hiện biểu diễn dưới dạng các luật, các luật được

truyền, nhận dạng mẫu, phân tích dữ liệu không gian, xử lý tín hiệu, lý thuyết đồ
thị, xác suất, và lập trình logic quy nạp, cây quyết định, .V .V ., có thể được phỏng
theo và tích hợp vào các hệ thống lai để khai phá dữ liệu. Các phương pháp phân
tích một tập dữ liệu lớn đã lừng được phát triển theo thống kê trong nhiều nám
nghiên cứu, tuy nhiên với dữ liệu lưu trữ rất lớn trong CSDL muốn khai phá thì các
phương pháp này đối diện với các thử thách về mặt hiệu quả và quy mô.
Trong mục nay, chúng tôi chỉ xem xét một sô' kỹ thuật quan trọng được
dùng trong khai phá dữ liệu: các công cụ truy vấn, k-láng giềng gần, cây quyết
định, các luật kết hợp.
1.4.1. Các công cụ truy vấn
Bước đầu tiên trong khai phá một tập dữ liệu luôn phải phân tích dữ liệu thô
sử dụng các công cụ truy vấn truyền thống.
Ví dụ, bằng việc áp dụng các ngôn ngữ truy vấn có cấu trúc đơn giản, như
SQL, có thể thu được tri thức có ích trong CSDL. Nó cho phép nhìn cùng một
thông tin theo nhiều chiều, có nghĩa là các phép toán của đại số quan hệ mà cho
phép một người dùng lựa chọn từ các bảng (các dòng và các cột của dữ liệu) hoặc
nối thông tin liên quan từ các bảng dựa trên các trường chung.
SQL chỉ có thể phát hiện dữ liệu không sâu, nhưng dễ sử dụng. SQL không
thực sự thuộc các kỹ thuật khai phá dữ liệu. Tuy nhiên, hầu hết các thông tin quan
tâm (gần 80%) có thể được lấy từ CSDL sử dụng SQL. Các kỹ thuật tinh vi hơn cần
15
cho việc khai phá các thông tin quan tâm còn lại (gần
2 0
%), nó gồm các tri thức ẩn
có thể là của các chiến lược quan trọng đối với các tổ chức lớn [7, 4].
1.4.2. K-Iáng giềng gần
Sự miêu tả của các bản ghi trong tập dữ liệu khi trỏ vào không gian nhiều
chiều là rất có ích đối với việc phân tích dữ liệu [7]. Việc dùng các miêu tả này, nội
dung của vùng lân cận có thể được định nghĩa, trong đó các bản ghi gần nhau trong
không gian được xem xét thuộc về lân cận (hàng xóm) của nhau. Khái niệm này

hoạch CSDL thành hai lớp mẫu: lớp các mẫu khẳng định bao gồm các bản ghi
trong đó thuộc tính tạp chí ô tô là đúng; và lớp các mẫu phủ định, bao gồm các bản
ghi trong đó thuộc tính ô tô là sai.
Giả sử rằng thuộc tính tạp chí thể thao hiện chiếm 90% các mẫu có giá trị
đúng (vì vậy,
1 0
% mẫu còn lại có giá trị sai), trong khi tất cả các thuộc tính khác
hiện chỉ chiếm 50% đến 60% các mẫu có giá trị đúng. Thì tạp chí thể thao là thuộc
tính quan trọng nhất.
Thuộc tính quan trọng nhất thường được dùng khi duyệt cây lần đầu tiên.
Với mỗi giá trị của thuộc tính này, một cạnh có giá trị này đối với thuộc tính được
chọn được kết hợp với cạnh đó. Theo cách này, kiểm tra thuộc tính đầu tiên tách
tập dữ liệu, và mỗi kết quả là bài toán học quyết định mới trong chính nó, với số
bản ghi ít hơn và thuộc tính ít hơn. Có thổ phân biệt ba trường hợp cho bài toán đệ
quy này.
1. Tập dữ liệu hiện tại chỉ chứa các mẫu khẳng định hoặc chỉ chứa các mẫu phủ
định (các bản ghi có cùng giá trị đối với thuộc tính tạp chí ô tô). Nếu tất cả các
mẫu là khẳng định, thì một nút với quyết định “yes” được tạo. Ngược lại, nếu
tất cả các mẫu là phủ định, thì một nút với quyết định “no” được tạo.
2. Tập dữ liệu hiện tại chứa cả các mẫu khẳng định và phủ định (các bản ghi có
giá trị khác nhau đối với thuộc tính tạp chí ô tô).
17
(a) Nếu có các thuộc tính phía trái thì có thể chọn thuộc tính quan trọng nhất
đối với tập này để tách các bản ghi còn lại.
(b) Ngược lại, có nghĩa là có nhiễu trong dữ liệu, VI các bản ghi trong tập đó
có cùng mô tả nhưng khác phân lớp.
3. Tập dữ liệu hiện tại là rỗng, nghĩa là không có dấu hiệu của giá trị thuộc tính
đó. Trong trường hợp này, một giá trị ngầm định có thể được tính toán từ một
lớp chiếm đa số tại nút cha và được trả về là quyết định.
Có nhiều thuật toán hiệu quả cho quy nạp cây quyết định có độ phức tạp

1. Sinh ra tất cả các tập mục mà có độ hỗ trợ lớn hơn ngưỡng s. Các tập
mục như vậy được gọi là các tập mục phổ biến.
2. Với mỗi tập mục phổ biến, sinh ra tất cả các luật mà có độ tin cậy lớn
hơn ngưỡng c.
Bài toán thứ hai có thể được giải quyết như sau: đối với một tập mục lớn X
và với một tập con Y của X (Ye X), xét tập X’ = X \Y gồm các thành phần của X
mà không thuộc Y. Luật X’ => Y được sinh ra nếu độ hỗ trợ của X đã tách bởi độ
hỗ trợ của X’ là lớn hơn c. Độ hỗ trợ của tập mục X là số bản ghi trong tập dữ liệu
với tất cả các thuộc tính trong X có giá trị True.
Việc sinh ra các luật kết hợp bằng việc sử dụng tất cả các tập mục phổ biến
là khá đơn giản. Tuy-nhiên, việc phát hiện tất cả các tập mục lớn cũng như giá trị
đối với các độ hỗ trợ của chúng là vấn đề chính nếu các yếu tố của tập các mục là
rất lớn.
Đặc trưng của siêu thị là có hàng nghìn mục. Số các mục khác biệt là 2m ,
trong đó m là số mục, vì thế việc tính độ hỗ trợ cho tất cả các tập mục có khả năng
mất rất nhiều thời gian tính toán.
Để giảm không gian tìm kiếm của các thuật toán tìm các luật kết hợp khai
thác các thuộc tính dưới đây của các tập mục phổ biến:
- Một tập con của tập mục phổ biến cũng phổ biến.
- Ngược lại, một mở rộng của tập mục không phổ biến là không phổ biến.
Các thuộc tính được dùng trong các thuật toán cơ bản đối với việc tìm tất cả
các tập mục phổ biến, lược đồ chính của nó có thể được tóm tắt như sau [15, 7]:
19
1. Kiểm tra độ hỗ trợ của tập mục có kích cỡ là 1, gọi là 1-itemset, bằng
việc quét CSDL. Loại bỏ các 1-itemset có độ hỗ trợ nhỏ hơn s.
2. Mở rộng các 1-itemset lớn thành các 2-itemset phổ biến bằng việc mỗi
lần bổ sung một mục của
1
-itemset phổ biến, để sinh ra tất cả các tập
mục ứng cử với hai thành phần. Kiểm tra độ hỗ trợ của các ứng cử viên

13, 14,7,9]:
1. Tim tất cả các tập mục mà độ hỗ trợ của nó lớn hơn độ hỗ trợ tối thiểu mà
người dùng xác định. Các tập mục thoả mãn độ hỗ trợ tối thiểu được gọi là các
tập mục phổ biến.
2. Dùng các tập mục phổ biến để sinh ra các luật mong muốn. Ý tưởng chung là
nếu nói ABCD và AB là các tập mục phổ biến, thì chúng ta có thể xác định nếu
luật AB => CD giữ lại bởi việc tính tỷ lệ conf = sup(ABCD)/sup(AB). Nếu conf
> minconf, thì luật được giữ lại. (Luật này sẽ thoả mãn độ hỗ trợ tối thiểu bởi vì
ABCD là phổ biến).
- Định nghĩa tập phổ biến: X là tập phổ biến nếu: support(X) > minsup(X).
- Cho X|, x 2 là các tập mục có các tính chất sau:
+ X| Ç x 2 thì minsup(X!) < minsup(X2).
+ Nếu x 2 phổ biến và X| Ç x 2 thì X, cũng phổ biến.
+ Nếu x 2 không phổ biến và x 2 ÇZ Xj thì Xị cũng không phổ biến.
Ví dụ: Cho giao dịch I = {Bánh mỳ, Bơ, Trứng, Sữa}, T = {1, 2, 3, 4 )
21
I
TID
Tập mục
1
Bánh mỳ, Bơ, Trứng
2
Bơ, Trứng, Sữa
3
Bơ
4
Bánh mỳ, Bơ
Từ bảng giao dịch trên ta rút ra:
Tập mục
Độ hỗ trợ tương ứng

Các tập mục phổ biến
Độ hỗ trợ tương ứng
Bánh mỳ
50%
Bơ
1 0 0
%
Trứng
50%
Bánh mỳ, Bơ
50%
Bơ, Trứng 50%
Nếu cho độ tin cậy tối thiểu là 60%, ta có
Luật
Độ tin cậy
tương ứng
Thoả mãn
minsup > 60% ?
Bánh mỳ => Bơ
1 0 0
% có
Bơ => Bánh mỳ
50%
không
Bơ => Trứng
50%
không
Trứng => Bơ
1 0 0
% có

Cho hệ thông tin nhị phân SB = (O, D, B, x). Cho P(O) là tập các tập con
của o, P(D) là tập các tập con của D. Các ánh xạ thông tin nhị phân ánh xạ pB và
được định nghĩa như sau:
Pb: P(D) -> P(0) và XB: P(O) -> P(D)
Cho s c D , pB(S) = Ịo e o I Vd eS, x (o , d) = 1}
Cho X c o, XB(X) = {d
6
D I V o e, x(o, d) = 1}
3. Tập chỉ báo phổ biên nhị phàn
Cho một hộ thông tin nhị phân SB = (O. D. B, x) và một ngưỡng u e[o, 1].
Cho s là một tập con của D, s là một tập chỉ báo phổ biến nhị phân với ngưỡng u
nếu:
Card(pB(S)) >= V* Card(O)
Cho Lb là một tập gồm tất cả các tập chỉ báo phổ biến nhị phân đã phát hiện
từSB, chúng có thuộc tính sau: v s e LB, T c s = > T e L B
Chúng biểu thị LBh là tập con của LB, nếu X G LBh, card(X) = h (h là số
nguyên đương).
4. Các luật kết hợp phổ biến nhị phân và hệ sô tin cậy
Cho hệ thông tin nhị phân SB = (O, D, B, x) và một ngưỡng o e[0, 1]. Cho L
là một phần tử của LB, X và Y là các tập con của L trong đó :
L = X u Y,x* {}, Y* {ỊvàXn Y* {}.
Chúng xác định các lụật kết hợp nhị phân giữa tập chỉ báo X và tập chỉ báo
Y là một ánh xạ thông tin: X —»Y. Hệ số tin cậy của luật này được biểu diễn là :
CFb(X -» Y) và được tính bằng: Card(pB(X) n Pb(Y )) / Card(pB(X)) (3)
24
Chúng ta biểu diễn RBp là tập tất cả các luật kết hợp phổ biến nhị phân, nó
được phát hiện từ SB.
Trong đó: CFB(r) >= p, Vr e RB p .
5. Các vectơ chỉ báo nhị phân và các phép toán
Cho một hệ thông tin nhị phân SB= (O, D, B, x) trong đó o = {Oị, . .