Tài liệu Luận văn phân lớp quan điểm khách hàng và ứng dụng

ĐẠI HỌC THÁI NGUYÊN ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG ------------------------ NGUYỄN THỊ THOA “PHÂN LỚP QUAN ĐIỂM KHÁCH HÀNG VÀ ỨNG DỤNG” LUẬN VĂN THẠC SỸ THÁI NGUYÊN – 2016 ĐẠI HỌC THÁI NGUYÊN ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG ------------------------- NGUYỄN THỊ THOA “PHÂN LỚP QUAN ĐIỂM KHÁCH HÀNG VÀ ỨNG DỤNG” CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ CHUYÊN NGÀNH: 60.48.01.01 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS ĐOÀN VĂN BAN THÁI NGUYÊN - 2016 MỤC LỤC CHƯƠNG 1 – PHÂN LỚP DỮ LIỆU ........................................................................3 1.1 Giới thiệu về phân lớp dữ liệu ..........................................................................3 1.2 Quá trình phân lớp dữ liệu ...............................................................................4 1.3 Các vấn đề liên quan đến phân lớp dữ liệu ......................................................8 1.3.1 Chuẩn bị dữ liệu cho việc phân lớp .............................................................8 1.3.2 So sánh các mô hình phân lớp .....................................................................9 1.3.3 Các phương pháp đánh giá độ chính xác của mô hình phân lớp ...............10 1.4 Kết luận chương 1 ..........................................................................................11 CHƯƠNG 2 – MỘT SỐ KỸ THUẬT TRONG PHÂN LOẠI VĂN BẢN..............12 2.1 Xử lý văn bản .................................................................................................12 2.1.1 Đặc điểm của từ trong tiếng việt ................................................................12 2.1.2 Tách từ .......................................................................................................13 2.2 Biểu diễn văn bản ...........................................................................................18 2.2.1 Mô hình logic .............................................................................................18 2.2.2 Mô hình phân tích cú pháp ........................................................................19 2.2.3 Mô hình không gian vector ........................................................................20 2.2.4 Mô hình Boolean .......................................................................................22 2.2.5 Mô hình tần suất ........................................................................................23 2.3 Độ tương đồng................................................................................................25 2.3.1 Khái niệm độ tương đồng ..........................................................................25 2.3.2 Độ tương đồng ...........................................................................................26 2.3.3 Các phương pháp tính độ tương đồng .......................................................26 2.4 Các phương pháp phân loại văn bản ..............................................................29 2.4.1 Phương pháp pháp Naïve Bayes (NB) .......................................................29 2.4.2 Phương pháp Support Vector Machine (SVM) .........................................31 2.4.3 Phương pháp K-Nearest Neighbor (K-NN) ...............................................35 2.4.4 Phương pháp Linear Least Square Fit (LLSF) ..........................................37 2.4.5 Phương pháp Centroid – based vector .......................................................38 2.4.6 Kết luận ......................................................................................................38 2.5 Kết luận chương 2 ............................................................................................40 CHƯƠNG 3 – CHƯƠNG TRÌNH THỬ NGHIỆM .................................................41 3.1 Xây dựng mô hình ứng dụng khai phá ý kiến phản hồi của khách hàng trên website dựa trên SVM ...........................................................................................41 3.1.1 Phát biểu bài toán .....................................................................................41 3.1.2 Mô hình ứng dụng khai phá ý kiến phản hồi của khách hàng trên website dựa trên SVM .....................................................................................................41 3.2 Yêu cầu phần cứng và phần mềm ....................................................................44 3.2.1 Cấu hình máy thực nghiệm .......................................................................44 3.2.2 Công cụ và phần mềm sử dụng ................................................................44 3.3 Một số kết quả và đánh giá ..............................................................................45 3.3.1 Kết quả thử nghiệm ..................................................................................45 3.3.2 Đánh giá kết quả .......................................................................................56 3.4 Kết luận chương 3 ............................................................................................57 KẾT LUẬN VÀ ĐỀ NGHỊ .......................................................................................58 DANH MỤC HÌNH ẢNH Hình 1.1 Quy trình phân loại văn bản [3] ........................................................ 4 Hình 1.2 Bước xây dựng mô hình phân lớp - Training..................................... 5 Hình 1.3 Ước lượng độ chính xác của mô hình ................................................ 6 Hình 1.4 Phân lớp dữ liệu mới .......................................................................... 7 Hình 1.5 Ước lượng độ chính xác của mô hình phân lớp bằng phương pháp holdout ............................................................................................................. 10 Hình 2.1 Biểu diễn vector văn bản trong không gian 2 chiều ........................ 21 Hình 2.2 Mô hình SVM [18] ........................................................................... 32 Hình 2.3 Margin - khoảng cách của các điểm tới biên ................................... 32 Hình 2.4 Mô hình SVM trong không gian ...................................................... 33 Hình 2.5 Mô hình thuật toán K-NN ................................................................ 35 Hình 3.1 Sơ đồ xử lý dữ liệu ........................................................................... 41 Hình 3.2 Giao diện Weka ................................................................................ 45 Hình 3.3 Chuyển đổi dữ liệu sang .arff ........................................................... 50 Hình 3.4 vector hóa dữ liệu ............................................................................. 51 Hình 3.5 Giao diện huấn luyện ....................................................................... 55 Hình 3.6 Kết quả huấn luyện........................................................................... 55 DANH MỤC BẢNG BIỂU Bảng 2.1 Biểu diễn văn bản trong mô hình Logic .......................................... 18 Bảng 2.2 Biểu diễn văn bản mô hình Vector .................................................. 21 Bảng 2.3 Biểu diễn văn bản mô hình Boolean................................................ 22 Bảng 3.1 kết quả huấn luyện và kiểm thử ....................................................... 56 1 MỞ ĐẦU I. ĐẶT VẤN ĐỀ Hầu hết các doanh nghiệp đều luôn muốn quan tâm đến ý kiến, phản hồi của khách hàng về sản phẩm, dịch vụ của họ như thế nào. Các đánh giá của khách hàng một mặt giúp cho những người dùng khác định hướng trong việc chọn lựa sản phẩm, mặt khác giúp cho các doanh nghiệp định hướng cải tiến chất lượng. Số lượng đánh giá về một sản phẩm mà chúng ta nhận được ngày càng tăng và có thể đến từ nhiều nguồn khác nhau (web bán hàng, diễn đàn, blog, mạng xã hội ...). Vì vậy, để có thể tổng hợp ý kiến phản hồi của khách hàng về chất lượng, thì phải tự động hóa được công việc thu thập và phân tích đánh giá. Công nghệ phân lớp dữ liệu đã, đang và sẽ phát triển mạnh mẽ trước những khao khát tri thức của con người. Trong những năm qua, phân lớp dữ liệu đã thu hút sự quan tâm các nhà nghiên cứu trong nhiều lĩnh vực khác nhau như học máy (machine learning), hệ chuyên gia (expert system), thống kê (statistics) ... Công nghệ này cũng ứng dụng trong nhiều lĩnh vực thực tế như: thương mại, nhà băng, maketing, nghiên cứu thị trường, bảo hiểm, y tế, giáo dục ... Phân lớp văn bản là bài toán cơ bản trong khai phá quan điểm. Các hệ thống phân lớp văn bản là các hệ thống phải có khả năng xác định, khai phá ra nội dung thông tin. Có thể coi phân lớp quan điểm là bài toán phân lớp văn bản theo hai lớp tích cực và tiêu cực. Do đó tôi chọn đề tài “Đánh giá sản phẩm trên các website thương mại điện tử dựa trên nhận xét của người dùng trên internet” đề tài nghiên cứu một số kỹ thuật phân lớp văn bản như K-means, Naïve Bayes, Maximum entropy và SVM để sử dụng trong phương pháp học máy phân lớp quan điểm khách hàng. 2 II. ĐỐI TƯỢNG VÀ PHẠM VI NGHIÊN CỨU  Đối tượng nghiên cứu: Các kỹ thuật phân lớp văn bản và ứng dụng để phân lớp quan điểm khách hàng đưa vào các website TMĐT bán hàng trực tuyến với số lượng truy cập và giao dịch lớn.  Phạm vi nghiên cứu Nghiên cứu các tài liệu bài viết trong và ngoài nước về kỹ thuật phân lớp dữ liệu để xây dựng phát triển bài toán “Phân lớp quan điểm khách hàng và ứng dụng” hiệu quả trong công việc phân tích, khai thác các nguồn ý kiến khách hàng. III. HƯỚNG NGHIÊN CỨU CỦA ĐỀ TÀI - Đề tài sẽ kết hợp phương pháp nghiên cứu lý thuyết với kết quả thực nghiệm. - Phân tích các tài liệu và thông tin liên quan. - Mô phỏng và thử nghiệm. IV. PHƯƠNG PHÁP NGHIÊN CỨU Nghiên cứu lý thuyết dựa trên các tài liệu về phân lớp dữ liệu, các thuật toán, phương pháp phân lớp … của các tác giả trong và ngoài nước. Thực nghiệm dựa trên các website TMĐT để xây dựng, đánh giá phương pháp. 3 CHƯƠNG 1 – PHÂN LỚP DỮ LIỆU 1.1 Giới thiệu về phân lớp dữ liệu Bài toán phân lớp quan điểm Là quá trình phân lớp một đối tượng dữ liệu vào một hay nhiều lớp cho trước nhờ một mô hình phân lớp mà mô hình này được xây dựng dựa trên một tập hợp các đối tượng dữ liệu đã được gán nhãn từ trước gọi là tập dữ liệu học (tập huấn luyện). Quá trình phân lớp còn được gọi là quá trình gán nhãn cho các đối tượng dữ liệu [5][3]. Như vậy, nhiệm vụ của bài toán phân lớp dữ liệu là cần xây dựng mô hình (bộ) phân lớp để khi có một dữ liệu mới vào thì mô hình phân lớp sẽ cho biết dữ liệu đó thuộc lớp nào. Có nhiều bài toán phân lớp dữ liệu, như phân lớp nhị phân, phân lớp đa lớp, phân lớp đa trị,…. Phân lớp nhị phân là quá trình tiến hành việc phân lớp dữ liệu vào một trong hai lớp khác nhau dựa vào việc dữ liệu đó có hay không một số đặc tính theo quy định của bộ phân lớp. Phân lớp đa lớp là quá trình phân lớp với số lượng lớp lớn hơn hai. Như vậy, tập hợp dữ liệu trong miền xem xét được phân chia thành nhiều lớp chứ không đơn thuần chỉ là hai lớp như trong bài toán phân lớp nhị phân. Về bản chất, bài toán phân lớp nhị phân là trường hợp riêng của bài toán phân lớp đa lớp. Trong phân lớp đa trị, mỗi đối tượng dữ liệu trong tập huấn luyện cũng như các đối tượng mới sau khi được phân lớp có thể thuộc vào từ hai lớp trở lên. Ví dụ như trang web về việc bùng phát bệnh cúm gia cầm, thủy cầm tại một số tính phía Bắc vừa thuộc về lĩnh vực y tế liên quan đến lây bệnh sang người nhưng cũng thuộc về lĩnh vực kinh tế liên quan đến ngành chăn nuôi… 4 Trong những trường hợp như vậy, việc sắp xếp một tài liệu vào nhiều hơn một lớp là phù hợp với yêu cầu thực tế. 1.2 Quá trình phân lớp dữ liệu Huấn luyện Kiểm tra Nhãn Tệp đầu vào Tập dữ liệu Học Tệp trích rút máy Tệp trích rút Phân lớp Kết quả Hình 1.1 Quy trình phân loại văn bản [3] Quá trình phân lớp dữ liệu thường gồm hai bước: xây dựng mô hình (tạo bộ phân lớp) và sử dụng mô hình đó để phân lớp dữ liệu. Bước 1 Bước xây dựng mô hình phân lớp (Training) Một mô hình sẽ được xây dựng dựa trên việc phân tích các đối tượng dữ liệu đã được gán nhãn từ trước. Tập các mẫu dữ liệu này còn được gọi là tập dữ liệu huấn luyện (training data set). Các nhãn lớp của tập dữ liệu huấn luyện được xác định bởi con người trước khi xây dựng mô hình, vì vậy phương pháp này còn được gọi là học có giám sát (supervised learning). Trong bước này, chúng ta còn phải tính độ chính xác của mô hình, mà cần phải sử dụng một tập dữ liệu kiểm tra (test data set). Nếu độ chính xác là chấp nhận được (tức là cao), mô hình sẽ được sử dụng để xác định nhãn lớp cho các dữ liệu khác mới trong tương lai. Trong việc test mô hình, sử dụng các độ đo để đánh giá chất 5 lượng của tập phân lớp, đó là độ hồi tưởng, độ chính xác, độ đo F1 ... Nội dung chi tiết về các độ đo này được trình bày trong mục. Tồn tại nhiều phương pháp phân lớp dữ liệu để giải quyết bài toán phân lớp tùy thuộc vào cách thức xây dựng mô hình phân lớp như phương pháp Bayes, phương pháp cây quyết định, phương pháp k-người láng giềng gần nhất, phương pháp máy hỗ trợ vector .... Các phương pháp phân lớp khác nhau chủ yếu về mô hình phân lớp. Mô hình phân lớp còn được gọi là thuật toán phân lớp. Thuật toán phân lớp Dữ liệu huấn luyện Tuổi 20 18 40 50 35 30 30 40 Xe Combi Sports Sports Family Minivan Combi Family Combi Giàu Cao Cao Cao thấp thấp cao thấp thấp Phân lớp Nếu tuổi < 31 hoặc Xe = sport thì Giàu = cao Hình 1.2 Bước xây dựng mô hình phân lớp - Training Bước 2 Phân lớp (classification) Bước thứ hai dùng mô hình đã xây dựng ở bước trước để phân lớp dữ liệu mới. Trước tiên độ chính xác mang tính chất dự đoán của mô hình phân lớp vừa tạo ra được ước lượng. Holdout là một kỹ thuật đơn giản để ước lượng độ chính xác đó. Kỹ thuật này sử dụng một tập dữ liệu kiểm tra với các mẫu đã được gán nhãn lớp. Các mẫu này được chọn ngẫu nhiên và độc lập với các mẫu trong tập dữ liệu đào tạo. Độ chính xác của mô hình trên tập dữ liệu kiểm tra 6 đã đưa là tỉ lệ phần trăm các các mẫu trong tập dữ liệu kiểm tra được mô hình phân lớp đúng (so với thực tế). Nếu độ chính xác của mô hình được ước lượng dựa trên tập dữ liệu đào tạo thì kết quả thu được là rất khả quan vì mô hình luôn có xu hướng “quá vừa” dữ liệu. Quá vừa dữ liệu là hiện tượng kết quả phân lớp trùng khít với dữ liệu thực tế vì quá trình xây dựng mô hình phân lớp từ tập dữ liệu đào tạo có thể đã kết hợp những đặc điểm riêng biệt của tập dữ liệu đó. Do vậy cần sử dụng một tập dữ liệu kiểm tra độc lập với tập dữ liệu đào tạo. Nếu độ chính xác của mô hình là chấp nhận được, thì mô hình được sử dụng để phân lớp những dữ liệu tương lai, hoặc những dữ liệu mà giá trị của thuộc tính phân lớp là chưa biết. Phân lớp Dữ liệu huấn luyện Tuổi Xe Giàu 27 Sports Cao 34 Family thấp 66 Family Cao 44 Sports Cao Giàu Cao thấp thấp cao Hình 1.3 Ước lượng độ chính xác của mô hình 7 Phân lớp Dữ liệu mới Tuổi Xe 27 Sports 34 Minivan 55 Family 34 Sports Giàu Giàu Cao thấp thấp cao Hình 1.4 Phân lớp dữ liệu mới Trong mô hình phân lớp, thuật toán phân lớp giữ vai trò trung tâm, quyết định tới sự thành công của mô hình phân lớp. Do vậy chìa khóa của vấn đề phân lớp dữ liệu là tìm ra được một thuật toán phân lớp nhanh, hiệu quả, có độ chính xác cao và có khả năng mở rộng được. Trong đó khả năng mở rộng được của thuật toán được đặc biệt trú trọng và phát triển. Có thể liệt kê ra đây các kỹ thuật phân lớp đã được sử dụng trong những năm qua:  Phân lớp cây quyết định (Decision tree classification)  Bộ phân lớp Bayesian (Bayesian classifier)  Mô hình phân lớp K-hàng xóm gần nhất (K-nearest neighbor classifier)  Mạng nơron  Phân tích thống kê  Các thuật toán di truyền  Phương pháp tập thô (Rough set Approach) 8 1.3 Các vấn đề liên quan đến phân lớp dữ liệu 1.3.1 Chuẩn bị dữ liệu cho việc phân lớp Việc tiền xử lý dữ liệu cho quá trình phân lớp là một việc làm không thể thiếu và có vai trò quan trọng quyết định tới sự áp dụng được hay không của mô hình phân lớp. Quá trình tiền xử lý dữ liệu sẽ giúp cải thiện độ chính xác, tính hiệu quả và khả năng mở rộng được của mô hình phân lớp. Quá trình tiền xử lý dữ liệu gồm có các công việc sau: i. Làm sạch dữ liệu Làm sạch dữ liệu liên quan đến việc xử lý với lỗi (noise) và giá trị thiếu (missing value) trong tập dữ liệu ban đầu. Noise là các lỗi ngẫu nhiên hay các giá trị không hợp lệ của các biến trong tập dữ liệu. Để xử lý với loại lỗi này có thể dùng kỹ thuật làm trơn. Missing value là những ô không có giá trị của các thuộc tính. Giá trị thiếu có thể do lỗi chủ quan trong quá trình nhập liệu, hoặc trong trường hợp cụ thể giá trị của thuộc tính đó không có, hay không quan trọng. Kỹ thuật xử lý ở đây có thể bằng cách thay giá trị thiếu bằng giá trị phổ biến nhất của thuộc tính đó hoặc bằng giá trị có thể xảy ra nhất dựa trên thống kê. Mặc dù phần lớn thuật toán phân lớp đều có cơ chế xử lý với những giá trị thiếu và lỗi trong tập dữ liệu, nhưng bước tiền xử lý này có thể làm giảm sự hỗn độn trong quá trình học (xây dựng mô hình phân lớp). ii. Phân tích sự cần thiết của dữ liệu Có rất nhiều thuộc tính trong tập dữ liệu có thể hoàn toàn không cần thiết hay liên quan đến một bài toán phân lớp cụ thể. Ví dụ dữ liệu về ngày trong tuần hoàn toàn không cần thiết đối với ứng dụng phân tích độ rủi ro của các khoản tiền cho vay của ngân hàng, nên thuộc tính này là dư thừa. Phân tích sự cần thiết của dữ liệu nhằm mục đích loại bỏ những thuộc tính không cần thiết, dư thừa khỏi quá trình học vì những thuộc tính đó sẽ làm chậm, phức tạp và 9 gây ra sự hiểu sai trong quá trình học dẫn tới một mô hình phân lớp không dùng được. iii. Chuyển đổi dữ liệu Việc khái quát hóa dữ liệu lên mức khái niệm cao hơn đôi khi là cần thiết trong quá trình tiền xử lý. Việc này đặc biệt hữu ích với những thuộc tính liên tục (continuous attribute hay numeric attribute). Ví dụ các giá trị số của thuộc tính thu nhập của khách hàng có thể được khái quát hóa thành các dãy giá trị rời rạc: thấp, trung bình, cao. Tương tự với những thuộc tính rời rạc (categorical attribute) như địa chỉ phố có thể được khái quát hóa lên thành thành phố. Việc khái quát hóa làm cô đọng dữ liệu học nguyên thủy, vì vậy các thao tác vào/ ra liên quan đến quá trình học sẽ giảm. 1.3.2 So sánh các mô hình phân lớp Trong từng ứng dụng cụ thể cần lựa chọn mô hình phân lớp phù hợp. Việc lựa chọn đó căn cứ vào sự so sánh các mô hình phân lớp với nhau, dựa trên các tiêu chuẩn sau: 1/ Độ chính xác dự đoán (predictive accuracy) Độ chính xác là khả năng của mô hình để dự đoán chính xác nhãn lớp của dữ liệu mới hay dữ liệu chưa biết. 2/ Tốc độ (speed) Tốc độ là những chi phí tính toán liên quan đến quá trình tạo ra và sử dụng mô hình. 3/ Sức mạnh (robustness) Sức mạnh là khả năng mô hình tạo ta những dự đoán đúng từ những dữ liệu noise hay dữ liệu với những giá trị thiếu. 4/ Khả năng mở rộng (scalability) Khả năng mở rộng là khả năng thực thi hiệu quả trên lượng lớn dữ liệu của mô hình đã học. 10 5/ Tính hiểu được (interpretability) Tính hiểu được là mức độ hiểu và hiểu rõ những kết quả sinh ra bởi mô hình đã học. 6/ Tính đơn giản (simplicity) Tính đơn giản liên quan đến kích thước của cây quyết định hay độ cô đọng của các luật. 1.3.3 Các phương pháp đánh giá độ chính xác của mô hình phân lớp Ước lượng độ chính xác của bộ phân lớp là quan trọng ở chỗ nó cho phép dự đoán được độ chính xác của các kết quả phân lớp những dữ liệu tương lai. Độ chính xác còn giúp so sánh các mô hình phân lớp khác nhau. Khóa luận này đề cập đến hai phương pháp đánh giá phổ biến là holdout và k-fold kiểm tra chéo. Cả hai kỹ thuật này đều dựa trên các phân hoạch ngẫu nhiên tập dữ liệu ban đầu. Trong phương pháp holdout, dữ liệu dưa ra được phân chia ngẫu nhiên thành hai phần là: tập dữ liệu đào tạo và tập dữ liệu kiểm tra. Thông thường 2/3 dữ liệu cấp cho tập dữ liệu đào tạo, phần còn lại cho tập dữ liệu kiểm tra. Tệp huấn luyện Mô hình phân lớp Độ chính xác phân loại Dữ liệu Tệp kiểm tra Hình 1.5 Ước lượng độ chính xác của mô hình phân lớp bằng phương pháp holdout 11 Trong phương pháp k-fold xác nhận chéo tập dữ liệu ban đầu được chia ngẫu nhiên thành k tập con (fold) có kích thước xấp xỉ nhau S1, S2, …, Sk. Quá trình học và test được thực hiện k lần. Tại lần lặp thứ i, Si là tập dữ liệu kiểm tra, các tập còn lại hợp thành tập dữ liệu đào tạo. Có nghĩa là, đâu tiên việc dạy được thực hiện trên các tập S2, S3, …, sau đó test trên tập S1; tiếp tục quá trình dạy được thực hiện trên tập S1, S3, S4, …, sau đó test trên tập S2; và cứ thế tiếp tục. Độ chính xác là toàn bộ số phân lớp đúng từ k lần lặp chia cho tổng số mẫu của tập dữ liệu ban đầu. 1.4 Kết luận chương 1 Trong chương I đã trình bày về bài toán phân lớp quan điểm, mô hình phân lớp dữ liệu và quá trình phân lớp dữ liệu. Đồng thời cũng đưa ra các vấn đề trong phân lớp dữ liệu như chuẩn bị dữ liệu trước khi phân lớp, giới thiệu một số tiêu chí so sánh và đánh giá độ chính xác của các thuật toán phân lớp dữ liệu. 12 CHƯƠNG 2 – MỘT SỐ KỸ THUẬT TRONG PHÂN LOẠI VĂN BẢN 2.1 Xử lý văn bản 2.1.1 Đặc điểm của từ trong tiếng việt Tiếng Việt là ngôn ngữ đơn lập [3][11]. Đặc điểm này bao quát tiếng Việt cả về mặt ngữ âm, ngữ nghĩa, ngữ pháp. Khác với các ngôn ngữ châu Âu, mỗi từ là một nhóm các ký tự có nghĩa được cách nhau bởi một khoảng trắng. Còn tiếng Việt, và các ngôn ngữ đơn lập khác, thì khoảng trắng không phải là căn cứ để nhận diện từ. Tiếng:  Trong tiếng Việt trước hết cần chú ý đến đơn vị xưa nay vẫn quan gọi là tiếng. Về mặt ngữ nghĩa, ngữ âm, ngữ pháp, đều có giá trị quan trọng.  Sử dụng tiếng để tạo từ có hai trường hợp:  Trường hợp một tiếng: đây là trường hợp một tiếng được dùng làm một từ, gọi là từ đơn. Tuy nhiên không phải tiếng nào cũng tạo thành một từ.  Trường hợp hai tiếng trở lên: đây là trường hợp hai hay nhiều tiếng kết hợp với nhau, cả khối kết hợp với nhau gắn bó tương đối chặt chẽ, mới có tư cách ngữ pháp là một từ. Đây là trường hợp từ ghép hay từ phức. Từ: Có rất nhiều quan niệm về từ trong tiếng Việt, từ nhiều quan niệm về từ tiếng Việt khác nhau đó chúng ta có thể thấy đặc trưng cơ bản của "từ" là sự hoàn chỉnh về mặt nội dung, từ là đơn vị nhỏ nhất để đặt câu. Người ta dùng "từ" kết hợp thành câu chứ không phải dùng "tiếng", do đó quá trình tách câu thành các "từ" cho kết quả tốt hơn là tách câu bằng “tiếng”. 13 2.1.2 Tách từ 2.1.2.1 Phương pháp Maximum Matching: Forward / Backward Phương pháp so khớp tối đa (MM-Maximum Matching) hay còn gọi là LRMM - Left Right Maximum Matching. Ở phương pháp này, chúng ta sẽ duyệt một ngữ hoặc câu từ trái sang phải và chọn từ có nhiều âm tiết nhất có mặt trong từ điển và cứ thực hiện lặp lại như vậy cho đến hết câu. Dạng đơn giản của phương pháp dùng để giải quyết nhập nhằng từ đơn. Giả sử chúng ta có một chuỗi ký tự C1, C2, …, Cn. Chúng ta sẽ áp dụng phương pháp từ đầu chuỗi. Đầu tiên kiểm tra xem C1 có phải là từ hay không, sau đó kiểm tra xem C1C2 có phải là từ hay không. Tiếp tục thực hiện như thế cho đến khi tìm được từ dài nhất . Dạng phức tạp: Quy tắc của dạng này là phân đoạn từ. Thông thường người ta chọn phân đoạn ba từ có chiều dài tối đa. Thuật toán bắt đầu từ dạng đơn giản, cụ thể là nếu phát hiện ra những cách tách từ gây nhập nhằng, như ở ví dụ trên, giả sử C1 là từ và C1C2 cũng là một từ, khi đó chúng ta kiểm tra ký tự kế tiếp trong chuỗi C1, C2, ..., Cn để tìm tất cả các đoạn ba từ có bắt đầu với C1 hoặc C1C2. Ví dụ : Giả sử chúng ta có được các đoạn sau: - C1 C2 C3 C4 - C1C2 C3C4 C5 - C1C2 C3C4 C5C6 Khi đó chuỗi dài nhất sẽ là chuỗi thứ ba. Do đó từ đầu tiên của chuỗi thứ ba (C1C2) sẽ được chọn. Thực hiện các bước cho đến khi được chuỗi từ hoàn chỉnh. Nhận xét : Phương pháp này thực hiện tách từ đơn giản, nhanh và chỉ cần dựa vào từ điển để thực hiện. Tuy nhiên, khuyết điểm của phương pháp này cũng chính 14 là từ điển, nghĩa là độ chính xác khi thực hiện tách từ phụ thuộc hoàn toàn vào tính đủ, tính chính xác của từ điển. 2.1.2.2 Phương pháp Transformation – based Learning (TBL) Phương pháp này tiếp cận dựa trên tập ngữ liệu đã đánh dấu. Theo cách tiếp cận này để cho máy tính có thể nhận biết ranh giới giữa các từ để có thể tách từ chính xác, chúng ta sẽ cho máy học các câu mẫu trong tập ngữ liệu đã được đánh dấu ranh giới giữa các từ đúng. Chúng ta thấy phương pháp rất đơn giản, vì chỉ cần cho máy học các tập câu mẫu và sau đó máy sẽ tự rút ra qui luật của ngôn ngữ và để từ đó sẽ áp dụng chính xác khi có những câu đúng theo luật mà máy đã rút ra. Và để tách từ được hoàn toàn chính xác trong mọi trường hợp thì đòi hỏi phải có một tập ngữ liệu tiếng Việt thật đầy đủ và phải được huấn luyện lâu để có thể rút ra các luật đầy đủ. 2.1.2.3 Mô hình tách từ bằng WFST và mạng Neural Mô hình mạng chuyển dịch trạng thái hữu hạn có trọng số Weighted Finit State Transducer (WFST) đã được áp dụng trong tách từ từ năm 1996 [13]. Ý tưởng cơ bản là áp dụng WFST với trọng số là xác suất xuất hiện của mỗi từ trong kho ngữ liệu. Dùng WFST để duyệt qua các câu cần xét, khi đó từ có trọng số lớn nhất là từ được chọn để tách. Phương pháp này cũng đã được sử dụng trong công trình đã được công bố của tác giả Đình Điền năm 2001, tác giả đã sử dụng WFST kèm với mạng Neural để khử nhập nhằng khi tách từ, trong công trình tác giả đã xây dựng hệ thống tách từ gồm tầng WFST để tách từ và xử lý các vấn đề liên quan đến một số đặc thù riêng của ngôn ngữ tiếng Việt như từ láy, tên riêng, ... và tầng mạng Neural dùng để khử nhập nhằng về ngữ nghĩa sau khi đã tách từ (nếu có). Chi tiết về hai tầng này như sau: a. Tầng WFST gồm có 3 bước 15 Bước 1: Xây dựng từ điển trọng số: theo mô hình WFST, thao tác phân đoạn từ được xem như là một sự chuyển dịch trạng thái có xác suất. Chúng ta miêu tả từ điển D là một đồ thị biến đổi trạng thái hữu hạn có trọng số. Giả sử:  H là tập các từ chính tả tiếng Việt (còn gọi là “tiếng”) - P là từ loại của từ .  Mỗi cung của D có thể là: - Từ một phần tử của H tới một hần tử của H - Các nhãn trong D biểu diễn một chi phí được ước lượng theo công thức: Cost = -log(f/N) Trong đó: f là tần số của từ, N là kích thước tập mẫu. Bước 2: Xây dựng các khả năng phân đoạn từ: Để giảm sự bùng nổ tổ hợp khi sinh ra dãy các từ có thể từ một dãy các tiếng trong câu, tác giả đã đề xuất phương pháp kết hợp dùng thêm từ điển để hạn chế sinh ra các bùng nổ tổ hợp, cụ thể là nếu phát hiện thấy một cách phân đoạn từ nào đó không phù hợp (không có trong từ điển, không có phải là tứ láy, không phải là danh từ riêng,…) thì tác giả loại bỏ các nhánh xuất phát từ cách phân đoạn đoạn đó. Bước 3: Lựa chọn khả năng phân đoạn từ tối ưu: Sau khi có được danh sách các cách phân đoạn từ có thể có của câu, tác giả đã chọn trường hợp phân đoạn từ có trọng số bé nhất. b. Tầng mạng Neural Mô hình được sử dụng để khử nhập nhằng khi tách từ bằng cách kết hợp so sánh với từ điển. Nhận xét: Mô hình này đạt được độ chính xác trên 97% theo như công bố trong công trình của tác giả, bằng việc sử dụng thêm mạng Neural kết hợp với từ điển để khử các nhập nhằng có thể có khi tách ra các được nhiều từ từ