Tóm tắt Luận án Khai phá dữ liệu tuần tự để dự đoán hành vi truy cập web

BỘ THÔNG TIN VÀ TRUYỀN THÔNG

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIÊN THÔNG

--------------------

TÓM TẮT LUẬN ÁN

KHAI PHÁ DỮ LIỆU TUẦN TỰ

ĐỂ DỰ ĐOÁN HÀNH VI TRUY CẬP WEB

NCS: NGUYỄN THÔN DÃ

NGƯỜI HƯỚNG DẪN KHOA HỌC:

TS. TÂN HẠNH

TS. PHẠM HOÀNG DUY

HÀ NỘI, NĂM 2020

Công trình hoàn thành tại:

Học viện Công nghệ Bưu chính Viễn thông

Người hướng dẫn khoa học:

TS. Tân Hạnh

TS. Phạm Hoàng Duy

Phản biện 1:

Phản biện 2:

Phản biện 3:

Luận án được bảo vệ trước Hội đồng cấp Học viện tại Học viện

Công nghệ Bưu chính Viễn thông, 122 Hoàng Quốc Việt, Hà Nội.

Vào lúc:

Có thể tìm hiểu luận án tại:

Thư viện Học viện Công nghệ Bưu chính Viễn thông

1

MỞ ĐẦU

Môi trường Web trong thời đại ngày nay trở thành một môi trường phổ biến cho

giao tiếp, tương tác và chia sẻ dữ liệu giữa các người dùng. Điều này dẫn đến hàng ngày,

hàng giờ dữ liệu đã không ngừng được tạo ra. Những dữ liệu này có thể được tận dụng để

thiết kế và xây dựng các mô hình dự đoán, đặc biệt là mô hình dự đoán hành vi truy cập

Web để hỗ trợ ra quyết định. Hơn nữa, sự phát triển không ngừng của các doanh nghiệp

hiện đại đã tạo ra áp lực và thách thức không nhỏ cho các nhà nghiên cứu khai phá dữ liệu.

Luận án này cố gắng giải quyết những khó khăn này bằng cách đề xuất các mô hình và giải

pháp khai phá dữ liệu tuần tự để dự đoán hành vi truy cập Web hiệu quả hơn như nâng cao

độ chính xác và giảm thời gian thực thi dự đoán.

Mục tiêu và phạm vi nghiên cứu

Để giải quyết bài toán khai phá dữ liệu tuần tự cho dự đoán truy cập Web, nghiên

cứu sinh đề ra 4 mục tiêu chính như sau:

(1) Nghiên cứu các bài báo liên quan đến luận án để tìm ra những ưu điểm, hạn chế của

các bài báo này, từ cơ sở đó nghiên cứu sinh đề xuất các giải pháp tốt hơn cho dự đoán

hành vi truy cập Web.

(2) Tìm một mô hình cơ sở dữ liệu phù hợp để hỗ trợ cho dự đoán hành vi truy cập Web.

(3) Tìm giải pháp tốt hơn để nâng cao tính chính xác cho dự đoán hành vi truy cập Web.

(4) Tìm giải pháp tốt hơn để giảm thời gian thực thi dự đoán hành vi truy cập Web.

Phạm vi nghiên cứu của luận án là khai phá dữ liệu tuần tự cho dự đoán truy cập Web

trên các tập clickstream và dữ liệu nhật ký truy cập Web (Web Log) lưu trên các máy chủ

Web, cụ thể là dữ liệu nhật ký thuộc các Web Server như IIS (máy chủ Web trên hệ điều

hành Microsoft Windows) và Apache (Các máy chủ Web trên các Hệ điều hành họ Linux).

Ý nghĩa và đóng góp

Khai phá dữ liệu tuần tự cho dự đoán truy cập Web là một trong những nghiên cứu

quan trọng trong khai phá dữ liệu. Chẳng hạn như dự đoán hành vi truy cập Web của người

học các lớp học trực tuyến, hành vi truy cập bất hợp pháp của tội phạm mạng, hành vi của

khác hàng trên các Website thương mại điện tử. Nhiểu công trình đã thực hiện và đạt được

những kết quả nhất định về độ chính xác và hiệu năng về thời gian dự đoán. Tuy nhiên, để

2

dự đoán truy cập Web hiệu quả, cần đề xuất các giải pháp tốt hơn về độ chính xác cũng

như vể thời gian.

Các đóng góp của luận án gồm:

(1) Đề xuất một giải pháp để thiết kế và xây dựng cơ sở dữ liệu tuần tự cho dự đoán truy

cập Web.

(2) Đề xuất một giải pháp để làm giảm thời gian dự đoán cho dự đoán truy cập Web.

(3) Đề xuất một giải pháp để tăng độ chính xác cho dự đoán truy cập Web.

(4) Đề xuất một mô hình kết hợp giữa tăng độ chính xác và giảm thời gian dự đoán.

Bố cục luận án

Bố cục luận án gồm có năm chương và một phần kết luận. Cụ thể, trong chương đầu

tiên, nghiên cứu sinh trình bày tổng quan về vấn đề cần nghiên cứu. Ở chương tiếp theo,

nghiên cứu sinh đưa ra các khái niệm về dữ liệu tuần tự và trình bày phương pháp thiết kế

cơ sở dữ liệu tuần tự để dự đoán truy cập Web. Trong Chương 3, nghiên cứu sinh trình bày

về giải pháp nâng cao hiệu quả về thời gian khai phá dữ liệu tuần tự cho dự đoán truy cập

Web. Tiếp theo, trong Chương 4, nghiên cứu sinh đề xuất giải pháp nâng cao hiệu quả về

