ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NHỆ
ĐÀO THẾ MẪN

ỨNG DỤNG PHÂN TÍCH MẪU CHUỖI TUẦN TỰ
VÀO VIỆC PHÁT HIỆN THÓI QUEN SỬ DỤNG
CÁC ỨNG DỤNG TRÊN THIẾT BỊ DI ĐỘNG Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60 48 05

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. NGUYỄN HÀ NAM
Chương 4 - THỰC NGHIỆM 30
4.1 Bộ dữ liệu thứ nhất 31
4.2. Bộ dữ liệu thứ 2 35
KẾT LUẬN 39
Phụ lục A – TÍNH KHOẢNG THỜI GIAN PHÂN TÁCH 40
Phụ lục B – MỘT SỐ KẾT QUẢ THỰC NGHIỆM CỤ THỂ 54
B1. Kết quả thực nghiệm bộ dữ liệu thứ 1 54
B2. Kết quả thực nghiệm Bộ dữ liệu thứ 2 61
TÀI LIỆU THAM KHẢO 71 2
DANH MỤC CÁC HÌNH VẼ

Hình 2.1 Dữ liệu thu được từ TBDĐ sử dụng Hệ điều hành Android 12
Hình 2.2 Dữ liệu ứng dụng gốc được lấy ra từ Hình 2.1 13
Hình 2.3. Giải thuật DFS với Kỹ thuật cắt tỉa 19
Hình 3.1 Mô hình tổng quát khai phá dữ liệu 20
Hình 3.2. Mô hình đề xuất tổng thể khai phá thói quen sử dụng phần mềm trên
TBDĐ 20
Hình 3.3. Phân tách dữ liệu theo các buổi trong ngày 22
Hình 3.4. Phân tách dữ liệu theo n ngày 22
Hình 3.5. Phân tách dữ liệu theo khoảng thời gian sử dụng 23
Hình 3.6. Phân tách dữ liệu theo thời gian trong cùng một Itemset 24
Hình 3.7. Trường hợp 1, 2 ứng dụng trong cùng một Itemset 24
Hình 3.8. Trường hợp 2, 2 ứng dụng trong cùng một Itemset 25
Hình 4.1 Giao diện của chương trình 30
Hình 4.2 Đồ thị so sánh giữa 2 giải pháp phân tách bộ dữ liệu 1 với minSup
={45% - 65%} 33
Hình 4.3 Đồ thị so sánh giữa 2 giải pháp phân tách bộ dữ liệu 1 với minSup

Bảng 4.3 Kết quả thử nghiệm trên bộ dữ liệu 2 phân tách theo hành vi 36
Bảng 4.4 Kết quả thử nghiệm trên bộ dữ liệu 2 phân tách theo ngày 36 5
MỞ ĐẦU
Hiện nay, xu hướng công nghệ phục vụ người tiêu dùng trên thế giới đang
chuyển sang công nghệ di động thể hiện qua việc rất nhiều hãng tên tuổi trên thế
giới đã và đang chuyển sang nghiên cứu, sản xuất đưa ra thị các thiết bị di động
(TBDĐ) thông minh như Sony, Philips, Panasonic, HP, Microsoft, Lenovo,
LG,…. Mỗi một TBDĐ bây giờ đã được tích hợp rất nhiều tính năng như: điện
thoại, máy ảnh, máy quay phim, thiết bị multi media, máy tính, điều khiển từ xa,
để phục vụ ngày càng nhiều nhu cầu của người dùng như liên lạc, giải trí, khai
thác thông tin, xử lý công việc, kinh doanh trực tuyến, điều khiển các thiết bị từ
xa,… của khách hàng.
Nhu cầu sử dụng các TBDĐ thông minh đang là một xu hướng không biên
giới giữa các quốc gia, giữa các tầng lớp dân chúng. Chính vì vậy, các hãng sản
xuất đã liên tục tung ra các dòng sản phẩm mới nhằm chiếm lĩnh thị trường cũng
như cạnh tranh với các đối thủ. Từ đó, nhu cầu nghiên cứu về những hành vi,
thói quen, xu hướng sử dụng của người dùng trên các TBDĐ đang được đặt ra
một cách cấp thiết cho tất cả các hãng sản xuất.
Nghiên cứu hành vi, thói quen, mạng xã hội của những người dùng trên
TBDĐ đang là một trong những đề tài nóng bỏng trên thế giới hiện nay, nó phục
vụ cho nhiều ngành khác nhau như tâm lý, xã hội, chiến lược kinh doanh của các
hãng sản xuất,…. Do đó, chúng tôi đã lựa chọn đề tài nghiên cứu thói quen sử
dụng phần mềm trên các TBDĐ để làm đề tài khóa luận tốt nghiệp này.
Nghiên cứu hành vi, thói quen sử dụng các phần mềm trên TBDĐ sẽ là
bước đầu tiên cho việc nghiên cứu các ngành khác trên TBDĐ như tâm lý, mạng
xã hội, vì mỗi phần mềm đó đều thuộc vào một trong các lớp ứng dụng trên
thiết bị (như lớp nhạc, lớp phim, lớp game, lớp tài chính, lớp liên lạc, …).

