BỘ CÔNG THƯƠNG
TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
------------

BÀI TẬP LỚN
MÔN HỌC: Lý thuyết tập thô và ứng dụng
ĐỀ TÀI : Tìm hiểu ứng dụng lý thuyết tập thô trong bài toán
“Phân cụm tập kết quả tìm kiếm web”.
Giáo viên hướng dẫn:
Lớp: KHMT1 – K7
Nhóm thực hiên:

Hà Nội, tháng 12 năm 2015

Page |0


LỜI NÓI ĐẦU
Ngày nay với sự bùng nổ thông tin , Word Wide Web(www) trở thành nguồn tài nguyên
khổng lồ và quý giá. Nó cung cấp cho chúng ta thông tin về mọi lĩnh vực đời sống xã hội, khoa
học v.v… Tuy nhiên đi đôi với sự thuận lợi ấy có một vấn đề được đặt ra là chúng ta làm thế
nào để truy cập và khai phá được nguồn tài nguyên ấy hiệu quả nhất. Từ vấn đề trên người ta
đã nghiên cứu và tạo ra Máy truy tìm web(Web search engine). Máy này có khả năng tìm kiếm
thông tin linh hoạt , nhanh chóng và rất dễ sử dụng . Người sử dụng chỉ cần đặt câu hỏi truy
vấn về vấn đề cần quan tâm là có được tập kết quả liên quan đến câu hỏi truy vấn đó.Hiện nay
Google1 , Altavista2 , HotBot3 , Lycos4 , AllTheWeb5 là những máy truy tìm hiệu quả và đang
được sử dụng rộng rãi . Ngoài ra, người ta cũng đã tạo ra các thư mục Web , chẳng hạn như
Yahoo6 ,Open Directory Project7 . Theo kiểu này thì các tài liệu Web được sắp xếp thành các
thư có phân cấp, người sử dụng có thể tìm thông tin bắng cách duyệt các cây thư mục và xác
định tài liệu mình cần tìm. Thế nhưng việc tìm kiếm thông tin theo những kiểu trên vẫn không

hiệu quả , chiếm nhiều thời gian vì:
-Khối lượng dữ liệu khổng lồ và tính động của các trang Web, nên máy truy tìm chỉ có
thể sắp xếp một phần các chỉ mục của Web.
-Người sử dụng đặt câu hỏi truy vấn quá ngắn, không thể hiện được hết ý định của họ ,
do vậy mà tập kết quả tìm kiếm Web là chung chung.
Từ ảnh hưởng hai nhân tố trên tập kết quả tìm kiếm Web có thể từ hàng nghìn đến hang
triệu tài liệu, do đó tìm được đúng tài liệu mình cần là công việc vô cùng khó khăn. Từ đó
nhằm giải quyết vấn đề này, bài toán phân cụm đã được đưa ra và áp dụng. Bài báo cáo sau
đây sẽ bước đâu tìm hiểu và làm rõ kỹ thuật “phân cụm tập kết quả tìm kiếm web” để người
đọc có một cái nhìn mới hơn, rõ ràng hơn về một lĩnh vực không phải là mới nhưng đem lại
kết quả tìm kiếm web có chất lượng hơn.

Page |1


MỤC LỤC
LỜI NÓI ĐẦU 1
MỤC LỤC

2

CHƯƠNG 1: LÝ THUYẾT TẬP THÔ 3
I.GIỚI THIỆU

3

II.HỆ THÔNG TIN

3


III.QUAN HỆ BẤT KHẢ PHÂN BIỆT
1.Sự dư thừa thông tin

4

4

2.Quan hệ tương đương – Lớp tương đương 5
3.Thuật toán xác định lớp tương đương 6
IV.XẤP XỈ TẬP HỢP

7

V.SỰ KHÔNG CHẮC CHẮN VÀ HÀM THUỘC 10
VI.SỰ PHỤ THUỘC GIỮA CÁC TẬP THUỘC TÍNH
VII.RÚT GỌN THUỘC TÍNH
1.Khái niệm

12

13

13

2.Ma trận phân biệt, hàm phân biệt

15

CHƯƠNG 2: BÀI TOÁN PHÂN CỤM TẬP KẾT QUẢ TÌM KIẾM WEB


18

I.GIỚI THIỆU BÀI TOÁN 18
II.ỨNG DỤNG LÝ THUYẾT TẬP THÔ TRONG GIẢI QUYẾT BÀI TOÁN
1.KHÁI NIỆM CƠ BẢN

19

19

2.GIẢI THUẬT PHÂN CỤM TẬP KẾT QUẢ TÌM KIẾM WEB

21

CHƯƠNG 3: MỘT SỐ GIAO DIỆN KHI CHẠY CHƯƠNG TRÌNH DEMO 29
1.Giao diện chương trình chính 29
2.Giao diện kết quả của thuật toán phân cụm K-means
TÀI LIỆU THAM KHẢO

29

30

Page |2


