Tài liệu Nghiên cứu xây dựng phân hệ trích lọc và phân loại dữ liệu

  • Số trang: 25 |
  • Loại file: PDF |
  • Lượt xem: 138 |
  • Lượt tải: 0
nganguyen

Đã đăng 34345 tài liệu

Mô tả:

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- NGUYỄN VĂN TẤN NGHIÊN CỨU XÂY DỰNG PHÂN HỆ TRÍCH LỌC VÀ PHÂN LOẠI DỮ LIỆU Chuyên ngành: TRUYỀN DỮ LIỆU VÀ MẠNG MÁY TÍNH Mã số: 60.48.15 TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI - 2012 LỜI CẢM ƠN Lời ñầu tiên tôi xin chân thành cảm ơn TS.Trần Thiện Chính ñã tận tình hướng dẫn, gợi mở và ñộng viên tôi suốt quá trình học tập và thực hiện luận văn Tôi xin chân thành cảm ơn các thầy, các cô Khoa Sau ñại học - Học viện Công nghệ Bưu chính Viễn thông, ñã tận tình giảng dạy, truyền ñạt, giúp ñỡ tôi trong quá trình học tập và tạo ñiều kiện thuận lợi cho tôi thực hiện tốt luận văn. Tôi xin gửi lời cám ơn ñến tất cả bạn bè, người thân và ñồng nghiệp tại Trung tâm ñiều hành thông tin - VNPT Hà Nội ñã tạo ñiều kiện và giúp ñỡ, hỗ trợ ñộng viên tôi trong quá trình thực hiện luận văn. Tôi xin chân thành cảm ơn! Hà nội ngày 10 tháng 10 năm 2012 Học viên Nguyễn Văn Tấn 2 CHƯƠNG 1 -MỞ ðẦU 1.1. ðặt vấn ñề Nhận thức ñược lợi ích và tầm quan trọng của công nghệ thông tin và truyền thông trong việc duy trì và thúc ñẩy sự phát triển bền vững, trong những năm qua lĩnh vực công nghệ thông tin (CNTT) nói chung và hoạt ñộng ứng dụng công nghệ thông tin trong xử lý dữ liệu nói riêng ñã phát triển nhanh chóng, mạnh mẽ và ngày càng có ý nghĩa quan trọng trong mọi mặt của kinh tế - xãhội. Vì vậy nhu cầu phân loại, lọc dữ liệu là một nhiệm vụ rất quan trọng có thể hữu ích trong tổ chức cũng như tìm kiếm thông tin trên nguồn tài nguyên lớn. Phân lớp dữ liệu là một nhiệm vụ rất quan trọng trong việc tổ chức cũng như tìm kiếm dữ liệu trên nhiều nguồn khác nhau. Mặt khác, phân lớp dữ liệu là một trong những thành phần cơ bản nhưng quan trọng nhất trong kiến trúc tổng thể của hầu hết các máy tìm kiếm. Hiện nay, bài toán này ñã và ñang nhận ñược nhiều sự quan tâm, nghiên cứu của các nhà khoa học. ðể tổng hợp trích lọc dữ liệu và phân loại dữ liệu cần phải xây dựng công cụ hỗ trợ tác nghiệp xử lý thành thông tin ñể hỗ trợ nhu cầu phân tích của các nhà lãnh ñạo, các nhà chiến lược trong tổ chức và sự ra ñời ứng dụng mới phục vụ cho mục ñích này ñược gọi là “Hệ trích lọc và xử lý dữ liệu”. Dữ liệu ñược lưu trữ, xử lý, kết xuất theo các nhóm và loại, các mục ñích cụ thể dưới dạng hướng chủ ñề. 1.2. Mục tiêu và phạm vi luận văn 1.2.1. Mục tiêu luận văn Với xu hướng phát triển mạnh mẽ trong công nghệ thông tin, ñặc biệt là lượng thông tin, nguồn dữ liệu cực kỳ lớn ñã ñòi hỏi phải có hệ thống lọc, xử lý và phân loại dữ liệu. Do vậy nhu cầu cần nghiên cứu và xây dựng các công cụ trích lọc, phân loại dữ liệu ñược ñặt ra nhằm nâng cao hiệu quả sử dụng nguồn dữ liệu. Xuất phát từ yêu cầu ñó, tác giả ñặt vấn ñề nghiên cứu xây dựng phân hệ trích lọc và phân tích dữ liệu. Mục ñích của ñề tài là hướng tới xây dựng bộ công cụ trích lọc, phân tích dữ liệu từ các nguồn khác nhau. 1.2.2. Phạm vi luận văn ðối tượng của ñề tài là các nguồn dữ liệu khác nhau trên Web hay Internet. Phạm vi nghiên cứu của ñề tài trong lĩnh vực trao ñổi, xử lý dữ liệu trên trang Web và các nguồn RSS, do thời hạn thực hiện luận văn có hạn nên trong phạm vi của luận văn này, sẽ thực hiện nghiên cứu phương pháp rút trích và phân loại trên công cụ GATE Framework 7.0 . 3 1.3. Kết quả ñạt ñược Nghiên cứu hệ thống trích lọc và phân loại dữ liệu từ nguồn URLs, RSS dụng GATE Framework trên các thư viện số, ñồng thời kết hợp với việc sử dụng cơ sở dữ liệu có sẵn, ñể dữ liệu trích lọc ñược ñảm bảo tính ñầy ñủ, chính xác cao. Tập trung vào cách rút ra ñược các thực thể và quan hệ dựa vào các API của GATE: Trong ñó tập trung vào rút trích thực thể và quan hệ của các chương trình ñã ñược xây dựng trước. 1.4. Bố cục luận văn Nội dung chính của luận văn ñược bố cục gồm có 3 chương như sau: Chương 1: Mở ñầu.Nội dung chương này xác ñịnh vấn ñề cần nghiên cứu của luận văn, mục tiêu và phạm vi của luận văn cũng như tóm lược kết quả ñạt ñược của luận văn. Chương 2: Khái quát trích lọc.Nội dung chương này phân loại dữ liệu, ñịnh nghĩa và khái niệm trích lọc dữ liệu từ trước ñến nay trên thế giới. Nghiên cứu nguyên tắc rút trích, phân loại dữ liệu, phương pháp rút trích hiện nay. phạm vi ứng dụng rút trich thông tin,ñặc trưng dữ liệu trong quá trình xử lý rút trích. Chương 3:Kỹ thuật rút trích dữ liệu và phân loại.Nội dung chương này thể hiện mô hình dữ liệu sử SVM và GATE Framework. ðặc tả dữ liệu và biểu diễn mô hình. Chương 4: Kết quả rút trích, và phân loại dữ liệu khi sử dụng công cụ GATE Framwork. CHƯƠNG 1-KHÁI QUÁT TRÍCH LỌC, PHÂN LOẠI DỮLIỆU 1.5. ðịnh nghĩa rút trích thông tin Các ñịnh nghĩa ñược dùng phổ biến trên internet liên quan ñến trích xuất thông tin bao gồm: Các nghiên cứu hiện nay liên quan ñến rút trích thông tin văn bản tập trung vào: - Rút trích các thuật ngữ (Terminology Extraction): Tìm kiếm các thuật ngữ chính có liên quan, thể hiện ngữ nghĩa, nội dung, chủ ñề tài liệu hay một tập các tài liệu. - Rút trích các thực thể ñịnh danh (NER):Việc rút trích ra các thực thể ñịnh danh tập trung vào các phương pháp nhận diện các ñối tượng, thực thể như: tên người, tên công ty, tên tổ chức, một ñịa danh, nơi chốn. - Rút trích quan hệ (Relationship Extraction):Cần xác ñịnh mối quan hệ giữa các thực thể ñã nhận biết từ tài liệu. Chẳng hạn xác ñịnh nơi chốn cho một tổ chức, công ty hay nơi làm việc của một người nào ñó. 4 1.6. Nguyên tắc rút trích thông tin Theo tiến sĩ Diana Maynard hầu hết các hệ thống rút trích thông tin(IE) nói chung thường tiến hành các bước sau: - Tiền xử lý . - Nhận biết ñịnh dạng tài liệu (Format detection). - Tách từ (Tokenization). - Phân ñoạn từ (Word Segmentation). - Giải quyết nhập nhằng ngữ nghĩa (Sense Disambiguation). - Tách câu (Sentence Splitting). - Gán nhãn từ loại (POS Tagging). - Nhận diện thực thể ñịnh danh (Named Entity Detection). - Nhận biết thực thể (Entity Detection). - Xác ñịnh ñồng tham chiếu (Coreference). 1.7. Phương pháp tiếp cận rút trích thông tin Các phương pháp trích xuất hiện nay có thể chia thành hai cách tiếp cận chính: tiếp cận công nghê tri thức (Knowledge Engineering) và tiếp cận học máy tự ñộng (Automatic Training). 1.8. Phương pháp ñánh giá rút trích thông tin Sadflk ðể ñánh giá kết quả của thông tin ñược trích xuất, các chuyên gia ñã ñưa ra ñộ ño và ñược sử dụng trong lĩnh vực truy vấn thông tin (IR) ñó là ñộ chính xác “Precision” và ñộ tin cậy “Recall”. ðộ chính xác Precision (P): Là phân số thể hiện tỷ lệ thông tin ñược rút trích ñúng. Bao nhiêu phần trăm thông tin ñược rút là ñúng. Tỷ lệ giữa số lượng câu trả lời ñúng tìm thấy với tổng số câu trả lời ñúng có thể. ðộ tin cậy Recall (R): Là ñộ ño hay phân số thể hiện khả năng tin cậy của thông tin ñược trích xuất. Tỷ lệ giữa tổng số câu trả lời ñúng tìm thấy với tổng số câu trả lời tìm thấy. R= tp (tp + tn) (1) P= tp (tp + fp ) (2) Với: tp là số kết quả ñúng ñược tìm thấy; tn là số kết quả ñúng mà không tìm thấy; fp 5 là số kết quả tìm thấy mà không ñúng. Người ta ñã tìm cách kết hợp hai ñộ ño này và ñề xuất một ñộ ño mới, ñó là F-Measure (F). Thông số β xác ñịnh mức ñộ tương quan giữa ñộ chính xác P (Precision) và ñộ tin cậy R (Recall). Các chuyên gia về rút trích thông tin thường sử dụng β = 1 ñể ñánh giá ñộ ño F. Khi ñó P và R ñược gán trọng số bằng nhau, hiệu năng của hệ thống ñược ñánh giá thông qua các giá trị khác nhau của ñộ chính xác R và ñộ tin cậy P, từ ñó có thể so sánh một cách dễ dàng. Với β = 1 thì F-Mearsure: F = 2× P× R ( P + R) 1.9. Một số phương pháp trích lọc và phân loại dữ liệu hiện nay 1.9.1. Phương pháp rút trích cụm từ khóa (Keyphrase Extraction) Việc rút trích trước ñây hầu hết dựa vào tiếp cận phân tích cú pháp, tách câu, thống kê tần xuất xuất hiện tf*idf ñể rút ra các cụm. Kết quả rút trích vẫn chưa thực sự tốt, còn khá nhiều “rác” (cụm vô nghĩa, cụm không thể hiện ñiện ngữ nghĩa của tài liệu ñề cập). Vấn ñề xác ñịnh chính xác các cụm từ khóa, cũng như xác ñịnh ñược biên giới của các từ khóa, cụm từ khóa từ tài liệu tiếng Việt hiện nay vẫn là một bài toán khó và vẫn ñang ñược quan tâm nghiên cứu. 1.9.2. Phương pháp sinh cụm từ khóa tự ñộng Phương pháp gán cụm từ khóa (Keyphrase Assignment):Tìm kiếm và chọn các cụm từ khóa từ từ vựng quản lý (Controlled Vocabulary) thích hợp nhất ñể mô tả tài liệu. Tập dữ liệu huấn luyện là một tập hợp các tài liệu với mỗi cụm từ trong từ vựng và dựa vào ñó ñể xây dựng một bộ phân lớp (classifier). Phương pháp trích xuất cụm từ khóa (Keyphrase Extraction):Sẽ dùng các kỹ thuật truy vấn thông tin và xử lý từ vựng ñể chọn ra các cụm từ khóa từ chính tài liệu ñang xét thay vì dùng các cụm từ ñịnh nghĩa trước trong từ vựng quản lý. 1.9.3. Phương pháp trích xuất các cụm từ khóa (KEA) KEA dùng phương pháp học máy Naïve Bayes ñể huấn luyện và rút trích các cụm từ khóa. 6 Theo nhận ñịnh của các tác giả, KEA là thuật toán có khả năng ñộc lập ngôn ngữ.Các bước sau thực hiện thuật toán KEA: Chi tiết tham khảo (Phụ lục A). 1.9.4. Phương pháp thống kê Hầu hết các nghiên cứu ñầu tiên cho rút trích dữ liệu ñều tập trung trên những tài liệu kỹ thuật (các bài báo khoa học). Các phương pháp cổ ñiển thường tập trung vào các ñặc trưng hình thái ñể tính ñiểm cho các câu và rút trích các câu quan trọng ñể ñưa vào tóm tắt. Sử dụng các ñặc trưng như: wordfrequency, stopwords, position, cuewords, title. Sử dụng phương pháp kết nối tuyến tính ñể kết hợp các ñiểm ñặc trưng lại với nhau: + Thử nghiệm với 400 dữ liệukỹthuật và kết quảñạt 44%. 1.9.5. Phương phápthống kê trên TF.IDF Phương pháp này còn gọi là mô hình túi từ (bag-of-words), sử dụng mô hình trọng số tần suất thuật ngữ và tần suất câu ñảo ngược (TF.IDF). Ở mô hình này, giá trị IDF ñược tính trên câu. Trongñó, TF là số lần xuất hiện của term trong1 câu. Và DF là số câu có chứa thuật ngữ. Tuy nhiên, phương pháp dung ñộ ño TF.IDF không ñược dùng ñộc lập, mà thường ñược kết hợp với các phương pháp khác như máy học, ñồ thị… ñể ñạt ñược hiệu quả cao hơn. 1.9.6. Phương pháp Naïve-Bayes Các hướng tiếp cận theo phương pháp này giả ñịnh rằng các ñặc trưng của dữ liệu ñộc lập nhau. Sử dụngbộ phân lớp Naïve-Bayes ñể xác ñịnh câu nào thuộc về tóm tắt và ngược lại: Chos là các câu cần xác ñịnh. F1…Fk là các ñặc trưng ñã ñược chọn, và giả ñịnh các thuộc tính ñộc lập nhau. Xác suất của câu s thuộc về tóm tắt ñược tính như sau: Sau khi tính xác suất các câu, n câu có xác suất cao nhất sẽ ñược rút trích. + Kết hợp thêm nhiều ñặc trưng phong phú hơn: tf.idf(singleword, two-noun word, named-entities), discourse(cohension) (sử dụng Wordnet và kỹ thuật sử lý ngôn ngữ tự nhiên ñể phân tích sự tham chiếu ñối với các thực thể). 1.9.7. Phương pháp mô hình Makov ẩn (Hidden Makov Model) Tác giả ñưa ra khái niệm về sự phụ thuộc cục bộ (local dependencies) giữa các câu và 7 sử dụng mô hình HMM ñể xác ñịnh sự phụ thuộc này. Các ñặc trưng sử dụng: position, number of term, like lihood of sentence. Mô hình HMM bao gồm 2s+1 trạng thái, trong ñó s là số trạng thái tóm tắt (câu thuộc tóm tắt) và s+1 là câu không thuộc tóm tắt. Hình 1.1 : Mô hình Hidden Makov Model Mô hình HMM xây dựng ma trận chuyển vị M, coi các ñặc trưng là ña biến và tính xác suất của các câu qua từng trạng thái. 1.9.8. Phương pháp máy học SVM SVM là một phương pháp phân loại xuất phát từ lý thuyết học thống kê. Ý tưởng của nó là ánh xạ (tuyến tính hoặc phi tuyến) dữ liệu vào không gian các vector ñặc trưng (space of feature vectors) mà ở ñó một siêu phẳng tối ưu ñược tìm ra ñể tách dữ liệu thuộc hai lớp khác nhau. Giả sử, chúng ta lựa chọn ñược tập các ñặc trưng là T={t1, t2, …, tn}, xi là vector dữ liệu ñược biểu diễn xi=(wi1, wi2, …, win), win∈R là trọng số của ñặc trưng tn. Với tập dữ liệu huấn luyện Tr={(x1, y1), (x2, y2), …, (xl, yl)}, (xi∈Rn), yi∈{+1, -1}, cặp (xi, yi) ñược hiểu là vector xi ñược gán nhãn là yi. Nếu coi mỗi xi ñược biểu diễn tương ứng với một ñiểm dữ liệu trong không gian Rn thì ý tưởng của SVM là tìm một mặt hình học (siêu phẳng) f(x) “tốt nhất” trong không gian nchiều ñể phân chia dữ liệu sao cho tất cả các ñiểm x+ ñược gán nhãn 1 thuộc về phía dương của siêu phẳng (f(x+)>0), các ñiểm x- ñược gán nhãn –1 thuộc về phía âm của siêu phẳng (f(x-)<0). 8 Hình 1.2 : H2 là mặt phẳng tốt nhất Việc tính toán ñể tìm ra siêu mặt phẳng tối ưu dùng kỹ thuật sử dụng toán tử Lagrange ñể biến ñổi thành dạng ñẳng thức là rất phức tạp và khó khăn. Hiện nay ñã có những bộ thư viện ñã hỗ trợ cho việc tính toán trên như : SVMlight, LIBSVM, jSVM, ... Ví dụ: Giả sử ta có một tập các ñiểm ñược gán nhãn dương (+1): {(3,1), (3, -1), (6, 1), (6, -1)}; và tập các ñiểm ñược gán nhãn âm (-1) trong mặt phẳng R+: {(1, 0), (0, 1), (0, -1), (-1, 0)}. Chúng ta sẽ dùng SVM ñể phân biệt hai lớp (+1 và -1). Bởi vì dữ liệu ñược chia tách một cách tuyến tính, rõ ràng, nên chúng ta sử dụng linear SVM (SVM tuyến tính) ñể thực hiện. Hình 1.3 : Các ñiểm dữ liệu ñược biểu diễn trên R+ Theo quan sát Hình 3.6, chúng ta chọn ra 3 vector hỗ trợ ñể thực thi các phép toán 9 nhằm tìm ra mặt phẳng phân tách tối ưu nhất: {s1 = (1,0), s2 = (3,1), s3 = (3, -1)} Hình 1.4 : Các vector hỗ trợ (support vector) ñược chọn Các vector hỗ trợ ñược tăng cường (augmented) bằng cách thêm 1. Tức là s1 = (1, 0), thì nó sẽ ñược chuyển ñổi thành s% = (1, 0, 1). Theo kiến trúc SVM, công việc của chúng ta là tìm ra những giá trị αi . α1Φ ( s1 ).Φ ( s1 ) + α 2 Φ ( s2 ).Φ ( s1 ) + α 3Φ ( s3 ).Φ ( s1 ) = −1 α1Φ ( s1 ).Φ ( s2 ) + α 2 Φ ( s2 ).Φ ( s2 ) + α 3Φ ( s3 ).Φ ( s2 ) = +1 α1Φ ( s1 ).Φ ( s1 ) + α 2 Φ ( s2 ).Φ ( s3 ) + α 3Φ ( s3 ).Φ ( s3 ) = +1 Bởi vì chúng ta sử dụng SVM tuyến tính nên hảm Φ () - dùng ñể chuyển ñổi vector từ không gia dữ liệu ñầu vào sang không gian ñặc trưng – sẽ bằng Φ () = I . Biểu thức trên ñược viết lại như sau: α1s%1.s%1 + α 2 s%2 .s%1 + α 3 s%3 .s%1 = −1 α1s%1.s%2 + α 2 s%2 .s%2 + α 3 s%3 .s%2 = +1 α1s%1.s%3 + α 2 s%2 .s%3 + α 3 s%3 .s%3 = +1 Rút gọn biểu thức trên thông qua việc tính toán tích vô hướng giữa các vector. 2α1 + 4α 2 + 4α 3 = −1 4α1 + 11α 2 + 9α 3 = +1 4α1 + 9α 2 + 11α 3 = +1 Giải hệ phương trình 3 ẩn trên ta có: α1 = -3.5, α2 = 0.75, α3 = 0.75. Tiếp ñến ta tính trọng số ω% thông qua công thức: 1  3 3  1 ω% = ∑ α i s%i = −3.5  0  + 0.75  1  + 0.75  −1  =  0  i 1         1  1   −2  Siêu phẳng phân chia 2 lớp ñó là: y = wx + b với w = (1, 0) và b = -2. 10 1.10. Phạm vi ứng dụng rút trích thông tin Khả năng ứng dụng của từ khóa và cụm từ khóa có thể kể ñến như sau: - Các kho dữ liệu văn bản lớn như các thư viện số phát triển rất nhanh dẫn ñến gia tăng giá trị thông tin tóm tắt. - Hỗ trợ người dùng nhận biết về nội dung của tài liệu và kho tài liệu. - Ứng dụng trong truy vấn thông tin  mô tả những tài liệu trả về từ kết quả truy vấn. ðịnh hướng tìm kiếm cho người dùng. - Nền tảng cho chỉ mục tìm kiếm. - Là ñặc trưng dùng trong kỹ thuật phân loại, gom cụm tài liệu. Việc gán các keyphrases cho tài liệu: Các cụm từ khóa thường ñược gán bằng tay, tức các tác giả chủ ñộng gán các cụm từ khóa cho tài liệu họ viết. ðối với các bộ chỉ mục chuyên nghiệp thường chọn các cụm từ một từ vựng quản lý.  Vấn ñề gặp phải ñối với các tài liệu không có cụm từ khóa. Việc gán bằng tay là quá trình tốn nhiều thời gian, công sức, cũng như cần có kiến thức chuyên môn.  Rất cần thiết các kỹ thuật rút trích tự ñộng. 1.11. Các ñặc trưng dữ liệu Các ñặc trưng ñộc lập nhau. Các ñặc trưng rời rạc: Vector ñặc trưng di có thể có nhiều thành phần mang giá trị 0 do có nhiều ñặc trưng không xuất hiện trong dữ liệu di (nếu tiếp cận theo cách sử dụng giá trị nhị phân 1, 0 ñể biểu diễn cho việc có xuất hiện hay không một ñặc trưng nào ñó trong dữ liệu ñang ñược biểu diễn thành vector), do ñó một cách tiếp cận khác là không sử dụng số nhị phân 0, 1 mà sử dụng giá trị số thực ñể phần nào giảm bớt sự rời rạc trong vector dữ liệu. Quá trình phân tích xử lý ngôn ngữ tự nhiên có các mức ñộ sâu xử lý khác nhau như: mức hình thái, mức cú pháp và mức ngữ nghĩa. 1.11.1. Mứcñộ hình thái ðặc trưng về chủ ñề(Thematic): thống kê từ, tần suất từ, stop words, TF.IDF. ðặc trưng về vị trí(Location) :vị trí câu trong dữ liệu hay ñoạn văn(câu ñầu tiên trong 11 mỗi ñoạn, n câu ñầu tiên của dữ liệu), phương pháp tiêu ñề(câu chứa từ có trong tiêu ñề), cue- words hay fixed-phrased (câu chứa những ngữ cố ñịnh). ðặc trưng về ñịnh dạng (format). ðặc trưng về chủ ñề trong dữ liệu (Threads of topic). ðặc trưng về cấu trúc chuỗi từ vựng (Lexical chains). ðặc trưng về cấu trúc lý luận (Rhetorical structure). 1.11.2. Mức ñộ ngữ nghĩa Hiện nay ñã có các phương pháp trích lọc (SVM, CRF, GATE, Naïve-Bayes, KEA ...) Trong ñó phương pháp trích lọc và phân loại GATE có những ưu nhược ñiểm: - Trích lọc ñược nhiều dạng dữ liệu ñầu vào: Text, Internet, Rss, XML, DBF và một số dạng văn bản khác. - Là công cụ mã nguồn mở, cho phép phát triển tiếp thành công cụ hữu ích ñể trích lọc dữ liệu, và phân loại dữ liệu cho một lĩnh vực chuyên sâu. Ví dụ: Nông nghiệp nông thôn, Y học, Dược … Vì vậy lựa chọn GATE Frame ñể nghiên cứu trích lọc và phân loại dữ liệu từ các nguồn Internet.GATE ñược viết hoàn toàn bằng Java và là phần mềm mã nguồn mở, ngoài ra, nó còn sử dụng JAPE (Java Annotation Patterns Engine) ñể xây dựng các bộ luật cho việc gán nhãn dữ liệu. CHƯƠNG 2 -KỸ THUẬT TRÍCH LỌC VÀ PHẦN LOẠI DỮ LIỆU GATE Framework 2.1. Biểu diễn dữ liệu cần trích lọc và phân loại 2.1.1. Dữ liệu ñầu vào a. Các ñối tượng dữ liệu có thể là kho tài liệu hay các tài nguyên ngôn ngữ như : danh sách, bộ từ vựng hay một cấu trúc phức tạp như bản thể học. Mỗi ñối tượng dữ liệu có thể bao gồm tối thiểu các thuộc tính như sau: - Tên: Tên của ñối tượng. - Vị trí lưu trữ: ðường dẫn vật lý ñến tập tin hay thư mục. - ðịnh dạng: Text, doc, pdf, xml, URL, RSS từ nguồn internet ... - Tính chất: xử lý tạm thời trong bộ nhớ hay xử lý và lưu trữ thường trực trên thiết bịlưu trữ. - Loại: Kho dữ liệu, danh mục từ, các bản thể học. - Bộ nhãn: Các thành phần trong ñối tượng dữ liệu như từ (word), cụm từ (chunk), 12 ñoạn (paragraph), câu (sentence) sẽ ñược gán nhãn theo một bộ nhãn nào ñó. b. Cách thức thu thập dữ liệu, tiền xử lý dữ liệu từ nguồn Internet(RSS, URL) như sau: Tiền sử lý dữ liệu: lọa bỏ dữ liệu dư thừa, sắp xếp dữ liệu ñầu vào, ñưa dữ liệu thành cấu trúc mới gọi là dữ liệu thô. Sử dụng công cụ Dacqpipe ñể xử lý dữ liệu cho Annotation GATE có nghĩa là dữ liệu ñầu vào (Corpus) ñã làm sạch nhiễu. Quá trình Dacqpipe xử lý ADC (Annotated Document corpus) cho GATE là dạng cấu trúc dữ liệu ñược loại bỏ nhiễu. Kết quả ñưa ra một tập dữ liệu thô ñã sắp xếp và làm sạch nhiễu ñóng nhãn có dạng (Token, Câu, Tên thực thể) ñược diễn tả với ñặc trưng XML. 2.1.2. Hướng tiếp cận nhận diện thực thể Hệ thống nhận diện thực thể có tên phổ biến: có thể kể ñến các hệ thống phổ biến hiện nay như: Hầu hết các phương pháp rút trích quan hệ tiếp cận theo các hướng như dựa trên luật (rule-base), dựa trên ñặc trưng (feature-based) và các phương pháp kernel (kernel-based). 2.2. Phương pháp trích lọc và phân loại dữ liệu từ một số nguồn khác nhau 2.2.1. Trích lọc 13 Dữ liệu Dữ liệu huấn test Dữ liệu tóm tắt Rút Nguồn trích ñặc trưng dữ liệu Nguồn dữ liệu ðóng Rút trích nhãn ñặc trưng Tập Luật Thuật toán huấn luyện Kết quả rút rich dữ liệu Hình 2.1 : Mô hình trích lọc dữ liệu SVM Framework chung cho hệ thống tóm tắt dữ liệu bằng phương pháp máy học. 2.2.2. Phân loại dữ liệu 2.2.2.1. Khái niệm: “Phân loại văn tài liệu là việc gán các nhãn phân loại lên một tài liệu mới dựa trên mức ñộ tương tự của tài liệu ñó so với các tài liệu ñã ñược gán nhãn trong tập huấn luyện”. 2.2.2.2. SVM trong bài toán rút trích metadata. Rút trích những trường metadata từ nội dung header của bài báo khoa học. Mỗi dòng trong header sẽ ñược phân lớp, gán nhãn yi với i = {0..15} tương ứng với 15 trường dữ liệu của metadata theo chuẩn Dublin Core: - Cách giải quyết: Các bước thực hiện như sau: + Bước 1: Chuẩn bị tập dữ liệu huấn luyện (training dataset) với các ñặc trưng về từ và dòng cho bộ phân lớp (15 ñặc trưng). Tiến hành tính toán các vector ñặc trưng trong tập 14 dữ liệu kiểm thử. + Bước 2: Phân lớp từng dòng ñộc lập theo 15 ñặc trưng, và gán nhãn tạm thời cho từng dòng. + Bước 3: Biểu diễn từng dòng lại theo 15 + 150 ñặc trưng. ðưa vào bộ phân lớp theo ngữ cảnh (context) và tiến hành gán nhãn lại. 2.2.3. Phương pháp tiếp cận rút trích thông tin: 2.2.3.1. Phương pháp rút trích thông tin dựa trên học máy (Machine Learning) Bằng cách học từ tập huấn luyện (quan sát các ñặc trưng của tập dữ liệu ñã ñược xác ñịnh bởi chuyên gia), hệ thống sẽ phân tích nội dung dữ liệu mà người dùng ñưa vào (thường là dạng text), ñể rút ra thông tin Metadata của tài liệu. 2.2.3.2. Phương pháp rút trích thông tin dựa vào tập luật Các luật ñược các chuyên gia có kinh nghiệm ñặt ra trước. Dựa vào các luật, hệ thống sẽ rút ra thông tin Metadata ở vùng tương ứng. Các luật cũng cần phải thay ñổi khi xuất hiện các loại dữ liệu mới mà những luật hiện có không thể giải quyết ñược. Vậy “ ðể có ñược một kết qủa phân loại ñạt kết qủa tốt thì cần những yếu tố gì ? ”. Có 3 yếu tố quan trọng tác ñộng ñến kết qủa phân loại dữ liệu: Cần một tập dữ liệu huấn luyện chuẩn và ñủ lớn ñể cho thuật toán học phân loại. Các phương pháp hầu hết ñều sử dụng mô hình vector ñể biểu diễn dữ liệu, do ñó phương pháp tách từ là một yếu tố quan trọng. Thuật toán sử dụng ñể phân loại phải có thời gian xử lý hợp lý , thời gian này bao gồm : thời gian học , thời gian phân loại dữ liệu , ngoài ra thuật toán này phải có tính tăng cường (incremental function). 2.3. ðặc tả trích rút dữ liệu và biểu diễn mô hình 2.3.1. Bước 1: Rút trích các vectơ ñặc trưng ðặc trưng từ cho phân nhóm từng dòng ðặc trưng Chú thích :rss: Sử dụng regular expression ñể so khớp. :url: Sử dụng regular expression ñể so khớp. :abstract: Tóm tắt 15 ðặc trưng Chú thích :keyword: key word, key words, keyword, keywords :intro: Introduction :prep: Giới từ: at, in, of :DictWord: Một từ ñược viết thường, có trong từ ñiển. :NonDictWord: Một từ ñược viết thường, không có trong từ ñiển. :Dig[3]: Một chữ số với 3 ký tự Bảng 2.1 : Những ñặc trưng dòng Những ñặc trưng trên ñược kết hợp với các bộ từ ñiển ñã biên soạn trước ñó: Các ñặc trưng trên phải ñược chuẩn hóa ( ) trọng số ñặc trưng về khoảng [0, 1] ñể nâng cao khả năng thực thi phân lớp của SVM. Mỗi dòng li trong header h sẽ ñược biểu diễn thành một vector xi: xi=(wi1, wi2, …, win), win∈R là trọng số của ñặc trưng tn trong dòng li. Như vậy, bài toán ñã ñược biểu diễn thành dạng bài toán ñúng theo ñặc tả SVM. Do ñó, nếu ta xây dựng một tập huấn luyện Tr={(x1, y1), (x2, y2), …, (xi, yi)}, Với xi là những vector ñã ñược tính các trọng số ñặc trưng win và ñã ñược gán nhãn sẳn yi∈ [1..15] của từng dòng huấn luyện. Từ ñó xây dựng các bộ phân lớp theo dòng cho từng lớp (class). Hình 2.2 : ñặc trưng trích lọc List-Word Hui Han C. Lee Giles Eren Manavoglu Database : Hongyuan Zha USA state Department of Computer Science and USA city name Engineering 8441 fist name last List word : The Pennsylvania State University Affiliation. Token + bigram : (look up into exist DB and Adrress. List word) Degree. Publish name CsenLen : 6 …. ClinePos : 2 Ví dụ : 2.3.2. Bước 2: Phân lớp các dòng ñộc lập theo 15 ñặc trưng, và gán nhãn tạm thời cho 16 từng dòng 2.3.3. Bước 3: Biểu diễn từng dòng lại theo 15 + 150 ñặc trưng. ðưa vào bộ phân lớp theo ngữ cảnh (context) và tiến hành gán nhãn lại: - Thông qua bộ phân lớp ñộc lập ta xây dựng tập Ω1với 15 ñặc trưng ñược ñề cập ở phần trên, bộ phân lớp theo ngữ cảnh Ω2 với 15 + 150 ñặc trưng : 15 ñặc trưng dòng của Ω1cộng với 150 ñặc trưng là những nhãn của 5 dòng trước và 5 dòng sau dòng ñang xét. CHƯƠNG 3 -ỨNG DỤNG CÔNG CỤ TRÍCH LỌC VÀ PHÂN LOẠI 3.1. Ứng dụng GATE trích lọc và phân loại dữ liệu 3.1.1. Sơ lược GATE 3.1.1.1. Giới thiệu về GATE ðề tài dựa trên xây dựng các luật, mẫu dựa trên thông tin cấu trúc và trình bày của tài liệu, kết hợp với những từ ñiển, ontologies và thư viện sẵn có của GATE ñể rút trích các metadata cho các tài liệu khoa học. Cung cấp một kiến trúc, hoặc một cấu trúc tổ chức cho những phần mềm xử lý ngôn ngữ. Cung cấp một nền (framework), hoặc một thư viện hiện thực kiến trúc. Cung cấp một môi trường phát triển (development environment) GATE ñược phát triển bằng ngôn ngữ Java nên khi cài ñặt GATE ta phải cài máy ảo java vào trước. Các thành phần trong GATE Kiến trúc của GATE có thể ñược thể hiện qua hình dưới ñây. 17 Hình 3.1 : Mô hình kiến trúc của GATE Dựa trên hình trên GATE bao gồm 7 lớp chính: - IDE GUI Layer (VTs): lớp giao diện người dùng. - Application Layer: các lớp ứng dụng mà GATE ñã xây dựng, ví dụ ANNIE, … - Document Format Layer: lớp quản lý loại các tài liệu theo ñịnh dạng: xml, html, … - Corpus Layer (LRs): lớp quản lý kho tài liệu (tập hợp một nhóm các tài liệu) - Processing Layer (PRs): lớp quản lý các ñối tượng xử lý tài liệu: NE, Co-ref, Tes, … - Language Resource Layer (LRs): lớp quản lý các ñối tượng dữ liệu ñặc biệt trong GATE như: Ontology, Word-net, Gazetteer, … - DataStore and Index Layers: lớp quản lý về lưu trữ như lưu lại trạng thái. 3.1.1.2. Tài nguyên ngôn ngữ (LR) ðược chia làm 3 thành phần chính: tài nguyên ngôn ngữ, tài nguyên xử lý và tài nguyên hiển thị. 3.1.1.3. Dữ liệu trong GATE Khi ta tạo một GATE Document thì GATE sẽ cần xác ñịnh ñó là loại dữ liệu thuộc ñịnh dạng nào (xml, html, ..) ñể ñưa ra thuật toán thích hợp ñể xử lý cho từng loại dữ liệu riêng biệt. 3.1.1.4. Xác ñịnh bộ ñọc(Right Reader) 3.1.2. Giới thiệu về GATE-ANNIE 3.1.2.1. Giới thiệu về ANNIE 18 ANNIE (A Nearly New Information Extraction System) là hệ thống rút trích thông tin bao gồm tập hợp các tài nguyên xử lý. 3.1.2.2. Các thành phần trong ANNIE Tokeniser: Tokeniser chia dữ liệu thành các thành phần ñơn giản, ñược gọi là TOKENS, với nhiều loại khác nhau như là: từ, số, dấu chấm câu, các ký tự ñặt biệt ($, £, &, # …) và khoảng trắng. Tokeniser Rules: một luật gồm có LHS (Left Hand Side) và RHS (Right Hand Side). LHS và RHS cách nhau bởi dấu ‘>’. Toán tử của LHS: - “|” hay - “:” xuất hiện 0 lần hoặc nhiều lần hơn. - “?” xuất hiện 0 lần hoặc 1 lần. - “+” xuất hiện 1 lần hoặc nhiều lần hơn. Toán tử của RHS:Sử dụng dấu “;” làm dấu phân cách, theo ñịnh dạng sau: {LHS} > {annotation type} ; {attribute 1}={value1};…; {attribute N}={value N} Gazetteer: Danh sách Gazetteer là những tập tin dữ liệu ñơn giản, với mỗi dòng là một thực thể. - ðể truy cập ñến các danh sách trong Gazetteer ta dùng một tập tin chỉ mục “list.def”. Cấu trúc của tập tin chỉ mục “list.def” gồm có: nhiều hàng, mỗi hàng mô tả một danh sách gồm có tên của danh sách ñó (list name), kiểu chính (major type), kiểu phụ (minor type) của những từ ñược liệt kê trong danh sách, những thông tin này ñược phân biệt bởi dấu hai chấm “:”. - Cách tạo một danh sách Gazetteer, Ở ñây ta dùng Notepad, tập tin sẽ gồm nhiều dòng, tại mỗi dòng là một tên của thực thể, có thể là một từ hoặc một cụm từ, chấp nhận có khoảng trắng. Và lưu lại với ñuôi mở rộng là “.lst”. Sau ñó ta mở tập tin chỉ mục “list.def” ñể thêm danh sách mới tạo vào. 3.1.3. JAPE 3.1.3.1. Giới thiệu JAPE – Java Annotation Patterns Engine là một thành phần của GATE, dùng ñể nhận biết các thực thể bằng luật ñược ñịnh nghĩa trước. 3.1.3.2. JAPE Grammar JAPE Grammar gồm một tập hợp nhiều phần (phase), mỗi phần chứa một tập các luật 19 ñược ñịnh nghĩa thành từng pattern. JAPE Grammar gồm có hai phần là vế trái (LHS) và vế phải (RHS) , hai vế ñược phân biệt bởi ký hiệu “-->”. Có cú pháp sau: LHS --> RHS. Vế trái chứa phần mô tả về những pattern chú thích, trong ñó có thể chứa các toán tử sau: - “|” hay - “:” xuất hiện 0 lần hoặc nhiều lần hơn. - “?” xuất hiện 0 lần hoặc 1 lần. - “+” xuất hiện 1 lần hoặc nhiều lần hơn. Vế phải bao gồm các chú thích do ta tự ñịnh nghĩa, chúng chứa thông tin về tên nhãn. Ngoài ra vế phải có thể chứa mã code Java ñể tạo hoặc chỉnh sửa các chú thích. Mỗi pattern mô tả chú thích bên vế trái có thể ñược tham chiếu tới vế phải bằng tên nhãn ñược gắn vào mỗi pattern. Tên nhãn này ñược ñặt sau dấu “:”. Ví dụ:ðoạn ngữ pháp ñơn giản gán nhãn cho môn thể thao “Soccer”. Hình 3.2 : Từ “Soccer” ñược gán nhãn là “Lookup” 20
- Xem thêm -