ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ
TRUYỀN THÔNG

TRẦN THỊ THU TRANG KHAI PHÁ LUẬT KẾT HỢP
TỪ DỮ LIỆU CHUỖI THỜI GIAN

LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH Thái Nguyên - 2012
ii

LỜI CAM ĐOAN
Tôi xin cam đoan luận văn “Khai phá luật kết hợp từ dữ liệu chuỗi thời
gian” là công trình nghiên cứu của riêng tôi dƣới sự hƣớng dẫn của PGS.TS.
Bùi Thế Hồng. Toàn bộ phần mềm do chính tôi lập trình và kiểm thử. Tôi xin
chịu trách nhiệm về lời cam đoan của mình.
Các số liệu và thông tin sử dụng trong luận văn này hoàn toàn là trung
thực.

2.2. Khai phá luật kết hợp 27
iv

2.2.1. Khai phá luật kết hợp từ cơ sở dữ liệu 27
2.2.2. Khai phá luật kết hợp từ dữ liệu chuỗi thời gian 28
2.3. Thuật toán khai phá luật kết hợp từ dữ liệu chuỗi thời gian 30
2.3.1. Thuật toán khai phá luật kết hợp từ dữ liệu thƣờng 30
2.3.2. Thuật toán khai phá luật kết hợp từ dữ liệu chuỗi thời gian 40
CHƢƠNG 3: XÂY DỰNG CHƢƠNG TRÌNH THỬ NGHIỆM 53
3.1. Phát biểu bài toán 53
3.2. Xây dựng chƣơng trình 54
KẾT
LUẬN
63
TÀI LIỆU THAM KHẢO 64

v

DANH MỤC HÌNH VẼ
Hình 1.1. Quá trình phát hiện tri thức trong cơ sở dữ liệu 8
Hình 1.2. Đồ thị thể hiện thành phần xu hƣớng dài hạn 15
Hình1.3. Đồ thị thể hiện thành phần mùa 16
Hình 1.4. Đồ thị thể hiện thành phần chu kỳ 16
Hình 1.5. Trung bình trƣợt hàm mũ 17
Hình 2.1. Một cây mẫu thƣờng xuyên 39
Hình 2.2. FP-Tree và CFP-Tree 42
Hình 2.3: Các khoản mục đƣợc ánh xạ 44

vii

DANH MỤC CÁC KÝ HIỆU, CÁC TỪ VIẾT TẮT
Các từ viết tắt
Nghĩa tiếng anh
Nghĩa tiếng việt
FI
Frequent Itemset
Tập mục thƣờng xuyên
FCI
Frequent Closed Itemset
Tập mục thƣờng xuyên
đóng
MFI
Maximally Frequent
Itemset
Tập mục thƣờng xuyên
lớn nhất

Với sự bùng nổ và phát triển của công nghệ thông tin đã mang lại nhiều
hiệu quả đối với khoa học cũng nhƣ các hoạt động thực tế, trong đó khai phá
dữ liệu là một trong những lĩnh vực mang lại hiệu quả thiết thực cho con
ngƣời. Khai phá dữ liệu đã giúp ngƣời sử dụng thu đƣợc những tri thức hữu
ích từ những cơ sở dữ liệu hoặc các kho dữ liệu khổng lồ khác. Luận văn đề
cập đến các khái niệm và vấn đề cơ bản trong khai phá luật kết hợp từ dữ liệu
chuỗi thời gian đƣợc áp dụng trong cơ sở dữ liệu bán hàng.
Luận văn cấu trúc gồm 3 chƣơng:
Chƣơng 1:
Trong chƣơng 1 tìm hiểu khái quát về khai phá dữ liệu và dữ liệu chuỗi
thời gian và phƣơng pháp tiền xử lý dữ liệu chuỗi thời gian.
Chƣơng 2:
Trong chƣơng 2 sẽ tìm hiểu phƣơng pháp khai phá dữ liệu từ chuỗi thời
gian qua thuật toán ITARM dựa trên cấu trúc cây CFPTree.

2