CHƯƠNG 1: LÝ THUYẾT TẬP THÔ
I.GIỚI THIỆU
Lý thuyết tập thô (rough set theory) lần đầu tiên được đề xuất bởi Z. Pawlak và
nhanh chóng được xem như một công cụ xử lý các thông tin mơ hồ và không chắc chắn. Lý

thuyết tập thô dựa trên giả thiết rằng để định nghĩa một tập hợp, chúng ta cần phải có thông
tin về mọi đối tượng trong tập vũ trụ. Ví dụ, nếu các đối tượng là những bệnh nhân bị một
bệnh nhất định thì các triệu chứng của bệnh tạo thành thông tin về bệnh nhân.
Như vậy tập thô có quan điểm hoàn toàn khác với quan điểm truyền thống của tập hợp,
trong đó mọi tập hợp đều được định nghĩa duy nhất bởi các phần tử của nó mà không cần biết
bất kỳ thông tin nào về các phần tử của tập hợp.
Rõ ràng, có thể tồn tại một số đối tượng giống nhau ở một số thông tin nào đó, và ta nói
chúng có quan hệ bất khả phân biệt với nhau. Đây chính là quan hệ mấu chốt và là điểm xuất
phát của lý thuyết tập thô : biên giới của tập thô là không rõ ràng, và để xác định nó chúng ta
phải đi xấp xỉ nó bằng các tập hợp khác nhằm mục đích cuối cùng là trả lời được (tất nhiên
càng chính xác càng tốt) rằng một đối tượng nào đó có thuộc tập hợp hay không.

II.HỆ THÔNG TIN
Một tập dữ liệu thể hiện dưới dạng bảng, trong đó mỗi dòng thể hiện cho một trường
hợp, một sự kiện, một bệnh nhân hay đơn giản là một đối tượng. Mỗi cột bảng thể hiện một
thuộc tính (là một giá trị, một quan sát, một đặc điểm, …) được “đo lường” cho từng đối
tượng. Ngoài ra giá trị của thuộc tính cũng có thể được cung cấp bởi chuyên gia hay bởi người
sử dụng. Một bảng như vậy được gọi là môt hệ thông tin (information system).
Một cách hình thức, hệ thông tin là một cặp A =(U,A) trong đó U là tập hữu hạn các đối
tượng và được gọi là tập vũ trụ, A là tập hữu hạn không rỗng các thuộc tính sao cho
với mọi

. Tập

được gọi là Tập giá trị của thuộc tính a.

Page |3


Ví dụ 1-1: Bảng dữ liệu dưới đây cho ta hình ảnh về một hệ thống tin với 7 đối tượng và

2 thuộc tính

Age

LEMS

x1

16 – 30

50

x2

16 – 30

0

x3

31 – 45

1 – 25

x4

31 – 45

1 – 25


x5

46 – 60

26 – 49

x6

16 – 30

26 – 49

x7

46 – 60

26 – 49

Bảng 1- 1 : Một hệ thông tin đơn giản
Ta có thể dễ dàng nhận thấy rằng trong bảng trên, các cặp đối tượng x3, x4 và x5, x7 có giá
trị bằng nhau tại cả 2 thuộc tính. Khi đó ta nói rằng các đối tượng này không phân biệt từng đôi
với tập thuộc tính {Age, LEMS}.
Trong nhiều ứng dụng, tập vũ trụ được phân chia thành các tập đối tượng con bởi một
tập các thuộc tính phân biệt được gọi là tập thuộc tính quyết định. Nói cách khác tập vũ trụ
đã được phân lớp bởi thuộc tính quyết định. Hệ thông tin trong trường hợp này được gọi là
một hệ quyết định. Như vậy hệ quyết định là một hệ thông tin có dạng A = (U , C ∪ D) trong
đó A = C ∪ D , C và D lần lượt được gọi là tập thuộc tính điều kiện và tập thuộc tính quyết
định của hệ thông tin.

III.QUAN HỆ BẤT KHẢ PHÂN BIỆT

1.Sự dư thừa thông tin
Một hệ quyết định (hay một bảng quyết định) thể hiện tri thức về các đối tượng
trong thế giới thực. Tuy nhiên trong nhiều trường hợp bảng này có thể được tinh giảm do tồn
tại ít nhất hai khả năng dư thừa thông tin sau đây:
Page |4


 Nhiều đối tượng giống nhau, hay không thể phân biệt với nhau lại được thể
hiện lặp lại nhiều lần.
 Một số thuộc tính có thể là dư thừa, theo nghĩa khi bỏ đi các thuộc tính này thì
thông tin do bảng quyết định cung cấp mà chúng ta quan tâm sẽ không bị mất
mát.
Ví dụ 1-2 : Trong bảng ở Bảng 1-2 dưới đây, nếu chúng ta chỉ quan tâm tới tập
thuộc tính {a, b, c} của các đối tượng thì ta sẽ có nhận xét: có thể bỏ đi thuộc tính c mà thông
tin về các đối tượng vẫn không đổi, chẳng hạn nếu ta có một đối tượng với hai thuộc tính a
, b nhận hai giá trị 0, 1 thì có thể nói ngay rằng giá trị của nó tại thuộc tính c là 1.

