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

Chia sẻ: Vo Kiem | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST

Báo xấu

115
lượt xem 27
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ố...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 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: 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ấ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 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 thức K = (U, R), X ⊆ U quan hệ tương đương R ∈ IND (K) Các tập: RX = U {Y ∈ U/R : Y ⊆ X} − − R X = U {Y ∈ U/R : Y ∩ X ≠ φ } 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 x∈ R X − nếu và chỉ nếu [x ]R ∈ X x∈ R X − nếu và chỉ nếu [x]R ∩ X ≠ ∅ − Và BN R X = R X − R X − được gọi là tập biên của X trên quan hệ R **Mệnh đề − a) X là xác định được trên R nếu và chỉ nếu R X = R X − − b) X là thô trên R nếu và chỉ nếu RX ≠RX − 4
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô 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ô: X ∩ [x ]R ) μ X (x ) = [x]R ta thấy: 0 ≤ μ X (x ) ≤ 1 Do đó R (X ) = {x ∈ U : μ X (x ) = 1} R (X ) = {x ∈ U : μ X (x ) > 0} BN R (X ) = {x ∈ U : 0 < μX (x ) < 1} 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 5
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô • P: I(U) → {0,1}: Hàm cấu trúc phân lớp tập I(x) của đối tượng x ∈ U vào một trong hai tập con là tập có cấu trúc với P(I(x)) = 1 và tập không có cấu trúc với P(I(x)) = 0 • Các xấp xỉ dưới và xấp xỉ trên của một tập X ⊆ U trong không gian ℜ L(ℜ,X) = {x ∈ U | P(I(x)) = 1 & υ(I(x),X) = 1} U(ℜ,X) = {x ∈ U : P(I(x)) = 1 & υ(I(x),X) > 0} ** Biểu diễn tài liệu trong TRSM • T = {t1, t2, ..., tn} = U : tập các thuật ngữ • D = {d1, d2, ..., dM}: tập M tài liệu • Với I là hàm chắc chắn với ngưỡng θ { } I θ (t i ) = t j f D (t i , t j ) ≥ θ ∩ {t i } f D(ti, tj) là số văn bản của tập D mà cả hai từ khoá ti và tj cùng xuất hiện • Hàm tính độ mập mờ: X ∩Y ν ( X ,Y ) = X • Hàm thuộc thô của từ khoá ti ∈T trong X ⊆ T: I θ (t i ) ∩ X μ (t i , X ) = ν ( I θ (t i ), X ) = I θ (t i ) • Từ những giả sử trên ta có thể coi tất cả các lớp dung sai của mỗi ti đều là các tập con có cấu trúc, nghĩa là P(Iθ(ti)) =1 với ∀ ti ∈ T • Các xấp xỉ trên và dưới của tập X ⊆ T trong không gian ℜ vừa xác định được: LR(X) = {ti ∈ T | ν ( I θ (t i ), X ) =1 } , UR(X) = { ti ∈ T | ν ( I θ (t i ), X ) >0 } 6
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô Trọng số của từ khoá ti trong văn bản dj được xác định như sau: ⎧ M ⎪1 + log( fd j (ti )) × log (ti ∈ d j ) f D (ti ) ⎪ ⎪ ⎪ log⎛ M ⎜ f (t ) ⎟ ⎞ ⎪ ⎝ D i ⎠ ωi j = ⎨min th ∈d j ωhj × (ti ∈ U ( R, d j )) ⎪ 1 + log⎛ M ⎜ f (t ) ⎟ ⎞ ⎪ ⎝ D i ⎠ ⎪0 (ti ∉ U ( R, d j )) ⎪ ⎪ ⎩ 7
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô CHƯƠNG II:GIẢI THUẬT PHÂN CỤM TẬP KẾT QUẢ TÌM KIẾM WEB 2.1 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 TRC 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 8
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô Ví dụ: Cho tập D= {d1, d2, d3, d4, d5, d6) Doc Title D1 Languege 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 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 9
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô 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 Từ ma trận TOL xác định lớp tolerance của các từ trong D Term Lớp Tolerance Information Information, query, retrieval, model, language Web Web, query, retrieval Query Information, web, query, retrieval, language Retrieval Information, web, query, retrieval, model,language Model Information, retrieval, model,language Language Information, query, retrieval, model,language Giải thuật được thực hiện để sinh ra K nhóm ( K được chọn phụ thuộc vào chiều dài (số lượng các snippet) của D) Giải thuật Input: D – tập N snippet, K- số nhóm, δ - ngưỡng tương tự với … Output: K nhóm các snippet từ tập D (có thể nạp chồng) với giá trị thuộc mờ 10
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô Bắt đầu D = {d1, d2,...., dM};K là một số tự nhiên - Ngẫu nhiên chọn K nhóm tài liệu C1, C2, ..., CK (các tài liệu đều thuộc D) - Tìm các biểu diễn R1, R2, ..., RK của mỗi nhóm vừa đýợc chọn Nếu S ( U ( ℜ, dj ) , Ri )> δ với ∀dj ∈ D thì Ci = Ci ∪ {dj} và m(dj) = S ( U ( ℜ , d j ) , R i ) Tính R1, R2, ...., RK Số phần tử của các nhóm có Y Y sự thay đổi ? NN Gán tài liệu du chưa được xếp vào nhóm văn bản mà có chứa tài liệu có độ tương tự với du lớn nhất và gán : m(du) = m(NN(du)) x S ( U( ℜ, du ) , U( ℜ, NN( du ) ) ) ; Tính lại R1, R2, ...., RK Kết thúc * Giải thuật xác định đại diện nhóm (determine_cluster- _representatives(RK)) Đại diện nhóm Rk thể hiện nét đặc trưng tiêu biểu của nhóm k, do đó : - Mỗi snippet di trong nhóm Ck phải chứa ít nhất một từ trong Rk . - Những từ trong Rk phải xuất hiện trong hầu hết các snippet thuộc nhóm Ck . - Không phải từ nào trong Rk cũng cần phải xuất hiện trong mỗi snippet thuộc về nhóm Ck . 11
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô Trọng số đối với mỗi từ tj trong Rk được tính như sau: wij = ∑ d i ∈Ck wij {d i ∈ Ck t j ∈ d i } Giải thuật: 1. Rk= ∅ 2. for all di ∈ Ck and tj ∈ di do 3. if f f C (t j ) / C k > σ do k 4. Rk = Rk ∪ tj 5. end if 6. end for 7. if di ∈ Ck and di ∩ Rk = ∅ then 8. Rk = Rk ∪ argmax Rk ∪ arg max t ∈d w j i ij 9. end if trong đó f C (t j ) là số tài liệu trong nhóm Ck có chứa từ tj . k ** Tạo nhãn cho mỗi nhóm Pha tạo nhãn cho từng nhóm chủ đề là công việc vô cùng quan trọng. Vì nhãn thể hiện đặc trưng chung của nhóm và do đó việc tạo ảnh hưởng đến chất lượng toàn bộ giải thuật phân cụm. Giải thuật tạo nhãn thực hiện dựa trên phương pháp n_gram để trích chọn nhóm từ trong phần tử đại diện của mỗi nhóm. Nhóm từ này được chọn làm nhãn (tên chủ đề) của nhóm. Theo phương pháp n_gram để nhóm từ thể hiện được tính sinh động của nhóm thì phải được chọn theo những tiêu chuẩn sau: + Mức độ thường xuyên xuất hiện của nhóm từ trong toàn tập D 12
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô + Mức độ thường xuyên xuất hiện của nhóm từ trong một nhóm + Chiều dài của nhóm (số từ hình thành nên nhóm từ) Do vậy, bằng quan sát trực quan phương pháp TD*IDF có thể thấy rằng những nhóm từ tương đối xuất hiện ít trong toàn tập D nhưng xuất hiện thường xuyên trong từng snippet của mỗi nhóm sẽ là ứng cử viên sáng giá cho việc chọn làm nhãn của nhóm 2.2 Một số thuật toán phân cụm không giám sát 2.2.1 Phương pháp phân hoạch • Thuật toán K-means • Thuật toán K-medoids 2.2.2 Phương pháp phân cấp Phân cụm phân cấp được chia thành hai phương pháp là : top-down và bottom-up. 1 Phương pháp bottom-up: Phương pháp này được thiết kế theo chiến lược từ dưới lên (bottom-up). Phương pháp này bắt đầu với mỗi đối tượng được khởi tạo tương ứng với các cụm riêng biệt, sau đó ghép những cụm này thành các cụm lớn hơn cho tới khi tất cả đối tượng đều nằm trong một cụm duy nhất hoặc cho tối khi gặp điều kiện dừng. 2 Phương pháp top-down: Phương pháp này được thiết kế theo chiến lược trên xuống (top-down), nó thực hiện ngược lại so với phương pháp bottom-up, tức là chia nhỏ cụm lớn thành các cụm nhỏ hơn cho tới khi mỗi đối tượng được chứa trong một cụm riêng lẻ hoặc gặp điều kiện dừng như: đạt đến số lượng các cụm cho phép, hoặc khoảng cách giữa hai cụm gần nhất đã lớn hơn khoảng cách ngưỡng. 13
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô • Thuật toán CURE CURE là thuật toán sử dụng chiến lược bottom-up của phương pháp phân cụm phân cấp. Khác với hai thuật toán phân cụm phân hoạch ở trên thuật toán CURE sử dụng nhiều đối tượng để biểu diễn cho một cụm thay vì sử dụng các trọng tâm hay đối tượng tâm. Các đối tượng đại diện của một cụm ban đầu được chọn rải rác đều ở các vị trí khác nhau, sau đó chúng được di chuyển bằng cách co lại theo một tỉ lệ nhất định nào đó. Khi hai cụm có cặp đối tượng đại diện gần nhất sẽ được trộn lại thành một cụm. • Thuật toán BIRCH BIRCH là thuật toán phân cụm phân cấp sử dụng chiến lược Top-down. Tư tưởng của BIRCH là không lưu toàn bộ đối tượng dữ liệu của các cụm trong bộ nhớ mà chỉ lưu các tham số thống kê. Đối với mỗi cụm dữ liệu, BIRCH chỉ lưu bộ ba (N, LS, SS), trong đó N là số đối tượng trong cụm, LS là tổng các giá trị thuộc tính của các đối tượng trong cụm, và SS là tổng bình phương của các giá trị thuộc tính của các đối tượng trong cụm. Bộ ba này được gọi là đặc trưng cụm (Cluster Feature- CF). Khi đó các cụm trong tập dữ liệu ban đầu sẽ được cho dưới dạng một cây 14
Phân cụm tập kết quả tìm kiếm web dựa vào tập thô TÀI LIỆU THAM KHẢO 1. Tolerance rough set approach to clustering web search result, Ngô Chi Lăng -2003 2. Unsupervised Word Discriimation by Clustering Similar Contexts,Amruta Purandare -2004 3. Valued Tolerance and Decision Rlues, Jerzy Stefanowski 4. From n_gramn to collocation an evaluation of xtract 15