triển các ứng dụng trên TBDĐ.
Việc nắm bắt được các thói quen, hành vi của người dùng đang là một
trong những vấn đề cấp thiết được đặt ra cho các doanh nghiệp sản xuất hoặc
kinh doanh các phần mềm trên TBDĐ. Nếu các kết quả nghiên cứu mang tính
khả quan thì từ đó người ta có thể đưa ra được các chiến lược kinh doanh hoặc
các chiến lược phát triển các phần mềm tiềm năng như phần mềm tích hợp, các
phần mềm cần được nâng cấp, cải tiến, ….
Dữ liệu log file trên các TBDĐ lưu trữ những hoạt động mà người dùng sử
dụng trong TBDĐ như dữ liệu về cuộc gọi, dữ liệu về tin nhắn, dữ liệu về các
ứng dụng, dữ liệu về vị trí, dữ liệu về thiết bị, mail, game, kinh doanh, dữ liệu
Bluetooth,…
Từ những dữ liệu trên, hiện đang có một số xu hướng nghiên cứu sau:
Một số nghiên cứu tìm các hành vi, thói quen dựa trên dữ liệu vị trí và dữ
liệu Bluetooth. Trong [1-4], các tác giả dựa vào thông tin vị trí của TBDĐ được
cung cấp bởi các nhà mạng để nghiên cứu, phân loại các hành vi, thói quen.
Nhóm tác giả đã phân tích, xây dựng mô hình về các mối quan hệ xã hội và các
thói quen hàng ngày của các cá nhân bằng cách sử dụng dữ liệu điện di động của
các cá nhân đó dựa trên việc phân loại dữ liệu ID của điện thoại di động vào địa
điểm khác nhau và từ đó phân tích các thói quen hành vi của người sử dụng. Các
nghiên cứu này sử dụng dữ liệu thu được thông qua Bluetooth để phân biệt giữa
các ngày trong tuần hoặc cuối tuần. Hạn chế của các nghiên cứu trên là thông tin
của ID di động chỉ có thể cung cấp các thông tin về vị trí. Nó không thể biết về

8
các hoạt động ở mức thấp.Ví dụ, dữ liệu ID di động có thể cho biết người sử
dụng tại nhà hoặc tại văn phòng / trường, nhưng nó không thể cho biết các hoạt
động bên trong như tham dự các bài giảng hoặc ngồi trong quán ăn tự phục vụ
mà người dùng tham gia.
Khắc phục những điểm này đã có một loạt các bài báo đã nghiên cứu hành
vi của các cá nhân thông quan sự kết hợp cả hai loại dữ liệu là dữ liệu từ các nhà