Bảng 1- 2 : Một bảng dữ liệu dư thừa thông tin

2.Quan hệ tương đương – Lớp tương đương
Chúng ta bắt đầu xem xét vấn đề dư thừa thông tin nói trên qua khái niệm quan hệ tương
đương. Một quan hệ 2 ngôi

được gọi là quan hệ tương đương khi và chỉ khi:

 R là quan hệ phản xạ:
 R là quan hệ đối xứng :
 R là quan hệ bắc cầu :

và


Một quan hệ tương đương R sẽ phân hoạch tập đối tượng thành các lớp tương đương,
Page |5


trong đó lớp tương đương của một đối tượng x là tập tất cả các đối tượng có quan hệ R với x.
Tiếp theo, xét hệ thông tin A=(U,A). Khi đó mỗi tập thuộc tính

đều tạo ra tương

ứng một quan hệ tương đương INDA:
INDA(B) =
INDA(B) được gọi là quan hệ B – bất khả phân biệt. Nếu

INDA(B) thì các đối

tượng x và x2 là không thể phân biệt được với nhau qua tập thuộc tính B. Với mọi đối tượng
, lớp tương đương của x trong quan hệ INDA(B) được kí hiệu bởi [ x] B . Cuối cùng, quan
hệ B – bất khả phân biệt phân hoạch tập đối tượng U thành các lớp tương đương mà ta kí hiệu
là

3.Thuật toán xác định lớp tương đương
Vào:
 Tập đối tượng O
 Tập thuộc tính B
Ra:
 Tập các lớp tương đương L
Thuật toán :
Bước 1 : L =
Bước 2 : Nếu O =

Thì : Thực hiện bước 5.
Ngược lại thực hiện bươc 3.
Page |6


Bước 3 : Xét

O
P = {x}
O = O\{x}
Với mọi phần tử

O:

Nếu x và y không thể phân biệt được qua tập thuộc tính B
Thì:

P=P

{y}

O = O\{y}
L=L

{P}

Bước 4 : Thực hiện bước 2
Bước 5 : Kết thúc

IV.XẤP XỈ TẬP HỢP

Cho hệ thông tin

, tập thuộc tính

, tập đối tượng

. Chúng ta có thể

xấp xỉ tập hợp X bằng cách sử dụng các thuộc tính trong B từ việc xây dựng các tập hợp B –
xấp xỉ dưới và B – xấp xỉ trên được định nghĩa như sau :
 B – xấp xỉ dưới của tập X :

 B – xấp xỉ trên của tập X :
Tập hợp

là tập các đối tượng trong U mà sử dụng các thuộc tính trong B ta có thể biết

chắc chắn được chúng là các phần tử của X
Tập hợp

là tập các đối tượng trong U mà sử dụng các thuộc tín trong B ta chỉ có thể

nói rằng chúng có thể là các phần tử của X
Page |7


Tập hợp BNB(X) =

được gọi là B – Biên của tập X và chứa những đối tượng mà


sử dung các thuộc tính của B ta không thể xác định được chúng có thuộc tập X hay không.
Tập hợp U\

được gọi là B – ngoài của tập X, gồm những đối tượng mà sử dụng tập

thuộc tính B ta biết chắc chắn chúng không thuộc tập X.
Một tập hợp được gọi là thô nếu đường biên của nó là không rỗng, ngược lại ta nói tập
này là rõ. Lưu ý rằng, khái niệm tập thô ở đây cũng gắn liền với tập thuộc tính.

Page |8


Một số tính chất của các tập hợp xấp xỉ :

Chúng ta kết thúc mục này với thuật toán xác định các xấp xỉ trên và xấp xỉ dưới của một
tập đối tượng theo một tập thuộc tính cho trước.
Thuật toán xác định xấp xỉ dưới
Vào :
 Tập các đối tượng X
 Tập các thuộc tính B
Ra :
 Tập các đối tượng B X
Thuật toán :
Bước 1: Khởi tạo B X =∅.
Xác định tập các phân hoạch P của tập vũ trụ U tạo bởi B.
Bước 2: U1 = U
Page |9


Nếu U1 ≠ ∅

Thì : Thực hiện bước 3.
Ngược lại : Thực hiện bước 5
Hết nếu
Bước 3: Xét x ∈ U1
Tìm phân hoạch Pi ∈ P sao cho : x ∈ Pi .
Nếu Pi ⊆ X
Thì : B X B X  Pi
Hết nếu
U1 = U1 \ Pi .
Bước 4: Thực hiện bước 2.
Bước 5: Kết thúc

Thuật toán xác định xấp xỉ trên
Vào :
 Tập các đối tượng X
 Tập các thuộc tính B
Ra :
 Tập các đối tượng B X
