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

HOÀNG VŨ
PHÂN CỤM NGƯỜI SỬ DỤNG WEB
DỰA TRÊN MẪU TRUY CẬP
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01 Người hướng dẫn khoa học: PGS. TS Trần Đình Quế TÓM TẮT LUẬN VĂN THẠC SỸ

HÀ NỘI – 2012

- 2 -

truy cập sẽ cung cấp nền tảng cho việc ra quyết định đối với việc tổ
chức không gian Web, tối ưu Web site [9][11].
Phân cụm người sử dụng Web là việc tạo các nhóm người sử
dụng có các mẫu truy cập Web tương tự nhau, cung cấp tri thức cho
việc cá nhân hóa các dịch vụ Web [10].
Việc nghiên cứu các mô hình phân cụm và áp dụng các phương
pháp phân cụm người dùng Web trong khai phá sử dụng Web là một
xu thế tất yếu vừa có ý nghĩa khoa học vừa mang ý nghĩa thực tiễn.
Luận văn tập trung nghiên cứu về ứng dụng của kỹ thuật phân
cụm người sử dụng Web dựa trên mẫu truy cập Web. Dựa trên
những tiêu chuẩn khác nhau, người dùng Web có thể được phân cụm
và tri thức hữu ích có thể được lấy ra từ các mẫu truy cập của họ. Nội
dung bao gồm:
 Tìm hiểu về bài toán phân cụm người sử dụng Web dựa trên
mẫu truy cập và các ứng dụng.
 Nghiên cứu, cài đặt các thuật toán sử dụng trong quá trình tiền
xử lý dữ liệu, bao gồm các giải thuật trong các pha:
- Làm sạch dữ liệu
- Xác định người sử dụng
- Xác định phiên của người sử dụng
- Xác định phiên giao dịch với đường dẫn đầy đủ
- Biểu diễn dữ liệu theo mô hình không gian vector
- 3 -- 5 -

Chương 1. TỔNG QUAN VỀ KHAI PHÁ WEB
1.1. Khai phá Web
Khai phá Web là việc sử dụng các kỹ thuật khai phá dữ liệu để
tự động hóa quá trình khám phá và trích rút những thông tin hữu ích
từ các tài liệu, các dịch vụ và cấu trúc Web.
Có thể phân các hướng nghiên cứu khai phá Web thành 3 lĩnh
vực chính, bao gồm:
 Khai phá nội dung Web (Web Content Mining): Khai phá nội
dung web là các quá trình xử lý để lấy ra các tri thức từ nội
dung các trang văn bản hoặc mô tả của chúng.
 Khai phá cấu trúc Web (Web Structure Mining): Nhờ vào
các kết nối giữa các văn bản siêu liên kết, World Wide Web có
thể chứa đựng nhiều thông tin hơn nhiều so với các thông tin ở
bên trong văn bản. Nội dung của khai phá cấu trúc Web là các
quá trình xử lý nhằm rút ra các tri thức từ cách tổ chức và liên
kết giữa các tham chiếu của các trang Web.
 Khai phá sử dụng Web (Web Usage Mining): Phân tích các
nhật ký truy cập (Web log) để khám phá ra các mẫu truy cập
của người dùng truy cập vào trang Web.
1.2. Khai phá sử dụng Web
Khai phá sử dụng Web là việc xử lý để lấy ra các thông tin hữu
ích trong các log file truy cập Web đã được ghi lại và tích luỹ về các
tương tác người dùng mỗi khi máy chủ nhận được yêu cầu truy cập.



- 7 -

Trong khai phá sử dụng Web, người ta thường sử dụng các kỹ
thuật:
 Luật kết hợp: để tìm ra những trang Web thường được truy
cập cùng nhau của người dùng, những lựa chọn cùng nhau của
người dùng.
 Kỹ thuật phân cụm: Phân cụm người dùng dựa trên các mẫu
