i
S húa bi Trung tõm Hc liu

đại học thái nguyên
Tr-ờng đại học CÔNG NGHệ THÔNG TIN Và TRUYềN
THÔNG
NGUYN TH LUYN

KHAI PH TP MC LI CH CAO
DA TRấN CU TRC CY TIN T LUN VN THC S KHOA HC MY TNH

thái nguyên - năm 2014
ii
Số hóa bởi Trung tâm Học liệu

®¹i häc th¸i nguyªn
Tr-êng ®¹i häc C¤NG NGHÖ TH¤NG TIN Vµ TRUYÒN
TH¤NG

NGUYỄN THỊ LUYẾN

[
Nguyễn Thị Luyến
iv
Số hóa bởi Trung tâm Học liệu

LỜI CẢM ƠN

Lời đầu tiên tôi xin gửi lời cảm ơn chân thành và biết ơn sâu sắc tới TS. Lê
Văn Phùng – Trƣờng Đại học công nghệ Thông tin và Truyền thông, Thầy đã chỉ
bảo và hƣớng dẫn tận tình cho tôi trong suốt quá trình làm việc và thực hiện luận
văn này.
Tôi xin chân thành cảm ơn sự dạy bảo, giúp đỡ, tạo điều kiện và khuyến
khích tôi trong quá trình học tập và nghiên cứu của các thầy cô giáo của Viện Công
nghệ thông tin, Trƣờng Đại học Công nghệ thông tin và Truyền thông - Đại học
Thái Nguyên.
Và cuối cùng, tôi xin gửi lời cảm ơn tới gia đình, ngƣời thân và bạn bè,
những ngƣời luôn ở bên tôi những lúc khó khăn nhất, luôn động viên tôi, khuyến
khích tôi trong cuộc sống và trong công việc.
Tôi xin chân thành cảm ơn!

Thái Nguyên, ngày 29 tháng 9 năm 2014
Tác giả


2.1.1 Cơ sở dữ liệu giao tác 13
2.1.2 Tập mục thƣờng xuyên và luật kết hợp 15
2.1.3 Bài toán khai phá luật kết hợp và một số thuật toán về khai phá tập mục
thƣờng xuyên 17
2.2 Bài toán Khai phá tập mục lợi ích cao 29
2.2.1 Khái niệm về tập mục lợi ích cao 29
2.2.2 Một số bài toán khai phá tập mục lợi ích cao 29
2.3 Khai phá tập mục lợi ích cao dựa trên cây tiền tố 34
2.3.1 Định nghĩa cây tiền tố 34
vi
Số hóa bởi Trung tâm Học liệu

2.3.2 Một số thuật toán khai phá tập mục lợi ích cao dựa trên cây tiền tố 35
2.3.3 Các cấu trúc cây tiền tố cho khai phá lợi ích cao 56
2.3.4 Thuật toán UP-Growth 59
2.4 Kết luận chƣơng 2 62
CHƢƠNG 3: THỰC NGHIỆM KHAI PHÁ TẬP MỤC LỢI ÍCH CAO DỰA
TRÊN CẤU TRÚC CÂY TIỀN TỐ 63
3.1. Bài toán phát hiện nhóm các mặt hàng có lợi nhuận cao 63
3.2. Mô tả dữ liệu 63
3.3 Xây dựng chƣơng trình 70
3.4 Thực nghiệm khai phá tìm tập mục lợi ích cao 71
3.5 Kết luận chƣơng 3 72
KẾT LUẬN 73
1. Những kết quả chính của luận văn 73
2. Hƣớng nghiên cứu tiếp theo 73
TÀI LIỆU THAM KHẢO 74
A. Tiếng việt 74
B. Tiếng Anh 74


Hình 2.16. Cây TWUI-tree có các mục dữ liệu sắp giảm dần theo TWU của
chúng trong cơ sở dữ liệu bảng 2.9 và bảng 2.10 58
Hình 2.17. Cây
TWUI-tree
của CSDL bảng 2.8 với minutil = 40 62
Hình 2.18. Cây UP-tree của CSDL bảng 2.8 với minutil = 40 62
Hình 3.1. Tệp CSDL.txt biểu diễn dữ liệu đầu vào 70
Hình 3.2. Giao diện chính của chƣơng trình 71
Hình 3.3. Tập các mục lợi ích cao 72

viii
Số hóa bởi Trung tâm Học liệu

DANH MỤC CÁC BẢNG

Bảng 1.1: Tập dữ liệu huấn luyện quyết định phân lớp mức lƣơng 10
Bảng 2.1: Biểu diễn ngang của cơ sở dữ liệu giao tác 14
Bảng 2.2: Biểu diễn dọc của cơ sở dữ liệu giao tác 14
Bảng 2.3: Ma trận giao tác của cơ sở dữ liệu cho ở bảng 2.1 15
Bảng 2.4: Cơ sở dữ liệu giao tác minh họa thực hiện thuật toán Apriori 21
Bảng 2.5: CSDL giao tác minh họa thực hiện thuật toán COFI-tree 25
Bảng 2.6: Các mục dữ liệu và độ hỗ trợ 25
Bảng 2.7: Các mục dữ liệu thƣờng xuyên đã sắp thứ tự 25
Bảng 2.8: Các mục DL trong giao tác sắp xếp giảm dần theo độ hỗ trợ 26
Bảng 2.9. CSDL giao tác 32
Bảng 2.10 Bảng lợi ích 32
Bảng 2.11: Lợi ích các giao tác của cơ sở dữ liệu bảng 2.9 và bảng 2.10 37
Bảng 2.12: Lợi ích TWU của các mục dữ liệu 37
Bảng 2.13: Các mục dữ liệu có lợ 38
Bảng 2.14. Các mục dữ liệu trong giao tác sắp giảm dần theo lợi ích TWU 38

1
, i
2
,…, i
n
}: Tập n mục dữ liệu.
I
p
: Mục dữ liệu thứ p.
m: Số giao tác một cơ sở dữ liệu giao tác.
Minconf: Độ tin cậy tối thiểu
minShare: Ngƣỡng cổ phần tối thiểu.
minsup: Ngƣỡng độ hỗ trợ tối thiểu.
minutil: Ngƣỡng lợi ích tối thiểu
n: Số mục dữ liệu một cơ sở dữ liệu giao tác.
Nếu X Y thì X gọi là tập con của tập Y, Y gọi là tập cha của tập X
P(Y/X): Xác suất có điều kiện (độ tin cậy của luật Y->X)
P(Y/X): Xác suất có điều kiện (độ tin cậy của luật kết hợp X->Y)
Sup(X): Tỷ lệ % của giao tác chứa tập X
T
q
: Giao tác thứ q.
U(X): Lợi ích của tập mục trong CSDL DB
X = ABC thay cho X = {A, B, C} trong các cơ sở dữ liệu giao tác ví dụ.
X, Y,…: Tập con của tập mục dữ liệu I, X, Y I.
PT
Prefix-tree
Cây tiền tố 1
1
Số hóa bởi Trung tâm Học liệu