Thuật toán :
Bước 1: Khởi tạo B X = ∅.
Xác định tập các phân hoạch P của tập vũ trụ U tạo bởi B.
Bước 2: X1 = X
P a g e | 10


Nếu X1 ≠ ∅
Thì : Thực hiện bước 3.
Ngược lại : Thực hiện bước 5
Hết nếu
Bước 3 : Xét x ∈ X1.

Tìm phân hoạch Pi ∈ P sao cho : x ∈ Pi .

B X  B X  Pi
Với mọi p ∈ Pi ∩ X1
X1 = X1\{p}
Hết với mọi
Bước 4 : Thực hiện bước 2.
Bước 5 : Kết thúc.

V.SỰ KHÔNG CHẮC CHẮN VÀ HÀM THUỘC
Chúng ta đã biết BNB(X) là tập các đối tượng trong tập vũ tụ U mà bằng cách sử dụng tập
thuộc tính B ta không thể xác định được chắc chắn chúng có thuộc tập đối tượng X đó hay
không. Do đó, sự không chắc chắn trong ngữ cảnh này gắn với một câu hỏi về độ thuộc của
các phần tử vào một tập hợp
B
Trong lý thuyết tập thô, hàm thuộc thô  x là khái niệm dùng để đo mức độ thuộc của một

đối tượng x trong tập vũ trụ U vào tập các đối tượng
giữa tập X và lớp tương đương

và được tính bởi mức độ giao nhau

mà đối tượng x thuộc về. Ta có:

P a g e | 11


Một số tính chất của hàm thuộc thô:

Ví dụ 1-3 : Xét bảng quyết định dưới đây

A0

A1

A2

A3

A4

x0

1

A

2

34

Black

x1

2

A

3


23

Blue

x2

4

B

3

32

White

x3

1

B

2

12

Black

x4


3

B

1

32

Blue

x5

1

B

4

12

Black

Bảng 1- 3 : Bảng quyết định dùng minh hoạ hàm thuộc thô
Xét tập thuộc tính B = {A0 , A1 }và tập đối tượng X = {x0 , x1 , x3 }. Lớp tương đương
tương ứng với quan hệ IND(B) là: E1 = {x0}, E2 = {x1}, E3 = {x2}, E4 = {x3, x5}, E5 = {x4}
Áp dụng định nghĩa hàm thuộc thô, ta thu được :

P a g e | 12



Từ định nghĩa hàm thuộc thô, hai khái niệm xấp xỉ trên và xấp xỉ dưới có thể được xây
dựng một cách tổng quát tương ứng với một độ rõ bất kỳ

như sau:

Lưu ý rằng hai khái niệm xấp xỉ trên và xấp xỉ dưới mà ta đã xây dựng trong phần 1.4
tương ứng với trường hợp độ rõ

=1.0.

VI.SỰ PHỤ THUỘC GIỮA CÁC TẬP THUỘC TÍNH
Một vấn đề quan trọng trong phân tích dữ liệu là khám phá sự phụ thuộc giữa các thuộc
tính. Một cách trực giác, một tập thuộc tính D được cho là phụ thuộc hoàn toàn vào tập thuộc
tính C, ký hiệu C ⇒ D, nếu tất cả các giá trị của các thuộc tính trong D có thể được xác định
duy nhất bởi các giá trị của các thuộc tính trong C. Nói cách khác, D phụ thuộc hoàn toàn vào
C nếu tồn tại một ánh xạ từ các giá trị của tập C tới các giá trị của tập D. Khái niệm phụ thuộc
thuộc tính được thể hiện dưới dạng hình thức như sau.
Cho C và D là các tập con của tập thuộc tính A. Ta nói D phụ thuộc C với độ phụ thuộc k
(0 ≤ k ≤ 1), kí hiệu C ⇒k D nếu:

trong đó

được gọi là C -vùng dương của D. Đây là tập các

đối tượng của U mà bằng cách sử dụng tập thuộc tính C ta có thể phân chúng một cách duy
nhất vào các phân hoạch của U theo tập thuộc tính D.
Dễ dàng thấy rằng :

P a g e | 13



Nếu k = 1 thì ta nói D phụ thuộc hoàn toàn vào C, ngược lại nếu k < 1 thì ta nói D phụ
thuộc một phần vào C với độ phụ thuộc k.
Có thể nhận thấy rằng nếu D phụ thuộc hoàn toàn vào C thì IND(C)⊆ IND(D). Điều này
có nghĩa là các phân hoạch tạo ra bởi tập thuộc tính C mịn hơn các phân hoạch tạo ra bởi D.

