BO GIAO DUC VA DAO TAO TRUONG DAI HOC BACH KHOA HA NOI. NGUYEN THI MINH DUC LAM MIN KET QUA TIM KIEM VAN BAN SU DUNG KY THUAT KHAI PHA VAN BAN - LUẬN VĂN THẠC SĨ - NGÀNH : XỨT.Y THÔNG TIN VA TRUYEN THONG MÃ SÔ:. Người hướng dẫn khoa học: PGS. Nguyễn Thị Kim Anh Hà Nội 2009 LOI CAM ON Hm xin chân thanh cam on PGS.
Nguyén Vhi Kim Anh, Trưởng Bộ môn Các hệ thống thông trn, Viện CNTT-TT, Trường Đại học Bách Khoa Hà Nội. Em dã nhận được sự hướng dẫn lận tình, các góp ÿ cụ thể của PGS. trong quá trình nghiên cứu và việt luận văn, Em cũng xin được gửi lời cảm ơn chân thành đến các thấp cô giáo giảng dạy lớp CH XITTA&TT 2007 dã cụng cắp cho em những kiến thức bỗ Ích, hỗ trợ em trong việc làm luận văn, và việc tiếp tục nghiên CỨu sau này. Fim xin chân thành cảm ơn Ban giảm dốc Dự án HỖ trợ và phát triển đào tạo đại học và sau đại học về CNT1-1T, Viện đào tao 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 2007- 2009.
Fìn cũng xin gửi lời cảm ơn dên các bạn đồng nghiệp và các anh chị học viên lớp ca học XLTT-TT 2007 đã hỗ trợ. động viên để em hoàn thành huận văn này. Cuối cùng, em xin bày tỏ lòng biết an đến gia đình, bạn bè, những người luôn động viên và giúp đỡ em trong quả trình học tập và 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 LO CAM DOAN Tôi xin cam đoan luận văn này là công trình nghiên cứu của chính bản thân.
Các nghiên cứu trong luận van nay dựa trên những tổng hợp lý thuyết và hiểu biết thực 18, không sao chép, Tác giả Nguyễn Thị Minh Đức MỤC LỤC ĐANH MỤC TỪ VIẾT LÁT DANH MUC BANG, SO DO, HÌNH VẼ MỞĐẦU. g quan về khai phá dữ liệu và các kỹ thuật dùng trong khai phá dữ liệu .1 Tổng quan về khai phá đữ liệu.2 Khai phá đã liệu sử dụng cây quyết định.1 Khải niệm khai phá đã liệu sử dụng cậy quyết định.2 Điễm mạnh của cây quyết định. Điểm yếu của cây quyết dịnh.3 Khai phá dữ liệu sử dụng luật kết hợip. Khải niệm về khai phá dữ liệu sử dụng luật kết hợp.2 Điễm mạnh của phương pháp phân tích luật kết hạp:.3 _ Điểm yếu của phương pháp phân tích luậi kế! hợp,.4 Khai phá dữ liệu sử dựng ĐO CHMU.41 Khải niệm khai phá dữ liệu sử dụng gom cụm 1.42 Diễm mạnh của dò tìm gom cụm tự động.
143 Điễm yếu của phương pháp dò tìm tự đông gom cụm.5 Khai phá dữ liệu sử đụng mạng neuraLL 1.1 Khái nệm khai phá đã liệu sử dụng mang neurdl. Điểm mạnh của mạng neurdl. Điểm yếu của phương pháp mạng neurdl. Cơ sở dữ liệu (CSDL) văn bản và khai nhá CSDI, văn TA NG.
DANH MỤC TỪ VIẾT TÁT CSDL: Cơ sở dữ liệu DM: Data Mining Khai pha dé ligu SQL: Structured Query Language - Ngôn ngữ truy vẫn có cấu trúc IR: Information Retrieval — Tìm kiếm thông tỉa NILP: Natural 1.anguaae Processinp — Xử lý ngôn ngữ tự nhiên IE: Information Extraction Trích chọn thông tin FCA: Formal Concept Analysis — Phân lích khái niệm hình thức 2.1 Vin dé biéu dién vin bắn và trích chon théng tin trong van bắn 21 241 Vắn dễ biểu diễn văn bản. 212 Trích chọn thông tín.2 Khai phủ CSDL văn bản 26 2.2 Khai nhá văn bản và khai phá dữ liệu.3 Các bài toứn trong khai phá văn bản và ứng đụng. 223 Kỹ thuậi phân tích khới niệm hình thức (FCA) và ứng đựng 38 rFn. Chương HI.
Làm mịn kết quả tim kiém van ban sit dung FCA.1 Tổng quan về tìm kiểm thông tine. và cà cà ca cọ no cà co 3.2 Làm màn kết quả từm kiểm sử đụng FCA.22 tấn dễ làm mịn kết quả tìm liễm và các hướng tiếp cận.2 Cách tiếu củn biên đổi câu truy vẫn, có xử dụng phân tích khái niệm hình thức và giàn khái niệm.3 Két ludn va huwdng nghién cttw tiép Meo. ee cee eee OF 33.2 Cach nếp cận biến đổi câu truy vấn dựa trên ngữ cảnh người dụng.2 _ Dánh giá, kết luận và hướng nghiên cửa tiếp theo. 6d TAI LIEU THAM KHAO.1 Vin dé biéu dién vin bắn và trích chon théng tin trong van bắn 21 241 Vắn dễ biểu diễn văn bản.
212 Trích chọn thông tín.2 Khai phủ CSDL văn bản 26 2.2 Khai nhá văn bản và khai phá dữ liệu.3 Các bài toứn trong khai phá văn bản và ứng đụng. 223 Kỹ thuậi phân tích khới niệm hình thức (FCA) và ứng đựng 38 rFn. Chương HI. Làm mịn kết quả tim kiém van ban sit dung FCA.1 Tổng quan về tìm kiểm thông tine.
và cà cà ca cọ no cà co 3.2 Làm màn kết quả từm kiểm sử đụng FCA.22 tấn dễ làm mịn kết quả tìm liễm và các hướng tiếp cận.2 Cách tiếu củn biên đổi câu truy vẫn, có xử dụng phân tích khái niệm hình thức và giàn khái niệm.3 Két ludn va huwdng nghién cttw tiép Meo. ee cee eee OF 33.2 Cach nếp cận biến đổi câu truy vấn dựa trên ngữ cảnh người dụng.2 _ Dánh giá, kết luận và hướng nghiên cửa tiếp theo. 6d TAI LIEU THAM KHAO. Tổng quan về khai phá dữ liệu và các kỹ thuật dùng trong khai phá dữ liệu 11 Tổng quan về khai phá dữ liêu Khai phá dữ liệu (Data mining-DkD là một khái niệm ra đời vào những năm cuối của thập kỹ 80.
Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tín cỏ giá trị tiểm Ấn trong các tập dữ hiệu lớn (các kho đữ liệu). Về bản chất, khai phá đữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để phát hiện ra các mẫu, các quy luật trong tập đỡ liệu. Nim 1989, Fayyad, Piatestsky-Shapiro va Smyth da ding khai niém Phat hién tri thitc trong oo ser dit lidu (Knowledge Discavery in Database — KI2) để chỉ toàn bô quá trình phát hiện các trí thức có ích từ ip đữ liệu lớn. Trong đó, khai phá dữ liệu là một bước đặc biệt trong toan bộ quá trình, sở dụng các giải thuật đặc biệt để chiết xuất ra các mẫu tử cơ sở đữ liệu.
Cáo giải thuật khai phá đữ liệu thường được mô lá như những chương trình hoạt đông trực tiếp trên file đữ liêu. Với các phương pháp học máy và thông kê trước đây, thường thì bước đầu tiên là các giải thuật nap loan bộ file đữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho đỡ liệu lớn, mô hình này không thể đáp ứng được. Không chí bởi vì nỗ không thể nạp hết dữ liệu vào trong bộ nhớ mả còn vì khó có thể chiết xuất đữ liệu ra các filc đơn giản để phân tích được.
Quá trình xứ lý khai pha dữ liệu bắt dầu bằng cách xác định chính xúc vẫn dễ cần giải quyết Sau dó sẽ xác dịnh các dữ quan dùng để xây dựng giải pháp. Bước tiếp theo là thu thập các dữ liệu có liên quan và xử lý chúng thành đạng sao cho giải thuật khai phá đữ liệu có thé hiểu được. Về lý thuyết thì có về rất đơn giản nhưng khi thực hiện thì đây thực sự là một quả trình rất khỏ khăn, gặp phải nhiều vướng, MO BAU Xã hội hiên đại là một xã hội của tông tin và xử lý thông tin, cùng với sự phát triển của mạng Internel, nguồn thông lin hiện nay vô cùng đa đạng phong phú và nhiều về số lượng. Tuy nhiên, để sử dụng hiệu quả nguồn thông tin, cần phải có phương pháp, thuật toán, quy trình, rồi đến cả những phần mềm, những công cụ để khai phá dữ liệu nói chung và khai phá văn bản nói riêng Nghiên cứu về khai phá dữ liệu, khai phá văn bản ngày càng phát triển, dcm lại những tiểm năng to lớn cho con người.
Đặc biệt khái phá văn bản trên Internet được chú ý, do đây là nguồn thông tin chia sé cực lớn. Cũng do khối lượng thông tin chia sẻ rất lớn mà viée tim kiém thông tin trên dỏ cũng gắp một số trở ngại. Trong phạm vị của dễ tải luận văn, em xin được trinh bày về một số vẫn đề sau: - Tìm hiểu chung về khai phá đỡ liệu và một sẽ kỹ thuật khai phá dữ liệu - Tim hiểu chung về khai phá văn bản và các bài 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 trong khai phá văn bản.
- Vấn đề tim kiếm thông tn, làm mịn kết quả tìm kiểm văn bản, hướng nghiên cứu dề xuất Với hiểu biết của bản thân, và thời gian nghiên cửu, nội đụng luận văn mới dừng lại ở nghiên cứu lý thuyết và thuật toán. Chính vi vậy em rất mong nhận được góp ý và hướng dẫn thêm của các thầy cô và các bạn, để việc nghiên cứu được thực hiện triệt để và mang tính ứng đụng cụ thể hơn nữa. Tổng quan về khai phá dữ liệu và các kỹ thuật dùng trong khai phá dữ liệu 11 Tổng quan về khai phá dữ liêu Khai phá dữ liệu (Data mining-DkD là một khái niệm ra đời vào những năm cuối của thập kỹ 80. Nó bao hàm một loạt các kỹ thuật nhằm phát hiện ra các thông tín cỏ giá trị tiểm Ấn trong các tập dữ hiệu lớn (các kho đữ liệu).
Về bản chất, khai phá đữ liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để phát hiện ra các mẫu, các quy luật trong tập đỡ liệu. Nim 1989, Fayyad, Piatestsky-Shapiro va Smyth da ding khai niém Phat hién tri thitc trong oo ser dit lidu (Knowledge Discavery in Database — KI2) để chỉ toàn bô quá trình phát hiện các trí thức có ích từ ip đữ liệu lớn. Trong đó, khai phá dữ liệu là một bước đặc biệt trong toan bộ quá trình, sở dụng các giải thuật đặc biệt để chiết xuất ra các mẫu tử cơ sở đữ liệu. Cáo giải thuật khai phá đữ liệu thường được mô lá như những chương trình hoạt đông trực tiếp trên file đữ liêu.
Với các phương pháp học máy và thông kê trước đây, thường thì bước đầu tiên là các giải thuật nap loan bộ file đữ liệu vào trong bộ nhớ. Khi chuyển sang các ứng dụng công nghiệp liên quan đến việc khai phá các kho đỡ liệu lớn, mô hình này không thể đáp ứng được. Không chí bởi vì nỗ không thể nạp hết dữ liệu vào trong bộ nhớ mả còn vì khó có thể chiết xuất đữ liệu ra các filc đơn giản để phân tích được.