MỞ ĐẦU
Ngày nay, sự phát triển không ngừng ứng dụng công nghệ thông tin (CNTT)
và truyền thông vào nhiều lĩnh vực đời sống, văn hóa, xã hội, quản lý kinh tế, khoa
học kỹ thuật, đã tạo ra nhiều cơ sở dữ liệu (CSDL) mới có quy mô lớn. Để khai
thác hiệu quả nguồn thông tin dữ liệu lớn đó nhằm hỗ trợ tiến trình ra quyết định,
ngƣời ta đã nghiên cứu một khuynh hƣớng kỹ thuật mới là Kỹ thuật Khai phá dữ
liệu bên cạnh các phƣơng pháp khai thác thông tin truyền thống.
Khai phá dữ liệu và khám phá tri thức (Data Mining and knowledge discovery)
là một lĩnh vực quan trọng của ngành Công nghệ thông tin. Đây là lĩnh vực đã thu
hút đông đảo các nhà khoa học trên thế giới và trong nƣớc tham gia nghiên cứu.
Khai phá tập mục thƣờng xuyên đƣợc biết đến nhƣ một bài toán con của khai phá
luật kết hợp đƣợc giới thiệu bởi Agrawal vào năm 1993 khi phân tích CSDL bán
hàng của siêu thị, phân tích sở thích mua của khách hàng bằng cách tìm ra những
mặt hàng khác nhau đƣợc khách hàng mua trong cùng một lần mua. Những thông
tin nhƣ vậy giúp ngƣời quản lý kinh doanh tiếp thị chọn lọc và thu xếp không gian
bày hàng hợp lý hơn, giúp cho việc kinh doanh hiệu quả hơn.
Mô hình khai phá tập mục thƣờng xuyên cơ bản có nhiều ứng dụng trong
thực tế bên cạnh đó còn có những hạn chế, không đáp ứng đƣợc nhu cầu của
ngƣời sử dụng.
Để đáp ứng yêu cầu của thực tiễn, khai phá tập mục thƣờng xuyên đã có nhiều
cách thức mở rộng và ứng dụng, từ thay đổi phƣơng pháp luận đến thay đổi đa dạng