duyệt để tìm ra sự liên quan giữa những người dùng Web và
các hành vi của họ.
Có rất nhiều định nghĩa khác nhau về kỹ thuật phân cụm, nhưng
về bản chất ta có thể hiểu phân cụm là các qui trình tìm cách nhóm
các đối tượng đã cho vào các cụm (clusters), sao cho các đối tượng
trong cùng 1 cụm tương tự (similar) nhau và các đối tượng khác cụm
thì không tương tự (dissimilar) nhau. Mục đích của phân cụm là tìm
ra bản chất bên trong các nhóm của dữ liệu.
1.3. Các kỹ thuật phân cụm
Các kỹ thuật phân cụm dữ liệu được chia làm một số loại:
Phương pháp dựa vào phân hoạch ( Partition Based Data Clustering
Method), phương pháp phân cấp (Hierarchical Based Data Clustering
Method), phương pháp dựa trên mật độ (Density Based Data
Clustering Method), phương pháp dựa trên lưới (Grid Based Data
Clustering Method).
- 8 -

Các đặc trưng

các đối tượng. Ở đây, chúng tôi chỉ trình bày một số các hàm đo
tương đồng phổ biến hay còn gọi là các hàm khoảng cách. Khoảng
cách tương đồng giữa hai mẫu thứ i và mẫu thứ k ký hiệu là d(i,k)
phải thỏa mãn các tính chất sau:
1. d(i,i)=0 với mọi i.
2. d(i,k)=d(k,i) với mọi cặp (i,k).
3. d(i,k)>=0 với mọi cặp (i,k).
Một số cách xác định hàm đánh giá độ tương đồng: Giả sử rằng
chúng ta có một ma trận mẫu [x
ij
] với x
ij
là giá trị của đặc trưng thứ j
của mẫu i. tất cả các đặc trưng là liên tục và được ước lượng theo tỷ
xích tỷ lệ. Hàm khoảng cách phổ biến là khoảng cách Minkowski [3]
dùng để ước lượng độ bất tương đồng. Mẫu thứ i tương ứng với dòng
thứ i của ma trận mẫu được ký hiệu là một vector cột x
i
.
x
i
= ( x
i1
,x
i2
, ,x
in
)
T
,i=1,2, ,n

với mọi (i,m,k) Bất đẳng
thức tam giác
Có ba khoảng cách phổ biến sử dụng khoảng cách Minkowsky
được định nghĩa như sau:
Khoảng cách Euclidean (r=2):
d (i,k )= (
∑
j=
1
d
x
ij
− x
kj

2
)
1/2
= [(x
i
− x
k
)
T
( x
i
− x
k
)]
1 /2

bao gồm:
1.3.2. Phân cụm dựa vào phân hoạch
Phương pháp phân cụm phân hoạch dựa trên ý tưởng ban đầu
tạo ra k phân hoạch, sau đó lặp lại nhiều lần để phân bố lại các đối
tượng dữ liệu giữa các cụm nhằm cải thiện chất lượng phân cụm.
- 11 -
1.3.3. Phân cụm dựa vào phân cấp
Phương pháp phân cụm phân cấp dựa trên ý tưởng cây phân cấp
để phân cụm dữ liệu. Có hai cách tiếp cận đó là phân cụm dưới lên
(Bottom up) và phân cụm trên xuống (Top down).
1.3.4. Phân cụm dựa trên mật độ
Phương pháp phân cụm dựa trên mật độ, căn cứ vào hàm mật
độ của các đối tượng dữ liệu để xác định cụm cho các đối tượng.
1.3.5. Phân cụm dựa trên lưới
Phương pháp phân cụm dựa trên lưới, ý tưởng của nó là đầu tiên
lượng hoá không gian đối tượng vào một số hữu hạn các ô theo một
cấu trúc dưới dạng lưới, sau đó thực hiện phân cụm dựa trên cấu trúc
lưới đó.
1.3.6. Phân cụm dựa trên mô hình
Ý tưởng chính của phương pháp phân cụm dựa trên mô hình là
giả thuyết một mô hình cho mỗi cụm và tìm kiếm sự thích hợp nhất
của đối tượng dữ liệu với mô hình đó, các mô hình tiếp cận theo
thống kê và mạng Nơron.
1.4. Một số phương pháp, thuật toán tiêu biểu
Phần này, chúng tôi trình bày một số thuật toán tiêu biểu đại
diện cho các kỹ thuật phân cụm phổ biến, tương đương với các mục,
bao gồm:

Từ bộ dữ liệu thô, để có thể trích chọn các tri thức hữu ích, dữ
liệu cần qua quá trình tiền xử lý, tổ chức dữ liệu và biểu diễn phù
hợp với định dạng để có thể tiến hành thực nghiệm phân cụm. Tiếp
theo đó, dữ liệu phù hợp sẽ được sử dụng cho công cụ phân cụm và
tiên hành thực nghiệm. Quá trình này có thể chia thành 02 bước,
trong mỗi bước sẽ bao gồm các pha như sau:
- 14 -
Bước 1: Tiền xử lý dữ liệu, bao gồm các pha:
 Pha làm sạch dữ liệu (Data Clearning)
 Pha xác định người sử dụng (User Identification)
 Xác định phiên của người sử dụng (Session Indentification)
 Hoàn thiện đường dẫn (Path Completion)
 Biểu diễn dữ liệu ( Biểu diễn các mẫu dữ liệu phù hợp với
chuẩn của công cụ thực nghiệm)
Bước 2: Phân cụm người sử dụng dựa trên mẫu truy cập:
 Sử dụng công cụ WEKA, áp dụng một số kỹ thuật phân cụm
tập dữ liệu
 So sánh, đánh giá kết quả.
Mẫu truy cập của người sử dụng Web được chiết xuất từ các file
nhật ký trên máy chủ Web, sau đó tổ chức vào các phiên đại diện cho
các giai đoạn của sự tương tác giữa người sử dụng Web và máy chủ
Web. Mẫu này bao gồm các trang mà họ đã đến thăm, và thời gian
họ đã dành trên mỗi trang. Mỗi người sử dụng sau đó có thể được đại
diện bởi một tập hợp gồm cặp thuộc tính ( URL truy cập, Thời gian
truy cập). Từ mỗi cặp thuộc tính này, chúng ta xác định một mẫu
người sử dụng.
Mục tiêu chính của phân cụm người sử dụng Web là để tìm ra
- 16 -
- Nếu từ một địa chỉ IP có nhiều yêu cầu với các mã trình
duyệt Web khác nhau thì mỗi trình duyệt Web sẽ gắn với 1
người sử dụng (trường hợp qua Proxy),
- Cùng 1 địa chỉ IP, nếu khoảng thời gian giữa 2 lần yêu cầu
lớn hơn 30 phút thì coi như xuất hiện một người sử dụng
mới.
- Sử dụng nhật ký truy cập với các liên kết và cấu trúc liên kết
site để xác định tiến trình duyệt Web của người dùng.
 Xác định phiên của người sử dụng: Phiên giao dịch người dùng
là một tập giới hạn của các click người dùng theo một hoặc
nhiều máy chủ Web. Sau đây là các quy tắc được sử dụng để
xác định phiên người sử dụng:
- Nếu có một người dùng mới, có một phiên làm việc mới;
- Trong một phiên giao dịch người sử dụng, nếu trang tiếp
mong muốn là rỗng, thì có một phiên giao dịch mới;
- Nếu thời gian các yêu cầu trang vượt quá một giới hạn xác
định (25 đến 30 phút), thì giả sử rằng người dùng sẽ bắt đầu
một phiên mới.
 Hoàn thiện đường dẫn: Do sự tồn tại của bộ nhớ đệm cục bộ và
máy chủ Proxy, có nhiều truy cập quan trọng không được lưu
trong nhật ký truy cập. Nhiêm vụ của pha hoàn thiện đường
dẫn là điền vào những trang bị thiếu.
 Với mỗi người sử dụng, xác định danh sách các trang Web
(URL) mà người đó truy cập. Để tránh dư thừa dữ liệu, các

