Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
1
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
PHẠM THỊ LÝ
Tên đề tài:
KHAI PHÁ TẬP MỤC THƢỜNG XUYÊN ĐÓNG
TRÊN DÕNG DỮ LIỆU
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số : 60.48.01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
hiện những tri thức tiềm ẩn.
Một trong các nội dung cơ bản trong khai phá dữ liệu là khai phá luật kết
hợp. Khai phá luật kết hợp gồm hai bƣớc: Bƣớc thứ nhất, tìm tất cả các tập mục
thƣờng xuyên, đòi hỏi sự tính toán lớn. Bƣớc thứ hai, dựa vào các tập mục
thƣờng xuyên tìm các luật kết hợp, đòi hỏi tính toán ít hơn, song gặp phải một
vấn đề là có thể sinh ra quá nhiều luật, vƣợt khỏi sự kiểm soát của ngƣời khai phá
hoặc ngƣời dùng, trong đó có nhiều luật không cần thiết. Để giải quyết vấn đề đó,
trong bƣớc thứ nhất, không cần thiết khai phá tất cả các tập mục thƣờng xuyên
mà chỉ cần khai phá các tập mục thƣờng xuyên đóng. Khai phá luật kết hợp dựa
trên tập mục thƣờng xuyên đóng cho hiệu quả cao hơn, nó đảm bảo không tìm ra
các tập mục thƣờng xuyên không cần thiết, không sinh ra các luật dƣ
thừa.Với ý nghĩa đó và mục đích tìm hiểu về bài toán tìm tập mục thƣờng xuyên
trên dòng dữ liệu, em đã quyết định lựa chọn đề tài “Khai phá tập mục thƣờng
xuyên đóng trên dòng dữ liệu”.
Nội dung luận văn gồm 3 chƣơng:
Chương 1: Tổng quan về khai phá dữ liệu
Chương 2: Khai phá tập mục thường xuyên đóng trên dòng dữ liệu
Chương 3: Chương trình thực nghiệm ứng dụng Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
3
CHƢƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
1.1. Khái niệm về khám phá tri thức và khai phá dữ liệu.
KPDL (Khai phá dữ liệu) là việc rút trích tri thức một cách tự động và hiệu
quả từ một khối dữ liệu lớn. Tri thức đó thƣờng ở dạng các mẫu có tính chất
không tầm thƣờng, không tƣờng minh (ẩn), chƣa đƣợc biết đến và có tiềm năng
mang lại lợi ích. Có một số nhà nghiên cứu còn gọi khai phá dữ liệu là phát hiện
Trong giai đoạn khai phá dữ liệu, có thể cần sự tƣơng tác của ngƣời dung
để điều chỉnh và rút ra các tri thức cần thiết. Các tri thức nhận đƣợc cũng có thể
đƣợc lƣu và sử dụng lại.
Hình 1.1:
Qúa trình phát hiện tri thức
Việc KPDL có thể đƣợc tiến hành trên một lƣợng lớn dữ liệu có trong các
CSDL (Cơ sở dữ liệu), các kho dữ liệu hoặc trong các loại lƣu trữ thông tin khác.
Các mẫu đáng quan tâm có thể đƣợc đƣa đến ngƣời dung hoặc đƣợc lƣu
5
Hình 1.2:
Kiến trúc của một hệ thống khai phá dữ liệu
- Máy chủ CSDL hay máy chủ kho dữ liệu
(
Database or warehouse server
).
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
6
khai phá đƣợc dùng.
- Giao diện người dung
(
Graphical user interface
).
Bộ phận này cho phép
ngƣời dùng giao tiếp với hệ thống KPDL. Ngoài ra bộ phận này còn cho phép
ngƣời dung xem các lƣợc đồ CSDL, lƣợc đồ kho dữ liệu (hay các cấu trúc dữ liệu),
các đánh giá mẫu và hiển thị các mẫu trong khuôn dạng khác nhau.
1.3 Các giai đoạn của quá trình khai phá dữ liệu
Các giải thuật khai phá dữ liệu thƣờng đƣợc miêu tả nhƣ những chƣơng
trình hoạt động trực tiếp trên tệp dữ liệu. Với các phƣơng pháp học máy và
thống kê trƣớc đây, thƣờng thì bƣớc đầu tiên là các giải thuật nạp toàn bộ tệp
dữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan
đến việc khai phá các kho dữ liệu, mô hình này không thể đáp ứng đƣợc. Không
chỉ bởi vì nó không thể nạp hết dữ liệu vào trong bộ nhớ mà còn vì khó có thể
chiết xuất dữ liệu ra các tệp đơn giản để phân tích đƣợc.
Quá trình khai phá dữ liệu đƣợc thể hiện bởi mô hình sau [3]:
7
liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi
v.v ).
+ Chọn thuật toán khai phá dữ liệu thích hợp và thực hiện việc khai phá dữ
liệu: nhằm tìm đƣợc các mẫu (pattern) có ý nghĩa dƣới dạng biểu diễn tƣơng ứng
với các ý nghĩa đó.
1.4. Một số kỹ thuật khai phá dữ liệu
Mục đích của khai phá dữ liệu là chiết xuất ra các tri thức có lợi cho kinh
doanh hay cho nghiên cứu khoa học… Do đó, ta có thể xem mục đích của khai
phá dữ liệu sẽ là mô tả các sự kiện và dự đoán. Các mẫu khai phá dữ liệu phát
hiện đƣợc nhằm vào mục đích này. Dự đoán liên quan đến việc sử dụng các biến
hoặc các đối tƣợng (bản ghi) trong CSDL để 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 đáng quan tâm.
Mô tả tập trung vào việc tìm kiếm các mẫu mô tả dữ liệu mà con ngƣời có thể
hiểu đƣợc.
Một số kỹ thuật phổ biến thƣờng đƣợc sử dụng để KPDL hiện nay là :
Phân lớp dữ liệu
Mục tiêu của phân lớp dữ liệu là dự đoán nhãn lớp cho các mẫu dữ liệu.
Quá trình gồm hai bƣớc: xây dựng mô hình, sử dụng mô hình để phân lớp dữ
liệu. Mô hình đƣợc sử dụng để dự đoán nhãn lớp khi mà độ chính xác của mô
hình chấp nhận đƣợc.
Phân nhóm dữ liệu
Phân nhóm là kỹ thuật khai phá dữ liệu tƣơng tự nhƣ phân lớp dữ liệu.
Tuy nhiên, sự phân nhóm dữ liệu là quá trình học không đƣợc giám sát, là quá
trình nhóm những đối tƣợng vào trong những lớp tƣơng đƣơng, đến những
đối tƣợng trong một nhóm là tƣơng đƣơng nhau, chúng phải khác với những đối
tƣợng trong những nhóm khác. Trong phân lớp dữ liệu, một bản ghi thuộc
về lớp nào là phải xác định trƣớc, trong khi phân nhóm không xác định trƣớc
Trong phân nhóm, những đối tƣợng đƣợc nhóm lại cùng nhau dựa vào sự
giá trị rời rạc.
Phát hiện sự thay đổi và độ lệch (change and deviation dectection):
Nhiệm
vụ này tập trung vào khám phá những thay đổi có ý nghĩa trong dữ liệu dựa
vào các giá trị chuẩn hay độ đo đã biết trƣớc, phát hiện độ lệch đáng kể giữa
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
9
nội dung của tập con dữ liệu và nội dung mong đợi. Hai mô hình độ lệch
thƣờng dùng là lệch theo thời gian và lệch theo nhóm. Độ lệch theo thời gian
là sự thay đổi có nghĩa của dữ liệu theo thời gian. Độ lệch theo nhóm là sự
khác nhau giữa dữ liệu trong hai tập con dữ liệu, tính cả trƣờng hợp tập con
của đối tƣợng này thuộc tập con kia, nghĩa là xác định dữ liệu trong một
nhóm con của đối tƣợng có khác nhau đáng kể so với toàn bộ đối tƣợng.
1.5. Các cơ sở dữ liệu phục vụ cho khai phá dữ liệu.
Dựa vào những kiểu dữ liệu mà kỹ thuật khai phá áp dụng, có thể chia dữ
liệu thành các loại khác nhau.
Cơ sở dữ liệu quan hệ
Đến nay, hầu hết dữ liệu đƣợc lƣu giữ dƣới dạng cơ sở dữ liệu quan hệ.
Cơ sở dữ liệu quan hệ là một nguồn tài nguyên lớn nhất chứa những đối tƣợng
mà chúng ta cần khai phá. Cơ sở dữ liệu quan hệ có cấu trúc cao, dữ liệu đƣợc
mô tả bởi một tập những thuộc tính và lƣu trong những bảng. Khai phá dữ liệu
trên cơ sở dữ liệu quan hệ chủ yếu tập trung khai phá mẫu. Ví dụ, trong cơ sở dữ
liệu của một ngân hàng, ta có thể tìm đƣợc những khách hàng có mức chi tiêu
cao, ta có thể phân loại những khách hàng này dựa vào quá trình chi tiêu của họ.
Cũng với việc phân tích những mục chi tiêu của khách hàng, chúng ta có thể
cung cấp một số thông tin của khách hàng đến những doanh nghiệp khác. Giả sử
rằng một khách hàng chi mỗi tháng 500 đô la cho thời trang, nếu đƣợc phép,
ngân hàng có thể cung cấp thông tin về khách hàng này cho những cửa hàng
Hầu hết nghiên cứu về lĩnh vực này ngày nay hình thành một hƣớng khai
phá dữ liệu mới gọi là khai phá mẫu lặp liên tục, khai phá tập mục dữ liệu thƣờng
xuyên trong cơ sở dữ liệu thời gian.
Cơ sở dữ liệu đa phương tiện
Số lƣợng trang web đang bùng nổ trên thế giới, web có mặt ở khắp mọi
nơi, duyệt web đã là nhu cầu của mọi tầng lớp trong xã hội. Thông tin trên web
đang phát triển với tốc độ rất cao, khai phá thông tin trên web (web mining) đã
trở thành một lĩnh vực nghiên cứu chính của khai phá dữ liệu, đƣợc các nhà
nghiên cứu đặc biệt quan tâm.
Khai phá dữ liệu web thông thƣờng đƣợc chia thành ba phạm trù chính:
Khai phá cách dùng web (web usage mining), khai phá c ấu trúc web (web
structure mining) và khai phá nội dung web (web content mining).
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
11
Khai phá cách dùng web tập trung vào việc khai phá thông tin của ngƣời
truy nhập web. Với những thông tin này ngƣời khai phá dữ liệu có thể cung cấp
những thông tin hữu ích cho ngƣời dùng và các nhà kinh doanh.
1.6. Các ứng dụng của khai phá dữ liệu
KPDL đƣợc vận dụng trong nhiều lĩnh vực khác nhau nhằm khai thác nguồn
dữ liệu phong phú đƣợc lƣu trữ trong các hệ thống thông tin. Tuỳ theo bản chất của
từng lĩnh vực, việc vận dụng KPDL có những cách tiếp cận khác nhau.
KPDL đƣợc vận dụng có hiệu quả để giải quyết các bài toán phức tạp trong
những ngành đòi hỏi kỹ thuật cao nhƣ: tìm kiếm mỏ dầu từ ảnh viễn
thám, xác
định vùng gãy trong ảnh địa chất để dự đoán thiên tai, cảnh báo hỏng hóc trong
các hệ thống sản xuất.
Phân nhóm và dự đoán là những kỹ thuật rất cần thiết cho việc quy hoạch
và phát triển hệ thống quản lý và sản xuất trong thực tế nhƣ: dự đoán tái sử
1.7.1 Khái niệm
Độ hỗ trợ (support):
Cho tập mục X I. Ta gọi độ hỗ trợ (Support) của X trong cơ sở dữ
liệu giao tác DB, ký hiệu supp(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à: Ta có: 0 supp(X) 1 với mọi tập mục X I
Với cơ sở dữ liệu cho ở bảng 1.1 ta có:
Supp(A) = 60%, Supp(CA) = 60%, Supp(CE) = 80%
1.7.2. Các cách tiếp cận khai phá tập mục thƣờng xuyên
Các nghiên cứu về khai phá tập mục thƣờng xuyên tập trung vào tìm các
thuật toán mới hoặc đề xuất giải pháp nâng cao hiệu quả các thuật toán đã có.
Phần này sẽ trình bày khái quát các kỹ thuật chính để khai phá tập mục thƣờng
xuyên.
Bài toán khai phá tập mục thƣờng xuyên có thể chia thành hai bài toán
nhỏ: tìm các tập mục ứng viên và tìm các tập mục thƣờng xuyên. Tập mục
ứng viên là tập mục mà ta hy vọng nó là 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 hỗ trợ 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 hai tiêu
chí sau :
- Phƣơng pháp duyệt qua không gian tìm kiếm.
Supp(X)=
T{T DB T X}
DB
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
13
BFS
DFS
Đếm
Giao
Đếm
Giao
AIS
Apriori
Dic
Partition
FP- Growth
Eclat
C
n
k
=
n!
k!(n-k)!
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
14
Phần tiếp theo mô tả chi tiết nội dung hai thuật toán tiêu biểu cho hai
phƣơng pháp: duyệt theo chiều rộng và duyệt theo chiều sâu. Thuật toán Apriori
tiêu biểu cho phƣơng pháp duyệt theo chiều rộng; Thuật toán FPgrowth, đại diện
cho phƣơng pháp duyệt theo chiều sâu.
1.7.3 Một số thuật toán tìm tập mục thƣờng xuyên
1.7.3.1. Thuật toán Apriori
Apriori là thuật toán khai phá tập mục thƣờng xuyên do R. Agrawal và
R. Srikant đề xuất vào năm 1993 [3], [7]. Ý tƣởng của thuật toán Apriori cũng là
15
Thuật toán duyệt cơ sở dữ liệu nhiều lần. Mỗi lần duyệt, thuật toán thực
hiện hai bƣớc: bƣớc kết nối và bƣớc tỉa. Trong lần lặp thứ k, thuật toán nối hai
(k-1)-tập mục để sinh ra k-tập mục, sử dụng tính chất Apriori để tỉa các tập ứng
viên. Bƣớc nối và bƣớc tỉa nhƣ sau:
Bước kết nối (tìm C
k
): Tập các k-tập mục ứng viên C
k
đƣợc sinh ra bởi
việc kết nối L
k
-1 với chính nó. Hai tập mục l1 và l2 của Lk-1 đƣợc nối nếu
chúng có (k-2) mục dữ liệu đầu bằng nhau, mục dữ liệu thứ (k-1) của l1 nhỏ hơn
của l
2
: (l
1
[1] = l
2
[1]) (l
1
[2] = l
2
[2]) … (l
1
[k-2] = l
2
toán áp dụng tính chất Apriori để rút gọn tập C
k
. Nếu có một (k-1)-tập mục con
nào đó của k-tập mục ứng viên mà không có mặt trong L
k
-1 thì ứng viên đó
không thể là thƣờng xuyên, có thể loại bỏ khỏi C
k
. Việc kiểm tra các (k-1)-tập
mục con có thể thực hiện nhanh bởi duy trì một cây băm của tất cả các tập mục
thƣờng xuyên đã tìm thấy.
Thuật toán Apriori (tìm các tập mục thƣờng xuyên)
Input: Cơ sở dữ liệu DB, ngƣỡng độ hỗ trợ minsup
Output: Tập các tập mục thƣờng xuyên L trong DB
Method:
(1) Tìm các 1-tập mục thƣờng xuyên, nhận đƣợc L
1
;
(2)
For (k=2; L
k-1
≠ k++) do begin
(3) Ck = apriori_gen(Lk-1, minsup); // Sinh tập ứng viên mới từ Lk-1
(4) For (each T DB ) do begin
(5)
C = subset(Ck,T) ; // Các tập mục ứng viên chứa trong T
(6) For (each c C )
(7) c.count++ ; // tăng số đếm c lên một đơn vị
k-1
) do
(3) if (l
1
[1] = l
2
[1]) and (l
1
[2] = l
2
[2]) and … and
(l
1
[k-2] = l
2
[k-2]) and (l
1
[k-1] < l
2
[k-1])
Then
(4) C
k
{ l
1
[1], l
1
[2], … l
1
[k-2],l
17
Bảng 1.1: Cơ sở dữ liệu giao tác minh họa thực hiện thuật toán Apriori
TID
Các mục dữ liệu
T1
A,C,D
T2
B,C,E
T3
A,B,C,E
T4
B,E
- Duyệt CSDL lần thứ nhất: tính độ hỗ trợ cho các 1-tập mục đƣợc kết quả
nhƣ sau: 1-tập
Count
1-tập
Count
{A}
2
Loại bỏ các 1-tập mục có
{A}
2
với L
1
ta đƣợc C
2
:
C
2
2-tập mục
{A,B}
{A,C}
{A,E}
{B,C}
{B,E}
{C,E}
- Duyệt CSDL lần thứ 2: tính độ hỗ trợ cho 2-tập mục
C
1
L
1
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
18
C
2
L
2
3-tập mục
Count
{B, C, E}
2 Nối L
3
với L
3
đƣợc L
4
= , thuật toán dừng.
Các tập mục thƣờng xuyên tìm đƣợc theo thuật toán Apriori là :
L= L1 L2 L3 ={ A, B, C, E, AC, BC, BE, CE, BCE}
Nhận xét : Thuật toán duyệt cơ sở dữ liệu nhiều lần, số lần duyệt bằng độ dài
của tập mục thƣờng xuyên dài nhất tìm đƣợc.
1.7.3.2. Thuật toán FP-Growth
Thuật toán Apriori gặp phải hai chi phí lớn:
- Chi phí sinh ra số lƣợng khổng lồ các tập ứng viên. Ví dụ, nếu có 104
mục thƣờng xuyên thì thuật toán Apriori sẽ cần sinh ra hơn 107 các ứng viên 2-
tập mục và thực hiện kiểm tra độ hỗ trợ của chúng.
2-tập mục
Count
{A, C}
2
{B,C}
2
{B,E}
(2) Thực hiện phƣơng pháp khai phá phát triển (growth) từng đoạn dựa
trên cây FP-tree gọi là phƣơng pháp FP-growth.
(3) 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 các nhiệm vụ nhỏ hơn.
Thuật toán FP-growth do nén toàn bộ cơ sở dữ liệu lên một cấu trúc dữ
liệu nhỏ hơn là cây FP-tree nên tránh đƣợc việc duyệt nhiều lần cơ sở dữ liệu
(thuật toán chỉ duyệt cơ sở dữ liệu 2 lần). Tiếp theo thuật toán khai phá cây
bằng cách phát triển dần các mẫu mà không sinh các tập mục ứng viên, do đó
tránh đƣợc khối lƣợng tính toán lớn. Phƣơng pháp FP- growth đã chứng tỏ đƣợc
tính hiệu quả của nó và có thể thực hiện khai phá cho cả các mẫu ngắn
và dài, nhanh hơn thuật toán Apriori , luôn chỉ cần duyệt CSDL 2 lần
Thuật toán FP- growth thực hiện như sau:
Đầu tiên, thuật toán duyệt CSDL lần thứ nhất để tính độ hỗ trợ của từng
mục (đếm số lần xuất hiện của từng mục).
Tiếp đến, những mục không đủ độ hỗ trợ bị loại. Các mục còn lại đƣợc sắp
theo thứ tự giảm dần của độ hỗ trợ (cũng tức là giảm dần theo số lần xuất hiện
trong CSDL), ta nhận đƣợc danh sách L các mục đã sắp.
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
20
Duyệt CSDL lần thứ hai, với mỗi giao tác t, loại các mục không đủ độ hỗ
trợ, các mục còn lại theo thứ tự giống nhƣ xuất hiện trong L (tức là thứ tự giảm
dần theo độ hỗ trợ) đƣợc cất vào cây FP-tree.
Phần tiếp theo thuật toán khai phá tìm các mẫu thƣờng xuyên trên cây FP-
tree đã xây dựng mà không cần duyệt lại CSDL nữa.
Để hiểu phƣơng pháp này làm việc thế nào, ta xét khai phá CSDL giao
tác DB sau với độ hỗ trợ tối thiểu minsup = 3/5.
Bảng 1.2 CSDL giao tác minh họa cho thuật toán FP- growth
TID
3
m
3
p
3
Bước 3: Duyệt CSDL lần thứ 3 và xây dựng cây FP-tree
Cây FP-tree đƣợc xây dựng nhƣ sau:
Khởi tạo cây T, gốc của cây có nhãn null.
Khi duyệt CSDL lần thứ hai, với mỗi giao tác, loại các mục không thƣờng
xuyên, các mục còn lại sắp theo thứ tự giảm dần của số lần xuất hiện,
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
21
dãy các mục thƣờng xuyên đó đƣợc thêm vào cây cùng với thay đổi số đếm
của các mục trên cây cho phù hợp. Quá trình xây dựng cây nhƣ hình 1.5 sau:
a:1
m:1
p:1
root
f:2
c:2
a:2
m:1
p:1
b:1
m:1
root
f:3
c:2
a:2
m:1
p:1
b:1
m:1
b:1
Root
c:3
f:4
a:3
m:2
p:2
b:1
c:1
p:1
b:1
Procedure insert_tree( string [p | P] , tree có gốc T)
1. Nếu T có nút con N mà N.itemname = p thì N.count++
2. Ngƣợc lại
3. Tạo một nút mới N;
4. N.itemname := p; N.count := 1;
5. Thay đổi nút liên kết cho p bao gồm N;
6. Nếu P khác rỗng gọi thủ tục insert_tree ( P, N );
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
23
Tìm các tập mục thường xuyên :
Sau khi xây dựng xong FP-tree cho CSDL, việc khai phá tìm các tập
mục thƣờng xuyên chỉ thực hiện trên FP-tree mà không cần duyệt CSDL nữa.
Thuật toán FP- growth nhƣ sau:
Bắt đầu từ dƣới lên của bảng header và cây, với mỗi mục A: dùng nút
liên kết duyệt qua tất cả các nút trên cây mà xuất hiện A, với mỗi nút N mà
N.itemname = A, xác định các tập mục thƣờng xuyên có xuất hiện A, thực hiện
bằng cách chỉ cần tìm các đƣờng đi từ gốc tới N. Ví dụ : đầu tiên xét mục p, sau
đó đến m, nhƣ sau.
Mục p:
+ Có 2 đƣờng:
+ Tìm theo cách đệ qui các tập mục thƣờng xuyên trên FP-tree
phụ thuộc, đầu tiên cho a, sau đó cho c và f. Cây FP-tree phụ thuộc của m nhƣ
hình 1.7 sau
Hình 1.8: FP-tree phụ thuộc của m
Cơ sở điều kiện của nút “am”
Cơ sở điều kiện của nút “cam”
(f:3,c:3)
(f:3)
Cây điều kiện FP của “am”
Cây điều kiện FP của “am”
Root
c:3
f:4
c:3
root
f:3
Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
25
Cơ sở điều kiện của nút “cm”
(f:3)
Cây điều kiện FP của “cm”
Hình 1.9 : Các FP-tree phụ thuộc của am, cm và cam
Thuật toán FP- growth :
Khai phá FP-tree đƣợc thực hiện bởi gọi lần đầu FP- growth (FP-tree,
null), thực hiện nhƣ sau:
Vào: Các phân hoạch CSDL D
N/P
và minsup.
Ra: Tập các mục phổ biến
Copyright: Tài liệu đại học ©