dụng kiến thức sƣu tập đƣợc vào giải quyết bài toán về khai phá tập mục lợi ích cao
dựa trên cấu trúc cây đặc biệt là cây “tiền tố”.
Nội dung luận văn gồm 3 chƣơng:
Chƣơng I: Tổng quan về khai phá dữ liệu.
Chƣơng II: Khai phá tập mục thƣờng xuyên và tập mục lợi ích cao.
Chƣơng III: Thực nghiệm khai phá tập mục lợi ích cao dựa trên cấu trúc cây
tiền tố.
3

Số hóa bởi Trung tâm Học liệu
CHƢƠNG 1
TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1 Quá trình khám phá tri thức
1.1.1 Khái niệm về quá trình khám phá tri thức và khai phá dữ liệu
Theo bách khoa toàn thƣ, khai phá dữ liệu (Data Mining- DM) là khâu chủ yếu

trong kho dữ liệu.
DM là hoạt động trọng tâm của quá trình khai phá tri thức. Quá trình phát hiện
tri thức gồm các bƣớc [1], [4]:
Bước 1 - Trích chọn dữ liệu (data selection): Là bƣớc trích chọn những tập
dữ liệu cần đƣợc khai phá từ các tập dữ liệu lớn (databases, data ware houses).
Bước 2 - Tiền xử lý dữ liệu (data preprocessing): Là bƣớc làm sạch dữ liệu
(xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán,…), rút gọn dữ
liệu (sử dụng các phƣơng pháp thu gọn dữ liệu, histograms, lấy mẫu…), rời rạc hóa
dữ liệu (dựa vào histograms, entropy, phân khoảng, ). Sau bƣớc này, dữ liệu sẽ
nhất quán, đầy đủ, đƣợc rút gọn và đƣợc rời rạc hóa.
Bước 3 - Biến đổi dữ liệu (data transformation): Là bƣớc chuẩn hóa và làm
mịn dữ liệu để đƣa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật
khai thác ở bƣớc sau.
Bước 4 - Khai phá dữ liệu (data mining): Đây là bƣớc quan trọng và tốn
nhiều thời gian nhất của quá trình khám phá tri thức, áp dụng các kỹ thuật khai phá
(phần lớn là các kỹ thuật của machine learning) để khai phá, trích chọn đƣợc các
mẫu (pattern) thông tin, các mối liên hệ đặc biệt trong dữ liệu.
Bước 5 - Đánh giá và biểu diễn tri thức (knowledge representation &
evaluation): Dùng các kỹ thuật hiển thị dữ liệu để trình bày các mẫu thông tin (tri thức)
và mối liên hệ đặc biệt trong dữ liệu đã đƣợc khai thác ở bƣớc trên biểu diễn theo dạng
gần gũi với ngƣời sử dụng nhƣ đồ thị, cây, bảng biểu, luật,…. Đồng thời bƣớc này cũng
đánh giá những tri thức khám phá đƣợc theo những tiêu chí nhất định.
Trong giai đoạn khai phá dữ liệu, có thể cần sự tƣơng tác của ngƣời dùng để
điều chỉnh và rút ra các tri thức cần thiết nhất. Các tri thức nhận đƣợc cũng có thể
đƣợc lƣu và sử dụng lại.
5