tiêu đó, thì nhóm tác giả đã xây dựng quy trình để thực hiện các công đoạn sau:
Phân lớp dữ liệu theo vị trí để xác định những di chuyển của người dùng, xây
dựng ma trận xác suất và dữ liệu di chuyển dùng để huẩn luyện, sử dụng mạng
Nơ ron và cây quyết định (DT) để xác định hành vi bất thường của những người
già hoặc những người đang trong giai đoạn đầu của bệnh mất trí nhớ.
Một cách tiếp cận khác, các nhà nghiên cứu trong [7] phát hiện các sự kiện
bất thường trong cuộc sống của những người già cô đơn bằng cách khai thác các
dữ liệu liên quan thu được của thiết bị cảm biến. Họ sử dụng thuật toán tìm luật
kết hợp với cụm thời gian để phân tích các hoạt động của người cao tuổi. Đầu
tiên, họ gom cụm từng hoạt động của người cao tuổi với thời gian và sau đó, dựa
vào kỹ thuật luật kết hợp để tìm tất cả các tập hành động thường xuyên.
Cao và các cộng sự [23] đề xuất một cách tiếp cận hiệu quả cho khai thác
thói quen trên điện thoại di động. Họ khai thác mối liên hệ giữa tương tác của
người dùng với bối cảnh sử dụng, dữ liệu từ file log của điện thoại di động được
sử dụng để khám phá ra thói quen người dùng. Các tác giả đã đưa ra một thuật
toán hiệu quả để giải quyết bài toán này. Các tác giả đã sử dụng các độ hỗ trợ
khác nhau, các độ tin cậy khác nhau để giải quyết thành công bài toán không cân
bằng dữ liệu giữa dữ liệu ngữ cảnh và dữ liệu tương tác của người dùng với
TBDĐ mà các phương pháp tiếp cận truyền thống về tìm luật kết hợp không giải
quyết được.
Chúng tôi đã chọn đề tài tìm hiểu thói quen của nhiều người dùng sử dụng
các phần mềm trên điện thoại di động trong hệ điều hành Android. Trong đề tài
này, chúng tôi chỉ tập trung tìm hiểu và phân tích thông tin về các phần mềm
được sử dụng trên các TBDĐ. Qua việc tìm hiểu dữ liệu này, chúng tôi mong
muốn phát hiện ra các thói quen sử dụng các phần mềm, các loại phần mềm trên
hệ điều hành Android. Từ đó ta có thể xây dựng các chiến lược để phát triển các
phần mềm tiền năng, hoặc các chiến lược khác trong kinh tế như quảng cáo, tiếp
thị,…
Cấu trúc của luận văn gồm:
Chương 1. Cung cấp thông tin về bài toán phân tích hành vi của người sử

IMEI: mã máy
Start: thời điểm khởi động ứng dụng
Với dữ liệu sử dụng phần mềm có thể là rất dài đối với một TBDĐ nếu
được lấy trong một khoảng thời gian tương đối lớn. Hơn nữa, số lượng các ứng
dụng ngày càng nhiều nên khi chúng tôi tìm hiểu cách khai phá tập luật tuần tự
thì kết quả không có khả quan. Nhưng khi chúng tôi tìm hiểu các cách để tìm ra
các mẫu chuỗi tuần tự thì kết quả khả quan hơn. Hình 2.1 sau minh họa dữ liệu
lấy được từ pha lấy dữ liệu, ta có thể nhận ra được rằng trong một thời gian rất
ngắn, dữ liệu đã ghi nhận rất nhiều ứng dụng được kích hoạt.
Khi quan sát dữ liệu trong Hình 2.1 chúng ta nhận thấy, dữ liệu được lưu
quá nhiều, một ứng dụng được lưu quá nhiều lần, các ứng dụng con được kích
hoạt từ ứng dụng cha cũng nhiều, có nhiều ứng dụng do hệ điều hành kích hoạt,
có nhiều ứng dụng do người dùng kích hoạt. Vấn đề đặt ra ở đây là làm thế nào
chỉ lấy được các ứng dụng gốc do người dùng kích hoạt. Ví dụ, làm thế nào để
lấy được ứng dụng gốc như Trình duyệt web, Email, GoogleTalk, … mà không
phải các ứng dụng do Hệ thống sinh ra, hoặc ra các ứng dụng gốc đó gọi các ứng
dụng khác của hệ thống trong quá trình thực thi.
Để làm được việc đó, chúng tôi đã lọc ra các ứng dụng thuộc hệ thống như
SystemApplication, Unknow, System, và toàn bộ các ứng dụng con của nó
được kích hoạt qua mã ID và PID.

12