VII.RÚT GỌN THUỘC TÍNH
1.Khái niệm
Xét hệ thông tin A = (U , A) và hai tập thuộc tính P, Q ⊆ A . Thuộc tính a∈ P được gọi là
có thể bỏ được (dispensible) trong P nếu IND(P) = IND(P − {a}), ngược lại ta nói a là không
thể bỏ được (indispensible) trong P. Rõ ràng thuộc tính có thể bỏ được không làm tăng / giảm
khả năng phân loại khi có / không có mặt thuộc tính đó trong P. Tập tất cả các thuộc tính
không thể bỏ được trong P được gọi là lõi (core) của P, ký hiệu CORE(P). Lưu ý rằng lõi có
thể là tập rỗng, và khi đó mọi tập con của P với lực lượng bằng card (P) − 1 đều giữ nguyên
khả năng phân loại của P.
Khi loại ra khỏi P một số thuộc tính có thể bỏ được thì ta được một tập rút gọn của P.
Nói cách khác, rút gọn của một tập thuộc tính P là tập thuộc tính B ⊆ P giữ nguyên khả năng
phân loại của P, hay IND(B) = IND(P). Dễ dàng thấy rằng, vì lõi của P là tập các thuộc tính
không thể bỏ được của P nên tất cả các rút gọn của P đều chứa tập thuộc tính lõi.
Một rút gọn B của tập thuộc tính P được gọi là rút gọn hoàn toàn nếu với mọi tập thuộc
tính B' ⊂ B, B' không là rút gọn của P. Như vậy rút gọn hoàn toàn là tập thuộc tính nhỏ nhất
trong tất cả các rút gọn có thể có của P và được ký hiệu là RED(P).
Tính chất: Tập thuộc tính lõi của P là giao của tất cả các rút gọn hoàn toàn của P, tức là:
CORE( P) =

RED(P)

Để minh hoạ cho những khái niệm trên, ta xét ví dụ sau.
Ví dụ 1-4 : Xét Bảng 1-3 với tập thuộc tính P = {a, b, c}. Ta có:
P a g e | 14



U | IND(P) = {{1},{2,3,4},{5,6},{7,8,9}}
U | IND({a}) = {{1,2,3,4},{5,6,7,8,9}}
U | IND({b}) = {{1,5,6},{2,3,4,7,8,9}}
U | IND({c}) = {{1,2,3,4},{5,6,7,8,9}}
U | IND({a, b}) = {{1},{2,3,4},{5,6},{7,8,9}}
U | IND({b, c}) = {{1},{2,3,4},{5,6},{7,8,9}}
U | IND({c, a}) = {{1,2,3,4},{5,6,7,8,9}}
Vì {a, b} và {b, c} là hai tập thuộc tính con nhỏ nhất của P và giữ nguyên khả năng phân
loại tập U của P, tức là : U | IND({a, b}) = U | IND({b, c}) = U | IND(P) nên chúng là hai rút
gọn hoàn toàn của P. Lõi của P là {b}.
Thuộc tính a được gọi là Q - có thể bỏ được (Q – dispensible) trong P nếu POSP(Q) =
POSP−{a} (Q), ngược lại là Q - không thể bỏ được (Q-indispensible). Tập tất cả các thuộc tính Q
- không thể bỏ được trong P được gọi là Q - lõi tương đối (Q – relative core) của P hay Q - lõi
(Q – core) của P và được ký hiệu là COREQ(P).
Tập thuộc tính B ⊆ P được gọi là Q - rút gọn (Q – reduct) của P khi và chỉ khi POS B(Q)
= POSP(Q) . Một tập Q - rút gọn B của P là Q - rút gọn hoàn toàn nếu với mọi tập thuộc tính B
'⊂ B, B' không là Q - rút gọn của P . Như vậy, Q - rút gọn hoàn toàn của P là tập thuộc tính
nhỏ nhất trong tất cả các Q - rút gọn của P và được ký hiệu là REDQ(P).
Tính chất: Tập thuộc tính Q - lõi của P là giao của tất cả các tập thuộc tính Q- rút gọn
tương đối của P, tức là:
COREQ(P) =

REDQ(P)

2.Ma trận phân biệt, hàm phân biệt
Xét hệ thông tin A = (U , A) có n đối tượng. Ma trận phân biệt của A là ma trận đối xứng
kích thước nxn có các phần tử cij được cho như sau:
cij = {a ∈ A | a( xi ) ≠ a( x j )} với i, j = 1,2,..., n


P a g e | 15


Như vậy mỗi phần tử cij của ma trận phân biệt là tập hợp các thuộc tính để phân biệt hai
đối tượng xi và xj .
Ví dụ 1-6 : Xét một hệ thông tin đơn giản trong Bảng 1-4 với 3 thuộc tính và 4 đối tượng.
Phần tử tại dòng 1 cột 3 cũng như phần tử tại dòng 3 cột 1 là tập thuộc tính {a, c} nói lên rằng
hai đối tượng x1 và x3 nhận giá trị khác nhau tại hai thuộc tính a và c.
x1

a
1

b
0

c
1

x2

1

1

2

x3


0

0

2

x4

1

0

1

Bảng 1- 4 : Hệ thông tin dùng minh hoạ ma trận phân biệt
Hệ thông tin trên sẽ có ma trận phân biệt kích thước 4 x 4 như sau :

