ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
HOÀNG MINH QUANG
CÁC TẬP MỤC THƯỜNG XUYÊN
TRONG KHAI PHÁ DỮ LIỆU VÀ ỨNG DỤNG LUẬN VĂN THẠC SỸ Hà Nội, 2010
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
HOÀNG MINH QUANG
Mở đầu 5
I.2.
Một số khái niệm cơ bản về tập mục 6
I.3.
Tập mục thường xuyên và luật kết hợp 7
I.4.
Mô tả bài toán khai phá luật kết hợp 9
I.5.
Một số thuật toán khai phá tập mục thường xuyên và luật kết hợp 14
I.6.
Thuật toán Apriori 16
I.7.
Thuật toán FP-Growth 20
II.
CÁC BÀI TOÁN MỞ RỘNG KHAI PHÁ TẬP MỤC
THƯỜNG XUYÊN 27
DANH MỤC VIẾT TẮT VÀ KÝ HIỆU
Các ký hiệu:
I={I
1
,I
2
,…,I
n
}. Tập n mục dữ liệu
DB={T
1
,T
2
, …, T
m
}. Cơ sở dữ liệu có m giao tác
db: Cơ sở dữ liệu giao tác con của DB, db ⊆ DB
i
p
: Mục dữ liệu thứ p
T
q
: Giao tác thứ q
n: Số mục dữ liệu trong một cơ sở dữ liệu giao tác
m: Số giao tác của một cơ sở dữ liệu giao tác
A, B, C…: Tên các mục dữ liệu trong cơ sở dữ liệu
X, Y,…: Tập con của tập mục dữ liệu I; X, Y ⊆ I
X = ABC thay cho X = {A,B,C} trong cơ sở dữ liệu giao tác
minsup: Ngưỡng độ hỗ trợ tối thiểu
minShare: Ngưỡng cổ phần tối thiểu
Bảng 8. Cơ sở dữ liệu giao tác cho khai phá tập mục cổ phần cao 29
Bảng 9. Xét CSDL Bảng 8 với minShare ≥ 30% 30
Bảng 10. Biểu diễn tất cả tập mục cổ phần cao 31
Bảng 11. CSDL minh họa có trường hợp hai hàm tới hạn bằng nhau 39
Bảng 12. CSDL minh họa trường hợp hai hàm tới hạn luôn bằng nhau. 40
Bảng 13. Giá trị của hai hàm tới hạn với k=1. 40
Bảng 14. Các giá trị lmv và hàm tới hạn với k=1. 43
Bảng 15. Các giá trị lmv và hàm tới hạn với k=2. 43
Bảng 16. các giá trị lmv và hàm tới hạn với k=3. 44
Bảng 17. Cơ sở dữ liệu giao tác trong khai phá tập mục lợi ích cao 47
Bảng 18. Bảng lợi ích các mục dữ liệu 47
Bảng 19. Cở sở dữ liệu giao tác lợi ích cao với khai pháp cổ phần cao 49
Giao diện 1. Sheet HUI, dữ liệu được sinh bởi chương trình 54
Giao diện 2. Sheet Profit, dữ liệu nhập vào bằng tay 54
Giao diện 3. Giao diện chương trình chính 55
hợp. 5I. KHAI PHÁ TẬP MỤC THƯỜNG XUYÊN
I.1. Mở đầu
Khai phá tập mục thường xuyên đóng vai trò quan trọng trong nhiều nhiệm
vụ khai phá dữ liệu. Khai phá tập mục thường xuyên xuất hiện như bài toán con
của nhiều lĩnh vực khai phá dữ liệu như khám phá luật kết hợp, khám phá mẫu
tuần tự, phân tích tương quan, phân lớp, phân cụm dữ liệu, khai phá Web,… Bài
toán khai phá tập mục thường xuyên được giới thiệu lần đầu bởi Agrawal vào
năm 1993 khi phân tích cơ sở dữ liệu bán hàng của siêu thị [9] trong mô hình
của bài toán khai phá luật kết hợp. Khai phá luật kết hợp là phát hiện những mối
quan hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu, các mối quan hệ đó chính là
các luật kết hợp.
Khai phá luật kết hợp có hai bước: bước thứ nhất, tìm các tập mục thường
xuyên thỏa mãn ngưỡng độ tối thiểu minsup cho trước, bước thứ hai, từ các tập
mục thường xuyên tìm được, sinh ra các luật kết hợp thỏa mãn ngưỡng độ tin
cậy minconf cho trước. Mọi khó khăn của bài toán khai phá luật kết hợp tập
trung ở bước thứ nhất, đó là khai phá tập mục thường xuyên thỏa mãn ngưỡng
độ hỗ trợ cho trước.
Kể từ khi Agrawa đề xuất, khai phá tập mục thường xuyên đã thu hút được
sự quan tâm của nhiều nhà nghiên cứu, đã có hàng trăm kết quả nghiên cứu
được công bố giới thiệu các thuật toán mới hay đề xuất các giải pháp nâng cao
hiệu quả các thuật toán đã có. Tập mục thường xuyên đã có vai trò quan trọng
trong nhiều ứng dụng thực tế như quản lý quan hệ khách hàng, nâng cao hiệu
quả của thương mại điện tử, trong lĩnh vực tin sinh học, phân tích cấu trúc
Protein và DNA, mở rộng truy vấn, phát hiện xâm nhập mạng…[13, 14, 15, 16].
}. Mỗi giao tác được gán một định danh T
id
.
Một tập mục
con X ⊆ I, gồm k mục phân biệt được gọi là 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.
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 T
id
và một danh sách các mục dữ liệu trong giao tác đó.
Giao tác Mục dữ liệu
T1 A, C, D
T2 B, C, E
T3 A, B, C, E
T4 B, E
Bảng 1. Biểu diễn cơ sở dữ liệu giao tác ngang
Biểu diễn dọc: Cơ sở dữ liệu là một danh sách các mục dữ liệu, mỗi mục
dữ liệu có một danh sách tất cả các định danh của các giao tác chứa mục dữ liệu
này.
7Mục dữ liệu
Các giao tác
A
1 ݇ℎ݅ ݅
∈ܶ
0 ݇ℎ݅ ݅
∉ܶ
Mục
T1
T2
T3
T4
A
1
0
1
0
E
0
1
1
1
Bảng 3. Biểu diễn cơ sở dữ liệu giao tác ma trận
I.3. Tập mục thường xuyên và luật kết hợp
Định nghĩa 1.2: Cho tập mục X ⊆ I. Độ hỗ trợ (Support) của tập mục X
trong cơ sở dữ liệu giao tác DB, ký hiệu sup(X), là tỷ lệ phần trăm của các giao
tác chứa tập mục X trên tổng số giao tác trong DB, tức là:
||
|}|{|
)sup(
DB
XTDBT
X
⊇
∈
=
Định nghĩa 1.3: Cho tập mục X⊆I với ngưỡng hộ trợ tối thiểu (minimum
support) minsup ∈ [0,1] (được xác định trước bởi người sử dụng). X được gọi là
tập mục thường xuyên (frequent itemset hoặc large itemset) với độ hỗ trợ tối
8
|}|{|
)/(
X
YX
TXDBT
TYXDBT
TXDBT
TYTXDBT
YXP
∪
=
⊆∈
⊆
∪
∈
=
⊂∈
⊆
∧
⊆
∈
=
Và ta có 0 ≤ conf(X →Y ) ≤ 1.
I.3.1. Bài toán khai phá luật kết hợp
Xác định tất cả X⇒
⇒⇒
⇒Y thỏa mãn độ hỗ trợ và độ tin cậy tối thiểu thì luật
X⇒
⇒⇒
loại 21 inches”. Những thông tin như vậy rất hữu ích trong việc định hướng
kinh doanh. Vậy vấn đề đặt ra là liệu có tìm được các luật như vậy bằng các
10công cụ khai phá dữ liệu hay không? Câu trả lời là hoàn toàn có thể. Đó chính là
nhiệm vụ khai phá luật kết hợp.
Giả sử chúng ta có một CSDL D. Luật kết hợp cho biết phạm vi mà trong
đó sự xuất hiện của tập các thuộc tính S nào đó trong các bản ghi (records) của
D sẽ kéo theo sự xuất hiện của một tập những thuộc tính khác U cũng trong
những bản ghi đó. Mỗi luật kết hợp được đặc trưng bởi một cặp tỉ lệ hỗ trợ
(support ration). Mỗi tỉ lệ hỗ trợ được biểu diễn bằng tỉ lệ % những bản ghi
trong D chứa cả S và U.
Vấn đề khám phá luật kết hợp được phát biểu như sau:
Cho trước tỉ lệ hỗ trợ (support ration) θ và độ tin cậy (confidence) β
Đánh số tất cả các luật trong D có các giá trị tỉ lệ hỗ trợ và tin cậy lớn hơn
θ và β tương ứng.
Ví dụ: Gọi D là CSDL mua bán và với θ = 40%, β = 90%
Vấn đề phát hiện luật kết hợp được thực hiện như sau:
Liệt kê (đếm) tất cả những quy luật chỉ ra sự xuất hiện một số các mục kéo
theo một số mục khác.
Chỉ xét những quy luật mà tỉ lệ hỗ trợ lớn hơn 40% và độ tin cậy lớn hơn
90%
Hay chúng ta hãy tưởng tượng, một công ty bán hàng qua mạng Internet.
Các khách hàng được yêu cầu điền vào các mẫu bán hàng để công ty có một
CSDL về các yêu cầu của khách hàng. Giả sử công ty quan tâm đến mối quan
hệ “tuổi, giới tính, nghề nghiệp => sản phẩm”. Khi đó có thể có rất nhiều câu
hỏi tương ứng với luật trên. Ví dụ: trong lứa tuổi nào thì những khách hàng nữ
là công nhân đặt mua mặt hàng gì đó, ví dụ áo dài chẳng hạn là nhiều nhất (thỏa
mãn một ngưỡng nào đó)?
tập mục thường xuyên, phải tính độ hỗ trợ của nó để kiểm tra. Tập mục thường
xuyên là tập mục có độ hỗ trợ lớn hơn hoặc bằng ngưỡng tối thiểu cho trước. Đã
có rất nhiều thuật toán tìm tập mục thường xuyên được công bố, ta có thể phân
chúng theo 2 tiêu chí:
12- Phương pháp duyệt qua không gian tìm kiếm
- Phương pháp xác định độ hỗ trợ của tập mục
Phương pháp duyệt qua không gian tìm kiếm được phân làm hai cách:
duyệt theo chiều rộng (Breadth First Search - BFS) và duyệt theo chiều sâu
(Depth First Search - DFS)
Duyệt theo chiều rộng là duyệt qua cơ sở dữ liệu gốc để tính độ hỗ trợ của
tất cả các tập mục ứng viên có (k-1) mục trước khi tính độ hỗ trợ của các tập
mục ứng viên có k mục. Với CSDL có n mục, lần lặp thứ k phải kiểm tra độ hỗ
trợ của tất cả C
k
n
tập ứng viên có k mục
Duyệt theo chiều sâu là duyệt qua CSDL đã được chuyển thành cấu trúc
dạng cây, quá trình duyệt gọi đệ quy theo chiều sâu của cây. Với cơ sở dữ liệu
có n mục dữ liệu, không gian tìm kiếm có 2
n
tập con, rõ ràng đây là bài toán NP
khó, do đó cần phải có phương pháp duyệt thích hợp, tỉa nhanh các tập ứng
viên.
Phương pháp xác định độ hỗ trợ của tập mục X được chia làm 2 cách: cách
thứ nhất là đếm số giao tác chứa X trong cơ sở dữ liệu và cách thứ 2 là tính
phần giao của các tập chứa định danh của các giao tác chứa X.
I.4.2. Một số tiếp cận khai phá luật kết hợp
mua phần mềm tiện ích văn phòng Microsoft Office, ”. Như vậy dạng luật đầu
là dạng luật tổng quát hóa của dạng luật sau và tổng quát theo nhiều mức khác
nhau.
Luật kết hợp mờ (fuzzy association rule): với những hạn chế còn gặp phải
trong quá trình rời rạc hóa các thuộc tính số (quantitave attributes), các nhà
nghiên cứu đã đề xuất luật kết hợp mờ nhằm khắc phục các hạn chế trên và
chuyển luật kết hợp về dạng tự nhiên hơn, gần gũi hơn với người sử dụng. Một
ví dụ của dạng này là: “thuê bao tư nhân =’yes’ AND thời gian đàm thoại lớn
AND cước nội tỉnh = ‘yes’ => cước không hợp lệ =’yes’, với độ hỗ trợ là 4% và
độ tin cậy là 85%”. Trong luật trên, điều kiện thời gian đàm thoại lớn ở về trái
của luật là một thuộc tính đã được mờ hóa.
Luật kết hợp với thuộc tính được đánh trọng số (association rule with
weighted items): trong thực tế, các thuộc tính trong CSDL không phải lúc nào
14cũng có vai trò như nhau. Có một số thuộc tính được chú trọng hơn và có mức
độ quan trọng cao hơn hơn các thuộc tính khác. Ví dụ khi khảo sát về doanh thu
hàng tháng, thông tin về thời gian đàm thoại, vùng cước là quan trọng nhiều hơn
so với thông tin về phương thức gọi… Trong quá trình tìm kiếm luật, chúng ta
sẽ gán thời gian gọi, vùng cước các trọng số lớn hơn thuộc tính phương thức
gọi. Đây là hướng nghiên cứu rất thú vị và đã được một số nhà nghiên cứu đề
xuất cách giải quyết bài toán này. Với luật kết hợp có thuộc tính được đánh
trọng số, chúng ta sẽ khai thác được những luật “hiếm” (tức là có độ hỗ trợ thấp
nhưng có ý nghĩa đặc biệt hoặc mang rất nhiều ý nghĩa).
Khai thác luật kết hợp song song (parallel mining of association rules):
Bên cạnh khai thác luật kết hợp tuần tự, các nhà làm tin học cũng tập trung
nghiên cứu các thuật giải song song cho quá trình phát hiện luật kết hợp. Nhu
cầu song song hóa và xử lý phân tán là cần thiết bởi kích thước dữ liệu ngày
càng lớn đòi hỏi tốc độ xử lý cũng như dung lượng bộ nhớ của hệ thống phải
việc tính toán nhiều tập con không đóng.
I.5.4. Thuật toán APRIORI
Ý tưởng chính của thuật toán này là: sinh ra các tập mục ứng viên từ các
tập mục thường xuyên ở bước trước, sử dụng kỹ thuật tỉa để bỏ bớt đi những tập
mục ứng viên không thỏa mãn ngưỡng hỗ trợ tối thiểu (minsup). Cơ sở của
thuật toán này là tính chất Apriori “Bất kỳ tập con nào của tập mục thường
xuyên cũng phải là tập mục thường xuyên”. Thuật toán giúp tỉa bớt những tập
ứng viên có tập con không thường xuyên trước khi tính độ hỗ trợ. Nhược điểm
của thuật toán là chi phí sinh ra số lượng khổng lồ tập ứng viên và phải duyệt
CSDL nhiều lần.
I.5.5. Thuật toán FP-Growth
Phát triển từ thuật toán Apriori, J.Han, J Pei, Y.Yin và R.Mao đã đề xuất
thuật toán FP-growth [14] nhằm khắc phục những hạn chế của thuật toán
Apriori. Thuật toán này được xây dựng với ba kỹ thuật chính là: Nén dữ liệu
thích hợp vào một cấu trúc cây gọi là FP-tree. Chỉ có 1–tập mục ở trong cây và
các nút của cây được sắp xếp để các nút xuất hiện thường xuyên hơn có thể dễ
dàn chia sẻ với các nút xuất hiện ít hơn; Thực hiện phương pháp khai phá phát
16triển (growth) từng đoạn dựa trên cây FP-tree gọi là phương pháp FP-growth;
Kỹ thuật tìm kiếm được dùng ở đây là dựa vào sự phân chia, “chia để trị”, phân
rã nhiệm vụ khai phá thành nhiệm vụ nhỏ hơn.
I.6. Thuật toán Apriori
Bước 1: Đếm 1-tập mục
Bước lặp:
- Kết hợp các (k-1)-tập mục sinh ra tập ứng viên C
k
- Tỉa các kết nối để thu được k-tập mục, xác định các tập mục thường
, minsup); //các ứng cử mới theo chương trình con
dưới đây.
for(
∀
giao dịch t
∈
D)
{ C
t
=Subset(C
k
,t);//ứng cử viên được chứa trong t
for(
∀
ứng cử c
∈
C
t
)
c.count++;
}
L
k
={c
∈
C
k
|c.count ≥ minsup}
k++;
}
k
;
18 }
Return C
k
;
}
Boolean has_infrequent_subset(c,L
k-1
)
{ for(
∀
(k-1)-subset s
∈
c)
if(s
∉
Lk-1)return TRUE;
else return FALSE;
}
I.6.3. Giải thích
Lần duyệt đầu tiên, sẽ tính số lần xuất hiện của mỗi mục để xác định các
1-tập mục thường xuyên. Lần duyệt thứ k (k≥2) sẽ bao gồm 2 giai đoạn:
Giai đoạn 1: tập mục thường xuyên L
k-1
đã tìm thấy ở các lần duyệt thứ
k-1 được sử dụng để sinh ra các tập ứng cử viên bằng việc sử dụng hàm
k-1
. Thủ tục này là đầy đủ đối
với bất kỳ tập nào L
k
với độ hỗ trợ tối thiểu thì các tập con kích cỡ (k-1) cũng
có độ hỗ trợ tối thiểu, do đó nếu ta mở rộng mỗi tập trong L
k-1
với tất cả các tập
19mục có thể và sau đó xóa tất cả các tập mà (k-1)–tập mục con của nó không
nằm trong L
k-1
, ta sẽ nhận được tập các tập trong L
k
.
Việc kết nối là tương đương với việc mở rộng L
k-1
với mỗi mục nằm trong
CSDL và sau đó xóa bỏ các tập này mà đối với nó (k-1)–tập mục nhận được
bằng việc xóa đi mục thứ (k-1) không nằm trong L
k-1
. Ở giai đoạn này C
k
⊇ L
k
.
Với lập luận như vậy, giai đoạn tỉa là giai đoạn người ta xóa khỏi C
k
mục không nằm trong t. Những lý luận tương tự áp dụng cho các mức sâu hơn.
Vì các mục trong bất kỳ tập nào cũng được sắp xếp thứ tự, nếu ta đến được một
20nút hiện tại bằng việc băm mục I, ta chỉ cần quan tâm đến những mục nhỏ hơn
trong t nó xuất hiện sau i.
//Bước tỉa: Xóa bớt tất cả các tập mục c ∈ Ck mà (k-1) tập con của c
không phụ thuộc L
k-1
.
for(
∀
tập mục c
∈
C
k
)
for(
∀
(k-1 – tập con s của c)
if(s
∉
L
k-1
)
delete c khỏi C
k
;
I.7. Thuật toán FP-Growth
toán không đệ quy khai phá cây FP-tree dựa trên cấu trúc cây COFI-tree [5].
Thuật toán COFI-tree có nhiều ưu điểm hơn thuật toán FP-growth
Thuật toán COFI-tree gồm 2 giai đoạn chính.
- Giai đoạn thứ nhất: Xây dựng cây FP-tree
- Giai đoạn thứ hai: Khai phá cây FP-tree chia thành nhiều bước tương
ứng với các mục dữ liệu trong bảng đầu mục của cây FP-tree, mỗi bước sử dụng
một cấu trúc dữ liệu phụ trợ là cây COFI-tree của mục dữ liệu đó.
Mỗi nút của cây FP-tree gồm 3 trường:
+ Tên mục dữ liệu
+ Độ hỗ trợ
+ Một con trỏ (Con trỏ này trỏ đến nút tiếp theo cùng tên trên cây hoặc là
null nếu không có)
Cây FP-tree có một bảng đầu mục (header table). Mỗi mục của bảng có 3
trường: tên mục dữ liệu, độ hỗ trợ và con trỏ, con trỏ này trỏ đến nút đầu tiên
biểu diễn mục dữ liệu này trong cây.
Cây COFI-tree có bảng đầu mục giống cây FP-tree nhưng các mục dữ liệu
có thứ tự ngược lại. Mỗi mục trong bảng đầu mục chứa 3 trường: tên mục dữ
liệu, độ hỗ trợ địa phương (số lần xuất hiện trong cây COFI-tree) và con trỏ (trỏ
đến nút đầu tiên biểu diễn mục dữ liệu này trong cây). Một danh sách liên kết
được duy trì giữa các nút cùng tên để thuận lợi cho quá trình khai phá. Mỗi nút
22của cây COFI-tree có 4 trường: tên mục dữ liệu, hai biến s và p (biến s biểu diễn
độ hỗ trợ của nút, biến p cho biết số lần nút đó đã tham gia tạo mẫu), con trỏ
(trỏ đến nút tiếp theo cùng tên trên cây)
Minh họa thuật toán COFI-tree
Xét CSDL với ngưỡng minsup = 3
TID
1
1
1
0
0
T03
1
1
0
1
0
0
T04
0
0
0
0
0
T07
1
1
1
0
0
1
T08
1
0
1
0
0
T11
1
1
1
0
0
0
Bảng 4. Cơ sở dữ liệu minh họa thực hiện thuật toán COFI-tree
Giai đoạn 1. Xây dựng cây FP-tree
Duyệt CSDL lần thứ nhất tính được độ hỗ trợ của mỗi mục dữ liệu, loại bỏ
các mục dữ liệu không thỏa mãn ngưỡng minsup = 3, sắp xếp giảm dần theo độ
hỗ trợ các mục
Mục dữ liệu
Độ hỗ trợ
A
7
B
7
B
6
D
5
Bảng 6. Các mục dữ liệu thường xuyên đã sắp thứ tự
23Duyệt cơ sở dữ liệu lần 2. Mỗi giao tác chọn ra các mục dữ liệu thường
xuyên, sắp chúng theo thứ tự giảm dần của độ hỗ trợ và chèn lên cây
Giao tác TID
Các mục dữ liệu
T01
C, B, D
T02
C, B, D
T03
T11
C, A, B
Bảng 7. Các mục dữ liệu trong giao tác sắp xếp giảm dần theo độ hỗ trợ
Từ bảng này ta có cây FP-tree
Hình 1. Hình cây FP-Growth
Giai đoạn 2. Khai phá cây FP-tree
Xét lần lượt các mục dữ liệu từ dưới lên trong bảng đầu mục cây FP-tree,
với mỗi mục xây dựng cây COFI-tree của nó, khai phá cây này tìm mẫu thường
xuyên, sau khi khai phá xong, loai bỏ cây đó và xây dựng cây COFI-tree cho
mục dữ liệu tiếp theo. Minh họa thuật toán qua xét mục dữ liệu đầu tiên D:
M
ụ
c
DL
Đ
ộ
hỗ
trợ
Con
trỏ
C
8A
D1
A4
B2
Copyright: Tài liệu đại học ©