AppName
Stop
PID
IMEI
PPID
Start
SystemApplication

Nov 27 22:31:08 2012
341
0
289
Nov 27 22:31:07 2012
SystemApplication
Nov 27 22:31:56 2012
79
0
59
Nov 27 22:30:19 2012
Search
Nov 27 22:31:57 2012
187
0
33
Nov 27 22:30:24 2012
SystemApplication
Nov 27 22:31:58 2012
137
0
59
Nov 27 22:30:19 2012
LogInfo
Nov 27 22:31:06 2012
339
0
289
Nov 27 22:31:05 2012
LogInfo

Clock
Nov 28 19:14:24 2012
235
0
232
Nov 28 19:13:54 2012
SystemApplication
Nov 28 19:14:24 2012
8
0
2
Nov 28 19:13:43 2012
SystemApplication
Nov 28 19:14:24 2012
188
0
124
Nov 28 19:13:47 2012
Pico TTS
Nov 28 19:14:24 2012
372
0
33
Nov 28 19:14:10 2012
SystemApplication
Nov 28 19:14:24 2012
33
0
1
Nov 28 19:13:43 2012

Nov 28 19:13:47 2012
SystemApplication
Nov 28 19:14:24 2012
30
0
1
Nov 28 19:13:43 2012
Downloads
Jan 02 13:57:11 2012
207
A000002470B55F
203
Jan 02 13:55:04 2012
LogInfo
Jan 02 13:55:54 2012
24528
A000002470B55F
24429
Jan 02 13:55:53 2012
SystemApplication
Jan 02 13:57:11 2012
14601
A000002470B55F
117
Jan 02 13:55:03 2012
Contacts Storage
Jan 02 13:57:11 2012
354
A000002470B55F
272

Jan 02 13:55:16 2012
SystemApplication
Jan 02 13:57:11 2012
35
A000002470B55F
2
Jan 02 13:55:03 2012
LogInfo
Jan 02 13:55:38 2012
24476
A000002470B55F
24429
Jan 02 13:55:37 2012
Hình 2.1 Dữ liệu thu được từ TBDĐ sử dụng Hệ điều hành Android

Để có dữ liệu có dạng chuỗi tuần tự như sau, S
i
= {app
1
, app
2
, , app
n
};
Trong đó:
- S
i
là thiết bị cầm tay thứ i
- app
j

i
thường có số lớn các ứng dụng (chuỗi dài - long
sequence).
Như vậy dữ liệu cuối cùng có dạng: imei, appName, start, stop (imei = s
i
)
AppName
Stop
PID
IMEI
PPID
Start
Email
Nov 27 22:31:57 2012
247
0
244
Nov 27 22:30:29 2012
Launcher
Nov 27 22:31:57 2012
132
0
118
Nov 27 22:30:22 2012
LogInfo
Nov 27 22:31:06 2012
339
0
289
Nov 27 22:31:05 2012

Package Access Helper
Nov 28 19:14:24 2012
241
0
240
Nov 28 19:13:56 2012
Pico TTS
Nov 28 19:14:24 2012
374
0
372
Nov 28 19:14:10 2012
Search
Nov 28 19:14:24 2012
274
0
268
Nov 28 19:14:01 2012
Contacts Storage
Jan 02 13:57:11 2012
354
A000002470B55F
272
Jan 02 13:55:11 2012
Contract Killer
Jan 02 13:57:11 2012
24031
A000002470B55F
24022
Jan 02 13:55:30 2012


Hình 2.2 Dữ liệu ứng dụng gốc được lấy ra từ Hình 2.1

Để có dữ liệu dạng trên thì chúng tôi đã có một pha riêng để lọc dữ liệu, pha
này phải làm các công việc sau: xác định các ứng dụng gốc
(1)
, loại bỏ các ứng
dụng con được kích hoạt từ ứng dụng gốc.