độ chính xác khai phá dữ liệu tuần tự cho dự đoán truy cập Web. Bên cạnh đó, trong

Chương 5, nghiên cứu sinh trình bày giải pháp tích hợp nâng cao độ chính xác và nâng cao

hiệu quả về thời gian khai phá dữ liệu tuần tự cho dự đoán truy cập Web.

CHƯƠNG 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU TUẦN TỰ

CHO DỰ ĐOÁN TRUY CẬP WEB

1.1. Giới thiệu

Để dự đoán truy cập Web, nhiều nghiên cứu sử dụng các tiếp cận dựa trên máy học.

Chẳng hạn, một số các công trình khoa học dùng phương pháp các như Association Rules,

Sequential Pattern, Sequential Rules, Markov và các phương pháp lai. Độ chính xác dự

đoán được xác định bằng công thức:

Accuracy = |successes| / |sequences|

(1.1)

Trong đó

Accuracy: Độ chính xác của dự đoán

3

|successes|: Số lượng chuỗi dự đoán thành công

|sequences|: Số lượng chuỗi dự đoán

1.2. Khái niệm dự đoán hành vi truy cập Web

Định nghĩa 1.1

Gọi U = {IP₁, IP₂, …, IP_k} là tập hợp người dùng truy cập Web với IP_ilà địa chỉ IP

của người dùng truy cập thứ i (1≤ 푖 ≤ 푘) và k là số lượng của các địa chỉ IP.

Cho một tập hợp các phần tử hữu hạn (ký hiệu) I = {i₁, i₂, ..., i_m}, một chuỗi tuần tự

〈

〉

Seq là một danh sách có thứ tự Seq = 푝₁, 푝₂, … 푝_푛, trong đó p_x∈ I (1 ≤ x ≤ n).

〈

〉

Gọi S = 푝₁, 푝₂, … 푝_푞, S ∈ Seq là chuỗi tuần tự các trang Web được truy cập bởi

người dùng có địa chỉ IP_ivới IP_i∈ U và q là số lượng của các trang Web được truy cập.

Nhật ký truy cập Web L = [l₁, l₂, …, l_v] là một dãy các dòng nhật ký l_j(1≤ 푗 ≤ 푣)

với v là số dòng nhật ký và l_j= (IP_i, p_i, t_i) là dòng nhật ký thứ j ghi nhận người dùng có địa

chỉ IP_i∈ U, truy cập vào trang Web p_i∈ S vào thời điểm t_i.

Định nghĩa 1.2

Cơ sở dữ liệu tuần tự truy cập Web SD = {s₁, s₂, …, s_N} là tập hợp các chuỗi s_m∈ 푆

(1≤ 푚 ≤ 푁) với N là số lượng các chuỗi dữ liệu tuần tự trong cơ sở dữ liệu tuần tự này.

Chẳng hạn, Bảng 1.1 trình bày một cơ sở dữ liệu tuần tự truy cập Web chứa 5 chuỗi

tuần tự được truy cập bởi 5 người dùng có địa chỉ IP khác nhau. Trong đó, chuỗi tuần tự

truy cập Web thứ nhất có 6 trang Web p₁, p₂, p₄, p₆, p₃và p₅được truy cập bởi người dùng

có địa chỉ IP₁theo thứ tự thời gian. Tương tự, chuỗi tuần tự truy cập Web thứ hai thể hiện

người dùng có địa chỉ IP₂truy cập lần lượt vào các trang Web p₄, p₃, p₅, p₆, p₂.

Bảng 1.1 Một ví dụ về cơ sở dữ liệu tuần tự truy cập Web

Địa chỉ IP

Chuỗi tuần tự truy cập Web

IP₁

IP₂

IP₃

IP₄

IP₅

s₁

s₂

s₃

s₄

s₅

〈

〉

푝₁, 푝₂, 푝₄, 푝₆, 푝₃, 푝₅

〉

푝₄, 푝₃, 푝₅, 푝₆, 푝₂

〉

푝₁, 푝₂, 푝₄, 푝₉, 푝₃, 푝₇, 푝₁₀

〉

푝₆, 푝₁, 푝₄, 푝₈, 푝₃, 푝₅

푝₄, 푝₂, 푝₈, 푝₆, 푝₃, 푝₅

4

Định nghĩa 1.3

Cho một chuỗi tuần tự các trang Web cần được dự đoán trang Web truy cập kế tiếp

〈 〉

S_query= 푝푎푔푒₁, 푝푎푔푒₂, … 푝푎푔푒_푚, S_query∈ Seq và page_ilà trang Web được truy cập thứ i

(1≤ 푖 ≤ 푚) và m là số lượng các trang Web trong chuỗi S_query(m còn được gọi là chiều dài

của chuỗi S_query).

Dự đoán hành vi truy cập Web là dự đoán trang Web sẽ được truy cập kế tiếp p_next

của S_querytrên cơ sở dữ liệu tuần tự truy cập Web SD bằng cách sử dụng phương pháp dự

đoán chuỗi tuần tự truy cập Web, chẳng hạn như phương pháp dự đoán chuỗi dữ liệu tuần

tự và việc dự đoán hành vi truy cập Web này được đặc tả bằng công thức sau:

P_next= F (S_query, SD)

(1.2)

Trong đó:

P_nextlà trang Web kế tiếp được dự đoán.

F hàm xử lý dự đoán.

S_querylà chuỗi tuần tự các trang Web cần dự đoán.

SD là cơ sở dữ liệu tuần tự truy cập Web.

Trong một số nghiên cứu trước đây F có thể dùng độc lập hay kết hợp nhiều nhiều pháp