Chƣơng 3:
Trong chƣơng 3 tiến hành cài đặt thuật toán ở chƣơng 2 và cài đặt ứng
dụng của thuật toán trên cơ sở dữ liệu bán hàng.
Luận văn này đƣợc hoàn thành dƣới sự hƣớng dẫn tận tình của PGS.TS
Bùi Thế Hồng, em xin bày tỏ lòng biết ơn chân thành của mình đối với thầy.
Em xin chân thành cảm ơn các thầy, cô giáo Viện Công nghệ thông tin,
Trƣờng Đại học Công nghệ thông tin và Truyền thông - Đại học Thái Nguyên
đã tham gia giảng dạy, giúp đỡ em trong suốt qúa trình học tập nâng cao trình
độ kiến thức. Tuy nhiên vì điều kiện thời gian và khả năng có hạn nên luận
văn không thể tránh khỏi những thiếu sót. Em kính mong các thầy cô giáo và
các bạn đóng góp ý kiến để đề tài đƣợc hoàn thiện hơn.
khái niệm đó đƣợc xem nhƣ hai lĩnh vực tƣơng đƣơng nhau. Nhƣng, nếu phân
chia một cách tách bạch thì khai phá dữ liệu là một bƣớc chính trong quá trình
khám phá tri thức.
1.1.2. Nhiệm vụ của khai phá dữ liệu
Các bài toán liên quan đến khai phá dữ liệu về bản chất là các bài
toán thống kê. Điểm khác biệt giữa các kỹ thuật khai phá dữ liệu và các
công cụ phục vụ tính toán thống kê mà chúng ta đã biết là ở khối lƣợng cần
tính toán. Một khi dữ liệu đã trở nên khổng lồ thì những khâu nhƣ: thu thập
dữ liệu, tiền xử lý và xử lý dữ liệu đều đòi hỏi phải đƣợc tự động hóa. Tuy
4

nhiên ở công đoạn cuối cùng, việc phân tích kết quả sau khi đã khai phá dữ
liệu vẫn luôn là công việc của con ngƣời.
Do là một lĩnh vực đa ngành, khai phá dữ liệu thu hút các lĩnh vực
khoa học khác nhƣ trí tuệ nhân tạo, cơ sở dữ liệu, marketing, toán học, vận
trù học, nhận dạng mẫu, tính toán thống kê …
Điều mà khai phá dữ liệu có thể làm rất tốt là phát hiện ra những giả
thuyết mạnh trƣớc khi sử dụng những công cụ tính toán thống kê. Mô hình
dự báo sử dụng kỹ thuật phân cụm để chia nhóm các sự vật, sự kiện sau đó
rút ra các luật nhằm tìm ra đặc trƣng cho mỗi nhóm và cuối cùng đề nghị
một mô hình. Ví dụ, những bạn đọc đăng ký dài hạn của một tạp chí có thể
phân nhóm dựa theo nhiều tiêu chí khác nhau (lứa tuổi, giới tính, thu
nhập…), sau đó tạp chí căn cứ vào đặc trƣng riêng của từng nhóm để đề ra
mức phí thu trong năm sao cho phù hợp nhất.
Chúng ta thấy những nhiệm vụ cơ bản nhất của khai phá dữ liệu là:
- Phân cụm, phân loại, phân nhóm, phân lớp. Nhiệm vụ là trả lời
câu hỏi: Một dữ liệu mới thu thập sẽ thuộc về nhóm nào? Quá trình này
thƣờng đƣợc thực hiện một cách tự động.
- Khai phá luật kết hợp. Nhiệm vụ là phát hiện ra những mối
quan hệ giống nhau của các bản ghi giao dịch. Luật kết hợp X=>Y có dạng

sánh mẫu theo chu kỳ và phân tích dữ liệu dựa trên tính tƣơng tự.
1.1.3. Triển khai việc khai phá dữ liệu
Một nhóm các tác giả đề nghị triển khai quá trình khai phá dữ liệu
theo 5 bƣớc:
Bƣớc 1: Xác định rõ mục tiêu thƣơng mại cần khai phá.
Bƣớc 2: Chuẩn bị dữ liệu (Thu thập, tiền xử lý, chuyển đổi
khuôn dạng dữ liệu nếu thấy cần thiết)
Bƣớc 3: Khai phá dữ liệu (Chọn thuật toán thích hợp)
Bƣớc 4: Phân tích kết quả thu đƣợc (Xem có gì thú vị không?)
6

Bƣớc 5: Tiêu hóa các tri thức thu lƣợm đƣợc (Nhằm đề ra kế
hoạch khai thác các thông tin mới)
Một tác giả khác cũng nói tới quy trình 5 bƣớc của khai phá dữ liệu,
với quan điểm gần giống nhƣ trên:
1.
Chiết xuất, biến đổi và nạp dữ liệu vào hệ thống kho dữ liệu.
2. Lƣu trữ và quản trị dữ liệu trong một cơ sở dữ liệu nhiều chiều
3.
Xác định mục tiêu cần khai phá (Sử dụng các công cụ phân
tích về mặt tác nghiệp)
4.
Sử dụng các phần mềm phân tích dữ liệu để khai phá dữ liệu
5.
Thể hiện kết quả khai phá dƣới khuôn dạng hữu ích hay bảng
biểu, đồ thị.
1.1.4. Một số ứng dụng khai phá dữ liệu
Ở thập kỷ 90 của thế kỷ XX, ngƣời ta coi khai phá dữ liệu là quá trình
phân tích cơ sở dữ liệu nhằm phát hiện ra các thông tin mới và giá trị,
thƣờng thể hiện dƣới dạng các mối quan hệ chƣa biết đến giữa các biến số.

