..

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------CHU THỊ THỊNH

CHU THỊ THỊNH

CÔNG NGHỆ THÔNG TIN

PHÁT HIỆN CÁC MẪU HỮU ÍCH TRONG
CƠ SỞ DỮ LIỆU GIAO DỊCH

LUẬN VĂN THẠC SĨ KỸ THUẬT
CƠNG NGHỆ THƠNG TIN

KHỐ 2016B
Hà Nội – Năm 2019


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
--------------------------------------CHU THỊ THỊNH

PHÁT HIỆN CÁC MẪU HỮU ÍCH TRONG
CƠ SỞ DỮ LIỆU GIAO DỊCH

CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN

LUẬN VĂN THẠC SĨ KỸ THUẬT
CÔNG NGHỆ THÔNG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC
PGS.TS NGUYỄN THỊ KIM ANH

Hà Nội – Năm 2019
2


MỤC LỤC
Trang phụ bìa
Lời cam đoan
Danh mục các ký hiệu, các chữ viết tắt
Danh mục các bảng
Danh mục các hình vẽ, đồ thị
MỞ ĐẦU
Chương 1 - TỔNG QUAN
1.1 Giới thiệu bài toán thực tiễn
1.2 Phát biểu bài toán tổng quát
Chương 2 - KỸ THUẬT SỬ DỤNG
2.1 Một số định nghĩa cở sở trong khai phá mẫu chuỗi
2.1.1 Cơ sở dữ liệu chuỗi
2.1.2 Độ hỗ trợ của chuỗi
2.1.3 Phép toán mở rộng chuỗi
2.1.4 Khai phá mẫu chuỗi
2.1.5 Cơ sở dữ liệu ngang
2.1.6 Cơ sở dữ liệu dọc
2.2 Một số thuật toán khai phá mẫu chuỗi
2.2.1 Giới thiệu thuật toán khai phá mẫu chuỗi
2.2.2 Thuật toán GSP
2.2.3 Thuật toán SPADE và SPAM

2.2.4 Thuật toán CM-SPAM và CM-SPADE
2.2.5 Thuật toán PrefixSpan
2.2.6 Nhận xét về các thuật toán
Chương 3 - ỨNG DỤNG THỰC TẾ
3.1 Môi trường và công nghệ sử dụng
3.2 Áp dụng vào hệ thống thực tế
3.2.1 Giới thiệu hệ thống thực tế
3.2.2 Cách thực hiện
3.2.3 Tiền xử lý dữ liệu
3.2.4 Xây dựng cấu trúc dữ liệu thuật tiện cho việc khai phá
3.2.5 Lựa chọn giá trị minsup để thử nghiệm
3.2.6 Thử nghiệm với các thuật tốn
3.2.7 Tích hợp vào hệ thống thực tế
Chương 4 - KẾT QUẢ VÀ BÀN LUẬN
4.1 Kết quả đạt được
4.2 Phân tích kết quả
4.3 Hướng phát triển
KẾT LUẬN VÀ KIẾN NGHỊ
TÀI LIỆU THAM KHẢO
3

Trang
2
4
5
6
7
8
10
10

12
14
14
14
15
16
17
17
17
19
19
20
23
27
32
35
38
38
40
40
41
41
42
44
45
50
58
58
58
60

61
62


LỜI CAM ĐOAN
Tôi xin cam đoan đề tài “Phát hiện các mẫu hữu ích trong Cơ sở dữ liệu giao
dịch” là một cơng trình độc lập khơng có sự sao chép của người khác. Đề tài là một
sản phẩm mà tơi đã nỗ lực nghiên cứu trong q trình học tập tại trường cũng như
làm việc tại Công ty Cổ phần Olbius Việt Nam. Trong q trình viết bài, tơi có tham
khảo một số tài liệu, bài báo có nguồn gốc rõ ràng và đã liệt kê đầy đủ trong tài liệu
tham khảo, dưới sự hướng dẫn của PGS. TS Nguyễn Thị Kim Anh.
Tơi xin cam đoan nếu có bất cứ vấn đề gì liên quan tới nội dung trong luận văn, tơi
xin chịu hồn tồn trách nhiệm.
Hà Nội, ngày 15 tháng 04 năm 2019
Tác giả luận văn

4


DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
Ký hiệu/Từ viết tắt

Ý nghĩa

CSDL

Cơ sở dữ liệu

SBD


Cơ sở dữ liệu chuỗi (Sequence database)

Support

Độ hỗ trợ của chuỗi

Minsup

Ngưỡng độ hỗ trợ tối thiểu

Bitvector

Vector thành phần là các bit

CMAP

Cấu trúc ánh xạ đồng xuất hiện (Co-occurrence Map)

5


DANH MỤC CÁC BẢNG
Bảng 1: Một cơ sở dữ liệu chuỗi ................................................................................ 15
Bảng 2: Biểu diễn bitvector cho CSDL dọc .............................................................. 27
Bảng 3: CMAPi và CMAPs cho CSDL trong Bảng 1 và minsup=2 ......................... 29
Bảng 4: CSDL chiếu của mẫu chuỗi <{a}> .............................................................. 33
Bảng 5: Kết quả chạy các thuật toán với minsup lần lượt 3.0%, 1.0% .................... 45
Bảng 6: Kết quả chạy các thuật toán với minsup lần lượt 0.9%, 0.8%, 0.7%, 0.6% 46
Bảng 7: Kết quả chạy các thuật toán với minsup lần lượt 0.5%, 0.4%, 0.3%, 0.2% 47


6


DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1: Biểu diễn dọc của một CSDL ngang ............................................................ 18
Hình 2: Cấu trúc bảng CSDL giao dịch thực tế......................................................... 41
Hình 3: Cấu trúc bảng CSDL giao dịch thực tế sau khi lọc ...................................... 43
Hình 4: So sánh hiệu năng 6 thuật tốn theo thời gian với giá trị minsup giảm dần 47
Hình 5: So sánh lượng bộ nhớ sử dụng khi chạy 6 thuật tốn với giá trị minsup giảm
dần............................................................................................................................... 49
Hình 6: Giao diện thực hiện chạy khai phá mẫu chuỗi và kết quả trả về ................. 53
Hình 7: Giao diện chạy khai phá mẫu chuỗi ............................................................. 54
Hình 8: Giao diện kết quả khai phá mẫu chuỗi ......................................................... 54
Hình 9: Màn hình lưu file kết quả sau khi chạy khai phá mẫu chuỗi ....................... 55
Hình 10: Nội dung file kết quả khai phá mẫu chuỗi ................................................. 56
Hình 11: Màn hình xem chi tiết các mẫu chuỗi kết quả tại một lượt chạy ............... 56
Hình 12: Màn hình lưu file Excel chứa danh sách mẫu chuỗi kết quả ..................... 57
Hình 13: Màn hình nội dung file Excel chứa danh sách mẫu chuỗi kết quả ............ 57

7


MỞ ĐẦU
Trong thời đại ngày nay, công nghệ thông tin đã là một phần không thể thiếu
trong các lĩnh vực khác nhau của đời sống xã hội. Khi mọi thứ đều được tin học
hóa, lượng dữ liệu thu nhập được nhiều hơn, sẽ xuất hiện các cơ hội và thách thức
khác nhau dựa trên nguồn dữ liệu đó để thu thập các thơng tin hữu ích phục vụ con
người. Bằng cách phân tích dữ liệu thơ đã thu thập được, có thể thu được rất nhiều
thơng tin hữu ích. Khi này, một bài tốn được đặt ra đó là cần lấy thơng tin gì và xử
lý dữ liệu thơ như thế nào. Để giải bài toán như vậy, chủ đề khai phá dữ liệu đã

được nghiên cứu rộng rãi và áp dụng tại nhiều nơi và trên nhiều lĩnh vực.
Áp dụng vào thực tế, tôi đang làm việc tại Công ty cổ phần Olbius Việt Nam,
chuyên cung cấp phần mềm ERP cho các doanh nghiệp phân phối, hiện tại đang
cung cấp hệ thống bán hàng tại các cửa hàng tạp hóa bán lẻ Co.opSmile, với quy
mơ vài trăm cửa hàng phân bố tập trung tại khu vực thành phố Hồ Chí Minh. Lượng
dữ liệu thu được trong q trình bán hàng tại cửa hàng cũng rất phong phú, tốc độ
gia tăng dữ liệu nhanh. Bản thân tự nhận thấy những cơ hội đối với lượng dữ liệu đó
nên đã liên hệ tới PGS. TS Nguyễn Thị Kim Anh, cô đã giúp tôi định hướng được
đề tài mà tôi cần thực hiện đó là “Phát hiện các mẫu hữu ích trong Cơ sở dữ liệu
giao dịch”.
Nhiệm vụ chính của luận văn là phát hiện các mẫu hữu ích từ bộ CSDL giao
dịch thực tế đang có để phân tích các chuỗi sản phẩm mà người dùng thường xuyên
mua sắm tại các cửa hàng tạp hóa bán lẻ. Để giải quyết bài tốn cá nhân, luận văn
cũng sẽ trình bày bài tốn tổng quát và sử dụng phương pháp khai pháp khai phá
cho bài tốn tổng qt đó. Phương pháp khai phá được sử dụng trong luận văn này
là khai phá mẫu chuỗi trong CSDL chuỗi. Việc phát hiện các mẫu chuỗi cũng có
nhiều ứng dụng khác trong cuộc sống như phân tích giỏ hàng, phân tích tính tương
tác trên các trang web, phân tích chuỗi văn bản, … nhưng trong luận văn này sẽ
trình bày ứng dụng phát hiện mẫu hữu ích để phân tích các chuỗi sản phẩm mà
người dùng thường xuyên mua tại các cửa hàng tạp hóa bán lẻ.
Để hồn thành luận văn, tơi đã đi theo phương pháp nghiên cứu như sau:
8


- Phân tích CSDL giao dịch hiện tại đang có để tìm ra mục tiêu thơng tin cần
khai thác. Phát biểu bài toán tổng quát từ bài toán cá nhân đang có.
- Nghiên cứu các thuật tốn phổ biến hiện nay để giải quyết bài toán tổng quát.
Chọn một số thuật toán phổ biến, tiến hành thử nghiệm trên bộ dữ liệu thực
tế. Từ đó, phân tích chọn ra một thuật toán phù hợp nhất để áp dụng vào hệ
thống thực tế.

- Áp dụng thuật toán đã chọn vào hệ thống đang có, triển khai cho khách hàng
sử dụng. Thêm một số tiện ích để tăng tốc việc xử lý dữ liệu trong thực tế.
Nhận được định hướng, hướng dẫn của cô Nguyễn Thị Kim Anh và việc
nghiên cứu của bản thân, tơi đã hồn thành được các u cầu đề ra. Nhưng do thời
gian thực hiện luận văn có hạn và kiến thức của tơi cịn hạn chế, nên việc thiếu sót
là khơng thể tránh khỏi, tơi nhất mong nhận được sự hướng dẫn góp ý của các thầy
cơ và các bạn để có một sản phẩm hồn thiện hơn trong thời gian tới.
Để có được kết quả như ngày hôm nay, em xin chân thành cảm ơn cô Nguyễn
Thị Kim Anh đã hướng dẫn em rất tận tình trong thời gian qua. Và em cũng cảm
ơn Công ty Cổ phần Olbius Việt Nam đã tạo điều kiện cho em thực hiện luận văn
này.
Em xin chân thành cảm ơn!
Hà Nội, ngày 15 tháng 04 năm 2019
Tác giả luận văn
Chu Thị Thịnh

9


Chƣơng 1 -

TỔNG QUAN

1.1 Giới thiệu bài toán thực tiễn
Hiện tại, tôi đang làm việc tại Công ty Cổ phần Olbius Việt Nam, chuyên cung
cấp giải pháp ERP cho các doanh nghiệp phân phối, và đang cung cấp hệ thống bán
hàng tại các cửa hàng tạp hóa bán lẻ Co.opSmile, với quy mô vài trăm cửa hàng
phân bố tập trung tại khu vực thành phố Hồ Chí Minh.
Ngày nay, với sự cạnh tranh không ngừng của ngành bán lẻ, việc đưa ra các
thơng tin phân tích thị trường, phân tích hành vi người dùng để nâng cao khả năng