như: Luật kết hợp, Clustering, Compact Prediction Tree (CPT), Compact Prediction Tree

Plus (CPT+).

1.3. Các phương pháp phổ biến

Theo F. Khalil và các đồng sự, những phương pháp phổ biến để dự đoán truy cập

Web là khai phá bằng luật kết hợp (Association Rules), gom cụm (Clustering) và mô hình

xác suất Markov.

* Ưu điểm, hạn chế và khuyến nghị:

 Các tiêu chí đánh giá

 Độ chính xác dự đoán: Mức độ phù hợp của trang Web kế tiếp tìm thấy so

với thực tế. Để độ chính xác dự đoán tốt yêu cầu không bị mất thông tin và

không bỏ qua các ứng viên tiềm năng, hay các trường hợp hiếm và giải quyết

loại bỏ các thông tin không cần thiết.

5

 Độ phức tạp thời gian thực thi dự đoán: Giải quyết vấn đề xử lý dự đoán

các tập dữ liệu lớn, cũng như không gian dự đoán lớn với độ phức tạp thời

gian nhỏ, đảm bảo thời gian thực thi nhanh.

 Ưu điểm:

 Ý tưởng chính của phương pháp gom cụm (Clustering) là để cải thiện hiệu

năng và tính linh hoạt của các công việc có tính chất cá nhân. Các phiên truy

cập Web có thể được nhận thông qua việc gom cụm các trang hay người

dùng.

 Các mô hình Markov thường được dùng để nhận biết trang Web kế tiếp mà

được truy cập bởi người dùng Web dựa trên chuỗi tuần tự các trang Web truy

cập trước đó.

 Các nghiên cứu dựa vào luật kết hợp (Association rule) khám phá các luật

kết hợp trên các kết quả dữ liệu nhật ký truy cập của người dùng để tìm nhóm

các trang Web mà được truy cập cùng nhau.

 Sự tích hợp các tiếp cận khác nhau đã giảm các hạn chế của từng phương

pháp cho nhau đã làm tăng hiệu quả truy cập Web, đặc biệt là về phương diện

độ chính xác.

 Nhiều nghiên cứu đã tận dụng thế mạnh của khai phá dữ liệu lịch sử truy cập

của người dùng dự đoán truy cập Web. Đây là một chủ đề rất quan trọng

trong khai khá dữ liệu và được nhiều nhà nghiên cứu quan tâm.

 Hạn chế:

 Các phương pháp khai phá Association Rules rất tốn chi phí thời gian khi xử

lý các mẫu có số lượng lớn và dài và được xây dựng trên mô hình không hỗ

trợ dự đoán nên trong quá trình dự đoán, thông tin đã bị hao hụt do đó làm

giảm đi độ chính xác dự đoán truy cập Web.

 Phương pháp phân nhóm cũng là phương pháp dự đoán làm mất thông tin do

xây dựng trên mô hình không hỗ trợ dự đoán [46].

 Phương pháp quan tâm đến thời gian truy cập của mỗi liên kết tuy quan trọng,

nhưng rất khó xác định là người truy cập có thực sự đang xem liên kết đó

hay không hay làm việc gì khác không liên quan.

6

 Các khuyến nghị:

 Tìm hiểu các phương pháp dự đoán truy cập Web tốt hơn để nâng cao độ

chính xác và cải thiện hiệu năng thời gian.

 Nghiên cứu kết hợp nhiều phương pháp để làm tăng hiệu quả dự đoán.

 Xem xét thông tin về mối liên hệ giữa các truy cập Web cũng cần được xem

xét như thứ tự thời gian giữa các truy cập, tầm ảnh hưởng, độ quan trọng của

mỗi liên kết trên Website.

1.4. Phương pháp dự đoán chuỗi dữ liệu tuần tự

Cho một tập hợp các chuỗi tuần tự huấn luyện, vấn đề của dự đoán chuỗi tuần tự là tìm

thành phần kế tiếp của một chuỗi tuần tự cho trước bằng cách quan sát các thành phần

trước đó.

1.4.1. Phương pháp cây dự đoán (Compact Prediction Tree - CPT)

Quá trình huấn luyện của CPT nhập vào một tập các chuỗi tuần tự huấn luyện và

tạo ra ba cấu trúc phân biệt: (1) Prediction Tree (PT), (2) Lookup Table (LT) và (3) Inverted

Index. Trong suốt quá trình huấn luyện, các chuỗi tuần tự được xem xét từng chuỗi tuần tự

để xây dựng dần ba cấu trúc này.

 Ưu điểm: Mô hình dự đoán chuỗi dự liệu tuần tự CPT có ưu thế về độ chính xác so

với những tiếp cận khác như khai phá luật kết hợp, khai phá luật liên tiếp, các mô

hình phát triển theo Markov.

 Hạn chế: CPT có thời gian thực thi còn chậm hơn một số giải thuật dự đoán chuỗi

tuần tự khác. Do đó cần một tiếp cận cải tiến hơn để giải quyết hạn chế này. Phần tiếp

theo sẽ mô tả chi tiết về một cải tiến của CPT.

1.4.2. Phương pháp cây dự đoán cải tiến (Compact Prediction Tree plus - CPT+)

CPT+ là một biến thể cải tiến từ giải thuật CPT. Đây là một mô hình dự đoán dùng

giải pháp nén các chuỗi tuần tự không làm mất mát thông tin bằng cách khai thác các độ

tương tự giữa các chuỗi tuần tự con. Độ chính xác của CPT cao hơn nhiều so với các mô

hình hiện tại như PPM, DG, AKOM trên các tập dữ liệu thực khác nhau nhưng thời gian