triệu USD; hay áp dụng khai phá dữ liệu vào phân tích các lần đăng nhập
Web vào các trang liên quan đến thị trƣờng để phát hiện sở thích khách
hàng, từ đó đánh giá hiệu quả của việc tiếp thị qua Web và cải thiện hoạt động
của các Website.
1.1.5. Quá trình phát hiện tri thức trong cơ sở dữ liệu
Khám phá tri thức trong cơ sở dữ liệu là lĩnh vực liên quan đến các
ngành nhƣ: thống kê, học máy, cơ sở dữ liệu , thuật toán, trực quan hoá dữ
liệu, tính toán song song và hiệu năng cao,…
Mục đích của quá trình phát hiện tri thức là rút ra tri thức từ dữ liệu
trong cơ sở dữ liệu lớn. Quá trình phát hiện tri thức trong cơ sở dữ liệu là quá
8

trình gồm nhiều giai đoạn và lặp lại, mà trong đó sự lặp lại có thể xuất hiện ở
bất cứ bƣớc nào.
Quá trình đó có thể đƣợc mô tả theo hình sau: Hình 1.1. Quá trình phát hiện tri thức trong cơ sở dữ liệu
Bước thứ nhất: Hình thành, xác định và định nghĩa bài toán. Là
tìm hiểu lĩnh vực ứng dụng từ đó hình thành bài toán, xác định các nhiệm vụ
cần phải hoàn thành. Bƣớc này sẽ quyết định cho việc rút ra đƣợc các tri thức
hữu ích và cho phép chọn các phƣơng pháp khai phá dữ liệu thích hợp với
mục đích ứng dụng và bản chất của dữ liệu.
Bước thứ hai: Thu thập và tiền xử lý dữ liệu. Là thu thập và xử lý
thô, còn đƣợc gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu (làm sạch dữ liệu),
xử lý việc thiếu dữ liệu (làm giàu dữ liệu), biến đổi dữ liệu và rút gọn dữ liệu
nếu cần thiết, bƣớc này thƣờng chiếm nhiều thời gian nhất trong toàn bộ qui

đoán dựa vào các suy diễn trên dữ liệu hiện thời. Các kỹ thuật này gồm có:
Phân lớp (classification), hồi quy (regession)…
Tuy nhiên, chỉ có một số phƣơng pháp thông dụng nhất là: Phân cụm
dữ liệu, phân lớp dữ liệu, phƣơng pháp hồi quy và khai phá luật kết hợp.
1.1.6.1. Phân cụm dữ liệu:
Mục tiêu chính của phƣơng pháp phân cụm dữ liệu là nhóm các đối
10

tƣợng tƣơng tự nhau trong tập dữ liệu vào các cụm sao cho các đối tƣợng
thuộc cùng một lớp là tƣơng đồng còn các đối tƣợng thuộc các cụm khác
nhau sẽ không tƣơng đồng. Phân cụm dữ liệu là một ví dụ của phƣơng pháp
học không có thầy. Không giống nhƣ phân lớp dữ liệu, phân cụm dữ liệu
không đòi hỏi phải định nghĩa trƣớc các mẫu dữ liệu huấn luyện. Vì thế có
thể coi phân cụm dữ liệu là một cách học bằng quan sát, trong khi phân lớp
dữ liệu là học bằng ví dụ. Trong phƣơng pháp này bạn không thể biết kết
quả các cụm thu đƣợc sẽ thế nào khi bắt đầu quá trình. Vì vậy, thông thƣờng
cần có một chuyên gia về lĩnh vực đó để đánh giá các cụm thu đƣợc. Phân
cụm dữ liệu đƣợc sử dụng nhiều trong các ứng dụng về phân đoạn thị
trƣờng, phân đoạn khách hàng, nhận dạng mẫu, phân loại trang Web…
Ngoài ra phân cụm dữ liệu còn có thể đƣợc sử dụng nhƣ một bƣớc tiền xử lý
cho các thuật toán khai phá dữ liệu khác.
1.1.6.2. Phân lớp dữ liệu:
Mục tiêu của phƣơng pháp 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 phân lớp dữ liệu thƣờng gồm hai bƣớc: Xây
dựng mô hình và sử dụng mô hình để phân lớp dữ liệu.
- Bƣớc 1: Một mô hình sẽ đƣợc xây dựng dựa trên việc phân tích
các mẫu dữ liệu sẵn có. Mỗi mẫu tƣơng ứng với một lớp, đƣợc quyết định
bởi một thuộc tính gọi là thuộc tính lớp. Các lớp dữ liệu này còn đƣợc gọi là
lớp dữ liệu huấn luyện. Các nhãn lớp của tập dữ liệu huấn luyện đều phải
đƣợc xác định trƣớc khi xây dựng mô hình.

