Bất đẳng thức biến phân tựa đơn điệu và thuật toán xấp xỉ giá trị

ủa hai thành phần chủ đề tìm kiếm và không gian tìm kiếm tương ứng với what và where cùng mối quan hệ giữa hai thành phần đó mà ta đã gặp trong chương 3. Do đó, việc tìm kiếm ở đây sẽ không chỉ phụ thuộc vào mức độ liên quan giữa nội dung câu truy vấn và nội dung tài liệu như trong hệ IR truyền thống mà nó còn bao gồm luôn cả sự ràng buộc về mặt không gian đề cập đến trong nội dung tài liệu và trong câu truy vấn. Một ví dụ dễ hiểu là với câu truy vấn “khách sạn Hà Nội” thì hệ IR truyền thống sẽ tìm những tài liệu nào có xuất hiện “khách” và/hoặc “sạn” và/hoặc “Hà” và/hoặc “Nội” và không quan tâm đến việc các khách sạn này nằm ở đâu trong thế giới thực. Trong khi đó, với hệ GIR thì các kết quả chắc chắn phải đảm bảo các khách sạn phải có vị trí địa lý thuộc Hà Nội. Vậy với cấu trúc lập mục được chọn cùng với các yêu cầu tìm kiếm không gian khác nhau, hệ thống sẽ có những phương thức tìm kiếm và xếp hạng như thế nào cho phù hợp và hiệu quả. Đó là nội dung mà luận văn sẽ trình bày trong phần còn lại của chương 4. 4.2 Tìm kiếm: Trong hầu hết mọi kiểu truy vấn trong một hệ GIR với cấu trúc lập chỉ mục kết hợp giữa nội dung và thuộc tính không gian của tài liệu (cấu trúc TS đã chọn trong chương 56 2) thì cơ chế tìm kiếm thường được áp dụng là tìm kiếm trên thành phần nội dung sao cho đảm bảo những kết quả tìm thấy phù hợp với câu truy vấn, đồng thời xác định vùng khung bao của tài liệu có giao nhau với vùng khung bao của câu truy vấn hay không. Kết quả sau cùng sẽ là những tài liệu vừa thỏa mãn câu truy vấn vừa có khung bao giao với khung bao của câu truy vấn. Tuy nhiên, đó là ý tưởng, còn hiện thực ý tưởng thì luôn gặp những vấn đề khó khăn. Tiêu chí để đánh giá một chức năng tìm kiếm hiệu quả có thể gói gọn trong 2 tiêu chí sau:  Độ chính xác của kết quả.  Tốc độ tìm kiếm. Về độ chính xác của kết quả: tiêu chí này phụ thuộc vào cấu trúc chỉ mục, cách lập chỉ mục và kết quả của quá trình phân tích câu truy vấn. Ở đây, với cấu trúc chỉ mục TS trong đó sử dụng cơ chế chỉ mục nghịch đảo (như các hệ IR truyền thống khác đang áp dụng) kết hợp với cấu trúc R-Tree cho chỉ mục không gian cộng với các thuật toán phân tích truy vấn cải tiến đặc biệt hướng tới đối tượng là các câu truy vấn tiếng Việt, cách dùng từ, quan niệm trong tiếng Việt qua thực nghiệm (hình 3-2, 3-3) đã cho thấy độ chính xác của các kết quả nhận được là khá cao. Về tốc độ tìm kiếm: tiêu chí này phụ thuộc vào tốc độ truy cập chỉ mục nội dung và tìm kiếm không gian. Trong đó chi phí cho phần tìm kiếm không gian đóng một vai trò quan trọng vì nó bao gồm luôn cả chi phí xác định vùng giới hạn của câu truy vấn. Có 3 loại truy vấn thường gặp là: tìm kiếm theo vùng (khách sạn ở gần Hà Nội), tìm kiếm xung quanh điểm (nhà hàng ở gần Nhà hát Thành Phố) và tìm kiếm theo đường (café ở trên đường Nam Kỳ Khởi Nghĩa). Mỗi loại truy vấn đều có một phương thức tìm kiếm riêng và độ phức tạp khác nhau. 57 4.2.1 Tìm kiếm theo vùng (Region-based Range Query): Đối với truy vấn theo vùng, điều đầu tiên chúng ta cần xác định là giới hạn của vùng đó như thế nào. Có hai cách lựa chọn để thể hiện giới hạn này (như trình bày trong 1.4) đó là chọn một khung bao hình chữ nhật bao quanh vùng hoặc dùng một đa giác thể hiện chính xác giới hạn của vùng. Độ phức tạp tìm kiếm ở đây sẽ phụ thuộc vào tiêu chí lựa chọn trên. Nếu ta chọn một khung bao chữ nhật, chi phí sẽ rất thấp vì ta có thể biết được khung bao đó từ định nghĩa trên ontology địa lý mà hệ thống sử dụng, vấn đề còn lại là sử dụng chỉ mục để tìm kiếm các tài liệu (đối tượng) nằm trong phần khung bao chữ nhật đó và sắp xếp các kết quả theo công thức tính trong phần 4.3.1 (sẽ trình bày bên dưới). Tuy nhiên, để chính xác hơn, thông thường người ta sẽ chọn cách thể hiện giới hạn vùng bằng một đa giác vừa đủ thể hiện hình ảnh của vùng đó. Lúc này độ phức tạp của bài toán sẽ cao hơn vì cần phải tốn thêm chi phí kiểm tra đối tượng có nằm trong đa giác hay không (sau khi đã tìm thấy những đối tượng nằm trong khung bao chữ nhật của vùng). Về phần kiểm tra một điểm có nằm trong đa giác hay không, đó là một dạng bài toán kinh điển trong các hệ thông tin địa lý (GIS), ta có thể sử dụng ma trận DE-9IM [24] để kiểm tra điều đó. Hình 4-1: Hình minh họa tìm kiếm theo vùng. 58 4.2.2 Tìm kiếm xung quanh điểm (Point-based Range Query): Đây là kiểu truy vấn mà vùng giới hạn tìm kiếm không rõ ràng, hệ thống chỉ biết duy nhất một đối tượng làm tâm điểm của truy vấn này chính là điểm mà người dùng muốn tìm các thông tin xung quanh nó. Vậy câu hỏi là “thế nào là xung quanh?”. Đối với truy vấn dạng này thường sẽ có hai hướng tiếp cận: thứ nhất là cho người dùng chọn 1 bán kính nhất định xung quanh điểm đó, sau đó sẽ tìm các đối tượng nằm trong vùng bán kính đó; và cách thứ hai là hệ thống sẽ tự tìm hết các đối tượng thỏa điều kiện tìm kiếm về mặt nội dung (textual) rồi sau đó sẽ thực hiện xếp hạng các đối tượng đó theo khoảng cách tăng dần so với tâm điểm. Nếu tiếp cận theo cách thứ nhất, vấn đề quay về bài toán tìm kiếm trong vùng. Còn nếu tiếp cận theo hướng thứ hai, thì bài toán sẽ trả giá bằng việc phải tìm tất cả các đối tượng liên quan (dĩ nhiên là sẽ có những đối tượng ở rất xa tâm điểm) nhưng bù lại hệ thống sẽ không tốn một chi phí kiểm tra nào khác. Vấn đề lựa chọn một cách tiếp cận nào là hợp lý tùy thuộc vào người xây dựng hệ thống, tiêu chí tìm kiếm của từng hệ thống. Hình 4-2: Hình minh họa tìm kiếm xung quanh điểm. 59 4.2.3 Tìm kiếm theo đường (Path-based Range Query): Đây là kiểu truy vấn phức tạp hơn cả vì lúc này một khung bao chữ nhật sẽ không đảm bảo tính chính xác của kết quả (hình 4-3). Một ví dụ dễ thấy là với truy vấn “khách sạn ở trên đường Nam Kỳ Khởi Nghĩa”, nếu ta dùng một khung bao chữ nhật cho câu truy vấn trên thì các kết quả sẽ có luôn cả những kết quả ở rất xa đường Nam Kỳ Khởi Nghĩa trong phần lớn trường hợp. Thay vào đó, trong trường hợp này, theo phương pháp tiếp cận truyền thống của các ứng dụng GIS, một vùng đệm (buffer) của đường sẽ được tạo ra dùng để làm vùng giới hạn tìm kiếm (hình 4-4) sẽ giúp cho các kết quả tìm thấy có tính hợp lý cao hơn. Lúc này, chi phí để tạo ra vùng đệm cho một đường là lớn hay nhỏ sẽ ảnh hưởng nhiều hay ít đến tốc độ tìm kiếm của hệ thống. Hình 4-3: Minh họa 1 đoạn đường và khung bao chữ nhật của nó. Hình 4-4: Minh họa 1 đoạn đường và vùng đệm của nó. M. Zadravec [18], đã đề xuất một thuật toán tạo vùng đệm với độ phức tạp là O(nlogn). Với độ phức tạp đó cùng với kết quả thực nghiệm của tác giả (bảng 4-1) đã cho thấy một điều rằng phương pháp tạo vùng đệm này chỉ tốt cho các ứng dụng GIS chứ không thể áp dụng tốt trong bài toán tìm kiếm trên đường của hệ GIR vì nó chiếm quá nhiều 60 thời gian so với tiêu chuẩn của một hệ tìm kiếm và hơn nữa độ chính xác của kết quả sẽ phụ thuộc khá nhiều vào mức độ mịn của các cung tròn ở hai đầu vùng đệm. Số lượng vector Thời gian thực hiện (giây) 300 0,1 600 0,4 900 0,5 1200 0,9 Bảng 4-1: Bảng kết quả thuật toán tạo vùng đệm của M. Zadravec. Tuy nhiên, ngoài cách lấy vùng đệm trên cũng còn có một số phương pháp khác để giải quyết bài toán tìm kiếm trên đường này, luận văn đã áp dụng một phương pháp Heuristic với độ phức tạp kiểm tra nhỏ hơn rất nhiều so với cách lấy vùng đệm và tính chính xác của kết quả cũng cao hơn do không phụ thuộc vào mức độ mịn của cung tròn ở hai đầu vùng đệm. Điều đó giúp hệ thống đảm bảo về mặt tốc độ tìm kiếm lẫn kết quả tìm kiếm. Ý tưởng của phương pháp đề nghị này là xây dựng khung bao cho câu truy vấn theo đường chính là vùng đệm của nó với bán kính r nhưng đặc biệt ở đây, phương pháp này sẽ không thực hiện công việc tạo ra vùng đệm vì chi phí thời gian quá lớn. Thay vào đó, phương pháp này sẽ tận dụng lợi thế tìm kiếm nhanh của cấu trúc R-Tree trên từng vector của đường để tạo ra một tập hợp các ứng cử viên trên đoạn vector đó. Tập ứng viên này sau đó sẽ được kiểm tra lại một lần nữa để xác định các tài liệu (đối tượng) thật sự nằm trong vùng đệm của đường thông qua một hàm đánh giá (hình 4-5). Cuối cùng, các kết quả trên từng vector của đường sẽ được sắp xếp theo độ tăng dần của khoảng cách so với đường và hội với nhau để có kết quả sau cùng. 61 Hình 4-5: Minh họa ý tưởng tìm kiếm theo đường. Các bước của phương pháp trên có thể được cụ thể hóa bằng đoạn mã giả sau: V := Tập các vector thuộc đường; r := Bán kính tìm kiếm. Foreach Vi in V Do VRect := Khung bao chữ nhật cho Vi Rect : = Khung bao VRect mở rộng theo chiều dọc và chiều ngang 1 khoảng = r D := Tập tài liệu thỏa mãn nội dung truy vấn và có khung bao giao với Rect lResultTemp := {Di  D | Vị trí của Di  Rect} Foreach lResultTempi in lResultTemp Do If IsCircleClip(lResultTempi, Vi, r) Then lResult := lResult  lResultTempi End If End Foreach End Foreach Return lResult 62 Trong thuật toán trên, điểm đáng chú ý chính là hàm đánh giá IsCircleClip với chức năng kiểm tra một đối tượng có nằm trong phần vùng đệm bán kính r của đường hay không bằng cách kiểm tra đường tròn có tâm là đối tượng đó, bán kính r có giao nhau với đường hay không. Đây chính là hàm Heuristic của phương pháp đề nghị này. Ý tưởng của Heuristic này là nếu một điểm là tâm của một đường tròn bán kính r cắt với một đoạn thẳng thì điểm đó sẽ nằm trong phần vùng đệm bán kính r của đoạn thẳng đó. Từ đó, ta có thể kiểm tra nếu một đường tròn có tâm là p bán kính r cắt vector Vi của đoạn đường V thì khi đó p sẽ nằm trong vùng đệm bán kính r của V. Lúc này, ta có thể lọc ra các tài liệu nào trong tập ứng cử viên thật sự thỏa điều kiện nằm trong vùng giới hạn của câu truy vấn mà không phải tốn chi phí tạo ra vùng đệm của câu truy vấn đó. Vậy từ đây, vấn đề là hàm đánh giá IsCircleClip trên có độ phức tạp như thế nào so với độ phức tạp của việc tạo ra vùng đệm của câu truy vấn. Thật may mắn là theo [19], hàm IsCircleClip này chỉ là một phép toán số học và có độ phức tạp là O(1). Hàm IsCircleClip có thể được xây dựng theo các bước như [19] đã làm nhưng sẽ được sửa đổi một chi tiết là thay vì xét giữa đường tròn và đường thẳng thì ở đây sẽ xét giữa đường tròn và đoạn thẳng: Hình 4-6: Các trường hợp tương quan giữa đoạn thẳng và đường tròn. 63 Ta có: dirx = x2 – x1. diry = y2 – y1. diffx =centerx – x1. diffy =centery – y1. t = (diffx * dirx + diffy * diry)/(dirx 2 + diry 2 ). Nếu t<0  t = 0. Nếu t>1  t = 1. closestx = x1 + (t * dirx). closesty = y1 + (t * diry). dx = centerx – closestx. dy = centery – closesty. dr = dx 2 + dy 2 . Nếu: dr <= r 2 : đường tròn cắt đoạn thẳng. dr > r 2 : đường tròn không cắt đoạn thẳng. Ta thấy rằng với phép toán trên, chi phí để kiểm tra 1 điểm có thật sự nằm gần đường hay không chỉ là O(1). Lúc này ta giả sử rằng chi phí để kiểm tra 1 điểm có nằm trong phần vùng đệm (thực chất là 1 đa giác) hay không cũng đạt độ phức tạp là O(1) (thực tế rất khó, ngoại trừ đã tốn 1 chi phí khá lớn trong tiền xử lý) thì cách tiếp cận mới này vẫn đạt tốc độ tìm kiếm nhanh hơn do không phải mất chi phí lấy vùng đệm của đường. 64 4.2.4 Đánh giá phương pháp tìm kiếm theo đường: Để kiểm tra tính chính xác và tốc độ tìm kiếm với phương pháp mới này, hệ thống đã thực hiện tìm kiếm các tài liệu liên quan với cùng 1 chủ đề ngẫu nhiên nào đó trên các đoạn đường với số lượng vector tăng dần lần lượt với phương pháp Buffering (tạo vùng đệm) và phương pháp mới đề xuất. Thực nghiệm được chạy trên bộ dữ liệu Thành Phố Hồ Chí Minh với xấp xỉ 100.000 đối tượng (tài liệu), phần cứng của máy là CPU Core 2 Duo 2.18Ghz, RAM 2Gb. Các kết quả so sánh trong bảng 4-2, 4-3 và các biểu đồ 4-7, 4-8 đều cho ta thấy hiệu quả vượt trội của phương pháp đơn giản này so với cách lấy vùng đệm. Ở khía cạnh tốc độ tìm kiếm, ta thấy rằng phương pháp mới gần như cho kết quả tức thời. Còn ở khía cạnh kết quả thu được thì như đã trình bày, phương pháp đề nghị sẽ luôn thu được nhiều kết quả hơn do không phụ thuộc vào độ mịn của cung tròn vùng đệm. Số lượng vector Thời gian tìm kiếm (ms) Buffering Phương pháp đề nghị (PRQ – Path-based Range Query) 20 0 15 200 124 16 500 803 16 1000 4365 31 1500 8238 78 2000 22562 79 Bảng 4-2: Số liệu so sánh giữa 2 phương pháp tìm theo đường về thời gian. 65 Hình 4-7: Biểu đồ so sánh 2 phương pháp tìm theo đường về thời gian. Số lượng vector Số đối tượng tìm thấy Buffering Phương pháp đề nghị (PRQ – Path-based Range Query) 20 503 674 200 591 791 500 765 812 1000 1543 1612 1500 2364 2370 2000 3572 3610 Bảng 4-3: Số liệu so sánh giữa 2 phương pháp tìm theo đường về số lượng kết quả. 66 Hình 4-8: Biểu đồ so sánh 2 phương pháp tìm theo đường về số lượng kết quả. 4.3 Xếp hạng: Đây là một phần việc sau cùng trước khi hoàn tất 1 qui trình tìm kiếm của hệ thống GIR/IR. Trong hệ IR truyền thống, việc xếp hạng chủ yếu chỉ dựa vào mức độ liên quan giữa nội dung tài liệu và nội dung truy vấn, có thể là liên quan thuần về mặt từ ngữ hoặc liên quan về mặt ý nghĩa, khái niệm, v.v… Trong khi đó với hệ GIR, mối quan hệ giữa kết quả tìm được và nội dung truy vấn ngoài yếu tố nội dung thì còn thể hiện thêm ở một yếu tố khác chính là yếu không gian giới hạn của câu truy vấn và không gian giới hạn trong tài liệu. Chính sự khác biệt này đã làm thay đổi mọi tiêu chí xếp hạng của hệ GIR so với hệ IR truyền thống. Từ đây, ta có thể mô hình công thức xếp hạng tài liệu trong hệ GIR như sau: Similarity(q, d) = b * TextualSim(q, d) + (1-b) * GeographicalSim(q, d) Trong đó: TextualSim(q, d) thể hiện độ liên quan về mặt từ ngữ giữa tài liệu d và truy vấn q. TextualSim(q, d) có thể được tính theo bất kỳ một công thức nào được cho là hiệu quả trong hệ IR truyền thống. Ở đây, trong luận văn này, công thức Okapi BM25[11, 25] đã được áp dụng để tính TextualSim(q, d). Còn GeographicalSim(q, d) 67 thể hiện độ liên quan về giới hạn không gian giữa tài liệu d và truy vấn q. Tham số b sẽ có giá trị trong khoảng [0,1] nhằm mục đích đưa kết quả sau cùng về miền giá trị [0,1]. Theo [1] thì tại GeoCLEF2005 với b = 0.6 người ta đạt được những độ đo chính xác nhất. Đến đây thì vấn đề đặt ra cần giải quyết là cách thức để đánh giá GeographicalSim(q, d) sao cho hiệu quả, hợp lý. Như đã nói qua ở 4.2, các câu truy vấn trong hệ GIR luôn thể hiện ở 1 trong 3 dạng: truy vấn theo vùng, theo điểm và theo đường. Do vậy, một cách lý tưởng là tìm ra 1 phương thức chung để đánh giá GeographicalSim trong cả 3 hình thức truy vấn trên. Tuy nhiên, điều đó dường như là không thể hoặc sẽ làm cho việc đánh giá kết quả trở nên kém hiệu quả bởi mỗi dạng truy vấn đều có những đặc trưng riêng biệt của nó kèm theo là những yêu cầu về xếp hạng kết quả cũng khác nhau. 4.3.1 Xếp hạng trong tìm kiếm theo vùng: Trong truy vấn theo vùng, L. Andrade [1] có phát biểu 3 độ đo thể hiện mối quan hệ giữa không gian giới hạn trong tài liệu kết quả (Sd) và trong câu truy vấn (Sq) dựa trên các khái niệm định nghĩa trong ontology như sau: Quan hệ chứa trong (Inclusion): dùng để kiểm tra xem Sd có nằm trong Sq hay không và độ lớn của độ đo này sẽ tùy thuộc số lượng các vùng không gian con của mỗi Sd, Sq. Inclusion (Sq, Sd) = 1)( 1)(   q d SndantNumOfDesce SndantNumOfDesce nếu Sd  Sq. = 0 nếu ngược lại. Quan hệ gần (Proximity): là nghịch đảo của khoảng cách 68 Proximity (Sq, Sd) = )( ),(tan 1 1 q dq SDiagonal SSceDis  Trong đó, khoảng cách (Distance(Sq, Sd)) được chuẩn hóa bởi đường chéo của khung bao của câu truy vấn (Diagonal(Sq)). Quan hệ anh em (Siblings): là một quan hệ nhị phân cho biết giữa Sq và Sd có chung cha trong cấu trúc ontology hay không. Siblings (Sq, Sd) = 1 nếu  Sx : parent(Sq) = Sx  parent(Sd) = Sx = 0 nếu ngược lại. Theo đó, độ đo GeographicalSim(Sq, Sd) sẽ có giá trị: GeographicalSim(Sq, Sd) = bb * {Inclusion(Sq, Sd)+Proximity(Sq, Sd)} + (1-bb) * Siblings(Sq, Sd). (Theo [1], bb=0.9 cho kết quả thực nghiệm tại GeoCLEF2005 tốt nhất). Một ví dụ dễ hình dung cho độ đo này là với truy vấn “khách sạn gần Hà Nội” thì những khách sạn thật sự nằm trong vùng Hà Nội sẽ được xếp lên đầu còn những khách sạn thuộc các vùng lân cận Hà Nội sẽ nằm ở phía sau. 4.3.2 Xếp hạng trong tìm kiếm xung quanh điểm: Như trình bày trong 4.2.2, nếu tiếp cận bài toán này theo cách chọn một bán kính nhất định thì bài toán trở về bài toán tìm kiếm theo vùng và phương thức xếp hạng cũng tương ứng theo vùng. Tuy nhiên, nếu tiếp cận theo cách thứ hai thì độ đo GeographicalSim(Sq, Sd) sẽ đơn giản hơn và chỉ phụ thuộc vào khoảng cách giữa Sq và Sd. GeographicalSim(Sq, Sd) = Proximity(Sq, Sd) 69 4.3.3 Xếp hạng trong tìm kiếm theo đường: Đối với truy vấn theo đường thì độ đo GeographicalSim(Sq, Sd) sẽ phụ thuộc vào 2 yếu tố sau:  Truy vấn quan tâm đến hướng.  Tuy vấn không quan tâm đến hướng. Truy vấn quan tâm đến hướng: nghĩa là trong loại truy vấn này yếu tố hướng tìm kiếm là rất quan trọng. Ví dụ ta có một đường đi từ A->B, hỏi tìm các trạm xăng nằm trên lộ trình đó. Trong trường hợp này việc xếp hạng kết quả sẽ tùy thuộc vào quá trình tìm kiếm trước đó mà không phụ thuộc nhiều vào độ đo GeographicalSim(Sq, Sd). Thông thường với dạng truy vấn này, quá trình tìm kiếm trước đó sẽ thực hiện tìm trên các vector xuất phát từ A và sẽ kết thúc ở các vector ở B. Khi đó các kết quả mặc nhiên sẽ được sắp xếp theo yêu cầu tìm kiếm và không cần 1 độ đo nào nhằm thay đổi thứ tự đó với công thức xếp hạng như sau: GeographicalSim(Sq, Sd) = Proximity(Sq, Sd) +   j i iv 0 || + Proximity(Sqsn, Sd). Với:  Sqsn là vị trí bắt đầu của vector thứ j+1 mà Sd thuộc về.    j i iv 0 || : Tổng độ dài của j vector trước đó. Trong một vài tình huống truy vấn, có thể không ẩn chứa bên trong nó những yêu cầu xếp hạng theo hướng đường nhưng vì bản chất của đối tượng đường được chọn mà việc sắp xếp kết quả cũng phải được thực hiện tương tự. Ví dụ đường Võ Thị Sáu, TPHCM là đường 1 chiều, nếu 1 truy vấn tìm “nhà hàng trên đường Võ Thị Sáu, 70 TPHCM” thì việc sắp hạng kết quả cũng phải được thực hiện theo yếu tố chiều đường vì nếu một kết quả nào đó nằm ở hàng đầu mà trong thực tế người tìm kiếm chỉ đến được nó ở phía cuối đường thì có vẻ bất hợp lý về tính logic. Đây có thể xem là một Heuristic trong cách thức xếp hạng kết quả. Truy vấn không quan tâm đến hướng: kiểu truy vấn này thì rõ ràng là đơn giản hơn. Với truy vấn dạng này thì hệ thống không quan tâm đến chiều đường hay hướng tìm kiếm, hệ thống chỉ quan tâm đến khoảng cách giữa Sd và Sq mà thôi, hay nói cách khác, độ đo ở đây vẫn chính là độ đo Proximity(Sq, Sd): GeographicalSim(Sq, Sd) = Proximity(Sq, Sd) ._.