dự đoán còn chậm hơn các mô hình này. Một chiến lược hiệu quả để làm giảm thời gian

dự đoán là truy xuất ít thông tin nhất nếu có thể khi dự đoán để tăng tốc độ dự đoán nhưng

cũng chọn lọc thông tin cẩn thận để tránh làm giảm độ chính xác. Để giải quyết vấn đề này,

7

một giải thuật cải tiến hơn được xây dựng là CPT+. Chi tiết của mô hình CPT+ được cải

tiến từ CPT theo ba chiến lược: Frequent Subsequence Compression (FSC), Simple

Branches Compression (SBC), Prediction with improved Noise Reduction (PNR).

1.4.3. Ưu điểm và hạn chế của phương pháp cây dự đoán cải tiến (CPT+)

 Ưu điểm: Mô hình dự đoán chuỗi dự liệu tuần tự CPT+ có ưu thế về độ chính xác

và thời gian so với những tiếp cận khác như khai phá luật kết hợp, khai phá luật liên

tiếp, các mô hình phát triển theo Markov, CPT.

 Hạn chế: Để dự đoán truy cập Web, tương tự như các mô hình dự đoán chuỗi tuần

tự khác, phương pháp cây dự đoán cải tiến (CPT+) vẫn cần giải quyết các vấn đề

về:

 Thời gian thực thi dự đoán còn chậm nếu không gian dự đoán lớn [46, 47] .

Vì thế cần đề xuất các giải pháp để làm tăng tốc độ thời gian dự đoán mà độ

chính xác vẫn bảo toàn.

 Nâng cao độ chính xác cho dự đoán: Xem xét các mối quan hệ, tương tác

giữa các trang với nhau để đưa ra các giải pháp để nâng cao hiệu quả về chính

xác cho dự đoán truy cập Web.

1.4.4. Tổng hợp so sánh các phương pháp dự đoán chuỗi dữ liệu tuần tự

Trên tập dữ liệu BMS, phương pháp CPT+ có độ chính xác vượt trội hơn những

phương pháp phổ biến thường dùng để dự đoán chuỗi tuần tự khác như CPT, DG, PPM và

AKOM.

Mặc dù có nhiều ưu điểm so với tiếp cận phổ biến trong dự đoán chuỗi dữ liệu tuần

tự, phương pháp CPT+ cũng còn một số hạn chế sau: (1) Thời gian xử lý chậm nếu cơ sở

dữ liệu tuần tự chứa nhiều chuỗi tuần tự có số phần tử truy cập lớn và kích cỡ của cơ sở dữ

liệu tuần tự càng lớn thì càng ảnh hưởng đến thời gian thực thi dự đoán; (2) Chưa xử lý

triệt để dữ liệu dư thừa do đó độ chính xác còn bị ảnh hưởng.

1.5. Đề xuất mô hình dự đoán hành vi truy cập Web

Luận án đề xuất dự đoán truy cập Web bằng cách kết hợp các giải pháp: Xây dựng

cơ sở dữ liệu tuần tự cho dự đoán truy cập Web, nâng cao độ chính xác cho dự đoán truy

cập Web (Chương 3) và nâng cao hiệu quả thời gian cho dự đoán truy cập Web (Chương

4). Mô hình được thể hiện một cách trực quan theo Hình 1.1.

8

Hình 1.1 Mô hình khai phá dữ liệu cho dự đoán truy cập Web kết hợp nâng cao độ chính

xác và nâng cao hiệu quả về thời gian

Diễn giải mô hình :

Bước 1: Xây dựng cơ sở dữ liệu tuần tự truy cập Web

(Chi tiết được trình bày ở Chương 2)

SDB = f₀(L)

Trong đó: Cơ sở dữ liệu tuần tự SDB là cơ sở dữ liệu được xây dựng theo một hàm

xử lý f₀.

(1.11)

Bước 2: Nâng cao hiệu quả về độ chính xác khai phá dữ liệu tuần tự cho dự đoán truy cập

Web

(Chi tiết được trình bày ở Chương 3)

SDB₁= g₁(SDB)

(1.12)

Cơ sở dữ liệu tuần tự SD₁là cơ sở dữ liệu SD được thu gọn bằng giải pháp loại bỏ

các chuỗi tuần tự dư thừa bằng cách dùng hàm xử lý g₁, cụ thể là giải thuật Page Rank.

9

Bước 3: Nâng cao hiệu quả về thời gian khai phá dữ liệu tuần tự cho dự đoán truy cập Web

(Chi tiết được trình bày ở Chương 4)

Cơ sở dữ liệu tuần tự truy cập Web ở bước này được xác định bằng công thức:

SDB₂= g₂(s_query, SDB₁)

(1.13)

Trong đó, cơ sở dữ liệu tuần tự truy cập Web SDB₂là cơ sở dữ liệu tuần tự truy cập

Web SDB₁được thu gọn bằng giải pháp loại bỏ các chuỗi tuần tự dư thừa bằng cách dùng

hàm xử lý g₂, cụ thể là giải thuật phân tích và so sánh chuỗi.

Bước 4: Trang Web kết quả dự đoán p_nextđược xác định bằng một hàm xử lý G, cụ thể là

CPT+ với dữ liệu đầu vào là chuỗi tuần tự cần dự đoán S_queryvà cơ sở dữ liệu tuần tự đã

được thu gọn SBD₂.

p_next= G(s_query, SDB₂)

(1.14)

1.6. Kết luận chương 1

Để dự đoán truy cập Web, các nhà nghiên cứu đã thực hiện các nghiên cứu khác

nhau từ các phương pháp độc lập như khai phá luật kết hợp, các mô hình phát triển từ