60% có nghĩa là: 60% các khách hàng mua máy tính cũng mua phần mềm.
Khai phá luật kết hợp đƣợc thực hiện qua hai bƣớc:
Bƣớc 1: Tìm tất cả các tập mục phổ biến, một tập mục phổ biến
đƣợc xác định qua tính hỗ trợ và thỏa mãn độ hỗ trợ cực tiểu.
12

Bƣớc 2: Sinh ra các luật kết hợp mạnh từ tập mục phổ biến, các
luật phải thỏa mãn độ hỗ trợ cực tiểu và độ tin cậy cực tiểu.
Phƣơng pháp này đƣợc sử dụng rất hiệu quả trong các lĩnh vực nhƣ
maketing có chủ đích, phân tích quyết định, quản lý kinh doanh, phân tích
giá thị trƣờng …
1.1.7. Những khó khăn trong khai phá dữ liệu
Việc nghiên cứu và ứng dụng kỹ thuật khai phá dữ liệu gặp nhiều khó
khăn, nhƣng không phải là không giải quyết đƣợc mà chúng cần đƣợc tìm
hiểu để có thể phát triển tốt hơn. Những khó khăn phát sinh trong khai phá dữ
liệu chính là dữ liệu trong thực tế thƣờng động, không đầy đủ, lớn và bị nhiễu.
Trong trƣờng hợp khác, ngƣời ta không biết cơ sở dữ liệu có chứa thông tin
cần thiết cho việc khai thác hay không và làm thế nào để giải quyết sự dƣ thừa
thông tin không thích hợp này.
- Dữ liệu lớn: Hiện nay các cơ sở dữ liệu với hàng trăm trƣờng và
bảng, hàng triệu bản ghi với kích thƣớc rất lớn, có thể lên đến GB. Các
phƣơng pháp giải quyết hiện nay là đƣa ra một ngƣỡng cho cơ sở dữ liệu, lấy
mẫu, các phƣơng pháp tính xấp xỉ, xử lí song song.
- Kích thƣớc lớn: không chỉ có số lƣợng bản ghi mà số các trƣờng
trong cơ sở dữ liệu cũng nhiều. Vì vậy mà kích thƣớc của bài toán trở nên lớn
làm tăng không gian tìm kiếm. Hơn nữa, nó cũng làm tăng khả năng một
thuật toán khai phá dữ liệu có thể tìm thấy các mẫu giả. Biện pháp khắc phục
là làm giảm kích thƣớc tác động của bài toán và sử dụng các tri thức biết
trƣớc để xác định các biến không phù hợp.
- Dữ liệu động: Đặc điểm cơ bản của hầu hết các cơ sở dữ liệu là

