Phân cụm tập kết quả tìm kiếm web dựa vào tập thô
1
CHƯƠNG I
PHÂN CỤM TẬP KẾT QUẢ TÌM KIẾM WEB DỰA
VÀO TẬP THÔ DUNG SAI
1.1 Phân cụm tập kết quả tìm kiếm Web
1.1.1 Khái niệm
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
1.1.2 Phép đo độ tương tự
Bản chất công việc phân cụm là nhóm những đối tượng tương tự với nhau
vào cùng một nhóm . Vậy cần phải có phép đo để đo độ tương tự giữa các đối
tượng.
Đối với các đối tượng là tài liệu thì người ta thường hay sử dụng phép đo
hệ số góc cosin để đo độ tương tự giữa hai tài liệu (mỗi tài liệu được biểu diễn
dưới dạng một vector). Công thức đo độ tương tự như sau:
Cosin(X,Y) =
∑∑
∑
==
=
+
t
i
t
i
ii
t
i
ii
yx
yx
11
22
1
Trong đó
-X (x1 ,x2 , …..,xt) và Y(y1 ,y2 ,…..,yt) là vector biểu diễn hai tài liệu
-xi ,yi là trọng số thành phần thứ I của vector X,Y tương ứng
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô
2
1.2 Lý thuyết tập thô
1.2.1 Cơ sở tri thức
Cho một tập hữu hạn U ≠ φ (vũ trụ) của các đối tượng được xét đến.
Một tập con X ⊆ U bất kỳ (trường hợp X = φ) của vũ trụ sẽ được gọi là một
khái niệm hoặc một phạm trù trong U
Một họ các khái niệm trong U được gọi là một tri thức về U
C = {Xi, X2, ... Xn}: gọi là một phân hoạch của tập U sao cho Xi ⊆ U, Xi ≠
φ, Xi ∩ Xj = φ với i ≠ j, i, j = 1, ... n và ∪Xi = U.
Một sự phân hoạch vũ trụ U được gọi là một quan hệ tương đương R trên U
Các phạm trù Xi với i=1, 2, …, n là các lớp tương đương của quan hệ R
Kí hiệu:
U/R là họ tất cả các lớp tương đương của R
[x]R là một lớp tương đương của R chứa phần tử x∈U
K= (U, ℜ) gọi là cơ sở tri thức trong đó U ≠ φ là một tập hữu hạn và ℜ là
một họ các quan hệ tương đương trên U
Nếu P ⊆ ℜ và P ≠ φ thì ∩ P (giao của tất cả các quan hệ tương đương
thuộc P) cũng là một quan hệ tương đương, và được ký hiệu là IND (P)
IND(P) còn được gọi là quan hệ không thể phân biệt được trên P
U/IND(P) hay U/P: là một họ của tất cả các lớp tương đương của quan hệ
tương đương IND(P)
U/P được gọi là tri thức cơ sở về U trong K
Lớp tương đương của IND(P) được gọi là phạm trù cơ sở của tri thức P
Nếu R ∈ ℜ thì R được gọi là một tri thức sơ cấp về U trong K và các lớp
tương đương của R được coi như là một phạm trù sơ cấp của tri thức R
IND(K): họ tất cả các quan hệ tương đương được định nghĩa trong K, nghĩa
là IND(K) = {IND(P): φ ≠ P ⊆ ℜ}
==> IND(K) là tập tối thiểu các quan hệ tương đương chứa tất cả các quan
hệ của K
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô
3
1.2.2 Định nghĩa tập thô
Trong lý thuyết tập thô , bất cứ một khái niệm không rõ ràng nào đều
được thay bằng một cặp khái niệm không chính xác gọi là xấp xỉ dưới và xấp
xỉ trên của khái niệm không rõ ràng. Xấp xỉ dưới bao gồm tất cả các đối tượng
chắc chắn thuộc về khái niệm và xấp xỉ trên gồm tất cả các đối tượng có thể thuộc
về khái niệm. Hiệu của xấp xỉ trên và xấp xỉ dưới tạo thành khoảng ranh giới của
khái niệm không rõ ràng . Trong lý thuyết tập thô khái niệm không rõ ràng dựa
trên các xấp xỉ và sự không phân biệt được(quan hệ tương đương).
Cho cơ sở tri thức K= (U, ℜ), X ⊆ U
- U ≠ φ là một tập hữu hạn và ℜ là một họ các quan hệ tương đương
trên U
- X là có thể xác định trên R (R – definable): nếu X là hợp của một
số các phạm trù sơ cấp trênR==>được gọi là tập xác định
- X là không xác định trên R (R – Undefinable): ngược lại ==> được
gọi là tập thô (tập không xác định)
- Tập X ⊆ U được gọi là xác định trong cơ sở tri thức K nếu tồn tại
một quan hệ tương đương R ∈ IND(K) sao cho X là tập xác định trên R
- TậpX⊆ U được gọi là không xác định trong K nếu X là tập thô trên
với mọi R ∈ IND (K).
Trong đó: R(R ⊆ UxU) được gọi là quan hệ không thể phân biệt khi nó là
một quan hệ tương đương.
3 tính chất của quan hệ tương đương R
9 Tính đối xứng:xRy⇔yRx , với bất kỳ x,y∈U
9 Tính bắc cầu: xRy ∧yRz⇒xRz, với bất kỳ x,y,z∈U
9 Tính phản xạ: xRx, với bất kỳ x∈U
Nếu quan hệ R chỉ thoả mãn hai tính chất phản xạ và đối xứng mà
không thoả mãn tính chất bắc cầu thì nó được gọi là một quan hệ dung
sai (Tolerance relation).
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô
4
Nếu R là một quan hệ dung sai thì hai phần tử x, y ∈ U được gọi là
tương tự nhau theo R (R-similar);
Nếu R là một quan hệ tương đương thì hai phần tử x, y ∈ U được gọi là
không thể phân biệt được bởi R (R-indiscernable).
1.2.3 Các tập xấp xỉ của tập thô
Cho cơ sở tri thức K = (U, R), X ⊆ U
quan hệ tương đương R ∈ IND (K)
Các tập:
lần lượt được gọi là các tập xấp xỉ dưới và tập xấp xỉ trên của X
Hoặc
Và
được gọi là tập biên của X trên quan hệ R
**Mệnh đề
b) X là thô trên R nếu và chỉ nếu XRXR −
−≠
XRx
−
∈nếu và chỉ nếu
XRx −
∈nếu và chỉ nếu
[
]
Xx R
∈
UX} Y:U/R{Y ⊆∈=
−XR
U}X Y:U/R{Y
φ
≠∩∈=
−
XR
[
]
∅
≠
∩
Xx R
XRXRXBNR−
−−=
a) X là xác định được trên R nếu và chỉ nếu XRXR −
−=
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô
5
1.2.4 Hàm thuộc thô
Hàm thuộc thô (rough membership function) thể hiện tính phụ thuộc của
một phần tử đối với một tập thô:
Do đó
1.2.5 Mô hình tập thô dung sai(Tolerance rough set model-TRSM )
Cho ℜ = (U, I, υ, P):
U: Tập vũ trụ các đối tượng
I: U→P(U) - Hàm không chắc chắn (uncertainty function)
υ: P(U)×P(U) → [0,1] - Độ mập mờ (vague inclusion)
P: I(U) → {0,1} – Hàm cấu trúc (structurality function)
• Giả sử đối tượng x được nhận biết bằng hàm thông tin Inf(x)
• I: U → P(U) : hàm không chắc chắn xác định I(x) là một lớp dung sai
(tolerance class) của tất cả các đối tượng có cùng thông tin với x
=> I có thể là một hàm bất kỳ sao cho thoả mãn điều kiện: x∈I(x) và y∈I(x)
nếu và chỉ nếu x ∈ I(y) với ∀x, y ∈U
• υ : P(U)× P(U)→ [0,1]: hàm mập mờ đánh giá mức độ bao hàm của các
tập hợp
– cụ thể, nó đánh giá độ bao hàm của lớp dung sai I(x) trong tập thô x
ta thấy:
()
[
]
[]
R
R
Xx
xX
x)∩
=
μ
{
}
{}
{}
() : ()1
() : () 0
() :0 ()1
X
X
RX
RX x U x
RX x U x
BN X x U x
μ
μ
μ
=∈ =
=∈ >
=
∈< <
)
10 ≤≤ x
X
μ