chăm sóc, đáp ứng đúng nhu cầu của khách hàng từ đó giữ khách hàng cũ và thu hút
thêm khách hàng mới là bài toán cấp thiết cần đặt ra với các doanh nghiệp phân
phối bán lẻ. Và cũng là thách thức đối với các doanh nghiệp cung cấp hệ thống
thông tin cho các doanh nghiệp phân phối này. Bằng việc cung cấp hệ thống thông
tin cho các đối tượng khách hàng trên, công ty tôi cần phải đưa ra những giải pháp
mới, công cụ mới để hỗ trợ khách hàng tốt hơn. Bản thân cá nhân nhận thấy vấn đề
như trên, tơi đã suy nghĩ tới việc phân tích, khai phá sâu hơn về nguồn dữ liệu đang
có. Thay vì chỉ cung cấp các công cụ tạo báo cáo, biểu đồ cho họ từ nguồn dữ liệu
hoạt động hiện tại.
Đặc điểm của nguồn dữ liệu khách hàng hiện tại của tôi như sau: số lượng
khách hàng thân thiết khá lớn trên phạm vi chuỗi cửa hàng được triển khai. Dữ liệu
liên quan tới các chuỗi giao dịch mua hàng tiêu dùng hằng ngày của khách hàng.
Lượng dữ liệu gia tăng nhanh. Với đặc điểm trên, tôi đã liên hệ tới cô Nguyễn Thị
Kim Anh, cô đã giúp tôi xác định được hướng phân tích, khai phá nguồn dữ liệu
trên để thu được kết quả mong muốn. Với nguồn dữ liệu là các giao dịch bán hàng
tại cửa hàng bán lẻ, có nhiều hướng khai phá dữ liệu như:
- Khai phá tập mục thường xuyên: là quá trình tìm các mục thường xuất hiện
cùng nhau trong một CSDL giao dịch của khách hàng. Từ các tập mục này,
các doanh nghiệp có thể đưa ra các quyết định chiến lược khác nhau để tăng
doanh thu như đồng quảng bá sản phẩm, đồng giảm giá và khuyến mại.
10


Hướng khai thác này sẽ không quan tâm tới thứ tự các giao dịch. Chính vì
vậy, khi áp dụng trên các bộ dữ liệu có thời gian hoặc thơng tin về thứ tự
giao dịch thì thơng tin thứ tự này sẽ bị loại bỏ. Đối với nhiều lĩnh vực, thứ tự
các sự kiện là quan trọng. Ví dụ, đối với phân tích văn bản, thứ tự các từ
trong câu là quan trọng; đối với phân tích thói quen khách hàng, thì thứ tự
các giao dịch mua hàng là quan trọng.
- Khai phá mẫu chuỗi thường xuyên: là quá trình phát hiện các chuỗi thú vị

trong một tập hợp các chuỗi. Nó có nhiều ứng dụng trong thực tế như phân
tích tình trạng bệnh của bệnh nhân, phân tích văn bản, phân tích thói quen
người tiêu dùng. Khai phá mẫu chuỗi thường xuyên đã khắc phục được
nhược điểm bỏ qua thông tin liên quan tới thứ tự sự kiện xuất hiện trong khai
phá tập mục thường xuyên. Từ đó có thể phát hiện ra các mẫu chuỗi hữu ích
hơn cho người dùng.
Qua q trình phân tích với nguồn dữ liệu thực tế, để có thể tận dụng nhiều
thơng tin hơn, tơi đã chọn hướng khai phá mẫu chuỗi thường xuyên và nhận đề tài
luận văn là “Phát hiện các mẫu hữu ích trong Cơ sở dữ liệu giao dịch”. Với đề
tài này, bài toán đặt ra đã rõ ràng hơn như sau: từ nguồn dữ liệu đang có, tơi sẽ cần
phát hiện được các mẫu chuỗi được coi là hữu ích. Việc đánh giá hữu ích có nhiều
lựa chọn như độ dài chuỗi, tần suất xuất hiện. Trong đó tơi lựa chọn đánh giá mức
độ hữu ích qua tần suất xuất hiện, chính bằng số lần xuất hiện của mẫu trong các
chuỗi mua sắm của khách hàng khác nhau. Khi đó có thể hiểu, mẫu nào được thực
hiện bởi nhiều khách hàng thì mẫu đó được coi là hữu ích. Sẽ có một ngưỡng làm
căn cứ cho phép xác định các mẫu cần xuất hiện trong bao nhiêu chuỗi mới được
gọi là hữu ích.
Để giải quyết bài tốn này, tơi đã đi theo phương pháp nghiên cứu như sau:
- Phân tích CSDL giao dịch hiện tại đang có để tìm ra mục tiêu thơng tin cần
khai thác. Phát biểu bài tốn tổng qt từ bài tốn cá nhân đang có.
- Nghiên cứu các thuật toán phổ biến hiện nay để giải quyết bài toán tổng quát.
Chọn một số thuật toán phổ biến, tiến hành thử nghiệm trên bộ dữ liệu thực
11


tế. Từ đó, phân tích chọn ra một thuật tốn phù hợp nhất để áp dụng vào hệ
thống thực tế.
- Áp dụng thuật toán đã chọn vào hệ thống đang có, triển khai cho khách hàng
sử dụng. Thêm một số tiện ích để tăng tốc việc xử lý dữ liệu trong thực tế.
Đi theo phương pháp nghiên cứu phía trên, tôi đã xây dựng cấu trúc luận văn