- 18 -
Sau khi tiền xử lý, thực hiện biểu diễn dữ liệu theo mô hình
không gian vector, dữ liệu được lưu trữ theo định dạng .arff.
3.3. Thực nghiệm phân cụm
3.3.1. Công cụ thử nghiệm
Công cụ chúng tôi dùng để thực nghiệm phân cụm là WEKA
(Waikato Environment for Knowledge Analysis -
http://sourceforge.net/projects/weka/). Công cụ này cung cấp hầu hết
các chức năng cơ bản phục vụ cho khai phá dữ liệu bao gồm các
thuật toán về tiền xử lý dữ liệu (filter), phân cụm (cluster), phân lớp
(classifier), luật kết hợp (association rule)
Để thực hiện việc tiền xử lý dữ liệu, chúng tôi đã xây dựng, căn
cứ vào các giải thuật đã nêu ở chương 2, chúng tôi đã xây dựng và
tổng hợp thêm các công cụ phục vụ cho việc thực nghiêm, bao gồm:
Bảng 3.3. Các công cụ, phần mềm hỗ trợ thực nghiệm
STT

Ứng dụng

Chức năng

Ngu
ồn

1.

DataClearning.java

ự xây dựng

4.

ToVector.java

Chuy
ển các dữ liệu
logfile
sau
T
ự xây dựng

- 19 -
khi đ
ã qua các pha ti
ền xử lý về
dạng vector phù hợp với định
dạng .csv và .arff mà WEKA
chấp nhận
3.3.2. Phương pháp thực nghiệm
Trong phần thực nghiệm, chúng tôi lựa chọn một số thuật toán
thông dụng, đại diện cho kỹ thuật phân cụm dựa vào phân hoạch và
kỹ thuật phân cụm dựa vào phân cấp như đã trình bày ở Chương 1,
bao gồm:
 Thuật toán K-means
 Thuật toán EM (Expectation Maximization)

Tổng hợp kết quả của việc thực nghiệm bởi các kỹ thuật trên
như sau:
Bảng 3.4. Kết quả phân cụm và thời gian tương quan giữa các thuật toán
STT Kỹ thuật phân cụm
Thời gian
(giây)
Độ chính
xác (%)
1.

K-Means
910 73.5943
2.

EM
1506 73.8117
3.

HierarchicalClusterer (BIRCH)
2658 74.8369
Từ bảng kết quả trên, chúng ta có thể thấy, kỹ thuật K-Means có
thời gian thực hiện là ngắn nhất, tuy nhiên, kết quả trả lại có độ chính
- 21 -
xác thấp nhất. Thuật toán EM thực hiện với thời gian trung bình, cho
kết quả tốt hơn so với kỹ thuật K-Means nhưng kém hơn so với
HierarchicalClusterer. Kỹ thuật phân cụm phân cấp với thuật toán
HierarchicalClusterer thực hiện với hời gian lâu nhất, tuy nhiên, kỹ

- 22 -
Từ kết quả thực nghiệm, chúng ta thấy, mỗi thuật toán có thời
gian thực hiện khác nhau, có một mức độ chính xác riêng và khả
năng thực hiện trên từng kích thước dữ liệu là khác nhau. Về độ
chính xác thì sự khác biệt giữa các kỹ thuật là không quá lớn.
Hai thuật toán phân cụm dựa trên phân hoạch K-Means và EM
có thời gian thực hiện nhanh hơn, kết quả trả lại cũng không có sự
khác biệt lớn. Thuật toán phân cụm phân cấp HierarchicalClusterer
thực hiện việc phân cụm với thời gian thực hiện lâu nhất (gần gấp 3
thời gian so với thuật toán K-Means), tuy nhiên, kết quả là độ chính
xác đạt được cao nhất.
Về tổng thể, trên cùng một bộ dữ liệu, các kỹ thuật phân cụm
dựa vào phân hoạch, phân cụm phân cấp với các thuật toán phân cụm
được lựa chọn mặc dù có thời gian thực hiện rất khác nhau, tuy
nhiên, kết quả độ chính xác đạt được không có sự khác biệt quá lớn.
Điều này cũng phần nào khẳng định quá trình tiền xử lý dữ liệu đã
được thực hiện khá tốt.
- 23 -
KẾT LUẬN

Luận văn tập trung nghiên cứu về ứng dụng của kỹ thuật phân
cụm người sử dụng Web dựa trên mẫu truy cập. Thông qua nghiên
cứu, thực nghiêm, chúng tôi đã đạt được một số kết quả sau:
 Khảo sát các kỹ thuật phân cụm trong khai phá dữ liệu, tập