2.2. Khai phá dữ liệu mẫu chuỗi tuần tự
2.2.1. Giới thiệu chung
Như phần 2.1 đã trình bày, vì đặc điểm của dữ liệu là dạng chuỗi dài theo
thời gian và có rất nhiều ứng dụng khác nhau được đưa vào sử dụng nên khi
chúng tôi thử nghiệm trên các giải thuật tìm luật tuần tự hành về vi sử dụng của
nhiều người thì kết quả không khả quan. Do đó, chúng tôi đã đi tìm hiểu các
mẫu chuỗi tuần tự về hành vi sử dụng của nhiều người thì có vẻ khả quan hơn.
Chính vì vậy, trong phần này chúng tôi sẽ giới thiệu tổng quan về các giải thuật (1)
Ứng dụng gốc là ứng dụng được kích hoạt trực tiếp từ người dùng từ desktop, hoặc từ các nhóm ứng dụng trên
hệ điều hành.

14
khai phá mẫu chuỗi tuần tự và lý do chúng tôi chọn giải thuật SPAM cho bài
toán này.
Dữ liệu dạng chuỗi các giá trị hoặc các sự kiện được kết hợp với thuộc tính
thời gian được gọi là dữ liệu chuỗi thời gian time-series [15] gọi tắt là dữ liệu
time-series. Một số dữ liệu time-series như: dữ liệu giao dịch khách hàng trong
các siêu thị, dữ liệu về tài chính – chứng khoán, dữ liệu về y học, dữ liệu về

tuần tự qua các sư
̣
kiê
̣
n khác nhau. Việc phát hiện các mẫu tuần tự được

15
sử dụng rộng rãi trong việc phân tích trình tự DNA. Một ví dụ về mẫu
tuần tự là mỗi khi chứng khoán của Microsoft giảm xuống 5%, cổ phiếu
IBM cũng sẽ giảm ít nhất 4% trong vòng ba ngày.
- Mẫu chu kỳ: mẫu chu kỳ là những mẫu có chu kỳ trong cơ sở dữ liệu
time-series, chu kỳ có thể là hàng ngày, hàng tuần, hàng tháng, theo mùa
hoặc hàng năm.
Rõ ràng, khai phá mẫu chu kỳ có thể được xem như là mô hình khai phá dữ
liệu tuần tự bằng cách đưa vào các chuỗi chu kỳ như là một tập hợp các chuỗi
tuần tự. Trong cơ sở dữ liệu giao dịch của khách hàng, mỗi chuỗi là một tập các
hàng mà khách hàng đã mua.
Trong thời gian qua, đã có nhiều lĩnh vực quan tâm nghiên cứu về dữ liệu
time-series. Tuy nhiên, cơ sở dữ liệu tuần tự bao gồm các chuỗi các sự kiện sắp
xếp có hoặc không thuộc tính thời gian. Cơ sở dữ liệu tuần tự là một trường hợp
đặc biệt của cơ sở dữ liệu time-series, kết quả nghiên cứu nhiều nhất trong khai
phá mẫu tuần tự tập trung vào hai vấn đề chính. Vấn đề đầu tiên là khai phá mẫu
tuần tự, nhằm tìm kiếm các chuỗi tuần tự thường xuyên xảy ra để mô tả dữ liệu
hoặc dự đoán các dữ liệu tương lai. Vấn đề thứ hai là khai phá mẫu chu kỳ, có
thể được xem như là khai phá mẫu tuần tự. Trong luận văn này chúng tôi đi vào
phần tiền xử lý dữ liệu cho bài toán khai phá mẫu tuần tự - chu kỳ để phát hiện
thói quen của con người.
2.2.2. Bài toán Khai phá mẫu chuỗi tuần tự
Để cho dễ hình dung về bài toán, ta có ví dụ 2.1 sau: Trong khi tiến hành
truy xuất dữ liệu của một cửa hàng bán sách người ta nhận thấy có trình tự mua

Bảng 2.1 Danh sách khách mua hàng
Mã_KháchHàng
ThờiGian_GiaoDịch
Mua_MãHàng
1
1
03/3/2013
05/3/2103
40
100
2
2
2
12/3/2013
14/3/2013
20/3/2013
20, 30
40
50, 70, 80
3
01/3/2103
40, 60, 80
4
4
4
09/3/2013
16/3/2013
26/3/2013
40
50, 80