gồm các phần như sau:
- Chương 1: Giới thiệu bài toán thực tế cần giải quyết. Trình bày một số
hướng nghiên cứu với bộ dữ liệu thực tế, và lựa chọn hướng nghiên cứu cụ
thể để giải quyết bài toán đặt ra. Từ đó phát biểu bài tốn tổng qt để có thể
áp dụng các phương pháp phổ biến hiện nay đã được chứng minh để giải bài
toán ban đầu.
- Chương 2: Nêu những khái niệm cơ sở để giải quyết bài toán. Trình bày một
số thuật tốn khai phá mẫu chuỗi phổ biến hiện nay. Phân tích ưu điểm và
nhược điểm của các thuật tốn, từ đó đánh giá hiệu năng của các thuật toán.
- Chương 3: Giới thiệu bộ dữ liệu thực tế. Tiến hành thử nghiệm các thuật tốn
đã tìm hiểu trên bộ dữ liệu đó. Phân tích và đánh giá kết quả, lựa chọn ra một
thuật toán phù hợp nhất áp dụng vào hệ thống triển khai cho khách hàng sử
dụng.
- Chương 4: Trình bày và phân tích những kết quả đạt được sau quá trình thử
nghiệm trên bộ dữ liệu thực. Nêu ra hướng nghiên cứu phát triển trong tương
lai.
1.2 Phát biểu bài toán tổng quát
CSDL giao dịch trong các cửa hàng tạp hóa bán lẻ là CSDL chứa thông tin
liên quan tới các lần mua hàng khác nhau của khách hàng tại cửa hàng đó. Một lần
mua hàng của khách hàng được gọi là một giao dịch, CSDL giao dịch chứa tập các
giao dịch. Một giao dịch chứa các sản phẩm được mua cùng nhau tại một thời điểm,
được thực hiện bởi một khách hàng tại một cửa hàng. Như vậy, sẽ có tập các giao
dịch được thực hiện bởi một khách hàng, tập các giao dịch này là có thứ tự, các sản
12


phẩm trong một giao dịch là khơng có thứ tự. Tổng quát, gọi tập giao dịch đó là một
“chuỗi” được thực hiện bởi một khách hàng.
Như vậy, CSDL giao dịch có thể được chuyển đổi thành một CSDL tương ứng
gọi là CSDL chuỗi, bao gồm các chuỗi được thực hiện bởi các khách hàng khác

nhau. Mỗi giao dịch được gọi là một tập mục, các tập mục trong chuỗi là có thứ tự
(theo thời gian mua hàng của khách hàng). Mỗi tập mục chứa các mục tương ứng
với từng sản phẩm trong 1 giao dịch, giữa các mục không phân biệt thứ tự (do các
sản phẩm trong một giỏ hàng sẽ khơng tính tới thứ tự, thứ tự của các sản phẩm này
là khơng có quy luật xác định, ví dụ như còn phụ thuộc vào thứ tự lấy hàng, thứ tự
nhân viên tính tiền cho khách, thứ tự sắp xếp hàng hóa trong cửa hàng).
Bài tốn đặt ra cần tìm các mẫu chuỗi hữu ích. Trong đó, một mẫu chuỗi được
xác định là hữu ích có thể dựa vào một số yếu tố như độ dài của mẫu chuỗi, số lần
chuỗi được thực hiện bởi các khách hàng khác nhau. Trong bài tốn này, tơi coi một
mẫu chuỗi là hữu ích khi nó có số lần xuất hiện bởi các khách hàng khác nhau thỏa
mãn ngưỡng nào đó do người dùng đặt ra (tần suất xuất hiện của mẫu chuỗi trong
các chuỗi giao dịch khách hàng).
Vậy bài toán khai thác mẫu hữu ích trong CSDL giao dịch có thể quy về bài
tốn tổng qt đó là khai phá mẫu chuỗi thường xuyên trong CSDL chuỗi.
Nhiệm vụ của khai phá mẫu chuỗi thường xuyên trong CSDL chuỗi là tìm tất cả các
mẫu chuỗi thỏa mãn điều kiện xuất hiện tại nhiều hơn hoặc bằng một số lượng
chuỗi giao dịch của khách hàng nào đó. Giới hạn nhỏ nhất do người dùng quyết
định, khi đó các chuỗi thỏa mãn điều kiện được gọi là hữu ích đối với người dùng.
Vấn đề khai phá mẫu chuỗi là một bài toán liệt kê tổ hợp, nhằm mục đích liệt
kê ra được tất cả các mẫu có lần xuất hiện (gọi là độ hỗ trợ) không nhỏ hơn ngưỡng
(độ hỗ trợ tối thiểu) mà người dùng đã thiết lập. Cách đơn thuần nhất là tính tốn độ
hỗ trợ của tất cả các chuỗi con có thể trong CSDL chuỗi, sau đó sẽ trả về các chuỗi
con thỏa mãn điều kiện ngưỡng độ hỗ trợ. Cách này khơng hiệu quả, vì số lượng
các chuỗi con có thể rất lớn khi chuỗi cha là dài. Giả sử, một chuỗi có q mục, như
vậy có thể có (

) chuỗi con khác nhau. Giải thích:
13



- Cách chọn:
o Số các chuỗi có 1 mục:

cách

o Số các chuỗi có 2 mục:

cách

o …
o Số các chuỗi có q mục:

cách

- Dựa theo đăng thức rút ra từ nhị thức Newton trong Tổ hợp có:

- Như vậy, tổng số chuỗi sẽ bằng
Hàm

là hàm tăng rất nhanh so với giá trị x. Như vậy, để giải quyết vấn đề

khai phá mẫu chuỗi cần các thuật toán hiệu quả hơn việc tính tốn đơn thuần như
trên, tránh việc cần qt tồn bộ khơng gian chuỗi trong CSDL chuỗi. Một số thuật
tốn khai phá mẫu chuỗi phổ biến hiện nay là GSP [8], SPADE [3], SPAM [2],
CM-SPADE [4], CM-SPAM [4] và PrefixSpan [1]. Trong phần tiếp theo của luận
văn, tôi sẽ đi phân tích các thuật tốn này để tìm ra thuật toán áp dụng hiệu quả cho
bài toán đã đặt ra trong thực tiễn.

Chƣơng 2 -


KỸ THUẬT SỬ DỤNG

2.1 Một số định nghĩa cở sở trong khai phá mẫu chuỗi
2.1.1 Cơ sở dữ liệu chuỗi
Cho

là một danh sách các mục, tương ứng với danh sách các

sản phẩm mà cửa hàng tạp hóa kinh doanh.
Một tập mục

(trong đó

) là một tập các

mục khác nhau không phân biệt thứ tự. Tương ứng với tập các sản phẩm khác nhau
trong một giao dịch mua hàng. Khơng mất tính tổng qt, giả sử rằng tất cả các mục
trong tập mục được sắp xếp theo thứ tự từ điển, ký hiệu
là độ dài của tập mục
Một chuỗi