x1

x2

x3

x4

x1

{}

{b, c}


{a, c}

{}

x2

{b, c}

{}

{a, b}

{b, c}

x3

{a, c}

{a, b}

{}

{a, c}

x4

{}

{b, c}


{a, c}

{}

Hình 1- 1 : Ma trận phân biệt của Bảng 1- 4
Ma trận phân biệt không chỉ được định nghĩa trên tập tất cả các thuộc tính của hệ thông
tin mà còn có thể được xây dựng trên một tập thuộc tính B ⊆ A bất kỳ. Trong trường hợp đó,
phần tử cij là tập các thuộc tính trong B phân biệt hai đối tượng xi, xj. Chẳng hạn với hệ thông
tin trong Bảng 1-4, ma trận phân biệt xây dựng trên tập thuộc tính {a, b} được thể hiện trong
Hình 1 - 2.
Xét ma trận phân biệt được xây dựng trên tập thuộc tính B ⊆ A. Giả sử tập thuộc tính B
phân hoạch tập đối tượng thành các lớp tương đương X1, X2,..., XK, và do hai đối tượng thuộc
một lớp tương đương thì nhận giá trị như nhau tại các thuộc tính trong B nên thay vì xây dựng
ma trận phân biệt giữa từng cặp đối tượng, ta xây dựng ma trận phân biệt giữa từng cặp lớp
tương đương. Khi đó, phần tử cij, ∀i, j ∈ {1,2,..., K} là tập hợp thuộc tính phân biệt hai đối
P a g e | 16


tượng bất kỳ thuộc hai lớp tương đương Xi và Xj, hay có thể nói cij là tập các thuộc tính phân
biệt
x1

x2

x3

x4

x1


{}

{b}

{a}

{}

x2

{b}

{}

{a, b}

{b}

x3

{a}

{a, b}

{}

{a}

x4


{}

{b}

{a}

{}

Hình 1- 2 : Ma trận phân biệt của hệ thông tin Bảng 1- 4 xây dựng trên tập thuộc tính
{a, b}
hai lớp tương đương Xi và Xj. Rõ ràng, ma trận phân biệt giữa từng lớp tương đương vẫn giữ
nguyên giá trị về thông tin như ma trận phân biệt giữa từng cặp đối tượng, ngoài ra kích thước
ma trận phân biệt đã được giảm đi đáng kể.
Một số lưu ý về hàm phân biệt:
 Các toán tử ∧ và ∨ sử dụng trong hàm phân biệt không phải là các toán tử
Boolean vì chúng không nhận các giá trị true hay false mà thể hiện cho ngữ nghĩa
có mặt hay không có mặt của một thuộc tính nào đó. Theo đó, hàm phân biệt:
fA = (a ∨ b ∨ c ∨ f ) ∧ (b ∨ d ) ∧ (a ∨ d ∨ e ∨ f ) ∧ (a ∨ b ∨ c ∨ d ) ∧
(b ∨ d ∨ e ∨ f ) ∧ (d ∨ c)
được hiểu như sau: các đối tượng trong hệ thông tin có thể được phân biệt với
nhau bằng cách sử dụng (thuộc tính a hoặc b hoặc c hoặc f ) và (thuộc tính b hoặc
d ) và (thuộc tính a hoặc d hoặc e hoặc f ) và (thuộc tính a hoặc b hoặc c hoặc d )
và (thuộc tính b hoặc d hoặc e hoặc f ) và (thuộc tính d hoặc c).
 Hàm phân biệt có thể xem như một tập các tập hợp. Ví dụ, hàm phân biệt trong
lưu ý trên tương đương với tập:
C = {{a, b, c, f}, {b, d}, {a, d, e, f}, {a, b, c, d}, {b, d, e, f}, {d , c}}
Và cũng giống như với ma trận phân biệt, tập nhỏ nhất có giao với tất cả các phần tử của
C chính là các rút gọn của hệ thông tin tương ứng. Ví dụ : {a, d} là một trong các tập nhỏ nhất
P a g e | 17



có giao với tất cả các phần tử của C nên nó là một rút gọn của hệ thông tin.

P a g e | 18