trạng “quá độ” dữ liệu (nghĩa là tìm kiếm quá mức cần thiết gây ra hiện
tƣợng chỉ phù hợp với dữ liệu đó mà không có khả năng đáp ứng cho các dữ
14

liệu lạ), làm cho mô hình hoạt động rất kém đối với các dữ liệu thử. Các giải
pháp khắc phục nhƣ đánh giá chéo, thực hiện theo nguyên tắc nào đó hoặc sử
dụng các biện pháp thống kê khác.
- Khả năng biểu đạt mẫu: Trong rất nhiều ứng dụng, điều quan
trọng là những điều khai thác đƣợc phải càng dễ hiểu với con ngƣời càng tốt.
Vì vậy, các giải pháp thƣờng bao gồm việc diễn tả dƣới dạng đồ họa, xây
dựng cấu trúc luật với các đồ thị có hƣớng, biểu diễn bằng ngôn ngữ tự nhiên
và kỹ thuật khác nhằm biểu diễn các tri thức và dữ liệu.
- Sự tƣơng tác với ngƣời sử dụng các tri thức sẵn có: Rất nhiều
công cụ và phƣơng pháp khai phá dữ liệu không thực sự tƣơng tác với ngƣời
dùng và không dễ dàng kết hợp cùng với các tri thức đã biết trƣớc đó. Việc
sử sụng tri thức miền là rất quan trọng trong khai phá dữ liệu. Đã có nhiều
biện pháp nhằm khắc phục vấn đề này nhƣ sử dụng cơ sở dữ liệu suy diễn
để phát hiện tri thức, những tri thức này sau đó đƣợc sử dụng để hƣớng dẫn
cho việc tìm kiếm khai phá dữ liệu hoặc sử dụng sự phân bố xác suất dữ liệu
trƣớc đó nhƣ một dạng mã hóa tri thức có sẵn.
1.2. Dữ liệu chuỗi thời gian
1.2.1. Khái niệm
1.2.1.1. Khái niệm chuỗi thời gian
Một chuỗi thời gian là một bộ sƣu tập quan sát các hạng mục dữ liệu
đƣợc xác định thông qua các phép đo lặp đi lặp lại theo thời gian.
Ví dụ, việc đo lƣờng giá trị của doanh số bán lẻ mỗi tháng trong năm
sẽ bao gồm một chuỗi thời gian. Điều này là do doanh thu bán hàng đƣợc xác
định rõ và thống nhất đo tại khoảng cách đều nhau. Số liệu thu thập đột xuất
hoặc chỉ một lần không phải là chuỗi thời gian.
15

X
t

t

t

Xu hƣớng giảm theo thời gian

16
Hình 1.3. Đồ thị thể hiện thành phần mùa
c. Thành phần chu kỳ
Thành phần này chỉ sự thay đổi của đại lƣợng X theo chu kỳ. Sự
khác biệt của thành phần này so với thành phần mùa là chu kỳ của nó dài hơn
một năm. Để đánh giá thành phần chu kỳ các giá trị của chuỗi tuần tự theo
thời gian sẽ đƣợc quan sát hàng năm.
Ví dụ:
Lƣợng dòng chảy đến hồ chứa Trị An từ năm 1959 đến 1985

/s) 1959 1960 1985 t(năm) 17

d. Thành phần bất thƣờng
Thành phần này dùng để chỉ những sự thay đổi bất thƣờng của các
giá trị trong chuỗi thời gian. Sự thay đổi này không thể dự đoán bằng các số
liệu kinh nghiệm trong quá khứ, về mặt bản chất này không có tính chu kỳ.
1.2.2. Tiền xử lý dữ liệu chuỗi thời gian
Dữ liệu thô ban đầu của cơ sở dữ liệu chuỗi thời gian thƣờng có nhiều
nhiễu và không đầy đủ. Vì vậy, trƣớc khi thực hiện các giải thuật khai phá dữ
liệu, ngƣời ta phải thực hiện quá trình tiền xử lý dữ liệu, hay còn gọi là quá
trình làm sạch dữ liệu mà thực chất là thực hiện việc lọc dữ liệu. Công đoạn
này nhằm mục đích nhận đƣợc những thông tin chính xác, đầy đủ và đáng tin
cậy hơn với càng ít nhiễu càng tốt[8].
Giả sử, dữ liệu thô a
raw

t) là giá trị EMA tại thời điểm (t -

t)
X(t) là dữ liệu thô tại thời điểm t.
Để chọn hệ số α cho quá trình lọc dữ liệu, ngƣời ta dựa vào đặc điểm
của mối liên hệ của đối tƣợng quan sát giữa các khoảng thời gian liền kề
nhau. Do các đối tƣợng biến đổi theo thời gian thƣờng có tính chất là: sự biến
đổi của các chu kỳ tiếp theo, các nhà phân tích dữ liệu thƣờng sử dụng các giá
trị của dãy số Fibonacci để thiết lập hệ số α.
Trong bài toán chúng ta sẽ chọn:
α = 1 / T, T  {8,13,55} (1.3)
Ở đây, sở dĩ ta chọn tập hợp ba giá trị là bởi vì khi phân tích xu hƣớng
biến đổi của các đối tƣợng biến đổi theo thời gian chúng ta cần phải kết hợp
thành phần tĩnh (giá trị α nhỏ - T =55), và thành phần động (giá trị α lớn hơn
– T=(8,13)).
Ta có công thức lọc dữ liệu cụ thể nhƣ sau: Close(t) là giá Close tại thời điểm t, EMA(t) là giá trị trung bình trƣợt
hàm mũ tại thời điểm t, EMA(t -

t) là giá trị trung bình trƣợt hàm mũ tại thời
điểm (t -

t).
Ở đây Close(t) chính là hàm thuộc tính, còn EMA(t) – là xấp xỉ của nó
trên khoảng thời gian

t.
1