Markov, CPT và CPT+… đến các phương pháp kết hợp các mô hình khác nhau. Trên cơ

sở nghiên cứu và phân tích các điểm mạnh và yếu của các phương pháp dự đoán hành vi

truy cập Web, luận án đã đề xuất và xuất bản công trình nghiên cứu [CT5].

CHƯƠNG 2. XÂY DỰNG CƠ SỞ DỮ LIỆU TUẦN TỰ

CHO DỰ ĐOÁN TRUY CẬP WEB

2.1. Giới thiệu

Chương 2 trình bày một giải pháp xây dựng cơ sở dữ liệu tuần tự cho dự đoán truy

cập Web. Cơ sở dữ liệu tuần tự được xây dựng từ các chuỗi tuần tự của tập dữ liệu click-

stream hoặc tập dữ liệu được chuẩn hóa từ nhật ký của máy chủ Web. Việc chuẩn hóa dữ

liệu từ máy chủ Web là quá trình tiền xử lý để làm sạch và biến đổi dữ liệu để phục vụ cho

dự đoán truy cập Web.

2.2. Hạn chế của dự đoán truy cập tuần tự trên Web Log

2.2.1. Hạn chế về không gian dự đoán

Web Log là tập hợp các tập tin nhật ký Web được thu thập từ máy chủ Web. Các

tập tin này chứa một khối lượng rất lớn dữ liệu được ghi nhận lại trong toàn bộ quá trình

10

một Website hoạt động. Bên cạnh đó, Web Log cũng chứa nhiều thông tin lỗi, dư thừa,

nhiễu thông tin, gây hiểu nhầm và không đầy đủ. Vì vậy, dữ liệu nhật ký web phải được

chuyển đổi thành dữ liệu tuần tự và công việc tiền xử lý là rất cần thiết để tránh nhiễu thông

tin, các ngoại lệ và các giá trị bị thiếu. Mục đích của tiền xử lý và biến đổi dữ liệu là để có

được dữ liệu sạch đáp ứng cho nghiên cứu dự đoán truy cập Web.

2.2.2. Hạn chế về thời gian dự đoán

Một hạn chế đáng chú ý cần xem xét khi dự đoán truy cập Web trên Web Log là

thời gian truy cập rất chậm do khối lượng thu thập dữ liệu trên các tập tin nhật ký là cực

kỳ lớn. Do vậy, việc thu hẹp kích thước của Web Log, thu hẹp phạm vi, không gian dự

đoán là công việc rất quan trọng để thời gian dự đoán được giảm xuống đến mức thấp nhất

có thể mà vẫn đảm bảo độ lớn và độ chính xác của thông tin truy cập Web cần dự đoán.

2.3. Khái niệm Web Usage Mining

2.3.1. Định nghĩa Web Usage Mining

Web Usage Mining là một ứng dụng của các kỹ thuật khai phá dữ liệu để tìm ra các

mẫu truy cập lịch sử thu được từ dữ liệu Web để hiểu và phục vụ tốt hơn nhu cầu của các

ứng dụng trên nền tảng Web [101].

Web Usage Mining là một kỹ thuật khai phá Web được dùng để tìm và phân tích

các mẫu lịch sử truy cập Web từ dữ liệu lịch sử Web (còn gọi là các Web Log) hay nói

cách khác Web Usage Mining chính là Web Log Mining.

2.3.2. Tầm quan trọng của Web Usage Mining

Trong nhiều năm gần đây, rất nhiều nghiên cứu đã được xuất bản để mô tả những

bước tiến lớn trong lãnh vực liên quan đến Web Usage Mining. Bên cạnh đó, tri thức thu

được từ các mẫu truy cập lịch sử Web có thể ứng dụng trực tiếp để quản lý hiệu quả các

hoạt động liên quan đến thương mại điện tử, dịch vụ điện tử, giáo dục điện tử...

2.3.3. Khái niệm cơ sở dữ liệu Web Log

2.3.3.1 Định nghĩa cơ sở dữ liệu Web Log

Các máy chủ Web (Web server) đăng ký một Web log đối với mỗi truy cập đơn lẻ

mà chúng nhận được, trong đó các phần quan trọng của thông tin về truy cập được ghi nhận

bao gồm URL truy cập, địa chỉ IP từ máy khách (Web client) và thời gian truy cập. [86]

11

Các tập tin Web log được chia thành nhiều phần nhỏ cho mục đích khai phá dữ liệu

nào đó. Để thu được các phần của các Web log, kỹ thuật tiền xử lý sẽ được áp dụng. Mỗi

phần của Web log là một chuỗi tuần tự các sự kiện từ một người dùng hay phiên truy cập

theo thứ tự thời gian tăng dần, chẳng hạn sự kiện nào đến sớm hơn xảy ra trước sự kiện

đến trễ hơn. [86] định nghĩa thành phần Web log (hay còn gọi là chuỗi tuần tự truy cập

Web) như sau:

2.3.3.2 Cấu trúc và nội dung Web Log

Cấu trúc và nội dung của Web Log phụ thuộc vào máy chủ tạo ra các Web Log đó.

Đa số các máy chủ Web hỗ trợ dưới dạng tùy chọn mặc định, định dạng tập tin nhật ký

chung (CLF). CLF còn được gọi là Định dạng Nhật ký Chung NCSA, là định dạng tệp văn

bản được tiêu chuẩn hóa được sử dụng bởi các máy chủ web khi tạo tệp nhật ký máy chủ.

2.3.4. Xây dựng cơ sở dữ liệu tuần tự cho dự đoán truy cập Web