, khi tập mục

chứa
(trong đó

. Ngồi ra, có

mục, ký hiệu | |


được gọi

.
) là một danh sách

có thứ tự các tập mục (tương ứng với danh sách các giao dịch có thứ tự của một
14


khách hàng). Chuỗi s được gọi là có độ dài
mục. Nói cách khác,
tập mục

| |

| |

hoặc -sequence khi chuỗi chứa
| |, chính bằng tổng độ dài của các

trong chuỗi s.

Một cơ sở dữ liệu chuỗi (SDB – Sequence database) là một danh sách các
chuỗi. Tương ứng với danh sách giao dịch của các khách hàng khác nhau. Ký hiệu:
có định danh chuỗi (SIDs) là 1, 2, ..., p.
Ví dụ, Bảng 1 biểu diễn một CSDL chuỗi.
SID

Chuỗi


1

<{a,b}, {c}, {f,g}, {g}, {e}>

2

<{a,d}, {c}, {b}, {a,b,e,f}>

3

<{a}, {b}, {f}, {e}>

4

<{b}, {f,g}>
Bảng 1: Một cơ sở dữ liệu chuỗi

CSDL chuỗi trong Bảng 1 có 4 chuỗi, có thể coi tương ứng với 4 chuỗi mua
sắm của 4 khách hàng khác nhau với các chuỗi có SID lần lượt là 1, 2, 3 và 4. Chuỗi
có SID bằng 1 có 5 tập mục lần lượt là {a,b}, {c}, {f,g}, {g} và {e} được sắp xếp
theo thứ tự thời gian thực hiện giao dịch. Tại tập mục đầu tiên {a,b} có 2 mục được
sắp xếp theo thứ tự từ điển là b

a.

2.1.2 Độ hỗ trợ của chuỗi
Một chuỗi

được gọi là được chứa trong một chuỗi
khi và chỉ khi tồn tại các số nguyên

, ký hiệu

sao cho
được chứa trong chuỗi

, thì chuỗi

. Nếu chuỗi

được gọi là chuỗi con của chuỗi

.

Ví dụ: chuỗi <{b}, {f,g}> được chứa trong chuỗi <{a,b}, {c}, {f,g}, {g},
{e}>, khi đó chuỗi <{b}, {f,g}> là chuỗi con của chuỗi <{a,b}, {c}, {f,g}, {g},
{e}>.

15


Độ hỗ trợ (support) của chuỗi
là số chuỗi chứa chuỗi

trong một CSDL chuỗi SDB được định nghĩa

, được ký hiệu là

. Độ hỗ trợ này được gọi là độ hỗ

trợ tuyệt đối (absolute support). Tổng qt hóa:

| |

|

Ngồi ra, có thể định nghĩa độ hỗ trợ của chuỗi là một tỉ số. Được gọi là độ hỗ
trợ tương đối (relative support), giá trị này được tính bằng số lượng các chuỗi chứa
chuỗi

chia tổng số lượng chuỗi trong CSDL chuỗi SBD. Tổng qt hóa:
|

|

Ví dụ: trong CSDL chuỗi tại Bảng 1, xét chuỗi s = <{b}, {f,g}> có:
- Độ hỗ trợ của chuỗi s bằng 2: sup(s) = 2, hay có thể nói độ hỗ trợ tuyệt đối
của s bằng 2, do có hai chuỗi là chuỗi 1 và chuỗi 4 chứa chuỗi s.
- Độ hỗ trợ tương đối của chuỗi s bằng 0.5: relsup(s) = sup(s)/|SDB| = 2/4 =
0.5.
2.1.3 Phép toán mở rộng chuỗi
Dựa vào định nghĩa tập mục, ta có các mục trong tập mục khơng phân biệt thứ
tự, nên khơng mất tính tổng qt, ta coi các mục được sắp xếp theo 1 thứ tự từ điển
(ký hiệu ). Như vậy, cũng có thể coi thứ tự này là thứ tự xử lý các mục trong một
CSDL chuỗi để tìm các mẫu chuỗi kết quả.
Các thuật tốn khai phá mẫu chuỗi đều tìm kiếm trên khơng gian dữ liệu bằng
2 phép toán cơ bản được gọi là s-extension (sequence-extension) và i-extension
(itemset-extension). Cả hai phép tốn này đều có mục đích tạo ra 1 chuỗi có độ dài
(k+1) từ 1 chuỗi có độ dài (k).
Tiền tố: chuỗi

được gọi là tiền tố của chuỗi


với mọi n < m khi và chỉ khi
chuỗi

bằng |

| mục đầu tiên của chuỗi

Phép s-extension: chuỗi
chuỗi

và
theo thứ tự từ điển.

được gọi là một chuỗi mở rộng s-extension của

với một mục , khi và chỉ khi chuỗi

16

là tiền tố của


chuỗi

và mục

n+1) trong chuỗi

thuộc tập mục đứng sau tất cả các tập mục của chuỗi

. Tổng quát:

Phép i-extension: chuỗi
chuỗi
chuỗi

.
được gọi là một chuỗi mở rộng i-extension của

với một mục , khi và chỉ khi chuỗi
và mục

thuộc tập mục cuối cùng của chuỗi

Tổng quát:

(mục

là tiền tố của

(mục n) trong chuỗi

.

.

2.1.4 Khai phá mẫu chuỗi
Cho một CSDL chuỗi SDB, và một ngưỡng độ hỗ trợ tối thiểu (minsupport –
gọi tắt là minsup) được thiết lập bởi người dùng. Chuỗi s được gọi là mẫu chuỗi
thường xuyên khi và chỉ khi độ hỗ trợ của chuỗi s không nhỏ hơn giá trị minsup đã

cho (sup(s)  minsup).
Mục tiêu của khai phá mẫu chuỗi là tìm ra tất cả các mẫu chuỗi thường xuyên.
2.1.5 Cơ sở dữ liệu ngang
Một CSDL chuỗi có định dạng dữ liệu ngang là một CSDL mà mỗi bản ghi là
một chuỗi. Ví dụ Bảng 1 là một biểu diễn của CSDL ngang.
2.1.6 Cơ sở dữ liệu dọc
Một CSDL chuỗi có định dạng dữ liệu dọc là một CSDL mà mỗi bảng đại
diện cho thông tin của một 1 mục, mỗi bản ghi là 1 cặp gồm mã chuỗi có chứa mục
đó và danh sác vị trí của các tập mục trong chuỗi nơi mà nó xuất hiện. Hình 1 là
một biểu diễn dọc của CSDL trong Bảng 1.

17


Hình 1: Biểu diễn dọc của một CSDL ngang
Với mỗi mục trong CSDL dọc, thông tin trong bảng đại diện cho mục đó được
gọi là IDList của mục. Biểu diễn dọc của một CSDL ngang là tập tất cả các IDList
của tất cả các mục đơn có trong CSDL đó. Có thể tạo các IDList của tất cả các mẫu
chỉ với một lần quét CSDL ngang 1 lần (và có thể chuyển từ CSDL dọc về CSDL
ngang), bằng cách quét CSDL ngang 1 lần để tạo IDList của các mẫu chứa 1 mục
đơn, IDList của các mẫu lớn hơn sẽ được tính bằng phép kết nối giữa IDList của
các mẫu nhỏ đã có sẵn. Tổng quát IDList, cho một mẫu
được chứa trong chuỗi
ký hiệu là

(
, là tập hợp các cặp có dạng

ngun thỏa mãn
IDList của mẫu


). Vị trí mục của
, trong đó

trong

là một số

mà

.

trong CSDL chuỗi SDB chính là tập hợp các vị trí mục của

trong tất cả các chuỗi mà nó xuất hiện. Tổng qt:
⋃
CSDL dọc có 2 tính chất hữu ích cho khai phá mẫu chuỗi:
- Tính chất 1: có thể tính tốn trực tiếp độ hỗ trợ của mẫu dựa vào IDList của
mẫu đó. Độ hỗ trợ chính bằng số lượng các chuỗi khác nhau trong IDList của
mẫu.
- Tính chất 2: cho mẫu

được tạo từ mẫu

và một phép mở rộng s-

extension hoặc i-extension với 1 mục i, có thể tạo IDList của một mẫu
18

mà



không cần quét CSDL gốc bằng cách kết nối IDList của mẫu

và IDList

của mục i.
2.2 Một số thuật toán khai phá mẫu chuỗi
2.2.1 Giới thiệu thuật toán khai phá mẫu chuỗi
Dựa theo thứ tự tìm kiếm có thể phân loại các thuật toán khai phá mẫu chuỗi
thành 2 loại:
- Thuật tốn tìm kiếm theo chiều rộng, cách thức xử lý như sau:
o Đầu tiên, quét CSDL gốc để tìm các chuỗi có độ dài 1 (chuỗi 1sequence) và là chuỗi thường xuyên.
o Sau đó, tạo chuỗi có độ dài 2 (chuỗi 2-sequence) bằng cách thực hiện
các phép mở rộng s-extension hoặc i-extenson từ chuỗi 1-sequence.
o Tiếp theo, tạo các chuỗi 3-sequence từ chuỗi 2-sequence, … cho tới
khi khơng cịn chuỗi nào có thể được tạo nữa.
- Thuật tốn tìm kiếm theo chiều sâu, cách thức thực hiện như sau:
o Đầu tiên, tìm các chuỗi 1-sequence
o Sau đó, thực hiện đệ quy các phép i-extension và s-extension với
chuỗi ban đầu để tạo các chuỗi lớn hơn.
o Tiếp theo, khi một chuỗi khơng thể dài thêm được nữa, thuật tốn sẽ
quay lui để tạo các mẫu khác từ các chuỗi khác.
Nhận xét 2 loại thuật tốn:
- Thuật tốn tìm kiếm theo chiều rộng: các thuật tốn tìm kiếm theo chiều rộng
có thể sẽ phải tìm kiếm trên khơng gian tìm kiếm rất lớn, do các chuỗi được
duyệt theo thứ tự độ dài của chúng. Giả sử, trong CSDL chuỗi có chứa
mục, trong trường hợp tệ nhất, thuật toán sẽ phải duyệt lên tới

chuỗi. Và


cần lưu trữ rất nhiều mẫu trong bộ nhớ.
- Thuật tốn tìm kiếm theo chiều sâu: khơng gian tìm kiếm cũng có thể lớn khi
chuỗi trong CSDL chuỗi là dài.

19


Khơng gian tìm kiếm của một CSDL chuỗi có thể rất lớn, do đó việc thiết kế
một thuật tốn hiệu quả để khai phá mẫu chuỗi là cần thiết. Và địi hỏi cần phải tích
hợp các kỹ thuật loại bỏ việc qt tất cả khơng gian tìm kiếm. Tính chất cơ bản
được sử dụng để cắt tỉa khơng gian tìm kiếm được gọi là tính chất “Apriori”.
Tính chất Apriori: cho bất kỳ 2 chuỗi
(

), thì

và

, nếu

là chuỗi con của chuỗi

phải có độ hỗ trợ nhỏ hơn hoặc bằng độ hỗ trợ của

. Như vậy,

độ hỗ trợ có tính chất đơn điệu. Hoặc có thể phát biểu như sau về tính chất Apriori:
trong các chuỗi k-sequence thường xuyên, một chuỗi k-sequence là thường xuyên
chỉ khi tất cả các chuỗi con của nó là thường xun.

Dựa vào tính chất Apriori, việc cắt trong khơng gian tìm kiếm được thực hiện
như sau: nếu một chuỗi là khơng thường xun, thì tất cả các chuỗi mở rộng của nó
cũng khơng thường xun. Như vậy, các chuỗi đó khơng phải là mẫu chuỗi cần tìm,
và khơng cần duyệt đến. Áp dụng tính chất Apriori, có thể giảm đáng kể khơng gian
tìm kiếm so với ban đầu.
Các thuật toán khai phá mẫu chuỗi sẽ khác nhau về:
- Phương pháp tìm kiếm chuỗi: theo chiều rộng hay chiều sâu;
- Loại CSDL biểu diễn: CSDL ngang, CSDL dọc;
- Cách sinh và xác định mẫu duyệt kế tiếp trong CSDL;
- Cách tính độ hỗ trợ của các mẫu.
Tiếp theo đây, sẽ giới thiệu một số thuật toán nổi tiếng trong khai phá mẫu
chuỗi gồm: thuật toán GSP [8], SPADE [3], SPAM [2], CM-SPADE [4], CMSPAM [4], PrefixSpan [1].
2.2.2 Thuật toán GSP
Thuật toán GSP [8] (Generalized Sequential Pattern Mining) là phiên bản
nâng cấp hơn so với thuật toán AprioriAll [7] bởi cùng nhóm tác giả. Thuật tốn
AprioriAll [7] là một thuật toán khai phá mẫu chuỗi được đề xuất sớm nhất. Các
thuật toán AprioriAll [7] và GSP [8] đều lấy cảm hứng từ thuật toán Apriori (thuật
toán Apriori là thuật tốn khai phá tập mục thường xun). GSP [8] có cách làm
20


việc giống với AprioriAll [7], nhưng GSP [8] không yêu cầu tìm tất cả các tập mục
thường xuyên trong lần đầu chạy. Thuật toán GSP [8] được thiết kế để khai phá các
mẫu chuỗi tổng quát. Ngoài ra, GSP [8] còn cho phép: đặt giới hạn về sự phân tách
thời gian giữa các tập mục liền kề trong một mẫu, đặt cửa sổ thời gian cho phép các
mục trong một tập mục mở rộng giao dịch, định nghĩa phân loại cho phép khám phá
mẫu ở các cấp độ khác nhau. Với bài toán đưa ra trong luận văn này, sẽ khơng sử
dụng 3 tham số riêng biệt có trong GSP [8]. Như vậy sẽ khơng xem xét tới nó và có
thể bỏ qua phần mở rộng trên.
Trong trường hợp mẫu chuỗi tổng quát, thuật toán GSP [8] sử dụng một CSDL

chuỗi chuẩn (giống Bảng 1), được gọi là CSDL ngang. Thuật tốn GSP [8] thực
hiện tìm kiếm theo chiều rộng để phát hiện các mẫu chuỗi thường xuyên.
Mã giả của thuật toán GSP:
Ký hiệu:
- SDB: CSDL chuỗi
- Fk là tập các chuỗi k-sequence
- Ck là tập các chuỗi ứng viên k-sequence
GSP (SDB, minsup)
1. Tạo các chuỗi có dạng <x> là các ứng viên 1-sequence
2. Quét CSDL 1 lần để tìm F1
3. k = 1;
4. While (Fk  ) do
5. Begin
6.
Ck+1 = APRIORI-GENERATE(Fk)
7.
If (Ck+1  ) do
8.
Begin
9.
For each (c  SDB)
10.
Tăng biến đếm của tất cả các chuỗi ứng viên trong Ck chứa c
11.
Fk+1 = tập các ứng viên trong Ck+1 thỏa mãn minsup.
12.
End If
13.
k=k+1;
14. End While

15. Trả về tập các chuỗi trong tập ⋃
;
APRIORI-GENERATE(Lk-1) //hàm sinh ứng viên mới từ tập Lk-1
1. Kết nối Lk-1 (chứa các chuỗi pi) với Lk-1 (chứa các chuỗi qj) theo quy tắc sau:
Thêm tập mục ở vị trí (k-1) của chuỗi q nối vào chuỗi p, được chuỗi k-sequence.
Ck = tập các chuỗi kết quả.
2. Xóa tất cả các chuỗi c  Ck mà tồn tại chuỗi con (k-1)-sequence của c  Lk-1.

21


Phân tích:
- Đầu tiên, GSP [8] quét CSDL để tính toán độ hỗ trợ của tất cả các chuỗi 1sequence. Sau đó, nó giữ lại tất cả các chuỗi 1-sequence trong bộ nhớ.
- Sau khi tạo các ứng viên, nó sẽ tính tốn độ hỗ trợ của mỗi ứng viên để chọn
ra các ứng viên có độ hỗ trợ khơng nhỏ hơn minsup và trả về kết quả.
Thuật toán GSP [8] kết thúc chỉ với 2 bước:
-

Đầu tiên, với một mẫu ứng viên
chuỗi con có độ dài k-1 của

, thuật tốn GSP [8] sẽ kiểm tra tất cả các

có phải là thường xun hay khơng. Nếu

có một chuỗi con khơng thường xun, thì

cũng khơng thể thường xun

(theo tính chất Apriori).

- Ngược lại, GSP [8] sẽ tiếp tục quét trong CSDL để tính tốn hỗ trợ của
nếu

,

là thường xun, nó sẽ trả về kết quả đầu ra.

Thuật toán GSP [8] được coi là thuật toán tốt nhất trong những thuật toán khai phá
mẫu chuỗi đầu tiên. Trong những năm gần đây, nhiều thuật tốn đã được giới thiệu
có hiệu năng tốt hơn GSP [8]. Do GSP [8] có một số hạn chế như:
- Quét nhiều lần CSDL: một trong những vấn đề của GSP [8] là số lần quét lặp
lại trong CSDL để tính tốn độ hỗ trợ của các mẫu ứng viên. Nó có thể rất
tốn kém trong CSDL lớn. Một số tối ưu hóa có thể giảm chi phí như các
chuỗi được sắp xếp trước theo kích thước để loại bỏ việc so sánh các mẫu dài
với các mẫu ngắn.
- Ứng cử viên không tồn tại: một vấn đề khác của GSP [8] là có thể các mẫu
tạo ra không tồn tại trong CSDL. Lý do GSP [8] tạo ra các ứng viên này là
do kết hợp các mẫu nhỏ hơn mà không quan tâm tới CSDL. Như vậy, GSP
[8] có thể lãng phí nhiều thời gian để xem xét các mẫu không tồn tại trong
CSDL.
- Giữ các ứng viên trong bộ nhớ: một vấn đề khác của GSP [8] là thuật tốn
tìm kiếm theo chiều rộng, ở bất kỳ thời điểm nào trong q trình chạy, nó
cũng phải giữ tồn bộ chuỗi thường xun có độ dài k trong bộ nhớ, để có
thể sinh các mẫu có độ dài k+1. Như vậy sẽ tốn kém lượng lớn bộ nhớ.
22


2.2.3 Thuật toán SPADE và SPAM
a. Thuật toán SPADE (Sequential Pattern Discovery using Equivalence classes)
Mã giả của thuật toán SPADE:

Ký hiệu:
- SDB: CSDL chuỗi
- V(SDB): CSDL biểu diễn dọc của CSDL chuỗi SDB
SPADE (SDB, minsup)
1. Quét SDB để tạo V(SDB) và khởi tạo là danh sách các mục đơn thường xuyên
ban đầu
2. ENUMERATE( , minsup)
ENUMERATE (một lớp tương đương F, minsup)
1. For each mẫu
2.
Trả về ;
3.
:= ;
4.
For each mẫu
, với j  i
5.
= MergePatterns( , )
6.
For each mẫu
7.
If sup( )  minsup then :=
8.
ENUMERATE( , minsup);

;

Phân tích:
Thuật tốn SPADE [3] có đầu vào là một CSDL chuỗi SDB và ngưỡng độ hỗ
trợ nhỏ nhất minsup. Thuật toán thực hiện các bước như sau:

- Đầu tiên SPADE [3] quét CSDL 1 lần để tạo cấu trúc biểu diễn dọc của
CSDL chuỗi ban đầu thu được CSDL dọc V(SDB) và tập các mục đơn
thường xuyên

.

- Sau đó, SPADE [3] gọi hàm ENUMERATE với lớp tương đương có kích
thước bằng 0. Một lớp tương đương có kích thước k được định nghĩa là tập
tất cả các mẫu thường xuyên chứa k mục có tiền tố giống nhau là (k-1) mục.
Chỉ có duy nhất một lớp tương đương có kích thước bằng 0 là lớp tương
đương

. Hàm ENUMERATE có 2 tham số là lớp tương đương F và

ngưỡng hỗ trợ tối thiểu minsup.
o Mỗi mẫu chuỗi

là thành viên của lớp tương đương đầu vào được

trả ra là mẫu chuỗi thường xuyên.
23


o Sau đó, biến

là lớp tương đương của tất cả các chuỗi mở rộng

thường xuyên của
o Sau đó, mỗi mẫu


được khởi tạo bằng tập rỗng.
), mẫu