Số hóa bởi Trung tâm Học liệu
kho dữ liệu
(Database or Ware house
Server)
Cơ sở dữ liệu
Kho dữ liệu
Các lƣu trữ
thông tin khác
Làm sạch; tích hợp dữ liệu;
lọc
Cơ sở
tri thức
(Knowledge
-base)
6

Số hóa bởi Trung tâm Học liệu Kiến trúc của một hệ thống DM điển hình có thể có các thành phần nhƣ hình
1.2 [3], [9].
- CSDL, kho dữ liệu hoặc các lưu trữ thông tin khác (Databases, Data ware
house,…): Đây là một hay một tập CSDL, các kho dữ liệu, các trang tính hay các
dạng lƣu trữ thông tin khác. Các kỹ thuật làm sạch dữ liệu và tích hợp dữ liệu có thể
đƣợc thực hiện trên những dữ liệu này.
- Máy chủ CSDL hay máy chủ kho dữ liệu (Database or Warehouse Server):
Máy chủ này có trách nhiệm lấy những dữ liệu tích hợp dựa trên các yêu cầu khai
phá của ngƣời dùng.
- Cơ sơ tri thức (Knowledge-base): Đây là miền tri thức dùng để hƣớng dẫn
việc tìm kiếm hay đánh giá độ quan trọng của các hình mẫu kết quả.
- Máy DM (Data mining engine): Một hệ thống DM cần phải có một tập các

của rất nhiều nhà nghiên cứu, nhờ có nhiều những ứng dụng trong thực tiễn, các
ứng dụng điển hình, có thể liệt kê nhƣ sau:
- Phân tích dữ liệu và hỗ trợ ra quyết định (Analysis & decition support).
- Điều trị trong y học (Medical): Mối liên hệ giữa triệu trứng, chuẩn đoán và
phƣơng pháp điều trị (chế độ dinh dƣỡng, thuốc men, phẫu thuật).
- Phân lớp văn bản, tóm tắt văn bản và phân lớp các trang Web (Text mining &
Web mining).
- Tin sinh học (Bio-informatics): Tìm kiếm, đối sánh các hệ gen và thông tin di
truyền, mối liên hệ giữa một số hệ gen và một số bệnh di truyền.
- Nhận dạng.
- Tài chính và thị trƣờng chứng khoán (Finance & Stock market): Phân tích
tình hình tài chính và dự đoán giá cổ phiếu.
- Bảo hiểm (Insurance).
- Giáo dục (Education).
1.2 Một số phƣơng pháp khai phá dữ liệu thông dụng
1.2.1 Phương pháp luật kết hợp
Sự kết hợp (hay mối quan hệ) là kỹ thuật khai phá dữ liệu đƣợc biết đến nhiều
hơn, hầu nhƣ quen thuộc và đơn giản. Ở đây, bạn thực hiện một sự tƣơng quan đơn
giản giữa hai hoặc nhiều mục, thƣờng cùng kiểu để nhận biết các mẫu. Ví dụ, khi
theo dõi thói quen mua hàng của ngƣời dân, bạn có thể nhận biết rằng một khách
8

Số hóa bởi Trung tâm Học liệu hàng luôn mua kem khi họ mua dâu tây, nên bạn có thể đề xuất rằng lần tới khi họ
mua dâu tây, họ cũng có thể muốn mua kem.
Việc xây dựng các công cụ khai phá dữ liệu dựa trên sự kết hợp hay mối quan
hệ có thể thực hiện đơn giản bằng các công cụ khác nhau. Ví dụ, trong InfoSphere
Warehouse một trình hƣớng dẫn đƣa ra các cấu hình của một luồng thông tin đƣợc

Một cây điển hình đƣợc chỉ ra trên hình 1.4 dành cho khách hàng mua sắm
máy tính với các thuộc tính tuổi, sinh viên, tiềm lực tài chính. Các nút (hình chữ
nhật) trong hình vẽ, trừ nút lá, biểu thị một phép thử trên 1 thuộc tính. Mỗi nút lá
(hình ovan) biểu thị 1 lớp (hoặc là mua máy tính = yes, hoặc là mua máy tính =no). youth Middle_aged Senior no yes Fair excellent
Hình 1.4 Cây quyết định về khái niệm mua máy tính
Một số thuật toán cây quyết định chỉ làm việc với cây nhị phân, trong khi đó,
một số thuật toán khác có thể làm việc với các cây không phải nhị phân.
Age
Student
Credit-rating?