2.3.4.1. Ý nghĩa của việc xây dựng cơ sở dữ liệu tuần tự

Việc xây dựng cơ sở dữ liệu tuần tự cho dự đoán truy cập Web có ý nghĩa rất quan

trọng trong khai phá dữ liệu tuần tự vì cơ sở dữ liệu tuần tự được hình thành từ dữ liệu thu

thập từ dữ liệu nhật ký Web vốn rất chứa nhiều thông tin dư thừa không cần thiết và gây

khó khăn trong việc dự đoán.

2.3.4.2. Giải thuật chuẩn hóa cơ sở dữ liệu tuần tự từ cơ sở dữ liệu Web Log

Để xây dựng cơ sở dữ liệu tuần tự, các thuộc tính của cơ sở dữ liệu Web Log sau

đây được xem xét: IP truy cập của người dùng (User_IP), Liên kết truy cập (Link), thời

điểm truy cập (Action_Time). Tùy theo Web Log mà các thuộc tính này có thể được ký

hiệu theo quy ước riêng. Hai giai đoạn chính để xây dựng cơ sở dữ liệu từ cơ sở dữ liệu

Web Log được trình bày như dưới đây.

Giai đoạn 1: Sắp xếp cơ sở dữ liệu Web Log theo từng User_IP

Biểu diễn mỗi User_IP sao cho trình tự thời gian truy cập của người dùng của tăng

dần. Bảng 2.2 minh họa một số mẫu tin của một cơ sở dữ liệu Web Log đã được sắp xếp

tăng dần theo thời gian truy cập của từng User_IP.

Giai đoạn 2: Xây dựng các chuỗi tuần tự dựa theo các User_IP

12

Với mỗi User_IP thực hiện các truy cập trong thời gian khác nhau, các chuỗi tuần

tự được xây dựng bằng cách biểu diễn các truy cập của từng User_IP theo hàng ngang như

sau:

Sequence 1 : Link_visited_1 -1 Link_visited_4 -1 Link_visited_5 -1 -2

Sequence 2: Link_visited_3 -1 Link_visited_2 -1 Link_visited_5 -1 Link_visited_6 -1 -2

Sequence 3: Link_visited_2 -1 Link_visited_3 -1 Link_visited_1 -1 -2

Sequence 4: Link_visited_7 -1 Link_visited_4 -1 -2

Trong đó, các chuỗi tuần tự Sequence 1, Sequence 2, Sequence 3, Sequence 4 tương

ứng với từng User_IP trong cơ sở dữ liệu Web Log trên. Kí hiệu -1 dùng để phân tách các

truy cập Web. Kí hiệu -2 để biểu diễn sự kết thúc của một chuỗi tuần tự.

Chi tiết giải thuật

Giải thuật biến đổi cơ sở dữ liệu Web Log thành cơ sở dữ liệu tuần tự của luận án

được trình bày trong công trình nghiên cứu [CT3]. Chi tiết của giải thuật như sau:

Dữ liệu nhập vào: Một thư mục chứa các tập tin Web log (cơ sở dữ liệu Web Log)

Dữ liệu thu được: Một danh sách các chuỗi dữ liệu tuần tự (một cơ sở dữ liệu tuần tự).

Bước 1: Mở kết nối với cơ sở dữ liệu Web Log

Bước 2: Thực thi vấn tin lấy các thuộc tính User_IP và thuộc tính Link_visited từ thư

mục chứa các tập tin Web Log.

Bước 3: Thực hiện giải thuật xây dựng cơ sở dữ liệu tuần tự với Mã giả (Pseudo Code)

như sau:

Khai báo các biến:

+ Arr_WebLog là mảng chứa các mẫu tin của cơ sở dữ liệu WebLog có được bằng cách

truy vấn các tập tin Web Log, những mẫu tin trùng lắp, dư thừa bị loại bỏ.

+ N là số lượng các mẫu tin chứa trong mảng Arr_WebLog.

+ Arr_User_IP là mảng một chiều chứa các địa chỉ IP người dùng Web User_IP. +

Arr_Link là mảng một chiều chứa các liên kết truy cập.

+ Arr_Distinct_User_IP là mảng một chiều lưu các giá trị User_IP khác nhau

+ Arr_Distinct_Link là mảng một chiều lưu các giá trị liên kết truy cập khác nhau

Link_visited

1. N ← Length(Arr_WebLog)

13

2. Arr_User_IP ← null

3. Arr_Link ← null

4. for i = 0 to N-1 do

5.

6.

Arr_User_IP(i) ← các giá trị của thuộc tính User_IP

Arr_Link(i) ← các giá trị của thuộc tính Link_visited

7. end for

8. Arr_Distinct_User_IP ← arr_Link.Distinct().ToArray();

9. Arr_Distinct_Link ← arr_Link.Distinct().ToArray();

10. count : Số lượng liên kết truy cập của người dùng.

11. count ← i

12. for k = 0 to count do

13.

14

for l = 0 to Count(Arr_Distinct_Link) do

if Arr_Link(k) ← Arr_Distinct_Link(l) then

Arr_Link(k) ← Arr_Link(k) + “ -1 “

// “ –1 “ : Ký hiệu phân cách giữa hai liên kết truy cập liên tiếp

end for

15.

16.

17.

18. end for

19. for j = 0 to count – 1 do

20.

21.

if Arr_User_IP(j) < > Arr_User_IP(j + 1) then

Arr_Link(j) ← Arr_Link (j) + “ –2 \r\n“

22. // “-2”: Ký hiệu kết thúc một chuỗi tuần tự trong cơ sở dữ liệu tuần tự

23. end for