CHƯƠNG 2: BÀI TOÁN PHÂN CỤM TẬP KẾT QUẢ TÌM KIẾM WEB
I.GIỚI THIỆU BÀI TOÁN
Sự phát triển nhanh chóng của mạng Internet đã sinh ra một khối lượng khổng lồ các dữ
liệu dạng siêu văn bản (dữ liệu Web). Các tài liệu siêu văn bản chứa đựng văn bản và thường
nhúng các liên kết đến các tài nguyên khác phân bố trên Web. Ngày nay, Web bao gồm hàng tỷ
tài liệu của hàng triệu tác giả được tạo ra và được phân tán qua hàng triệu máy tính được kết
nối qua đường dây điện thoại, cáp quang, sóng radio v.v.. Web đã và đang được sử dụng phổ
biến trong nhiều lĩnh vực như báo chí, phát thanh, truyền hình, hệ thống bưu điện, trường học,
các tổ chức thương mại, chính phủ v.v.. Chính vì vậy lĩnh vực Web mining hay tìm kiếm tự
động các thông tin phù hợp và có giá trị trên Web là một chủ đề quan trọng trong Data Mining
và là vấn đề quan trọng của mỗi đơn vị, tổ chức có nhu cầu thu thập và tìm kiếm thông tin trên
Internet.
Hiện nay, các hệ thống tìm kiếm thông tin hay nói ngắn gọn là các máy tìm kiếm Web
thông thường trả lại một danh sách các tài liệu được phân hạng mà người dùng sẽ phải tốn
công chọn lọc trong một danh sách rất dài để có được những tài liệu phù hợp. Ngoài ra các
thông tin đó thường rất phong phú, đa dạng và liên quan đến nhiều đối tượng khác nhau. Điều
này tạo nên sự nhập nhằng gây khó khăn cho người sự dụng trong việc lấy được các thông tin
cần thiết.
Có nhiều hướng tiếp cận khác nhau để giải quyết vấn đề này. Các hướng này thường chú
ý giảm sự nhập nhằng bằng các phương pháp lọc hay thêm các tùy chọn để cắt bớt thông tin và
hướng biểu diễn các thông tin trả về bởi các máy tìm kiếm thành từng cụm để cho người dùng
có thể dễ dàng tìm được thông tin mà họ cần. Đã có nhiều thuật toán phân cụm tài liệu dựa trên
phân cụm ngoại tuyến toàn bộ tập tài liệu. Tuy nhiên việc tập hợp tài liệu của các máy tìm

kiếm là quá lớn và luôn thay đổi thì khó có thể phân cụm ngoại tuyến. Do đó, việc phân cụm
phải được ứng dụng trên tập các tài liệu nhỏ hơn được trả về từ các truy vấn và thay vì trả về
một danh sách rất dài các thông tin gây nhập nhằng cho người sử dụng cần có một phương
pháp tổ chức lại các kết quả tìm kiếm một cách hợp lý.

P a g e | 19


II.ỨNG DỤNG LÝ THUYẾT TẬP THÔ TRONG GIẢI QUYẾT BÀI
TOÁN
1.KHÁI NIỆM CƠ BẢN
a.Phân cụm
Phân cụm là nhóm các đối tượng lại thành các cụm sao cho thoả mãn :
-Các đối tượng trong mỗi cụm là giống nhau hoặc gần nhau được xác định bằng độ tương
tự . Hay nói cách khác, các đối tượng trong mỗi cụm là tương tự nhau.
-Những đối tượng không cùng một cụm là không tương tự nhau.
Cần phân biệt giữa phân lớp với phân cụm: Phân lớp còn được gọi học có giám sát . Là
quá trình xếp một đối tượng vào trong những lớp đã biết trước . Ví dụ phân lớp các bệnh nhân
theo dữ liệu hồ sơ bệnh án . Phân cụm còn được gọi học không giám sát .Là quá trình xếp các
đối tưọng theo từng cụm tự nhiên, tức là số lượng và tên cụm chưa được biết trước . Việc phân
cụm rất có ích trong đưa ra cái nhìn tổng quan trên toàn thể dữ liệu. Để đạt được điều đó, mỗi
cụm cần được tạo nhãn chủ đề, điểu này giúp cho việc định hướng người dùng về tài liệu trong
cụm đó. Việc tạo nhãn cho cụm là một vấn đề quan trọng và được nhiều nghiên cứu quan tâm.
Yêu cầu về việc phân cụm xuất phát từ lĩnh vực thống kê, nó được áp dụng cho dữ liệu số
. Tuy nhiên, trong lĩnh vực khoa học máy tính và khai phá dữ liệu thì khái niệm này được mở
rộng cho cả dữ liệu text hoặc multimedia.

b.Phân cụm tập kết quả tìm kiếm web
Phân cụm tập kết quả Web là tổ chức sắp xếp tập kết quả tìm kiếm thành một số nhóm
chủ đề riêng theo cách bố cục tổng thể đến chi tiết, giống như các thư mục. Ví dụ đối với câu

hỏi truy vấn “Clinton” thì kết quả được trình bày theo các chủ đề như:”Bill Clinton”, “Hillary
Clinton”, “George Clinton”, v.v…. Theo cách trình bày này cả những người sử dụng không có
kinh nghiệm trong việc đặt câu hỏi truy vấn cũng có thể dễ dàng xác định nhanh chóng và
chính xác tài liệu quan tâm . Mặt khác, đối với những người sử dụng đặt câu hỏi chung chung
với mục đích biết thêm những chủ đề con sẽ không phải mất nhiều thời gian .Thay vào đó , họ
chỉ cần duyệt theo từng nhóm chủ đề.
P a g e | 20


