BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI *** NGUYỄN THỊ MINH ĐỨC LÀM MỊN KẾT QUẢ TÌM KIẾM VĂN BẢN SỬ DỤNG KỸ THUẬT KHAI PHÁ VĂN BẢN LUẬN VĂN THẠC SĨ NGÀNH : XỬ LÝ THÔNG TIN VÀ TRUYỀN THÔNG MÃ SỐ: ./ ./ Người hướng dẫn khoa học: PGS Nguyễn Thị Kim Anh Hà Nội 2009 LỜI CẢM ƠN Em xin chân thành cảm ơn PGS Nguyễn Thị Kim Anh, Trưởng Bộ môn Các hệ thống thông tin, Viện CNTT-TT, Trường Đại học Bách Khoa Hà Nội Em nhận hướng dẫn tận tình, góp ý cụ thể PGS trình nghiên cứu viết luận văn Em xin gửi lời cám ơn chân thành đến thầy cô giáo giảng dạy lớp CH XLTT&TT 2007 cung cấp cho em kiến thức bổ ích, hỗ trợ em việc làm luận văn, việc tiếp tục nghiên cứu sau Em xin chân thành cảm ơn Ban giám đốc Dự án Hỗ trợ phát triển đào tạo đại học sau đại học CNTT-TT, Viện đào tạo Sau đại học tạo điều kiện cho phép em tham gia lớp cao học XLTT-TT khóa 20072009 Em xin gửi lời cám ơn đến bạn đồng nghiệp anh chị học viên lớp cao học XLTT-TT 2007 hỗ trợ, động viên để em hoàn thành luận văn Cuối cùng, em xin bày tỏ lòng biết ơn đến gia đình, bạn bè, người ln động viên giúp đỡ em q trình học tập cơng tác Hà nội, ngày 26 tháng 11 năm 2009 Học viên Nguyễn Thị Minh Đức LỜI CAM ĐOAN Tôi xin cam đoan luận văn cơng trình nghiên cứu thân Các nghiên cứu luận văn dựa tổng hợp lý thuyết hiểu biết thực tế, không chép Tác giả Nguyễn Thị Minh Đức MỤC LỤC DANH MỤC TỪ VIẾT TẮT DANH MỤC BẢNG, SƠ ĐỒ, HÌNH VẼ MỞ ĐẦU Chương I Tổng quan khai phá liệu kỹ thuật dùng khai phá liệu 1.1 Tổng quan khai phá liệu………………………………… 1.2 Khai phá liệu sử dụng định……………………….6 1.2.1 Khái niệm khai phá liệu sử dụng định .6 1.2.2 Điểm mạnh định 1.2.3 Điểm yếu định 1.3 Khai phá liệu sử dụng luật kết hợp…………………………10 1.3.1 Khái niệm khai phá liệu sử dụng luật kết hợp 10 1.3.2 Điểm mạnh phương pháp phân tích luật kết hợp: 11 1.3.3 Điểm yếu phương pháp phân tích luật kết hợp 12 1.4 Khai phá liệu sử dụng gom cụm……………………………14 1.4.1 Khái niệm khai phá liệu sử dụng gom cụm .14 1.4.2 Điểm mạnh dị tìm gom cụm tự động 15 1.4.3 Điểm yếu phương pháp dị tìm tự động gom cụm 16 1.5 Khai phá liệu sử dụng mạng neural……………………… 16 1.5.1 Khái niệm khai phá liệu sử dụng mạng neural 16 1.5.2 Điểm mạnh mạng neural 17 1.5.3 Điểm yếu phương pháp mạng neural .18 Chương II Cơ sở liệu (CSDL) văn khai phá CSDL văn bản………………………………………………………………………21 2.1 Vấn đề biểu diễn văn trích chọn thơng tin văn 21 2.1.1 Vấn đề biểu diễn văn .21 2.1.2 Trích chọn thơng tin .23 2.2 Khai phá CSDL văn 26 2.2.2 Khai phá văn khai phá liệu 31 2.2.3 Các toán khai phá văn ứng dụng 33 2.2.3 Kỹ thuật phân tích khái niệm hình thức (FCA) ứng dụng 38 2.3 Kết chương……………………………………………………….53 Chương III Làm mịn kết tìm kiếm văn sử dụng FCA .54 3.1 Tổng quan tìm kiếm thơng tin……………………………… 54 3.2 Làm mịn kết tìm kiếm sử dụng FCA……………………….57 3.2.1 Vấn đề làm mịn kết tìm kiếm hướng tiếp cận .57 3.2.2 Cách tiếp cận biến đổi câu truy vấn, có sử dụng phân tích khái niệm hình thức giàn khái niệm 58 3.3 Kết luận hướng nghiên cứu tiếp theo…………………………62 3.3.1 Cách tiếp cận biến đổi câu truy vấn dựa ngữ cảnh người dùng 62 3.3.2 Đánh giá, kết luận hướng nghiên cứu .64 TÀI LIỆU THAM KHẢO 66 DANH MỤC TỪ VIẾT TẮT CSDL: Cơ sở liệu DM: Data Mining – Khai phá liệu SQL: Structured Query Language - Ngơn ngữ truy vấn có cấu trúc IR: Information Retrieval – Tìm kiếm thơng tin NLP: Natural Language Processing – Xử lý ngôn ngữ tự nhiên IE: Information Extraction – Trích chọn thơng tin FCA: Formal Concept Analysis – Phân tích khái niệm hình thức DANH MỤC BẢNG, SƠ ĐỒ, HÌNH VẼ Hình 1.1: Sơ đồ mơ tả q trình khai phá liệu (trang 5) Hình 1.2 Phân loại kỹ thuật khai phá văn ( trang 6) Hình 1.3: Mẫu kết với phương pháp định (trang 6) Hình 1.4 Sơ đồ biểu diễn kết gom cụm liệu ( trang14) Hình 2.1: Ví dụ biểu diễn văn (trang 21) Hình 2.2: Sơ đồ khái niệm trích chọn thơng tin (trang 23) Hình 2.3 Sơ đồ quy trình khai phá văn (trang 27) Hình 2.4: Các tốn khai phá văn cách tiếp cận (trang 32) Hình 2.5 :Ví dụ phân loại văn (trang 34) Hình 2.6 : Khái niệm phân cụm văn (trang 36) Hình 2.7 Hiển thị dendogram phân cấp tích tụ (trang 39) Bảng 2.1: Bảng ngữ cảnh ví dụ (trang 43) Hình 2.8: Giàn khái niệm xây dựng cho bảng ngữ cảnh ví dụ (trang 43) Hình 2.9: Biểu diễn rút gọn khái niệm cho giàn khái niệm hình 2.8 (trang 44) Hình 2.10: Lưu đồ thuật toán cho giải thuật Bayes sơ khai (trang 46) Hình 3.1 Sơ đồ mơ tả hệ thống tìm kiếm thơng tin (trang 55) Hình 3.2: Ví dụ hiển thị gợi ý làm mịn câu truy vấn hệ thống REFINER (trang 62) MỞ ĐẦU Xã hội đại xã hội thông tin xử lý thông tin, với phát triển mạng Internet, nguồn thông tin vô đa dạng, phong phú nhiều số lượng Tuy nhiên, để sử dụng hiệu nguồn thông tin, cần phải có phương pháp, thuật tốn, quy trình, đến phần mềm, công cụ để khai phá liệu nói chung khai phá văn nói riêng Nghiên cứu khai phá liệu, khai phá văn ngày phát triển, đem lại tiềm to lớn cho người Đặc biệt, khai phá văn Internet ý, nguồn thông tin chia sẻ cực lớn Cũng khối lượng thơng tin chia sẻ lớn mà việc tìm kiếm thơng tin gặp số trở ngại Trong phạm vi đề tài luận văn, em xin trình bày số vấn đề sau: - Tìm hiểu chung khai phá liệu số kỹ thuật khai phá liệu - Tìm hiểu chung khai phá văn toán khai phá văn bản, giới thiệu kỹ thuật phân tích khái niệm hình thức, ứng dụng khai phá văn - Vấn đề tìm kiếm thơng tin, làm mịn kết tìm kiếm văn bản, hướng nghiên cứu đề xuất Với hiểu biết thân, thời gian nghiên cứu, nội dung luận văn dừng lại nghiên cứu lý thuyết thuật tốn Chính vậy, em mong nhận góp ý hướng dẫn thêm thầy cô bạn, để việc nghiên cứu thực triệt để mang tính ứng dụng cụ thể Chương I Tổng quan khai phá liệu kỹ thuật dùng khai phá liệu 1.1 Tổng quan khai phá liệu Khai phá liệu (Data mining-DM) khái niệm đời vào năm cuối thập kỷ 80 Nó bao hàm loạt kỹ thuật nhằm phát thông tin có giá trị tiềm ẩn tập liệu lớn (các kho liệu) Về chất, khai phá liệu liên quan đến việc phân tích liệu sử dụng kỹ thuật để phát mẫu, quy luật tập liệu Năm 1989, Fayyad, Piatestsky-Shapiro Smyth dùng khái niệm Phát tri thức sở liệu (Knowledge Discovery in Database – KDD) để toàn trình phát tri thức có ích từ tập liệu lớn Trong đó, khai phá liệu bước đặc biệt tồn q trình, sử dụng giải thuật đặc biệt để chiết xuất mẫu từ sở liệu Các giải thuật khai phá liệu thường mô tả chương trình hoạt động trực tiếp file liệu Với phương pháp học máy thống kê trước đây, thường bước giải thuật nạp toàn file liệu vào nhớ Khi chuyển sang ứng dụng công nghiệp liên quan đến việc khai phá kho liệu lớn, mơ hình khơng thể đáp ứng Khơng khơng thể nạp hết liệu vào nhớ mà cịn khó chiết xuất liệu file đơn giản để phân tích Q trình xử lý khai phá liệu bắt đầu cách xác định xác vấn đề cần giải Sau xác định liệu liên quan dùng để xây dựng giải pháp Bước thu thập liệu có liên quan xử lý chúng thành dạng cho giải thuật khai phá liệu hiểu Về lý thuyết đơn giản thực thực trình khó khăn, gặp phải nhiều vướng mắc như: liệu phải nhiều (nếu chiết xuất vào tệp), quản lý tệp liệu, phải lặp lặp lại nhiều lần toàn q trình (nếu mơ hình liệu thay đổi),… Sẽ cồng kềnh với giải thuật khai phá liệu phải truy cập vào toàn nội dung sở liệu làm việc Vả lại, điều không cần thiết Có nhiều giải thuật khai phá liệu thực dựa thống kê tóm tắt đơn giản sở liệu, mà tồn thơng tin sở liệu dư thừa mục đích việc khai phá liệu Bước chọn thuật toán khai phá liệu thích hợp thực việc khai phá liệu để tìm mẫu (pattern) có ý nghĩa dạng biểu diễn tương ứng với ý nghĩa (thường biểu diễn dạng luật phân loại, định, phát luật kết hợp, biểu thức hồi quy,…) Thống kê Xác định Xác định liệu Thu thập tiền xử lý DL Giải thuật Data Mining Dữ liệu trực tiếp Hình 1.1 Sơ đồ mơ tả q trình khai phá liệu Các kĩ thuật khai phá liệu chia thành hai nhóm chính, nhóm dự báo, nhóm mơ tả Trong nhóm dự báo gồm số kỹ thuật phân loại, hồi quy, phân tích loạt thời gian, định, mạng neural Nhóm có tên gọi kỹ thuật có khả dự báo tính chất tập liệu sau hệ thống huấn luyện với tập liệu mẫu Nhóm thứ hai nhóm mơ tả, gồm có kỹ thuật sau: Gom cụm, Tổng kết, Phát luật kết hợp, Phát trình tự Nhóm có tên mơ tả sau thực kỹ thuật tập Luật 52 phần giao tăng dần trình bày Để xác định liên kết khái niệm, ta thực sau: xét khái niệm, với thuộc tính m khơng thuộc cấu trúc khái niệm tại, xác định khái niệm (X1, Y1), khái niệm X1 bao gồm đối tượng có thuộc tính bao gồm cấu trúc khái niệm cha, thuộc tính m; có cấu trúc Y1 thuộc tính chung đối tượng thể Quá trình xác định khái niệm thuật tốn có ưu điểm so với thuật toán chỗ, phép toán đạo hàm thực lần thuộc tính, thuật tốn đạo hàm cho phép hợp, số lượng thuộc tính phải lớn Hơn nữa, cấu trúc Y1 xác định dựa tìm kiếm khái niệm X1 mà làm phép đạo hàm từ X1 Việc lựa chọn khái niệm lớn (kết nối trực tiếp đến khái niệm tại) thực tốt, đặt biến đếm count cho khái niệm Khi bắt đầu xét khái niệm cho khái niệm, count tất khái niệm đặt Mỗi tìm thấy khái niệm X1 bao gồm đối tượng có thuộc tính bao gồm cấu trúc khái niệm cha, thuộc tính m, count khái niệm tăng lên Chỉ có khái niệm có count với số lượng sai khác số thuộc tính cấu trúc khái niệm cha cấu trúc 53 khái niệm coi khái niệm lớn nhất, có kết nối trực tiếp đến khái niệm cha 2.3 Kết chương Với lịch sử phát triển khai phá văn bản, nhiều kỹ thuật nghiên cứu áp dụng để ngày nâng cao hiệu việc khai phá văn Cho đến năm gần đây, phân tích khái niệm hình thức - FCA lên kỹ thuật mới, sử dụng phân tích liệu dạng văn có hiệu Đồng thời, nghiên cứu cho thấy FCA có nhiều khả ứng dụng cho toán khai phá liệu nói chung khai phá văn nói riêng 54 Chương III 3.1 Làm mịn kết tìm kiếm văn sử dụng FCA Tổng quan tìm kiếm thơng tin Hình 3.1 Sơ đồ mơ tả hệ thống tìm kiếm thơng tin Tìm kiếm thơng tin (Information Retrieval – IR) coi lĩnh vực có từ trước đời máy tính Giả sử có kho sách, người muốn tìm tài liệu lĩnh vực đó, tìm tài liệu cần cách đọc hết sách (văn bản) kho loại sách khơng thích hợp Có thể thấy rằng, việc thực cách thông thường với nguồn thông tin khổng lồ thời đại Việc duyệt văn tìm văn thích hợp cần phải thực nhờ trợ giúp máy tính Google Yahoo! số công ty cố gắng giải vấn đề Vấn đề cụ thể sau: cho trước tập hợp văn câu truy vấn người dùng, tìm tập tập hợp ban đầu, tương xứng với câu truy vấn Vấn đề nghe 55 đơn giản, lại ẩn chứa nhiều điều tinh tế Cả tập hợp văn câu truy vấn mơ hồ thiếu xác định ngữ nghĩa rõ ràng Không giống cấu trúc cứng nhắc sở liệu truyền thống, văn thường khơng có cấu trúc Một câu truy vấn “bóng đá” mơ hồ tìm nhiều văn hóa khác Có phải người dùng thực muốn tìm “túc cầu giáo”? Hơn nữa, làm từ khơng xuất văn nói bóng đá? Và văn coi không tương xứng hay không? Việc đánh giá tương xứng chí khó kể người trực tiếp thực việc Mỗi người với kiến thức tảng khác dẫn đến kết đánh giá khác biệt Để thực việc tìm kiếm văn phù hợp tập hợp văn cho trước, sử dụng số thuật tốn tìm kiếm : tìm kiếm Boolean, tìm kiếm nối tiếp, tìm kiếm dựa cụm văn Các thuật toán thực sở tập hợp văn thực thao tác tiền xử lý như: lập mục, gán nhãn, phân cụm Nói đến tìm kiếm thơng tin trọng vào thuật tốn tìm kiếm, vấn đề thuộc lập mục, gán nhãn, phân cụm, lại liên quan đến mảng khác khai phá văn nói chung Kiểu tìm kiếm áp dụng phổ biến tìm kiếm Boolean: Câu truy vấn tạo mục toán tử Boolean (AND, OR, NOT) Hệ thống tìm văn theo cụm từ tạo câu truy vấn, nói cách khác câu truy vấn có giá trị “true” văn Một số hệ thống cho phép mở rộng thu hẹp kết tìm kiếm dựa từ điển cấu trúc, cho người dùng biết mục có liên quan, có mức độ xác cao hơn, mức độ tổng quát cao so với mục câu truy vấn gốc Rõ ràng để thực tìm kiếm dựa toán tử Boolean, cần lập danh sách mục, kèm với trỏ, số hiệu văn 56 có mục Tốn tử AND thực phép giao hai tập hợp văn mục, toán tử OR thực phép hội, toán tử NOT việc loại bỏ tập văn mục khỏi tập văn kết thời tìm kiếm Boolean có cách thực thật rõ ràng, nhiên chưa thể mức độ liên kết mục Do có ưu điểm dễ triển khai có hiệu tính tốn cao nhờ sử dụng toán tử Boolean, nên hệ thống tìm kiếm dùng câu truy vấn Boolean sử dụng nhiều thực tế Tuy nhiên hệ thống có số hạn chế cần khắc phục Thứ nhất: đem lại kết gồm tập văn rỗng ngược lại, nhiều văn bản, xuất phát từ cấu trúc câu truy vấn với tốn tử Thứ hai, kết trả khơng đáp ứng u cầu tìm kiếm, số trường hợp người dùng chưa thực xác định rõ yêu cầu tìm kiếm Trên thực tế, có nghiên cứu thực nghiệm nhằm khắc phục hạn chế Việc thể kết lại gây vấn đề Nhiều người thích kết xếp hạng từ cao xuống thấp theo độ tương thích, nhiên, việc xếp hạng mang tính tương đối, cách xếp hạng, số người kết tốt, người khác lại chưa hoàn toàn hài lịng Chính vậy, người ta tiếp tục nghiên cứu để hướng tới cách giải vấn đề tìm kiếm thơng tin cách linh hoạt toàn diện Một số định hướng nghiên cứu gần tìm kiếm thơng minh, có cách tiếp cận trọng vào ngữ nghĩa từ, từ đồng nghĩa, hay mức độ mơ hồ từ ngữ Có cách tiếp cận lại vào thứ tự từ nêu câu truy vấn, đưa gợi ý khác cho người dùng, tổ hợp xếp khác từ câu truy vấn Tất hướng nghiên cứu, cách tiếp cận nhằm mục đích đem lại kết tìm kiếm tốt cho người dùng 57 3.2 Làm mịn kết tìm kiếm sử dụng FCA 3.2.1 Vấn đề làm mịn kết tìm kiếm hướng tiếp cận Tìm kiếm thơng tin dạng khai phá văn với mục đích tìm thơng tin với yêu cầu người tìm Tuy nhiên, hệ thống hiểu câu truy vấn mà người dùng nhập vào, người dùng nhập câu truy vấn chưa hồn tồn thể u cầu tìm kiếm Chính thường có trường hợp số lượng kết nhiều, mặt khác, xếp lại không với mong muốn người dùng, có trường hợp số kết lại q ít, khơng đáp ứng u cầu tìm kiếm người dùng Để cải thiện số lượng kết tìm kiếm, hệ thống cần phân tích câu truy vấn, tìm khái niệm hình thức, so khớp với giàn khái niệm tập văn bản, đưa gợi ý truy vấn khác để người dùng lựa chọn Các gợi ý truy vấn phải có liên hệ với câu truy vấn ban đầu theo logic định, nhiên giúp làm giảm tăng số lượng kết tìm được, tạo thuận lợi cho người dùng duyệt danh sách kết Vấn đề biến đổi câu truy vấn dựa hướng : - Căn khái niệm câu truy vấn, duyệt giàn khái niệm xung quanh khái niệm khái niệm cha, khái niệm con, hình thành câu truy vấn để cải thiện số lượng kết tìm kiếm (hướng tiếp cận sử dụng phân tích khái niệm hình thức – FCA- giàn khái niệm) - Căn lịch sử câu truy vấn người dùng: dựa thực tế người dùng tìm kiếm vấn đề vài truy vấn gần Do đó, câu truy vấn có tập khái niệm có liên quan đến trùng khớp với khái niệm câu truy vấn tại, hệ thống đưa câu truy vấn khác, đem lại số lượng kết hợp lý 58 - Căn câu truy vấn người dùng, sử dụng liên hệ từ đồng nghĩa với thuật ngữ câu truy vấn, để tạo câu truy vấn có số lượng kết tìm kiếm cải thiện so với câu truy vấn ban đầu 3.2.2 Cách tiếp cận biến đổi câu truy vấn, có sử dụng phân tích khái niệm hình thức giàn khái niệm Trong ứng dụng tìm kiếm thơng tin, mối quan hệ đối tượng – thuộc tính thường văn – thuật ngữ Ta thấy, nút giàn khái niệm cặp đôi gồm văn có chung thuật ngữ, thuật ngữ xuất văn Một câu truy vấn nhập vào gồm từ, thế, coi câu truy vấn nút (một khái niệm) giàn khái niệm, từ câu truy vấn thuật ngữ thuộc khái niệm Như duyệt lên duyệt xuống giàn, để đến khái niệm tổng quát hơn, khái niệm chi tiết Tương ứng với khái niệm tổng quát số lượng văn nhiều hơn, ngược lại, khái niệm chi tiết có số văn Ở cách tiếp cận, áp dụng cho trường hợp số lượng văn thuật ngữ đủ nhỏ, người ta xây dựng giàn khái niệm trước, sau ánh xạ câu truy vấn vào nút giàn khái niệm, nơi có số thuật ngữ trùng với thuật ngữ câu truy vấn, khái niệm mang tính tổng quát có tập thuật ngữ lớn tập thuật ngữ câu truy vấn (Các giải thuật tìm tập khái niệm xây dựng giàn đề cập chương 2) Tùy thuộc vào trường hợp cần tăng hay giảm số lượng kết quả, hệ thống chọn lựa nút cha hay nút nút coi tương đương với khái niệm câu truy vấn Trường hợp câu truy vấn ánh xạ vào nút đáy giàn (tồn thuật ngữ, khơng có văn bản), đương nhiên câu truy vấn nhập vào cụ thể, chi tiết, có hướng làm bớt tính cụ thể câu truy vấn, nên 59 hiển thị nút nút đáy, để người dùng có số lựa chọn thực giảm tính cụ thể câu truy vấn Tuy phương pháp tạo giàn khái niệm toàn ánh xạ câu truy vấn vừa trình bày cụ thể rõ ràng mặt thuật tốn, đánh đổi u cầu tính tốn lớn phải xây dựng toàn giàn (như phân tích trên), đặc biệt số lượng văn thuật ngữ tăng, trường hợp khái niệm câu truy vấn nhập vào không trùng với nút giàn khái niệm, hệ thống phải cập nhật lại giàn Để khắc phục điều này, người ta đến giải pháp khác: Xây dựng phần giàn khái niệm, coi khái niệm câu truy vấn khái niệm trung tâm, tiếp xác định khái niệm cha, khái niệm con, thực duyệt phần giàn khái niệm để biến đổi câu truy vấn Cụ thể giải pháp sau: - Từ câu truy vấn, xác định thuật ngữ, sau xác định văn chứa tất thuật ngữ này, thể khái niệm trung tâm Kiểm tra lại toàn văn để xác định tập đầy đủ thuật ngữ có tất văn đó, cấu trúc khái niệm trung tâm - Xác định nút khái niệm trung tâm, cách thêm dần thuật ngữ vào tập thuật ngữ khái niệm trung tâm, lần thêm, đánh giá lại tập văn có chứa tất thuật ngữ tập thuật ngữ Đây trình lặp, tiến hành duyệt qua toàn thuật ngữ sở liệu - Xác định nút cha, bớt dần thuật ngữ, xác định tập văn tương ứng với tập thuật ngữ mới, trình lặp tiến hành khơng cịn thuật ngữ 60 - Việc xác định nút cha, nút khái niệm trung tâm sử dụng giải thuật xây dựng phận giàn đoạn giả mã đây, khái niệm (X,Y) khái niệm thuộc câu truy vấn - Kết thu phần giàn khái niệm Do xây dựng phần nên tiết kiệm thời gian hơn, giảm bớt độ lớn nhớ lưu trữ phần giàn khái niệm hiển thị phục vụ cho việc biến đổi câu truy vấn 61 Ngoài vấn đề thay đổi câu truy vấn trên, với hệ thống truy xuất thơng tin cần có giao diện hợp lý, giúp người dùng thấy rõ mối liên hệ câu truy vấn cũ câu truy vấn mới, so sánh tương quan số lượng kết trả câu truy vấn trước sau điều chỉnh, để thấy rõ mức độ cải thiện Xem xét hệ thống thực tế, sử dụng giàn khái niệm để biến đổi câu truy vấn hệ thống Refiner Đây hệ thống biến đổi câu truy vấn Boolean, để làm mịn kết tìm kiếm Hệ thống tìm kiếm thơng tin sử dụng câu truy vấn theo kiểu Boolean có số ưu điểm nhược điểm trình bày phần 3.1 Trong hệ thống Refiner, nhận câu truy vấn, hệ thống tính tốn phần giàn khái niệm lân cận với khái niệm câu truy vấn hiển thị Hình 3.2: Ví dụ hiển thị gợi ý làm mịn câu truy vấn hệ thống REFINER 62 Kết hiển thị rõ ràng, nhờ người dùng khai thác thơng tin nút lân cận khái niệm thuộc câu truy vấn Do xây dựng phần giàn, nên hệ thống có đủ thời gian để tính tốn hiển thị lại người dùng dịch chuyển đến nút khác với nút chứa khái niệm câu truy vấn Hiệu áp dụng giàn khái niệm: có khái niệm gồm thể cấu trúc, nên hiển thị gợi ý làm mịn câu truy vấn, mà khơng phải thời gian tìm kiếm tập sở liệu văn lớn với câu truy vấn gợi ý, để có số lượng văn tương ứng, giúp người dùng dễ so sánh lựa chọn câu truy vấn tối ưu Ưu điểm phương pháp biến đổi câu truy vấn làm mịn kết sử dụng FCA thể chỗ, hệ thống đưa gợi ý biến đổi câu truy vấn cho người dùng chọn lựa, biến đổi định hướng tới nội dung văn có sưu tập, tránh cho người dùng khỏi việc bỏ bớt thêm vào câu truy vấn cũ hay số thuật ngữ cách ngẫu nhiên, dẫn đến kết so với câu truy vấn ban đầu Như vậy, người dùng tìm kiếm thơng tin hiệu 3.3 Kết luận hướng nghiên cứu 3.3.1 Cách tiếp cận biến đổi câu truy vấn dựa ngữ cảnh người dùng Như biết, mạng Internet đem lại cho người khả truy cập gần không giới hạn đến loại thông tin Cũng lượng thông tin chủng loại mạng ngày nhiều, với câu truy vấn, người dùng nhận nhiều kết Dĩ nhiên việc tìm kết phù hợp với yêu cầu số lượng lớn tài liệu tả thật khó khăn Các chế tìm kiếm thường xử lý câu truy vấn mà không xem xét đến ngữ cảnh xuất câu truy vấn Để giải vấn đề 63 trên, hướng tiếp cận xem xét đến ngữ cảnh người dùng với câu truy vấn Ngữ cảnh người dùng hiểu yếu tố mơ tả ý định người dùng nhận thức môi trường xung quanh họ Các yếu tố bao gồm: tâm lý, xã hội, văn hóa, trình độ Tìm kiếm thơng tin theo ngữ cảnh kết hợp nhiều công nghệ, tri thức truy vấn, ngữ cảnh người dùng để tìm thơng tin thích đáng Phương pháp sử dụng đến hồ sơ người dùng ontology (biểu diễn hình thức tập khái niệm mối quan hệ chúng) để xử lý câu truy vấn Hồ sơ người dùng tập hợp thông tin cá nhân người dùng cụ thể, cho thấy lĩnh vực quan tâm ưa thích người, phân biệt với người dùng khác Hồ sơ người dùng tĩnh, hay động, có cách yêu cầu người dùng điền thơng tin vào mẫu có sẵn, cách ghi lại cách duyệt web người dùng Với câu truy vấn, xử lý hồ sơ người dùng khác có tập kết khác Một hồ sơ người dùng động lưu trữ theo bảng, thành cặp thuộc tính –giá trị Mỗi cặp đại diện cho đặc tính hồ sơ Các đặc tính nhóm lại thành chủng loại Hệ thống sử dụng hồ sơ người dùng để thực tăng cường cho câu truy vấn cấu trúc lại câu truy vấn Việc tăng cường câu truy vấn thực cách thêm vào câu truy vấn thuật ngữ mô tả hồ sơ người dùng không xung đột với thuật ngữ câu truy vấn Việc cấu trúc lại câu truy vấn thực cách biểu diễn câu truy vấn theo giàn đồ ảo, xác định nguồn liệu sử dụng thực truy vấn Ontology dùng để lý giải đặc điểm miền dùng để xác định miền Sử dụng ontology tối thiểu hóa việc dùng sai khái niệm câu truy vấn thông qua hỗ trợ người dùng hiểu mối 64 quan hệ khái niệm Ví dụ người dùng tìm cơng việc Giảng viên, ontology gợi ý thuật ngữ tương xứng “giảng dạy”, “nghiên cứu” Trong cách tiếp cận biến đổi câu truy vấn thông qua ngữ cảnh người dùng, ontology dùng để xác định khái niệm hồ sơ người dùng có liên quan đến câu truy vấn, nhờ tính tốn thuật ngữ tương xứng Các q trình tiến hành là, phân tích cú pháp truy vấn mở rộng truy vấn, làm mịn truy vấn, hiển thị truy vấn Q trình phân tích cú pháp xác định thuật ngữ câu truy vấn, đồng thời xác định từ đồng nghiã Quá trình mở rộng truy vấn: hệ thống thực tìm kiếm thuật ngữ câu truy vấn gốc, từ đồng nghĩa với thư viện ontology để tìm khái niệm liên quan Các khái niệm so sánh với khái niệm hồ sơ người dùng, để tìm khái niệm chung Từ khái niệm chung, tìm loại hồ sơ người dùng, tiếp tìm thuộc tính hồ sơ người dùng Các thuộc tính thêm vào câu truy vấn gốc Quá trình làm mịn câu truy vấn: đánh giá lại mức độ tương xứng thuộc tính thêm vào, để chọn lựa thêm lần Sau trình làm mịn, câu truy vấn biến đổi hiển thị cho người dùng lựa chọn, xem câu truy vấn gần sát với yêu cầu tìm kiếm thơng tin 3.3.2 Đánh giá, kết luận hướng nghiên cứu So với cách tiếp cận làm mịn câu truy vấn dùng giàn khái niệm, phương pháp làm mịn câu truy vấn sử dụng ngữ cảnh người dùng mang tính hướng người dùng hơn, mang tính tương tác nhiều Tuy nhiên, phương pháp đòi hỏi phải thiết lập mẫu hồ sơ người dùng tối ưu, phải xem xét đến phương thức thu thập thông tin để lập hồ sơ người dùng Phương pháp sử dụng ngữ cảnh người dùng đặc biệt có hiệu áp dụng với sở liệu văn mà có tần suất sử dụng trung bình người 65 dùng thường xuyên Khi người dùng đưa nhiều truy vấn, ngữ cảnh người dùng hình thành rõ ràng, hỗ trợ tối đa cho trình làm mịn câu truy vấn Phương pháp sử dụng giàn khái niệm áp dụng cho trường hợp vừa nêu trên, trường hợp ngược lại, tần suất sử dụng trung bình người dùng khơng thường xun, hay số lượng người dùng lớn, nội dung sở liệu văn đa dạng lĩnh vực Do kết nghiên cứu luận văn dừng lại mức đề xuất hướng giải quyết, mà chưa ứng dụng thực tế, nên để đánh giá xác hiệu giải pháp này, hướng đến ứng dụng tìm kiếm cho sở liệu văn dự án trung dài hạn Do vấn đề quản lý sở liệu văn dự án Việt Nam thực theo kiểu truyền thống, việc tìm kiếm văn bản, dự án nửa thời gian khó khăn Để xây dựng ứng dụng này, việc áp dụng giải pháp biến đổi câu truy vấn dựa giàn khái niệm, cần có thêm khâu xử lý văn bản, trích chọn thơng tin văn để lập sở liệu Mặt khác, để ứng dụng phát huy tốt hiệu phải áp dụng cho loại dự án khác nhau, địi hỏi phải có q trình tìm hiểu đặc điểm loại dự án, rút đặc điểm chung, riêng, nhờ thiết kế ứng dụng linh hoạt, hiệu Cũng xem xét đến hướng nghiên cứu kết hợp hai cách tiếp cận sử dụng giàn khái niệm, ngữ cảnh người dùng để có kết tối ưu 66 Tiếng Việt: TÀI LIỆU THAM KHẢO Nguyễn Linh Giang, Nguyễn Mạnh Hiển, (2005), “Phân loại văn tiếng Việt với phân loại vectơ hỗ trợ SVM” Trần Lâm Quân, (2009), Báo cáo thu hoạch định kỳ đề tài “Tìm kiếm thơng minh dựa tri thức” Nguyễn Trần Thiên Thanh, Trần Khải Hồng, (2005), “Tìm hiểu hướng tiếp cận toán phân loại văn xây dựng phần mềm phân loại tin tức báo điện tử” Tiếng Anh: Arzucan Özgür, (2002), “Supervised and Unsupervised machine learning techniquefor text document categorization” Ho Tu Bao, (2000), Introduction to Knowledge Discovery and Data Mining, Claudio Carpineto, Giovani Romano, (2004), Concept Data Analysis – Theory and Applications, Ounas ASFARI, Bich-liên Doan, Yolaine Bourda, Jean-Paul Sansonnet, (2009), “Personalized Access to Information by Query Reformulation Based on the State of the Current Task and User Profile” Raymond J Mooney and Un Yong Nahm, (2005) “Text Mining with Information Extraction” Ronell Fieldman, James Sanger, (2007), The Text Mining Handbook, ... chương……………………………………………………….53 Chương III Làm mịn kết tìm kiếm văn sử dụng FCA .54 3.1 Tổng quan tìm kiếm thơng tin……………………………… 54 3.2 Làm mịn kết tìm kiếm sử dụng FCA……………………….57 3.2.1 Vấn đề làm mịn kết tìm kiếm hướng tiếp... vi đề tài luận văn, em xin trình bày số vấn đề sau: - Tìm hiểu chung khai phá liệu số kỹ thuật khai phá liệu - Tìm hiểu chung khai phá văn toán khai phá văn bản, giới thiệu kỹ thuật phân tích... chúng khai phá văn tìm kiếm mẫu liệu văn có cấu trúc, khai phá liệu trích từ mẫu liệu có cấu trúc Khai phá liệu phát triển, khai phá văn giai đoạn ban đầu (Wen, 2001) khai phá văn phức tạp so khai