ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
KHOA CÔNG NGHỆ THÔNG TIN
NHÓM 4 – CAO HỌC KHOA HỌC MÁY TÍNH B
(NĂM HỌC 2010 – 2012)
KHAI PHÁ LUẬT KẾT HỢP
VỚI CƠ SỞ DỮ LIỆU LỚN
TIỂU LUẬN MÔN HỌC
KHAI PHÁ DỮ LIỆUHuế, tháng 9/2011
ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
KHOA CÔNG NGHỆ THÔNG TIN
NHÓM 4 – CAO HỌC KHOA HỌC MÁY TÍNH B
(NĂM HỌC 2010 – 2012)
KHAI PHÁ LUẬT KẾT HỢP
VỚI CƠ SỞ DỮ LIỆU LỚN
TIỂU LUẬN MÔN HỌC
KHAI PHÁ DỮ LIỆU
GIÁO VIÊN HƯỚNG DẪN: NHÓM HỌC VIÊN THỰC HIỆN:
TS. HOÀNG THỊ LAN GIAO TRẦN NHƯ ĐĂNG TUYÊN
LÊ BÁ MINH PHONG
NGUYỄN THỊ THANH TÂM
NGUYỄN THỊ THÀNH
NGUYỄN VŨ CÁT TƯỜNG
TRẦN THỊ MỸ NGÂN
Huế, tháng 9/2011
III. KẾT LUẬN 45
TÀI LIỆU THAM KHẢO 46
LỜI NÓI ĐẦU
Khai phá dữ liệu (hay Data mining) là một quá trình trích xuất thông tin
có mối quan hệ hoặc có mối tương quan nhất định từ một kho dữ liệu lớn
hoặc cực lớn nhằm mục đích dự đoán các xu thế, các hành vi trong tương lai,
hoặc tìm kiếm những tập thông tin hữu ích mà bình thường không thể nhận
diện được.
Các công cụ, kỹ thuật data mining có thể trả lời các câu hỏi mà các
công cụ truyền thống đòi hỏi rất nhiều thời gian cần thiết để có thể giải đáp
được (thậm chí các cách truyền thống không thể giải được). Nó có thể tìm
thấy được những thông tin cực kỳ hữu ích mà rất dễ bị bỏ qua hoặc không
xem xét đến để có thể dự đoán những xu thế/ hành động xảy ra trong tương
lai. Data mining là giai đoạn quan trọng nhất trong tiến trình khai phá tri thức
từ cơ sở dữ liệu, các tri thức này hỗ trợ trong việc ra quyết định trong khoa
học và kinh doanh.
Để có thể data mining một cách hiệu quả, điều đầu tiên cần phải thu
thập dữ liệu và định nghĩa lại theo các tiêu chí cần phân tích. Các kỹ thuật
data mining có thể cài đặt rất nhanh chóng trên các nền tảng phần mềm, phần
cứng phổ thông mà không cần đòi hỏi quá phức tạp, tuy vậy data mining
thường gắn liền với việc phân tích một khối lượng dữ liệu cực lớn nên cần
ứng dụng các công nghệ high performance client/server hoặc xử lý song song
(parallel programming).
Dưới sự hướng dẫn của cô giáo, TS. Hoàng Thị Lan Giao, nhóm chúng
tôi mạnh dạn tìm hiểu đề tài “Khai phá luật kết hợp trong CSDL lớn”.
Trong quá trình tìm hiểu và trình bày sẽ không tránh khỏi những thiếu sót, rất
mong cô giáo và các bạn đóng góp ý kiển để tiểu luận được hoàn thiện hơn.
NHÓM 4 – CAO HỌC KHMT B (2010 – 2012)
4
I. ĐẶT VẤN ĐỀ
luật kết hợp. Các khái niệm cơ bản của các khai phá luật kết hợp được đưa ra
trong mục 2.1.2. Mục 2.1.3 trình bày một cách thức để phân biệt các loại luật
kết hợp
2.1.1 Phân tích giỏ mua hàng
Giả sử, là quản lý của một chi nhánh AllElectronics, bạn muốn tìm hiểu
thêm về các thói quen mua sắm khách hàng. Bạn tự hỏi: “Những nhóm các
mặt hàng nào mà khách hàng có thể mua trên cùng một chuyến đi đến siêu
thị?". Để trả lời câu hỏi của bạn, người phân tích thị trường có thể tìm hiểu
trên các hóa đơn bán lẻ của khách hàng tại cửa hàng. Các kết quả có thể được
sử dụng để lập kế hoạch tiếp thị hay quảng cáo, cũng như trong cách thiết kế
các gian hàng. Ví dụ, phân tích thị trường có thể giúp nhà quản lý thiết kế bố
trí các gian hàng với các mặt hàng thường xuyên được mua với nhau lại gần
với nhau để khuyến khích khách hàng trong việc mua sắm. Nếu khách hàng
mua máy tính cũng có xu hướng mua phần mềm quản lý thì nên bố trí, sắp
xếp cho cả hai ở gần nhau để khuyến khích khách hàng mua nhằm tăng doanh
số bán hàng của cả hai. Trong một chiến lược khác, đặt phần cứng và phần
mềm ở hai đầu của cửa hàng có thể lôi kéo khách hàng mua những mặt hàng
đó để nhận các mặt hàng khác trên đường đi. Ví dụ, sau khi quyết định mua
một máy tính đắt tiền, một khách hàng có thể tìm hệ thống bảo mật để mua
nên nghĩ đến việc tìm các phần mềm, và có thể quyết định mua một hệ thống
bảo mật mức độ gia đình là tốt. Việc phân tích thị trường cũng có thể giúp các
nhà bán lẻ lên kế hoạch mà các mặt hàng đưa vào bán với giá giảm. Nếu
khách hàng có xu hướng mua máy tính và máy in với nhau thì có thể thấy
rằng việc bán các máy in có thể ngang bằng việc bán máy tính.
Nếu chúng ta có số lượng lớn tập hợp các mặt hàng có sẵn tại cửa hàng,
ta đặt mỗi mặt hàng có một giá trị Boolean đại diện cho sự có mặt hay vắng
mặt của mặt hàng đó. Mỗi giỏ hàng có thể được đại diện bởi một vector các
giá trị Boolean gán cho biến này. Các vectơ Boolean có thể được phân tích để
6
gán cho các mặt hàng thường xuyên được mua với nhau. Ví dụ, các thông tin
B, với A
⊆
I, B
⊆
I và .
Một luật mà đáp ứng cả độ hỗ trợ tối thiểu (min_sup) và độ tin cậy tối
thiểu (min_conf) thì được gọi là mạnh. Chúng ta qui định min_sup và
min_conf xảy ra giữa 0% và 100%
Một tập các mục được gọi là một tập mục. Một tập mục có chứa các k
mặt hàng gọi là một k-tập mục. Tập {computer,
financial_managerment_software} là 2-tập mục. Tần suất xuất hiện của tập
mục là số các giao dịch có chứa các tập mục. Điều này cũng được biết đến
như là đếm tần số hoặc độ hỗ trợ của tập mục. Một tập mục thõa mãn độ hỗ
trợ tối thiểu nếu tần số xuất hiện của tập mục là lớn hơn hoặc bằng min_sup
và tổng số các giao dịch trong D. Số lượng các giao dịch cần thiết cho tập
mục để đáp ứng độ hỗ trợ tối thiểu gọi là tính hỗ trợ tối thiểu. Nếu tập mục
thõa mãn độ hỗ trợ tối thiểu, thì đó là tập tập mục phổ biến. k-tập mục phổ
biến được ký hiệu là L
k
.
7
Làm thế nào để khai phá được luật kết hợp trong tập dữ liệu lớn. Khai
phá luật kết hợp qua 2 bước:
-
Tìm tất cả các tập mục phổ biến. Theo định nghĩa, mỗi tập mục này sẽ
xảy ra thường xuyên như là một xác định trước độ hỗ trợ tối thiểu
-
Tạo ra các luật kết hợp mạnh cho các tập mục phổ biến.
Bằng việc định nghĩa, những quy tắc này phải đáp ứng độ hỗ trợ tối
8
3. Căn cứ vào các mức trong các luật. Một số phương pháp để khai thác
luật kết hợp có thể tìm thấy ở mức. Ví dụ, giả sử một tập hợp các luật kết hợp
được khai thác dưới đây
age(X, “30…39")
buys(X, “laptop computer") (4)
age(X, “30…34")
buys(X, “computer") (5)
Trong quy tắc (4) và (5), các mặt hàng đã mua được tham chiếu ở mức
khác nhau. (Tức là, "computer” là mức trừu tượng cao hơn "laptop
computer”). Chúng tôi tham khảo việc khai phá luật kết hợp đa mức. Nếu các
quy tắc trong một tập đã cho không tham chiếu đến các mục hoặc các thuộc
tính tại các mức khác nhau thì đó là luật kết hợp đơn mức.
2.2 Khai phá luật kết hợp luận lý một chiều từ tập giao tác.
Trong phần này, chúng ta sẽ biết đến các phương pháp khai phá luật kết
hợp hình thức đơn giản như một chiều, đơn cấp, luật kết hợp nhị phân cũng
như thảo luận về market basket analysis trong mục 6.1.1. Chúng ta sẽ bắt
đầu bằng thuật toán Apriori, đây là thuật toán cơ bản để tìm tập mục phổ biến
(trong mục 6.2.1). Một thủ tục sinh ra tập luật kết hợp mạnh từ tập mục phổ
biến được thảo luận trong mục 6.2.2. Mục 6.2.3 trình bày một số thay đổi đối
với thuật toán Apriori nhằm cải tiến hiệu quả và khả năng của nó. Mục 6.2.4
đưa ra phương pháp khai phá luật kết hợp khác, nó khác với Apriori, nó
không liên quan việc sinh ra tập mục phổ biến “ứng cử”. Mục 6.2.5 mô tả
cách nguyên lý Apriori có thể được áp dụng để cải tiến hiệu suất cho câu trả
lời “iceberg queries – truy vấn núi băng trôi” rất phổ biến trong
2.2.1 Thuật toán Apriori
Apriori là thuật toán có ảnh hưởng đối với việc tìm tập mục phổ biến cho
luật kết hợp nhị phân. Tên của thuật toán thì dựa vào nguyên nhân mà thuật
cả tập con của nó cũng sẽ bị lỗi y như nó vậy. Nó được gọi là anti-monotone
bởi vì thuộc tính đơn điệu trong ngữ cảnh kiểm tra bị lỗi.
“Thuộc tính Apriori được sử dụng trong thuật toán như thế nào?” Để
hiểu về vấn đề này, chúng ta sẽ cùng xem dùng L
k-1
để tìm L
k
như thế nào. Có
2 bước trong quá trình này, đó là bước kết nối và bước rút gọn.
1. Bước kết nối: để tìm L
k
, một tập ứng cử k-tập mục được sinh ra bằng
cách nối L
k-1
với chính nó. Tập mục ứng cử này được ký hiệu C
k
. Lấy l
1
và l
2
là
những mục trong L
k-1
. Ký hiệu l
i
[j] là mục thứ j trong l
i
(ví dụ: l
1
[k-2] là phần
^
(l1[k-2] =
l2[k-2])
^
(l1[k-1] < l2[k-1]). Điều kiện l
1
[k-1] < l
2
[k-1] bảo đảm mỗi tập sinh
ra đều không giống nhau. Tập mục kết quả theo dạng nối l
1
và l
2
là l
1
[1]l
1
[2]…
l
1
[k-1]l
2
[k-1].
2. Bước làm gọn: C
k
là tập cha của L
k
, nghĩa là những thành viên trong
nó có thể có hoặc không là phổ biến, nhưng tất cả trong k-tập mục phổ biến
thì chứa trong C
T400
T500
T600
T700
T800
T900
I1, I2, I5
I2, I4
I2, I3
I1, I2, I4
I1, I3
I2, I3
I1, I3
I1, I2, I3, I5
I1, I2, I3
Hình 6.2 Giao tác dữ liệu cho một chi nhánh điện tử
Ví dụ 6.1 Chúng ta cùng xem một ví dụ cụ thể của Apriori dựa vào tập
giao tác dữ liệu D của hình 6.2. Ở đây có 9 giao tác trong cơ sở dữ liệu này,
nghĩa là |D| = 9. Chúng ta sử dụng hình 6.3 để minh họa thuật toán Apriori
cho việc tìm tập mục phổ biến trong D.
1. Đầu tiên của thuật toán, mỗi mục là 1 thành viên của tập 1-tập mục
ứng cử, C
1
. Thuật toán đơn giản có thể quét tất cả giao tác được sắp theo số
thứ tự sự kiện của mỗi mục.
2. Giả thiết độ hỗ trợ tối thiểu của giao tác là 2 (min_sup = 2/9 = 22%).
Tập 1-tập mục phổ biến là L
1
có thể định nghĩa ngay sau đó. Nó bao gồm 1-
tập mục ứng cử thỏa ngưỡng hỗ trợ tối thiểu min_sup.
2
= {{I1,I2,I3}, {I1,I2,I5}, {I1,I3,I5}, {I2,I3,I4},
{I2,I3,I5}, {I2,I4,I5}}. Dựa vào thuộc tính Apriori tất cả của tập mục phổ
biến phải là tập phổ biến, chúng ta có thể định nghĩa 4 ứng cử cuối không thể
là phổ biến. Vì vậy có thể loại nó khỏi C
3
, theo đó ta lưu kết quả có được của
những kết quả không cần thiết độ hỗ trợ của chúng trong suốt quá trình quét
tuần tự tập con của D để định nghĩa L
3
. Lưu ý rằng khi cho một k-tập mục
ứng cử , chúng ta chỉ cần kiểm tra nếu (k-1)-tập con của nó là phổ biến khi
thuật toán Apriori sử dụng level-wise trong chiến lược tìm kiếm.
7. Giao tác trong D được quét theo thứ tự để định nghĩa L
3
bao gồm 3-
tập mục ứng cử trong C
3
thỏa ngưỡng hỗ trợ tối thiểu. (hình 6.3).
8. Thuật toán sử dụng L
3
nối L
3
để sinh ra tập ứng cử 4-tập mục C
4
. Mặc
dù kết quả nối là {{I1,I2,I3,I5}, tập mục này được rút gọn thì tập con của nó
là {{I2,I3,I5}} không phổ biến. Như vậy C
4
= và thuật toán kết thúc và đưa
con là phổ biến được đưa ra ở thủ tục has_infrequent_subset.
Thuật toán: Apriori tìm tập mục phổ biến sử dụng phương pháp level-
wise lặp lại dựa vào ứng cử sinh ra
Input: cơ sở dữ liệu, D số các giao tác, ngưỡng hỗ trợ tối thiểu min_sup
Output: L tập mục phổ biến trong D
(1) L
1
= 1-tập mục phổ biến (D)
(2) for (k=2; L
k-1
≠ ; k++{
(3) C
k
=apriori_gen(L
k-1
,min_sup);
(4) for mỗi giao tác t D {//quét D để đếm
(5) C
t
=tập con(C
k
,t); //lấy tập con của t là ứng cử
(6) for mỗi ứng cử c C
t
(7) c.count++;
(8)}
(9) L
k
= {c C
k
2
[k-2]) ^ (l
1
[k-1]<l
2
[k-
1]) then
(4) c = l
1
nối l
2
; //bước kết nối:sinh tập ứng cử
(5) if has_infrequent_subset(c,L
k-1
) then
(6) delete c; //bước rút gọn: loại ứng cử không thỏa
(7) else thêm c vào C
k
;
(8) }
(9) return C
k
;
Procedure has_infrequent_subset(c:k-tập mục ứng cử; L
k-1
: (k-1)-tập mục
phổ biến);// sử dụng prior knowledge
(1)for mỗi (k-1)-tập con s của c
(2) if s L
k-1
2.2.3 Cải tiến hiệu suất Apriori.
“Làm cách nào để cải tiến hiệu năng của Apriori?” Nhiều cách khác
nhau đã đưa ra để cải tiến hiệu năng của thuật toán cơ bản Apriori này. Một
số trong các cách khác nhau này được liệt kê ở dưới.
Áp dụng kỹ thuật băm (băm tập mục đếm được): Một kỹ thuật băm có
thể được dùng để giảm kích thước của k-tập mục ứng cử Ck với k > 1. Ví dụ,
khi quét mỗi giao tác trong cơ sở dữ liệu để sinh ra 1-tập mục phổ biến L1, từ
1-tập mục phổ biến trong C1 chúng ta có thể sinh tất cả 2-tập mục cho mỗi
giao tác, băm (xem hình) chúng vào các khe chứa khác nhau của cấu trúc
bảng băm và tăng số khe chứa tương ứng (hình 6.6). Một 2-tập mục mà có số
khe chứa tương ứng trong bảng băm và ngưỡng hỗ trợ ở dưới không là phổ
biến thì bị loại khỏi tập ứng cử. Khi đó một kỹ thuật băm có thể làm giảm số
lượng k-tập mục phổ biến (đặc biệt khi k=2).
16
Giảm số giao tác (giảm số giao tác được quét trong lần lặp tiếp theo):
một giao tác không chứa bất kỳ k-tập mục phổ biến thì không thể chứa bất kỳ
(k+1)-tập mục phổ biến. Vì vậy, khi một giao tác có thể được đánh dấu hoặc
bị loại từ đó khi đó việc quét tiếp theo của cơ sở dữ liệu đối với j-tập mục, j >
k sẽ không phải làm.
Phân vùng (phân vùng dữ liệu để tìm tập mục ứng cử): một kỹ thuật
phân vùng có thể được dùng mà kỹ thuật này đòi hỏi chỉ 2 cơ sở dữ liệu quét
đến chính tập mục phổ biến (hình 6.7). Nó bao gồm 2 pha. Trong pha 1, thuật
toán chia nhỏ các giao tác của D vào n vùng không phủ nhau. Nếu ngưỡng hỗ
trợ tối thiểu đối với giao tác trong D là min_sup, khi đó độ hỗ trợ tối thiểu tập
mục đối với vùng là min_sup x số giao tác trong vùng đó. Với mỗi vùng, tất
cả tập mục phổ biến trong vùng được tìm ra. Những tập mục phổ biến này
được đề cập như là những tập mục phổ biến cục bộ. Thủ tục sử dụng một cấu
trúc dữ liệu đặc biệt mà đối với mỗi tập mục, ghi lại TIDs của những giao tác
chứa những mục trong tập mục. Điều này cho phép tìm tất cả k-tập mục phổ
biến cục bộ, với k = 1, 2, …, trong chỉ 1 lần quét cơ sở dữ liệu.
mục phổ biến mà chúng đã bị lỗi trong lần duyệt thứ nhất. Phương pháp lấy
mẫu đặc biệt hữu ích khi độ tin cậy là quan trọng ở mức tối đa như khi một
ứng tính toán mạnh phải được chạy trên một nền tảng rất phổ biến.
Đếm tập mục động (thêm những tập ứng cử tại những điểm khác nhau
trong suốt một lần quét): kỹ thuật đếm một tập mục động được đề xuất ở khi
mà cơ sở dữ liệu được phân vào những khối đánh dấu bởi những điểm bắt
đầu. Trong sự thay đổi này, những tập mục ứng cử mới có thể được thêm tại
bất kỳ điểm bắt đầu nào, không giống trong Apriori, ở đó xác định những tập
mục ứng cử mới ngay lập tức trước khi mỗi lần quét cơ sở dữ liệu hoàn thành.
Kỹ thuật là động vì thế nó đánh giá độ hỗ trợ của tất cả những tập mục mà đã
được đếm , thêm những tập mục ứng cử mới nếu một trong những tập con của
chúng được đánh giá là phổ biến. Kết quả thuật toán yêu cầu quét cơ sở dữ
liệu ít hơn Apriori.
Những phương pháp khác nhau giải quyết khai phá luật kết hợp đa cấp
và đa chiều được thảo luận trong phần còn lại của chương này. Khai phá luật
kết hợp liên quan dữ liệu không gian, dữ liệu thời gian liên tiếp và dữ liệu đa
phương tiện được thảo luận ở chương 9.
2.2.4 Khai phá tập mục phổ biến không sinh ứng cử.
Như chúng ta đã thấy, trong nhiều trường hợp, phương pháp sinh ứng cử
và kiểm tra ứng cử của Apriori làm giảm kích thước của tập ứng cử một cách
đáng kể và dẫn đến việc thực thi có lợi. Tuy nhiên, nó có thể nhận hai giá trị
không tầm thường.
• Cần phải sinh một lượng lớn những tập ứng cử. Ví dụ, nếu 10
4
1-tập
mục phổ biến, thuật toán Apriori sẽ cần phải sinh hơn 10
7
2-tập mục ứng cử
và cộng dồn nhằm kiểm tra lần xuất hiện tập phổ biến. Hơn nữa, để khai phá
môt mẫu phổ biến kích thước 100, (a
xử lý trong L theo trình tự (ví dụ, sắp xếp theo giảm dần của độ hỗ trợ) và
một nhánh được tạo đối với mỗi giao tác. Ví dụ, quét giao tác đầu tiên.
“T100: I1, I2, I5”, chứa 3 mục (I2, I1, I5) trong L theo thứ tự, dẫn đến cấu
trúc của nhánh đầu tiên của cây có 3 nút: ((I2: 1), (I1: 1), (I5: 1)), ở đây I2 là 1
liên kết vì nó là con của gốc. I1 liên kết đến I2 và I5 liên kết đến I2. Ở giao
tác thứ hai, T200, chứa những mục I2 và I4 trong L theo thứ tự, và kết quả có
một nhánh ở đây I2 liên kết với gốc và I4 liên kết đến I2. Tuy nhiên, nhánh
này sẽ chia sẻ tiền tố giống nhau (I2) với đường đi có sắn cho T100. Do đó
chúng ta thay giá trị(gia lượng) độ ở nút I2 bằng 1 và tạo thêm một nút mới
(I4: 1) mà nút này liên kết như là con của nút (I2: 2). Trong trường hợp
chung, khi xem nhánh thêm vào cho một giao tác, độ hỗ trợ của mỗi nút mà
tiền tố như nhau thì cho giá trị là 1 và những nút cho những mục tiếp theo tiền
tố được tạo ra và liên kết phù hợp.
Để giảm giao cắt trên cây, một mục đầu bảng được tạo ra để mỗi điểm
mục tương ứng một lần xuất hiện trên cây thông qua một xích liên kết các nút.
Cây đạt được sau khi quét tất cả các giao tác xem hình 6.8 với các liên kết nút
19
kết hợp. Do đó, vấn đề của khai pha mẫu phổ biến trong cơ sở dữ liệu được
chuyển thành khai phá FP-tree.
Tiến trình khai phá của cây FP-tree như sau. Bắt đầu từ mẫu phổ biến độ
dài 1 (như 1 mẫu đầu tiên ở hậu tố), xây dựng nó nền tảng mẫu điều kiện (“cơ
sở dữ liệu nhỏ” mà chứa tập đường dẫn tiền tố lần xuất hiện trên FP-tree với
mẫu hậu tố), sau đó xây dựng nó (điều kiện) FP-tree và thực hiện khai phá đệ
quy trên một cây. Tăng mẫu đạt được bằng cách ghép mẫu hậu tố với những
mẫu phổ biến sinh ra từ điều kiện FP-tree.
Khai phá FP-tree được tóm tắt trong bảng 6.1 và chi tiết như sau. Đầu
tiên chúng ta xem I5 là mục cuối cùng trong L. Lý do ở sau sẽ trở nên rõ khi
chúng ta giải thích tiến trình khai phá FP-tree. I5 xuất hiện trong 2 nhánh của
FP-tree ở hình 6.8. (Số lần xuất hiện của I5 có thể dễ dàng tìm thấy theo
đường liên kết của nó). Dạng đường dẫn bởi những nhánh này là: ((I2 I1 I5:
tác Trans trong D làm như sau.
Lựa chọn và sắp xếp những mục phổ biến trong Trans theo thứ tự của
L. Đặt sắp xếp danh sách mục phổ biến trong Trans là [p|P], với p là phần tử
đầu tiên và P là phần còn lại của danh sách. Gọi thủ tục insert_tree([p|P], T),
thủ tục thực hiện như sau. Nếu T có con N thì N.item-name = p.item-name,
sau đó tăng độ N lên 1; ngược lại tạo một nút mới N và đặt độ là 1, nó liên kết
đến cha nó là liên kết đến nút T và nó liên kết với nút có item-name giống
nhau thông qua cấu trúc liên kết nút. Nếu P khác rỗng, gọi đệ quy
insert_tree(P, N).
2. Khai phá một FP-tree thực hiện bằng cách gọi FP-growth(FP_tree,
null) và thực hiện như sau.
Procedure FP_growth(Tree, )
(1) If Tree chứa một đường dẫn đơn P thì
(2) For mỗi biến đổi (biểu thị như ) của những nút trong đường
dẫn P
(3) Sinh mẫu U với độ hỗ trợ = độ hỗ trợ tối thiểu của những
nút trong
(4) Else với mỗi a
i
trong tiêu đề của Tree {
(5) Sinh mẫu = a
i
U với hỗ trợ = độ hỗ trợ a
i
;
(6) Xây dựng , dựa vào mẫu điều kiến s và sau đó là điều kiện của
FP-tree Tree
β
;
21
Khái niệm phân cấp trong hình trên có 4 mức, bắt đầu từ mức 0, 1, 2, 3. Theo
quy ước, các cấp trong một hệ thống khái niệm được đánh số từ trên xuống
dưới, bắt đầu từ mức 0 ở nút gốc (mức trừu tượng chung nhất). Ở đây, cấp 1
bao gồm computer, software, printer và computer accessor; cấp 2 bao gồm
home computer, laptop computer, education software, financial management
software, ; và cấp 3 bao gồm IBM home computer, , Microsoft educational
software, … Cấp độ 3 là cấp độ trừu tượng nhất của hệ thống này. Khái niệm
phân cấp có thể được xác định bởi người dùng quen thuộc với các dữ liệu,
hoặc có thể tồn tại ngầm trong các dữ liệu.
Các mục trong bảng trên đang ở mức thấp nhất của hệ thống phân cấp.
Đây là điều khó khăn để tìm kiếm mặt hàng được mua nhiều nhất. Ví dụ, nếu
“IBM home computer " hoặc “Sony b/w printer" xảy ra ở một phần rất nhỏ
của các giao dịch, sau đó nó có thể tìm được các kết hợp mạnh đến các mục
đó. Rất ít người có thể mua hàng như nhau, làm cho nó không có tập mục
{ IBM home computer, Sony b/w printer} thõa mãn độ hỗ trợ tối thiểu. Dễ
dàng tìm thấy các luật kết hợp mạnh giữa “IBM home computer " và “ b/w
printer” hơn là giữa “IBM home computer " và “Sony b/w printer". Tương tự
như vậy, nhiều người có thể mua “computer” và “printer” với nhau, hơn là
mua “IBM home computer " và “Sony b/w printer" với nhau. Nói cách khác,
các tập mục phổ biến chẳng hạn như {IBM home computer, b/w printer} và
{computer, printer} có nhiều khả năng có độ hỗ trợ tối thiểu hơn tập mục phổ
23
biến có chứa dữ liệu chỉ mức độ nguyên thủy, như {IBM home computer,
Sony b/w printer}. Từ đây có thể dễ dàng tìm thấy các kết hợp giữa các mục
tại nhiều mức khái niệm với nhau.
Các luật được tạo ra từ khai phá luật kết hợp với khái niệm phân cấp
được gọi là luật kết hợp đa mức.
2.3.2 Phương pháp để khai phá luật kết hợp đa cấp.
“Làm thế nào để khai thác luật kết hợp đa mức hiệu quả trên khái niệm
phân cấp?”
Mỗi cấp độ trừu tượng có hỗ trợ tối thiểu của nó. Mức trừu tượng thấp
hơn thì có ngưỡng hỗ trợ tương ứng nhỏ hơn. Ví dụ, trong hình trên, các
ngưỡng hỗ trợ tối thiểu cho cấp 1 và 2 là 5% và 3%. Như vậy, “computer”,
“laptop computer” và “home computer” đều được xem là phổ biến. Đối với
khai phá các kết hợp đa mức để giảm độ hỗ trợ, có một số chiến lược tìm
kiếm thay thế sau:
-
Độc lập theo từng cấp (level by level): Đây là việc tìm kiếm đầy đủ
theo chiều rộng, nơi mà việc xác định tập mục thường xuyên được bỏ qua.
Mỗi nút được kiểm tra, bất kể cha của nó có phải là tập mục phổ biến không
-
.
-
Level-cross fitering by single item:
-
Một mục ở cấp độ thứ i được kiểm tra nếu và chỉ nếu nút của nó tại
mức i-1 là phổ biến. Nếu một nút là phổ biến thì nút đó sẽ được kiểm tra, nếu
không, con cháu của nó được cắt bỏ. Ví dụ, trong hình sau, các nút hậu duệ
của “computer” (ví dụ, “laptop computer" và “home computer”) là không
được kiểm tra, vì “computer” không phổ biến
25
Copyright: Tài liệu đại học ©