trợ tối thiểu là 40% ta thu được kết quả và ánh xạ kết quả đó sang các giá trị tự
nhiên từ 1 đến 5 cho dễ quản lý được trình bày tại Bảng 2.3 dưới đây.
Bảng 2.3 Danh mục thỏa mãn điều kiện minsup = 40%
Tập mục
Ánh xạ
(40)
1
(50)
2
(80)
3
(50, 80)
4
100
5

Trong Bảng 2.2 thì 20, 30, 40,. là các mục (mã sản phẩm). (20, 30), (50,
70, 80) được gọi là 2 tập mục (itemset). Tập mã sản phẩm trong cùng dấu () là
các mã sản phẩm được mua tại cùng một thời điểm cho nên tứ tự các mục trong
đó là không quan trọng. <(40)(100)> là một chuỗi tuần tự các giao dịch nên phải
tuân theo trình tự.
Sequential pattern là một chuỗi các itemset xuất hiện phổ biến có trình tự,
tất cả các item trong cùng một itemset được giả sử là chúng có cùng tại thời
điểm giao dịch hoặc chúng có trong cùng một khoảng thời gian giao dịch (time
gap). Thông thường tất cả các giao dịch của một khách hàng được gắn kết với
nhau theo trình tự thời gian và được xem là một chuỗi.
Tnh Chứa: một chuỗi a <a
1
,a
2

s
)(

(2)
Trong đó:
- Support(s): là độ hỗ trợ cho chuỗi s

18
- C
s
: là số khách hàng có giao dịch chứa chuỗi s
- TN: là số khách hàng có trong cơ sở dữ liệu
Khai phá chuỗi tuần tự (Sequential pattern mining): là tiến trình trích
xuất ra một số các mẫu tuần tự mà có độ hỗ trợ vượt qua ngưỡng tối thiểu. Vì số
lượng chuỗi là rất lớn vì thế người ta thường đưa vào giá trị hỗ trợ tối thiểu để
lọc kết quả. Những mẫu tuần tự có độ hỗ trợ vượt qua ngưỡng hỗ trợ tối thiểu là
những mẫu mong muốn và có giá trị. Tuy nhiên, có một số mẫu tuần tự không
vượt qua ngưỡng hỗ trợ cực tiểu nhưng vẫn có giá trị trong một số bài toán cụ
thể, để giải quyết việc này [12] đã đưa ra một khái niệm là ma trận SUPRISE để
đo giá trị của các chuỗi.
2.2.3. Một số thuật toán khai phá mẫu tuần tự
Hầu hết các giải thuật ban đầu đều dựa trên tính chất Apriori trong khai
phá luật kết hợp như: AprioriAll, AprioriSome, DynamicSome trong [15], GSP
[16] và SPADE [24]. Sau này, một loạt các dữ liệu dựa trên giải thuật được đề
xuất, như: FreeSpan [17] và PrefixSpan [18]. SPADE [21] là một giải thuật dựa
trên lưới, MEMISP [20] dùng cách tiếp cận đa
́
nh chỉ mục của bộ nhớ , trong đó
SPIRIT [19] tập trung vào tích hợp các ràng buộc qua các biểu thức thông
thường.

),),, ,,(
21 nnk
ISsssn
)
(1)


temp
S

(2)


temp
I