24. List ← null: Khởi tạo mảng một chiều để lưu trữ các chuỗi tuần tự

25. for j = 0 to count do

26. //Chọn các chuỗi tuần tự có từ 3 liên kết truy cập trở lên:

27.

28.

if (Number_of_Links ≥ 3)

Add Arr_Link(j) to List

29. end for

30. Xuất ra kết quả: Một danh sách các chuỗi tuần tự (Một cơ sở dữ liệu tuần tự)

14

2.3.6. Các kết quả thử nghiệm

Giải thuật được thực hiện trên một máy tính cá nhân với cấu hình như sau:

* Cấu hình phần cứng

RAM: 32 GB (31.6 GB usable); Intel(R) Core(TM) i7-4800MQ CPU @ 2.70GHz.

* Cấu hình phần mềm

Hệ điều hành 64-bit Windows 10 Education.

Môi trường lập trình C# 2013, thư viện Log Parser Studio 2.2.

* Dữ liệu

Các cơ sở dữ liệu Web Log được thu thập từ các Website dưới đây:

Website 1: periwinklelecottages.com

Website 2: palmviewsanibel.com

Website 3: devqa.robotec.co.il

Website 4: inees.org

Thông tin của các cơ sở dữ liệu Web Log được trình bày như minh họa của Bảng 2.3.

Bảng 2.1 Thông tin các cơ sở dữ liệu Web Log

Website 1 Website 2 Website 3 Website 4

Số lượng

3511237

97449

61015

4267

4217568

74814

40901

3535

2527429 593367

Các chuỗi tuần tự

Kích cỡ

629

7405

5467

119

1188

451

(MB)

Số lượng các

IP khác nhau

Số lượng các liên

kết khác nhau

* Các kết quả thử nghiệm:

Bảng 2.2 So sánh thời gian thực hiện giải thuật xây dựng cơ sở dữ liệu tuần tự

Website 1 Website 2 Website 3 Website 4

15

Non-Parallel

(Thời gian thực thi

giải thuật tuần tự)

(milliseconds)

121836

85683

12382

3508

Parallel

(Thời gian thực thi

giải thuật song song)

(milliseconds)

97449

12211

74814

9678

9893

312

3312

330

Số lượng chuỗi tuần

tự được tạo

Kết quả thử nghiệm cho thấy khi kích cỡ của cơ sở dữ liệu Web Log càng lớn thì

khoảng cách về thời gian thực thi bằng tiếp cận tuần tự và song song của giải thuật xây

dựng cơ sở dữ liệu tuần tự càng cao. Điều đó có nghĩa là với cơ sở dữ liệu Web Log càng

lớn xử lý tính toán song song cho giải thuật sẽ cho hiệu quả tốt hơn. Nghiên cứu sinh cũng

đã công bố một số công trình liên quan đến nghiên cứu này là công trình [CT2], [CT3] và

[CT6]. Ngoài ra, nghiên cứu liên quan đến thiết kế cơ sở dữ liệu tuần tự từ cơ sở dữ liệu có

nhãn thời gian (temporal networks) cũng đã được nghiên cứu sinh thực hiện trong công

trình nghiên cứu [CT8].

2.3.7. Đánh giá và thảo luận

Các kết quả thực nghiệm trên đã trình bày cách thức xây dựng các cơ sở dữ liệu tuần

tự để dự đoán truy cập Web bằng hai phương pháp xử lý tuần tự và song song.

Bên cạnh đó, một vấn đề được đặt ra là việc xây dựng và chuẩn hóa các cơ sở dữ liệu

có thực sự cần thiết? Để tìm câu trả lời cho câu hỏi này, số liệu trong Bảng 2.5 cho thấy

rằng có sự chênh lệch rất lớn về số lượng các mẫu tin trong các cơ sở dữ liệu Web Log so

với số lượng các mẫu tin trong các cơ sở dữ liệu tuần tự trên 4 Website được nghiên cứu.

Bảng 2.3 Độ tương quan về số lượng mẫu tin giữa cơ sở dữ liệu Web Log và cơ sở dữ

liệu tuần tự

Số mẫu tin

cơ sở dữ liệu Web Log cơ sở dữ liệu tuần tự

16

Website 1

periwinklelecottages.com ¹

Website 2

3511237

4217568

2527429

593367

12211

9678

312

palmviewsanibel.com ²

Website 3

devqa.robotec.co.il ³

Website 4

330

inees.org ⁴

Cụ thể, trong Website thứ nhất, cơ sở dữ liệu tuần tự thu được chỉ có 12211 mẫu

tin, chỉ xấp xỉ 1/287 so với số lượng mẫu tin trong cơ sở dữ liệu Web Log của cùng Website.

Tương tự, trong Website thứ hai, cơ sở dữ liệu tuần tự thu được chỉ có 9678 mẫu

tin, chỉ xấp xỉ 1/435 so với số lượng mẫu tin trong cơ sở dữ liệu Web Log của cùng Website.

Hai ví dụ còn lại ở Website thứ ba và Website thứ tư, các cơ sở dữ liệu tuần tự thu

được có số mẫu tin là không đáng kể so với cơ sở dữ liệu Web Log của các Website này.

Số lượng các mẫu tin thu được trong các cơ sở dữ liệu tuần tự là không đáng kể so

với số mẫu tin trong các cơ sở dữ liệu Web Log. Điều này cho thấy cơ sở dữ liệu tuần tự

đã được loại bỏ những thông tin dư thừa không cần thiết. Như vậy, cơ sở dữ liệu thu được

từ cơ sở dữ liệu Web Log đem lại nhiều lợi ích: (1) Không gian dự đoán được thu hẹp giúp