yes
no
yes
yes
no
10

Số hóa bởi Trung tâm Học liệu
2
23
15
Bad
3
40
70
Good
4
55
40
Bad
5
55
100
Good
6
45
60
Good
Cây quyết định phân lớp mức lƣơng ứng với dữ liệu trong bảng 1.1 có dạng: Age?
11

Số hóa bởi Trung tâm Học liệu

Hình 1.6 Các bước thực hiện thuật toán K-Mean
Thuật toán K-Means thực hiện qua các bước chính sau:
1. Chọn ngẫu nhiên K tâm (centroid) cho K cụm (cluster). Mỗi cụm đƣợc đại
diện bằng các tâm của cụm.
2. Tính khoảng cách giữa các đối tƣợng (objects) đến K tâm (thƣờng dùng
khoảng cách Euclidean)
3. Nhóm các đối tƣợng vào nhóm gần nhất
4. Xác định lại tâm mới cho các nhóm
5. Thực hiện lại bƣớc 2 cho đến khi không có sự thay đổi nhóm nào của các
đối tƣợng
1.3 Kết luận chƣơng 1
Chƣơng 1 trình bày chi tiết các khái niệm cơ bản, kiến trúc, quá trình khai phá
dữ liệu và một số phƣơng pháp khai phá dữ liệu thông dụng. Phƣơng pháp luật kết
hợp, phƣơng pháp cây quyết định, phƣơng pháp K- Mean (Phân cụm), đều là những
thuật toán đơn giản, quen thuộc và rất quan trọng trong quá trình khai phá tập mục
lợi ích cao.
Trong chƣơng 2 sẽ trình bày các khái niệm cơ bản về tập mục thƣờng xuyên và
tập mục lợi ích cao, cấu trúc cây tiền tố và các thuật toán khai phá tập mục lợi ích
cao sử dụng cấu trúc cây tiền tố. 13

Số hóa bởi Trung tâm Học liệu

21
.
Mỗi giao tác đƣợc gán một định danh TID. Một tập mục con X I, gồm k mục phân
biệt đƣợc gọi là một k-tập mục. Giao tác T gọi là chứa tập mục X nếu X T.
Biểu diễn cơ sở dữ liệu giao tác: Cơ sở dữ liệu giao tác thƣờng đƣợc biểu diễn ở
dạng biểu diễn ngang, biểu diễn dọc và biểu diễn bởi ma trận giao tác.
14

Số hóa bởi Trung tâm Học liệu Biểu diễn ngang: Cơ sở dữ liệu là một danh sách các giao tác. Mỗi giao tác có
một định danh TID và một danh sách các mục dữ liệu trong giao tác đó.
Ví dụ 1:
Bảng 2.1: Biểu diễn ngang của cơ sở dữ liệu giao tác

TID
Mục dữ liệu
T1
B, C, D
T2
B, C, D
T3
A, B, D
T4
C, D, F
T5
C, D
T6
A, C

F
T4, T7

15

Số hóa bởi Trung tâm Học liệu Ma trận giao tác: Cơ sở dữ liệu giao tác
12
, ,
m
DB TT T

trên tập các mục
(item)
12
, , ,
n
I i i i
đƣợc biểu diễn bởi ma trận nhị phân
( ) ,
pq m n
Mm
ở đó:
1
0
qp
qp
iT

1
1
0
1
0
0
T4
0
0
1
1
0
1
T5
0
0
1
1
0
0
T6
1
0
1
0
0
0
T7
1
1

0
0 2.1.2 Tập mục thường xuyên và luật kết hợp
Định nghĩa 2 (Độ hỗ trợ)
Cho tập mục
.XI
Ta gọi độ hỗ trợ (Support) của X trong cơ sở dữ liệu giao
tác
,DB
ký hiệu
sup( ),X
là tỷ lệ phần trăm các giao tác chứa
X
trên tổng số các
giao tác trong
,DB
tức là:
DB
XTDBT
X
}
)sup(

Ta có:
1)sup(0 X
với mọi tập mục
IX