(3) For each (
n
Si
)
(4) if ((
}{,, ,,
21
isss
k
) is frequent)
(5)
}{iSS
temptemp


temptemp


(11) For each (
temp
Ii
)
(12) DFS-Pruning((
}{, ,,
21
isss
k

),
temp
S
, all elements in
temp
I
greater then i)

20
Chương 3 - MÔ HÌNH ĐỀ XUẤT
3.1. Mô hình đề xuất tổng thể
Mô hình khai phá dữ liệu thông thường được mô tả trong Hình vẽ

Tạo kho
dữ liệu
Tiền xử lý
dữ liệu

trữ dữ liệu; xử lý dữ liệu; khai phá dữ liệu; phân tích, so sánh kết quả. Chúng tôi
sẽ lần lượt giới thiệu các modul như sau:
- Thu thập dữ liệu: chức năng của modul này là tập hợp dữ liệu sử dụng các
phần mềm từ các file log của các TBDĐ như máy tính bảng, điện thoại
thông minh, …. Thành một file dữ liệu được chuẩn hóa từ trước theo định
dạng như được mô tả tại Hình 2.1
- Modul lưu trữ dữ liệu: dữ liệu từ file trong modul thứ nhất sẽ được đưa
vào lưu trữ trong CSDL MySQL sau đó áp dụng các câu lệnh SQL để
thanh lọc các dữ liệu không cần thiết như dữ liệu về các luồng, chương
trình con, chương trình không phải người dùng kích hoạt,… để chỉ giữ lại
trong CSLD tập các ứng dụng gốc theo định dạng như Hình 2.2.
- Module xử lý dữ liệu:
o Đọc trong CSDL ra và tiến hành xây dựng nên các chuỗi tuần tự sử
dụng phần mềm cho từng thiết bị. Như vậy, mỗi một TBDĐ sẽ có
một chuỗi tuần tự sử dụng các phần mềm bao gồm các thuộc tính
định danh thiết bị, tên ứng dụng, thời điểm kích hoạt, thời điểm kết
thúc như được mô tả tại Hình 2.2.
o Phân tách chuỗi dữ liệu dài ban đầu thành các chuỗi dữ liệu ngắn
hơn để làm dữ liệu đầu vào cho module khai phá. Để thực hiện
được phần này, chúng tôi đề ra một số phương pháp phân tách dữ
liệu được trình bày tại mục 3.2.
- Module khai phá dữ liệu: Từ tập dữ liệu thu được từ modul trên, chúng tôi
sử dụng một số giải thuật khai phá và đánh giá về hiệu quả của các giải
thuật đó, qua đó chúng tôi nhận thấy giải thuật SPAM là hiệu quả hơn cả
so với các giải thuật SPADE, PrefixSpan về tốc độ khai phá và về độ lớn
của dữ liệu. Sau khi có kết quả của một số lần thử nghiệm trên phương án
phân tách thứ nhất, chúng tôi lại quay lại modul phân tách dữ liệu để thực
thi phương pháp phân tách dữ liệu thứ 2 và tiếp tục tiến hành khai phá cho
một số lần thử nghiệm với tham số khác nhau.
- Modul phân tích kết quả: sau khi có kết quả của các phương án phân tách,

) có thời
điểm kết thú thực thi
n
i,app
stopTime
cách ứng dụng đầu tiên (app
1
) của
Sequence
i+1
kế tiếp có thời điểm bắt đầu kích hoạt
1
app1,i
startTime

một khoảng
thời gian tối thiểu là t:
t

n1
appi,app1,i
stopTimestartTime

(3)
Start Sequence
00:00:00
Stop Sequence

mà có thời gian kích hoạt startTime
app_j+1
của app
j+1
và
thời gian kết thúc timeStop
app_j
của app
j
cách nhau khoảng thời gian ∆t, tùy
thuộc vào giá trị của ∆t so với t
ngưỡng
mà ta xác định được 1 trong 2 trường hợp:
- Cả 2 item app
j
và app
j+1
cùng trong một itemset
- app
j
và app
j+1
thuộc 2 itemset khác nhau.
Một số trường hợp phân tách Itemset sau:
* 2 ứng dụng (item) thuc 2 itemset khác nhau
o Có dạng:
1,;stopTimestartTimet
j1j
appi,appi,



,
j
appi,
stopTime
tương ứng là thời điểm kích hoạt ứng
dụng thứ j+1 và thời điểm kết thúc ứng ựng thứ j trong sequence i.

Hình 3.6. Phân tách dữ liệu theo thời gian trong cùng một Itemset

Đối với cách phân tách trên như Hình 3.6 thì chuỗi thứ i có 2 itemset là
itemset
k
và itemset
k+1
. Mỗi một itemset chỉ có 01 phần tử (itemset
k
chỉ có app
i
,
itemset
k+1
có app
j+1
).
* 2 ứng dụng (item) thuc cùng 1 itemset.
Dạng 1. ∆t>0
o dạng:
1,;stopTimestartTimet
j1j

1appi,
j
startTime


Itemset
k

j
app i,
stopTime

app
j

app
j+1

Itemset
k+1
time
Sequence
i

1i,app
j
startTime


Itemset