c.Hiệu quả
Việc phân các tài liệu thành từng nhóm cơ bản đã được chứng minh là có hiệu quả trong
trình duyệt một tập lớn các tài liệu. Do đó việc phân cụm tập kết quả cũng có những ưu điểm
sau:
- Việc tổ chức tập kết quả tìm kiếm thành các chủ để tạo điều kiện thuận lợi khi duyệt lớn
các kết quả tìm kiếm
- Tên của các chủ đề giúp người sử dụng phát hiện được chủ để chính và do đó có thể xác
định nhanh chóng chủ để mình quan tâm.
- Việc phân chia tập kết quả thành các chủ để giúp người sử dụng có thể nghiên cứu thêm
tài liệu liên quan đến các chủ để khác mà họ thường bỏ qua khi duyệt danh sách kết quả tìm
kiếm được trình bày theo phương thức truyền thống ranked list, vì những tài liệu này ở rất xa
trang đầu.

d.Yêu cầu
- Liên quan: Phân cụm phải tạo ra được các nhóm chủ đề khác biệt từ tập kết quả tìm
kiếm web, những kết quả có liên quan với nhau được sắp xếp vào cùng 1 nhóm và không liên
quan thì ở nhóm khác.
- Tính tổng thể: Nhãn của mỗi chủ đề phải ngắn gọn và chính xác. Như vậy mới giúp
người sử dụng xác định nhanh chóng chủ để quan tâm và tránh phải duyệt rải rác trên toàn tập
kết quả.
- Nạp chồng: Vì mỗi tài liệu có thể thuộc về nhiều chủ để do vậy một tài liệu có thuộc

vào nhiều nhóm khác nhau.
- Tốc độ: Vì được sử dụng trong hệ thông online, do vậy một yêu cầu về tốc độ xử lý
phân cụm là vô cùng quan trọng để không làm chậm quá trình xử lý truy vấn.

P a g e | 21


2.GIẢI THUẬT PHÂN CỤM TẬP KẾT QUẢ TÌM KIẾM WEB
a .Giải thuật
Input : Tập D gồm N snippet d1, d2,…., dN
Output : K nhóm chủ đề khác biệt
Mô hình dữ liệu:
* Áp dụng mô hình không gian vector để biểu diễn kết quả tìm kiếm snippet. Cụ thể:
- Mỗi snippet được biểu diễn bởi một vector nhiều chiều. Mỗi một chiều là tương ứng với
một từ trong snippet.
- Giả sử trong tập N snippet có M từ riêng biệt nhau. Khi đó, một snippet được biểu diễn
dưới dạng một vector như sau:
di= (wi1, wi2 , ..., wiM) , trong đó wij là trọng số của từ thứ j trong snippet di .
Vì mỗi một snippet trong D có một chiều dài riêng (có số lượng từ khác nhau). Do vậy
để giải thuật phân cụm cho ra kết quả chính xác thì cần chuẩn hóa số chiều của vectơ tương
ứng với mỗi snippet trong D. Như vây, với tập D sẽ tạo thành một ma trận document-terms.
Giải thật phân cụm gồm có 5 pha:
1. Tiền xử lý snippet
2. Trích chọn từ đặc trưng của mỗi snippet (những từ thể hiện nội dung chính của
snippet)
3. Sinh các lớp tolerance
4. Phân cụm
5. Tạo nhãn cho từng nhóm

P a g e | 22



Ví dụ: Cho tập D= {d1, d2, d3, d4, d5, d6)
Doc

Title

D1

Language modeling approach to information retrieval: the importance of a query
term

D2

Title language model for information retrieval

D3

Two-stage language models for information retrieval

D4

Building a web theaurus from web link structure

D5

Implicit link analysis for small web search

D6


Query type classification for web document retrieval

Bước 1: Dựa vào ma trận tần số xuất hiện TF để tính ma trận xuất hiện nhị phân OC. Tuy
nhiên trong trường hợp này OC=TF:
Document/Term Information web

Query

Retrieval

Model

Language

D1

1

0

1

1

0

1

D2


1

0

0

1

1

1

D3

1

0

0

1

1

1

D4

0


1

0

0

0

0

D5

0

1

0

0

0

0

D6

0

1


1

1

0

0

P a g e | 23


Bước 2: Tính ma trận cùng tần số xuất hiện (term co-occurrence) COC
Term

Information web

Query

Retrieval

Model

Language

Information 3

0

1


3

2

3

web

0

3

1

1

0

0

Query

1

1

2

2


0

1

Retrieval

3

1

2

4

2

3

Model

2

0

0

2

2


2

Language

3

0

1

3

2

3

Bước3: Tính ma trận nhị phân tolerance(term tolerance binary)TOL với θ > 1
Term

Information web

Query

Retrieval

Model

Language

Information 1


0

1

1

1

1

web

0

1

1

1

0

0

Query

1

1


1

1

0

1

Retrieval

1

1

1

1

1

1

Model

1

0

0


1

1

1

Language

1

0

1

1

1

1

P a g e | 24