cho thời gian thực hiện dự đoán truy cập Web được tốt hơn; (2) Việc dự đoán sẽ chính xác

hơn khi những dữ liệu dư thừa, không phục vụ cho dự đoán được loại bỏ trước khi áp dụng

các giải pháp dự đoán truy cập Web.

2.3.7. Kết luận chương 2

Trong chương này, luận án đã trình bày các tiếp cận để xây dựng cơ sở dữ liệu tuần

tự phục vụ cho dự đoán truy cập Web. Cụ thể, nghiên cứu sinh đã đề xuất một giải pháp

¹Truy cập ngày 22/8/2017

²Truy cập ngày 22/8/2017

³Truy cập ngày 23/8/2017

⁴Truy cập ngày 23/8/2017

17

khác nhau để thiết kế cơ sở dữ liệu tuần tự từ cơ sở dữ liệu nhật ký Web. Ngoài ra, nghiên

cứu sinh cũng thực hiện các công trình nghiên cứu liên quan về chủ đề này như thiết kế cơ

sở dữ liệu tuần tự cho mạng có nhãn thời gian [CT8].

CHƯƠNG 3. NÂNG CAO HIỆU QUẢ VỀ ĐỘ CHÍNH XÁC

KHAI PHÁ DỮ LIỆU TUẦN TỰ CHO DỰ ĐOÁN TRUY CẬP WEB

3.1. Giới thiệu

Chương 3 trình bày một giải pháp tích hợp giải thuật PageRank với CPT+ để nâng

cao hiệu quả về độ chính xác khai phá dữ liệu tuần tự cho dự đoán truy cập Web. Dữ liệu

đầu vào cho nghiên cứu là các cơ sở dữ liệu tuần tự được thu thập từ các tập dữ liệu thu

thập từ các tập dữ liệu click-stream, cụ thể là các cơ sở dữ liệu tuần tự FIFA, KOSARAK,

MSNBC⁵. Tuy nhiên, những cơ sở dữ liệu tuần tự này cần được cải thiện thêm về độ chính

xác vì các cơ sở dữ liệu tuần tự này còn ẩn chứa nhiều dữ liệu dư thừa và không có ý nghĩa

cho dự đoán truy cập Web. Bằng giải pháp áp dụng kỹ thuật tính toán Page Rank cho các

chuỗi dữ liệu tuần tự kết hợp với CPT+, nghiên cứu sinh thu được các cơ sở dữ liệu tuần

tự có độ chính xác cao hơn để hỗ trợ cho dự đoán truy cập Web tốt hơn về độ chính xác.

3.2. Ý tưởng của giải pháp sử dụng Page Rank để nâng cao hiệu quả về độ chính xác

cho dự đoán truy cập Web

Một số lý do tính toán Page Rank được chọn cùng với CPT+ để nâng cao hiệu quả

về độ chính xác cho dự đoán truy cập Web:

(1) Thuật toán PageRank là một thuật toán nổi tiếng và có nhiều ứng dụng.

(2) Dựa trên giả định là các liên kết truyền đạt các khuyến nghị của con người có thể

được rút ra trực tiếp, nhiều người đã tiến hành nghiên cứu về phân tích liên kết (Chẳng hạn

PageRank và HITS để khai thác cấu trúc Web nhằm nắm bắt tầm quan trọng của một trang

Web.

(3) Về bản chất, PageRank diễn giải một siêu liên kết từ trang pageA đến trang pageB

dưới dạng phiếu bầu.

⁵https://www.philippe-fournier-viger.com/spmf/index.php?link=datasets.php

18

3.3. Nội dung của giải pháp nâng cao hiệu quả về độ chính xác cho dự đoán truy cập

Web

Tính toán PageRank dựa trên ý tưởng đếm backlinks (trích dẫn) đến một trang nhất

định. Các nhà phát triển giải thuật PageRank đưa ra một công thức để tính chỉ số Page

Rank của một trang A (liên kết A) như sau:

PR(page A) = (1-df) + df(PR(T₁)/C(T₁) + PR(T₂)/C(T₂) +...+ PR(T_n)/C(T_n))

Trong đó

(3.1)

PR(page A): Chỉ số PageRank của trang Web A

T_i: Một trang liên kết đến trang A

PR(T_i): Chỉ số PageRank của trang T_i

C(T_i): Số lượng các trang mà T_iliên kết đến

df: Chỉ số damping factor (df = 0.85 được nhiều nhà nghiên cứu sử dụng)

3.4. Giải pháp nâng cao độ chính xác dự đoán truy cập Web với giải thuật PageRank

và CPT+

3.4.1. Phương pháp thực hiện

Giả sử một cơ sở dữ liệu tuần tự SD có N chuỗi tuần tự.

Bước 1: Biến đổi cơ sở dữ liệu tuần tự thành cơ sở dữ liệu đồ thị.

Mỗi cặp liên kết liên tiếp {p_i, p_j} theo (trình tự thời gian) trong một chuỗi tuần tự có

thể được xem như là một mối quan hệ giữa hai đỉnh (nút) của đồ thị có hướng. Trong đó,

đường nối p_ip_jxuất phát từ p_ivà kết thúc ở p_jlà cạnh nối của hai đỉnh này.

Chẳng hạn, giả sử có một cơ sở dữ liệu với hai chuỗi tuần tự sau S₁=

〈

〉

〈

〉

푝퐴, 푝퐷, 푝푍, 푝퐾, 푝푁 và S₂= 푝퐷, 푝푁, 푝푇 . Đồ thị có hướng biểu diễn cho cơ sở dữ liệu

tuần tự này có thể được mô tả như minh họa ở Hình 3.2.