(

được gộp với

để tạo các

mẫu lớn hơn. Kết quả của phép gộp là tập . Với mỗi mẫu thuộc tập
, tính tốn độ hỗ trợ của mẫu bằng cách kết nối giữa các IDList
của

và

. Nếu độ hỗ trợ của mẫu lớn hơn hoặc bằng minsup, thì

mẫu là một mẫu chuỗi thường xuyên. Bổ sung vào tập

. Cuối

cùng, sau khi tất cả các mẫu

sẽ chứa

được so sánh với

, tập

toàn bộ lớp tương đương của các mẫu bắt đầu từ tiền tố

gọi đệ quy hàm ENUMERATE với

. Tiếp theo,

và ngưỡng hỗ trợ tối thiểu

minsup để phát hiện các mẫu chuỗi lớn hơn.
o Khi tất cả các vòng lặp kết thúc, tất cả các mẫu chuỗi thường xuyên
được trả ra.
Nhận xét thuật toán SPADE:
Thuật toán SPADE [3] là một thuật tốn sử dụng tìm kiếm theo chiều sâu, và
loại bỏ một vài nhược điểm của thuật toán GSP [8]. Thuật toán SPADE [3] lấy cảm
hứng từ thuật toán Eclat (thuật tốn khai phá tập mục thường xun). Nó sử dụng
một CSDL dọc. Sử dụng các tính chất của CSDL dọc, thuật tốn SPADE [3] đã
thăm dị được tồn bộ khơng gian tìm kiếm của các mẫu bằng cách đọc CSDL duy
nhất 1 lần để tạo IDList của các mục đơn. Sau đó, tìm các mẫu lớn hơn bằng cách
kết nối các IDList của các mẫu nhỏ đơn đã có sẵn, và tính tốn độ hỗ trợ của mẫu.
Như vậy, tất cả các mẫu thường xuyên được duyệt hết mà không cần lặp lại việc
quét CSDL, và không cần lưu trữ quá nhiều mẫu trong bộ nhớ máy tính.

24


b. Thuật toán SPAM (Sequential Pattern Mining)
Mã giả của thuật toán SPAM:
Ký hiệu:
- SDB: CSDL chuỗi
- V(SDB): CSDL biểu diễn dọc của CSDL chuỗi SDB
SPAM (SDB, minsup)
1. Quét SDB để tạo V(SDB) và khởi tạo là danh sách các mục đơn thường xuyên

ban đầu
2. For each mục
3.
SEARCH(<{ }>, ,
|
, minsup).
SEARCH(pat, , , minsup)
1. Trả về kết quả mẫu pat.
2.
:=
:=
3. For each mục
,
4.
If (mở rộng s-extension của mẫu pat với mục là thường xuyên)
then
:=
5. For each mục
,
6.
SEARCH(mở rộng s-extension của mẫu pat với mục ,
,
|
, minsup)
7. For each mục
,
8.
If (mở rộng i-extension của mẫu pat với mục là thường xuyên)
then
:=

9. For each mục
,
10.
SEARCH(mở rộng i-extension của mẫu pat với mục ,
,
|
, minsup)

Phân tích:
Thuật tốn SPAM [2] có đầu vào là một CSDL chuỗi SDB và ngưỡng độ hỗ
trợ tối thiểu minsup. Thuật toán thực hiện các bước như sau:
- Đầu tiên SPAM [2] quét CSDL 1 lần để tạo cấu trúc biểu diễn dọc của CSDL
chuỗi ban đầu thu được CSDL dọc V(SDB) và tập các mục đơn thường
xuyên

.

- Tiếp theo, duyệt từng mục thường xuyên

, SPAM [2] gọi hàm

SEARCH với 3 tham số lần lượt là mẫu <{ }>, tập các mục đơn thường
xuyên
|

, tập con các mục thuộc

có thứ tự từ điển xếp sau mục

, và ngưỡng hỗ trợ tối thiểu minsup. Hàm SEARCH trả về mẫu


<{ }> và tiếp tục khám phá đệ quy các mẫu ứng viên bắt đầu bằng tiền tố
25