ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN ĐÌNH VĂN

MỘT SỐ THUẬT TOÁN KHAI PHÁ
LUẬT DÃY VÀ ỨNG DỤNG THỬ NGHIỆM
VÀO HỆ THỐNG QUẢN LÝ KHÁCH HÀNG
VÀ TÍNH HÓA ĐƠN NƯỚC
LUẬN VĂN THẠC SĨ
Hà N
ộ
i


NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Hà Quang Thụy
Hà N
ộ
i
-
20
11

- 3 -
Khai phá luật dãy Nguyễn Đình VănLỜI CAM ĐOAN

Tôi xin cam đoan luận văn này với đề tài “Một số thuật toán khai phá dãy và ứng
dụng thử nghiệm vào hệ thống quản lý khách hàng và tính hóa đơn nước” là công trình
do tôi nghiên cứu và hoàn thành dưới sự hướng dẫn của PGS. TS. Hà Quang Thụy,
trong luận văn có sử dụng một số tài liệu tham khảo như đã nêu trong phần “Tài liệu
tham khảo”.
Tác giả luận văn

Nguyễn Đình Văn
- 4 -
Khai phá luật dãy Nguyễn Đình Văn
3.4 Thực nghiệm và đánh giá 55
3.4.1 Giới thiệu thực nghiệm 55
3.4.2 Kết quả thực nghiệm và nhận xét 57
KẾT LUẬN 58
- 5 -
Khai phá luật dãy Nguyễn Đình VănCÁC ĐỊNH NGHĨA VÀ CHỮ VIẾT TẮT
Chữ viết tắt Diễn giải
Candidate Ứng viên
CSDL Cơ sở dữ liệu
Element Thành phần dãy
Frequent item Phần tử thường xuyên
Gcd Hàm tính ước số chung lớn nhất
Item Phần tử
Itemset Tập hợp các phần tử (item) xảy ra cùng lúc
Large sequence Dãy phổ biến
Maximal sequence Dãy tối đa, dãy phổ biến nhất
Projected database CSDL quy chiếu
Sequence Dãy
Support Độ hỗ trợ
Support threshold Ngưỡng hỗ trợ
Supsequence Dãy con
Threshold Ngưỡng
- 6 -
Khai phá luật dãy Nguyễn Đình VănMỞ ĐẦU

số đối sánh giữa luật dãy và luật kết hợp. Giới thiệu sơ bộ các phương pháp tiếp cận
khai phá luật dãy và các thuật toán điển hình tương ứng. Nội dung của chương này
được tổng hợp từ các tài liệu [1,3-4,13].
Trong chương hai, luận văn tập trung giới thiệu các thuật toán khai phá luật dãy
như AprioriAll [1], AprioriSome [1], GSP [2] là những thuật toán khởi thủy khai phá
luật dãy. Giới thiệu hai phương pháp khai phá luật dãy được công bố thời gian gần đây
- 7 -
Khai phá luật dãy Nguyễn Đình Vănlà “Khai phá luật dãy sử dụng kỹ thuật phân vùng” [10] và “Khai phá luật dãy bằng mã
hóa khối cơ bản” [16].
Trong chương ba, luận văn giới thiệu tổng quan về Hệ thống Quản lý khách hàng
và tính hóa đơn nước, đồng thời đề xuất ứng dụng khai phá luật dãy với thuật toán
AprioriAll. Trong đó, đưa ra yêu cầu đầu bài và mô hình cụ thể giải quyết bài toán.
Luận văn sử dụng dữ liệu mô phỏng của Xí nghiệp kinh doanh nước sạch Hoàn Kiếm
làm dữ liệu thử nghiệm để thực thi chương trình, đánh giá kết quả thực nghiệm.
Luận văn được hỗ trợ một phần từ Đề tài QG.10-38.
Luận văn được thực hiện dưới sự hướng dẫn của PGS. TS. Hà Quang Thụy –
trường Đại học Công Nghệ. Em xin bày tỏ lòng biết ơn sâu sắc tới Thầy đã hướng dẫn
và có ý kiến chỉ dẫn quý báu trong quá trình em thực hiện luận văn. Xin chân thành
cảm ơn Thạc sĩ Đặng Tiểu Hùng – Công ty CSE đã đóng góp nhiều ý kiến bổ ích để
bản luận văn được hoàn thiện hơn. Cuối cùng xin bày tỏ lòng biết ơn tới những người
thân trong gia đình, bạn bè đã động viên và giúp đỡ để tác giả hoàn thành bản luận văn
này.
Cho A là tập các phần tử. Giao dịch T được gọi là chứa A nếu và chỉ nếu A  T.
Một luật kết hợp có dạng A  B, trong đó A  I, B  I và A  B = Ø.
Độ hỗ trợ (support) và độ tin cây (confidence) là 2 tham số dùng để đo lường
luật kết hợp.
Luật A  B trong tập giao dịch D với độ hỗ trợ (support) s, kí hiệu là support(A
 B), trong đó s là tỉ lệ phần trăm của các giao dịch trong D mà có chứa A  B. Hay
