Phân cụm tập kết quả tìm kiếm web dựa vào tập thô

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ố...
Nội dung trích xuất từ tài liệu:
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô Phân cụm tập kết quả tìm kiếm web dựa vào tập thô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 SAI1.1 Phân cụm tập kết quả tìm kiếm Web1.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ànhmột số nhóm chủ đề riêng theo cách bố cục tổng thể đến chi tiết, giống như cácthư mục1.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 nhauvà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 đốitượ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 đohệ 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ễndưới dạng một vector). Công thức đo độ tương tự như sau: t ∑x y i =1 i i Cosin(X,Y) = t t ∑ xi2 + i =1 ∑y i =1 2 i 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 1 Phân cụm tập kết quả tìm kiếm web dựa vào tập thô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 2 Phân cụm tập kết quả tìm kiếm web dựa vào tập thô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ấpxỉ 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ượngchắ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ộcvề 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ủakhá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ựatrê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 Tính đối xứng:xRy⇔yRx , với bất kỳ x,y∈U Tính bắc cầu: xRy ∧yRz⇒xRz, với bất kỳ x,y,z∈U 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). 3 Phân cụm tập kết quả tìm kiếm web dựa vào tập thô 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 ...