là xác suất P(A  B ).
Công thức để tính độ hỗ trợ của luật A  B như sau:
support(A  B) = P(A  B ) =
N
Bn )A (


Trong đó: N là tổng số giao dịch; n(A  B ) là số giao dịch có chứa (A  B )
- 9 -
Khai phá luật dãy Nguyễn Đình Văn Luật A  B có độ tin cậy (confidence) c trong tập giao dịch D, kí hiệu là
confidence(A  B), trong đó c là tỉ lệ phần trăm của các giao dịch trong D có chứa A
và cũng chứa B. Hay là xác suất P(B | A).
Công thức để tính độ tin cậy của luật A  B là xác suất có điều kiện B khi đã biết
A, như sau:
confidence(A  B) = P(B | A ) =
)(
)A (
An
Bn



Khai phá luật dãy Nguyễn Đình Văn Trong gian hàng, mỗi mặt hàng gắn với một biến Boolean biểu thị sự có mặt hay
vắng mặt của mặt hàng đó. Tiếp đến, mỗi giỏ hàng có thể được thể hiện bởi một vector
Boolean các giá trị được gán cho các biến đó. Các vector Boolean biểu thị các mẫu
mua hàng mà ở đó các mặt hàng được kết hợp một cách thường xuyên hoặc được mua
với nhau. Các mẫu này có thể được biểu thị ở dạng các luật kết hợp. Ví dụ, khách hàng
mua máy tính cũng có xu hướng mua phần mềm diệt virus cùng lúc, có thể được biểu
diễn với luật kết hợp như sau:
computer  antivirus_software [support = 2%, confidence = 60%]
support = 2% nghĩa là có 2% trong tất cả các giao dịch được phân tích cho thấy máy
tính và phần mềm diệt virus được mua cùng lúc. confidence = 60% nghĩa là có 60% số
lượng khách hàng đã mua máy tính thì cũng mua phần mềm. Thông thường, các luật
kết hợp được quan tâm nếu chúng đáp ứng được cả ngưỡng hỗ trợ tối thiểu và ngưỡng
tin cậy tối thiểu. Các ngưỡng này có thể được thiết lập bởi người dùng.
Một số thuật toán thường được sử dụng cho khai phá luật kết hợp như: Apriori,
Eclat, Frequent-Pattern tree, … .Dưới đây sẽ trình bày chi tiết thuật toán Apriori vì
thuật toán này được mở rộng để sử dụng cho khai phá luật dãy.
1.1.3 Thuật toán Apriori
Tư tưởng của thuật toán Apriori là:
- Tìm tất cả các tập thường xuyên (frequent itemsets): k-itemset (itemsets gồm
k items) được dùng để tìm (k+1)-itemset.
- Đầu tiên tìm 1-itemset (ký hiệu L
1
); L
1
được dùng để tìm L
2
(2-itemsets); L

for each transaction t in database do
increment the count of all candidates in C
k+1
that
are contained in t
L
k+1
= candidates in C
k+1
with min_support
end
- 11 -
Khai phá luật dãy Nguyễn Đình Văn return 
k
L
k

Cụ thể, thực hiện theo các bước sau:
Bước 1: Duyệt toàn bộ CSDL để có được độ hỗ trợ s của 1-itemset, so sánh s với
min_sup, để có được 1-itemset (L
1
)
Bước 2: Thực hiện phép nối (join) L
k-1
với L
k-1
để sinh ra tập ứng viên k-itemset. Loại

tin giao dịch mua bán hàng bao gồm các thông tin về mã khách hàng (customer-id),
thời gian giao dịch (transaction-time) và các mặt hàng trong giao dịch.
 Các khái niệm
Một itemset là một tập không rỗng các phần tử (item).
Một dãy (sequence) là một danh sách có thứ tự các itemset.
Không mất tính tổng quát, chúng ta giả sử rằng một tập các phần tử được ánh xạ
tới một tập các số nguyên liền kề. Ta biểu thị itemset i bởi (i
1
i
2
i
m
), trong đó i
j
là một
phần tử. Ta biểu thị dãy s bởi (s
1
s
2
s
n
), trong đó s
j
là một itemset.
- 13 -
Khai phá luật dãy Nguyễn Đình Văn Dãy (a
1


để biểu thị
quan hệ “được chứa trong”. Ví dụ, dãy <(3) (4,5) (8)>

<(7) (3 8) (9) (4 5 6) (8)>, vì
((3)  (3 8), (4 5)  (4 5 6) và (8)  (8). Tuy nhiên, dãy <(3) (5)> không được chứa
trong <(3 5)> và ngược lại. Phần tử 3 và 5 trong dãy <(3) (5)> mô tả chúng không nằm
trong cùng một lần giao dịch, trong khi phần tử 3 và 5 trong dãy <(3 5)> mô tả chúng
nằm trong một lần giao dịch. Trong một tập các dãy, một dãy s là lớn nhất hay tối đa
(maximal) nếu s không được chứa trong bất kỳ dãy nào khác.
Tất cả các giao dịch của cùng một khách hàng có thể được xem như là một dãy.
Trong đó, mỗi giao dịch được xem như một tập các phần tử, và danh sách các giao
dịch theo thứ tự tăng dần về thời gian giao dịch tương ứng với một dãy. Chúng ta gọi
đó là một dãy khách hàng (customer-sequence). Ta biểu thị các giao dịch của một
khách hàng được sắp xếp thứ tự tăng dần theo thời gian là (T
1
, T
2
, , T
n
). Tập các
phần tử (item) trong T
i
được biểu thị bởi itemset(T
i
). Dãy customer-sequence của một
khách hàng là một dãy <itemset(T
1
) itemset(T
2

4
4
10, 20
90
30
40, 60, 70
30
30, 50, 70
30
90
40, 70
90
Hình 1.1: CSDL gốc
CSDL trong hình 1.2 đã được sắp xếp theo mã khách hàng (customer-id) và thời gian
giao dịch.
Customer Id Transaction Time Items Bought
1 June 25 '93 30
- 14 -
Khai phá luật dãy Nguyễn Đình Văn1 June 30 '93 90
2
2
2
June 10 '93
June 15 '93
June 20 '93
10, 20
30

kiện giàng buộc hỗ trợ, và là các mẫu dãy mong muốn. Mẫu dãy <(30) (90)> xuất hiện
trong các giao dịch của khách hàng 1 và 4. Mẫu dãy <(30) (40 70)> xuất hiện trong
giao dịch của khách hàng 2 và 4.(Vì (40 70) là tập con của (40 60 70) nên cũng được
tính cho khách hàng 2).
Ví dụ về một dãy mà không có hỗ trợ tối thiểu là dãy <(10 20) (30)>, dãy này chỉ
xuất hiện trong giao dịch của khách hàng 2. Các dãy <(30)>, <(40)>, <(70)>,
<(90)>, <(30) (40)>, <(30) (70)>, <(40 70)> mặc dù thỏa mãn hỗ trợ tối thiểu, nhưng
chúng không phải dãy tối đa nên không phải là kết quả cần tìm.
Sequential Patterns with support > 25%
<(30) (90)>
<(30) (40 70)>
Hình 1.4: Tập kết quả
1.2.2 Một số ứng dụng
 Khai phá dãy cho các mẫu hành vi người dùng trong lĩnh vực thương mại điện
thoại di động [7]
Sự phát triển của máy tính và các công nghệ truyền thông gần đây giúp cho các
hệ thống liên lạc cá nhân (Personal Communication Systems - PCSs) ngày càng trở
nên phổ biến, đặt ra vấn đề về quản lý thông tin di động.
- 15 -
Khai phá luật dãy Nguyễn Đình Văn Mô hình hóa một cách hiệu quả các mẫu hành vi của người sử dụng trong các hệ
thống điện thoại di động đem lại lợi ích không chỉ cho người sử dụng trong những truy
cập thông minh, mà còn đem lại lợi nhuận tài chính cho các nhà cung cấp dịch vụ di
động như quảng cáo. Trong môi trường web, người sử dụng di động có thể yêu cầu các
loại hình dịch vụ khác nhau và ứng dụng của điện thoại di động, PDA hay máy tính
xách tay từ bất cứ đâu tại bất kỳ thời gian nào thông qua GSM, GPRS hoặc mạng
không dây. Rõ ràng là những hành vi của người sử dụng điện thoại di động (trong đó
vị trí và dịch vụ vốn đã cùng tồn tại) trở nên phức tạp hơn so với các hệ thống web

- 16 -
Khai phá luật dãy Nguyễn Đình Văn Nhằm khắc phục những hạn chế trên, người ta đã phát triển một thuật toán dự
đoán di động hiệu quả. Những qui luật này được gọi là các mẫu di động. Sau đó, các
luật di động này được trích xuất ra từ các mẫu di động. Các quy tắc di động được gắn
với quỹ đạo hiện tại của một người sử dụng điện thoại di động, và được sử dụng cho
các dự đoán hướng di chuyển tiếp theo của người dùng. Thuật toán dự đoán này là
khai phá các mẫu di động của người dùng và sinh ra các luật di động, được thực hiện
offline bởi hệ thống. Tuy nhiên, dự báo di chuyển được thực hiện online. Điều đó có
nghĩa là bất cứ khi nào người dùng có ý định thực hiện một di chuyển trong một khu
vực nhất định, một yêu cầu dự đoán sẽ được gửi đến hệ thống và dự đoán được thực
hiện bởi hệ thống bằng cách sử dụng các luật di động dựa trên thuật toán dự đoán.
Hình 1.5: Kiến trúc tổng thể của hệ thống quản lý thông tin di động
1.2.3 Luật dãy và luật kết hợp: một số đối sánh
Vấn đề của luật kết hợp là tìm kiếm các mẫu thường xuyên, các liên kết, các mối
tương quan, hoặc các cấu trúc có quan hệ nhân quả giữa tập các phần tử hoặc các đối
tượng trong các CSDL giao dịch, CSDL quan hệ, các kho thông tin khác. Lĩnh vực
khai phá luật kết hợp được phát triển với nhiều mục đích như thực hiện phân tích thói
quen mua bán hàng, trong đó cần tìm những mặt hàng được mua với nhau nhiều nhất.
Như trong khai phá web, khai phá luật kết hợp tìm các trang web liên quan được truy
cập theo đợt, điều đó sẽ cung cấp những ước tính nhất định về xác suất truy cập web.
Ví dụ như “Nếu một người truy cập trang CNN thì có đến 60% khả năng họ sẽ truy
cập trang ABC News trong tháng đó”.
Trong khi đó, vấn đề của luật dãy là tìm kiếm các mẫu có liên quan đến yếu tố
thời gian trên một CSDL dãy (các phần tử được sắp thứ tự), ví dụ như CSDL nhật ký
duyệt web. Khai phá luật dãy được xem là mở rộng của khai phá luật kết hợp, vì luật
kết hợp chỉ khảo sát các mẫu không có liên quan đến yếu tố thời gian. Khai phá luật
dãy có vai trò rất quan trọng trong nhiều ứng dụng thực tế, ví dụ như việc phát hiện tri

1
và s
2
). Một phương pháp
khác sử dụng nguyên lý "Generating-Pruning" là PSP (Masseglia et al., 1998). Sự
khác biệt chính với GSP là các ứng viên cũng như các dãy phổ biến được quản lý
trong một cấu trúc hiệu quả hơn. Các phương pháp trình bày cho đến nay được thiết kế
để phụ thuộc ít nhất có thể vào bộ nhớ chính. Vì chúng cần phải tải toàn bộ CSDL
(hoặc một ánh xạ của CSDL) trong bộ nhớ chính. Phương pháp này đạt hiệu quả cao
khi CSDL có thể phù hợp với bộ nhớ.
Cust

June 04, 2004 June 05, 2004 June 06, 2004

June 07, 2004
C1 Camcorder, MiniDV Digital Camera MemCard USB Key
C2 Camcorder, MiniDV DVD Rec, DVD-R Video Soft
C3 DVD Rec, DVD-R MemCard Video Soft USB Key
C4 Camcorder, MiniDV Laptop DVD Rec, DVD-R

Hình 1.6: Các dãy dữ liệu của 4 khách hàng mua trong 4 ngày
 Phương pháp dựa trên định dạng dọc (Vertical format-based method)
Trong (Zaki, 2001), tác giả đề xuất thuật toán SPADE (Sequential PAttern
Discovery using Equivalent Class – Khai phá mẫu dãy sử dụng lớp tương đương). Ý
tưởng chính của phương pháp này là một phân cụm các dãy phổ biến dựa trên các tiền
tố phổ biến của chúng và tính các dãy ứng viên nhờ một ánh xạ của CSDL (nạp trong
bộ nhớ chính). SPADE chỉ cần quét CSDL ba lần để trích xuất các mẫu dãy. Lần quét
đầu tiên nhằm tìm kiếm các phần tử thường xuyên, lần thứ hai để tìm kiếm các dãy
phổ biến có độ dài 2 (length 2) và lần cuối cùng để kết hợp các dãy phổ biến có độ dài
2, một bảng chứa định danh tương ứng của các dãy và tập các phần tử trong CSDL (ví

trợ (50%). Mặt khác, mẫu dãy <(Camcorder, MiniDV)> là mẫu dãy đóng vì nó được
chứa trong mẫu dãy s
1
nhưng có độ hỗ trợ là 75%, khác với độ hỗ trợ của s
1
là 50%.
Thuật toán đầu tiên cho việc trích xuất các mẫu dãy đóng là CloSpan (Yan et al.,
2003) với việc phát hiện các mẫu tuần tự không đóng, tránh được một số lượng lớn các
lần gọi đệ quy. Thuật toán CloSpan dựa trên việc phát hiện các mẫu tuần tự có độ dài
2, ví dụ như “A luôn xảy ra trước hoặc sau B”. Xét CSDL trong hình 1.6, chúng ta biết
rằng <(DVD Rec) (Video Soft)> là một mẫu thường xuyên. Các tác giả của thuật toán
CloSpan đề xuất các phương pháp liên quan để chứng minh rằng <(DVD-R)> luôn
luôn xảy ra trước <(Video Soft)>. Dựa vào quan sát này, CloSpan có thể chỉ ra rằng
<(Rec DVD, DVD-R) (Video Soft)> là mẫu thường xuyên mà không cần bất kỳ lần
quét CSDL nào nữa.
Thuật toán BIDE (Wang và Han, 2004) là mở rộng của thuật toán CloSpan như
sau. Đầu tiên, thông qua một phần mở rộng dãy mới, được gọi là BI-Directional
Extension, thuật toán sử dụng cả hai phương pháp là mẫu tiền tố và kiểm tra thuộc tính
đóng để phát triển. Thứ hai, để lược bớt không gian tìm kiếm sâu hơn so với phương
pháp tiếp cận trước, thuật toán đề nghị một phương pháp lược bớt gọi là BackScan. Ý
tưởng chính của phương pháp này là để tránh mở rộng dãy bằng cách phát hiện trước
phần mở rộng đã được chứa trong một dãy rồi.
- 19 -
Khai phá luật dãy Nguyễn Đình Văn Khai phá mẫu dãy tăng dần (Incremental Mining of Sequential Patterns)
Khi CSDL phát triển, vấn đề duy trì các mẫu dãy trong một thời gian dài trở nên
rất cần thiết vì một số lượng lớn các bản ghi mới có thể được thêm vào CSDL. Để
phản ánh hiện trạng của CSDL, ở đó các mẫu dãy trước đó sẽ trở nên không thích hợp

DigiCam MemCard
USB Key

Camcorder,
MiniDV
DVD Rec,
DVD-R
Video Soft
DVD Rec,
DVD-R
MemCard

Video Soft USB Key

Camcorder,
MiniDV
Laptop DVD Rec,
DVD-R

- 20 -
Khai phá luật dãy Nguyễn Đình VănCamcorder: 3
MiniDV: 3
DigiCam: 1


độ thay đổi không đáng kể. Kết hợp với các giải pháp hiệu quả, những vấn đề này có
thể phù hợp với dữ liệu thực tế có mốc thời gian (timestamp) (khi mà luật kết hợp đã
không giải quyết được) và cung cấp những kết quả hữu ích.
Ta sử dụng CSDL giao dịch mua bán hàng làm ví dụ, với các thông tin về: định
danh của dãy hoặc định danh khách hàng (sequence-id or customer-id), thời gian giao
dịch (transaction-time) và mặt hàng liên quan trong giao dịch (item). Một CSDL như
vậy được gọi là CSDL dãy. Chính xác hơn, mỗi giao dịch là một tập hợp các mặt hàng
(itemset) và mỗi dãy là một danh sách các giao dịch được sắp xếp theo thời gian giao
dịch. Đối với hiệu quả của việc trợ giúp ra quyết định, mục đích là để tìm ra những
thói quen tiêu biểu của người dùng. Để làm được việc đó, đòi hỏi phải có một CSDL
dãy và đưa ra giá trị hỗ trợ tức là số lần xuất hiện trong CSDL. Một mẫu dãy phổ biến
là một dãy mà tần xuất xuất hiện trong CSDL vượt ngưỡng quy định. Vấn đề tìm kiếm
tất cả các mẫu thường xuyên từ lượng dữ liệu khổng lồ đòi hỏi chi phí về mặt thời gian
là rất lớn. Thông thường, việc kiểm tra của tất cả các kết hợp có thể trong dữ liệu là
vấn đề khó và những thuật toán mới tập trung vào dữ liệu dãy được coi là quan trọng
đối với một tổ chức.
Khai phá luật dãy có thể được áp dụng rộng rãi trên các ứng dụng từ nhiều loại
dữ liệu có thời gian liên quan. Ví dụ, từ một CSDL mua bán hàng, một mẫu dãy có thể
được dùng để phát triển các chiến lược tiếp thị và sản phẩm; Bằng cách phân tích
weblog, các mẫu dãy rất hữu ích cho việc xây dựng website công ty giúp khách hàng
truy cập một cách dễ dàng các liên kết phổ biến nhất (Kosala và Blockeel, 2000); Ta
cũng có thể thấy CSDL báo động mạng viễn thông, phát hiện xâm nhập (Hu và Panda,
2004), các dãy ADN (Zaki, 2003), …
Chúng ta chia vấn đề khai phá luật dãy thành các giai đoạn sau đây:
 Giai đoạn sắp xếp (Sort Phase): CSDL (D) được sắp xếp, với mã khách hàng
(custorm-id) là khóa chính và thời gian giao dịch (transaction-time) là khóa phụ. Bước
này chuyển đổi ngầm cơ sơ dữ liệu giao dịch gốc thành CSDL dãy khách hàng.
 Giai đoạn Litemset (Litemset Phase): Trong giai đoạn này, chúng ta tìm tập tất cả
litemsets L, đồng thời cũng tìm kiếm tập tất cả các dãy phổ biến 1-sequence, vì tập này
cũng là {<l> | l  L}.

là một litemset.
CSDL chuyển đổi này gọi là D
T.
Tiếp tục sử dụng CSDL trong phần 1.2 làm ví
dụ, việc chuyển đổi CSDL Hình 1.3 được thể hiện trong Hình 2.1. Ví dụ, trong trong
việc chuyển đổi dãy khách hàng với Id 2, giao dịch (10 20) bị loại bỏ vì nó không chứa
bất kỳ litemset nào và giao dịch (40 60 70) được thay thế bằng tập litemsets {(40),(70),
(40 70)}.
Customer

Id
Original
Customer Sequence

Transformed
Customer Sequence
After Mapping
1
2

3
4

5
< (30) (90)>
< (10 20) (30)
(40 60 70) >
< (30 50 70)>
< (30) (40 70) (90)>


phổ biến (large sequences). Giai đoạn này được kết hợp với giai đoạn dãy (Sequence
Phase) để giảm chi phí thời gian trong việc tính các dãy không tối đa.
Tập tất cả các dãy phổ biến S được tìm thấy trong giai đoạn dãy, thuật toán tiếp
theo đây có thể được sử dụng để tìm các dãy tối đa. Với n là độ dài của dãy dài nhất.
for ( k = n; k > 1; k – – ) do
foreach k-sequence s
k
do
Delete from S all subsequences of s
k

2.2 Các thuật toán khởi thủy
Phần này giới thiệu ba thuật toán cơ bản khai phá luật dãy bao gồm: AprioriAll,
AprioriSome, GSP. Đây là những thuật toán rất phổ biến trong khai phá luật dãy.
2.2.1 Thuật toán AprioriAll
 Thuật toán AprioriAll
L
1
= {large 1-sequences}; // Result of the litemset phase
for ( k = 2; L
k-1
≠Ø; k++ ) do
begin
C
k
New candidates generated from L
k-1
(see Apriori Candidate Generation).
foreach customer-sequence c in the database do
Increment the count of all candidates in C


select p.litemset
1
, p.litemset
2
, , p.litemset
k-1
, q.litemset
k-1

from L
k-1
p, L
k-1
q
where p.litemset
1
= q.litemset
1
, . . ., p.litemset
k-2
= q.litemset
k-2
;
Next, delete all sequences c  C
k
such that some (k-1)-subsequence of c is not
in L
k-1
:

2
2
3
2
2
Hình 2.4: Large 3-Sequences

<1 2 3 4>
<1 2 4 3>
<1 3 4 5>
<1 3 5 4>
Hình 2.5: Candidate 4-Sequences (after join)

<1 2 3 4>
Hình 2.6: Candidate 4-Sequences (after pruning)
Ta cần chứng minh rằng C
k
 L
k
. Rõ ràng là bất kỳ dãy con nào của một dãy phổ
biến cũng cần có độ hỗ trợ tối thiểu. Do đó, nếu ta mở rộng mỗi dãy trong L
k-1
với tất
cả tập các phần tử phổ biến có thể, sau đó xóa tất cả những dãy mà có dãy con (k-1)-
- 25 -
Khai phá luật dãy Nguyễn Đình Vănsubsequences của chúng mà không nằm trong L
k-1

viên nào được tạo trong lần duyệt thứ 5. Các dãy phổ biến tối đa là ba dãy như hình
2.12.
<{1 5} {2} {3} {4}>
<{1} {3} {4} {3 5}>
<{1} {2} {3} {4}>
<{1} {3} {5}>
<{4} {5}>
Hình 2.7: Dãy khách hàng

Sequence Support
<1>
<2>
<3>
<4>
<5>
4
2
4
4
2
Hình 2.8: Dãy phổ biến 1-sequences

Sequence Support
<1 2>
<1 3>
<1 4>
<1 5>
<2 3>
<2 4>
<3 4>