Tài liệu Khai thác dữ liệu văn bản trên thiết bị di động sử dụng các dịch vụ đám

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG ──────── * ─────── LUẬN VĂN TỐT NGHIỆP THẠC SĨ NGÀNH KỸ THUẬT PHẦN MỀM ĐỀ TÀI: KHAI PHÁ DỮ LIỆU VĂN BẢN TRÊN THIẾT BỊ DI ĐỘNG SỬ DỤNG CÁC DỊCH VỤ ĐÁM MÂY HỌC VIÊN THỰC HIỆN : NGUYỄN THỊ THÚY HẰNG LỚP : 2014B-KTPM SỐ HIỆU HỌC VIÊN : CB140147 GIẢNG VIÊN HƯỚNG DẪN : PGS.TS. CAO TUẤN DŨNG HÀ NỘI 11-2017 MỤC LỤC LỜI CAM ĐOAN ……………………………………………………….4 DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ ……………...6 DANH MỤC CÁC HÌNH ẢNH …………………………………..7 DANH MỤC CÁC BẢNG BIỂU …………………………………..8 CHƯƠNG 1: KHAI PHÁ DỮ LIỆU …………………………………11 1.1. Khái niệm về khai phá dữ liệu …………………………..11 1.2. Quy trình khai phá dữ liệu …………………………………13 1.3. Các kỹ thuật khai phá dữ liệu …………………………..16 1.4. Các công cụ khai phá dữ liệu …………………………..22 CHƯƠNG 2: ĐIỆN TOÁN ĐÁM MÂY …………………………..25 2.1. Sự ra đời của điện toán đám mây …………………………..25 2.2. Kiến trúc mô hình điện toán đám mây 2.3. Các dịch vụ điện toán đám mây …………………...28 …………………………..28 2.4. Các mô hình triển khai điện toán đám mây …………….34 2.5. Khai phá dữ liệu trong điện toán đám mây …………….35 CHƯƠNG 3: KHAI THÁC Ý KIẾN VÀ PHÂN TÍCH CẢM XÚC 3.1. Định nghĩa .38 ……………………………………………….38 3.2 Các định nghĩa liên quan …………………………………40 3.3. Các tác vụ của phân tích cảm xúc …………………………..42 3.4. Các cấp phân tích khác nhau …………………………..44 3.5. Bài toán phân lớp cảm xúc …………………………………45 CHƯƠNG 4: CÔNG CỤ PHÂN TÍCH Ý KIẾN, CẢM XÚC CỦA KHÁCH HÀNG TRÊN THIẾT BỊ DI ĐỘNG …………………..57 4.1. Hoàn cảnh ra đời ………...……………………………...57 4.2. Bài toán phản hồi của khách hàng …………………………..58 4.3. Chức năng của công cụ …………………………………59 4.4. Kết quả xây dựng hệ thống …………………………………64 4.5. Đánh giá ưu điểm, nhược điểm của hệ thống …………….77 Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 2 CHƯƠNG 5: KẾT LUẬN VÀ ĐỀ XUẤT 5.1. Hệ thống …………………………..78 ……………………………………………………...78 5.1.1. Đánh giá chung ………………………………………..78 5.1.2. Công việc đã làm được …………………………………78 5.1.3. Những vấn đề chưa giải quyết …………………………..78 5.1.4. Định hướng phát triển đề tài …………………………..79 5.2. Công cụ sử dụng ……………………………………………….79 5.2.1. Đánh giá chung ………………………………………..79 5.2.2. Khả năng áp dụng ………………………………………..79 TÀI LIỆU THAM KHẢO ………………………………………..81 Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 3 LỜI CAM ĐOAN Tôi xin cam đoan: 1. Những nội dung trong luận văn này là công trình nghiên cứu của tôi dưới sự hướng dẫn trực tiếp của TS. Cao Tuấn Dũng. 2. Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng tên tác giả, tên công trình, thời gian, địa điểm công bố. 3. Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. 4. Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi xin chịu hoàn toàn trách nhiệm. Hà Nô ̣i, ngày 15 tháng 10 năm 2017 Tác giả luâ ̣n văn Nguyễn Thị Thúy Hằng Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 4 LỜI CẢM ƠN Trong quá trình học tập, nghiên cứu và thực hiện luận văn thạc sỹ, tôi đã nhận được nhiều sự hỗ trợ, đóng góp nhiệt tình của các cá nhân và tổ chức tạo điều kiện cho tôi hoàn thành luận văn này. Qua đây tôi cũng xin gửi lời cảm ơn chân thành, sâu sắc tới các cá nhân và tập thể đã giúp đỡ tôi trong thời gian vừa qua. Trước hết, tôi xin chân thành cảm ơn thầy giáo PGS.TS Cao Tuấn Dũng, Viện Công Nghệ Thông Tin, Trường Đại Học Bách Khoa Hà Nội là người đã trực tiếp hướng dẫn, nhận xét và giúp đỡ tôi trong suốt quá trình thực hiện luận văn này. Tôi xin chân thành cảm ơn các thầy cô trong Viện Công Nghệ Thông Tin, các thầy cô trong Viện Đào Tạo Sau Đại Học đã giúp đỡ, tạo điều kiện và hướng dẫn tôi trong suốt thời gian học tập tại trường. Cuối cùng, tôi xin chân thành cảm ơn gia đình, bạn bè và đồng nghiệp, những người đã gắn bó cùng tôi trong suốt thời gian học tập và thực hiện luận văn và tạo điều kiện cho tôi thực hiện tốt luận văn này. Do thời gian thực hiện có hạn và hạn chế về kiến thức chuyên ngành nên luận văn của tôi còn nhiều thiếu sót. Mong nhận được các ý kiến đóng góp của các thầy cô để luận văn của tôi được hoàn thiện hơn. Tôi xin chân thành cảm ơn! Hà Nội, ngày 01 tháng 11 năm 2017 Học viên Nguyễn Thị Thúy Hằng Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 5 DANH MỤC CÁC TỪ VIẾT TẮT VÀ THUẬT NGỮ STT 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Ý nghĩa Cross-Industry Standard Process (Quy trình xử lý dữ liệu công nghiệp chuẩn) SEMMA Sample, Explore, Modify, Model, and Assess CRISPCross-Industry Standard Process for Data Mining DM (Quy trình xử lý dữ liệu công nghiệp chuẩn cho khai phá dữ liệu) ANN Artificial Neural Networks (Mạng nơ ron nhân tạo) SAS Statistical Analysis System (Hệ thống phân tích thống kê) PE Processing Element (Yếu tố xử lý) IaaS Infrastructure as a Service (Dịch vụ cơ sở hạ tầng) PaaS Platform as a Service (Dịch vụ nền tảng) SaaS Software as a Service (Dịch vụ phần mềm) ASP Application Service Provider (Nhà cung cấp dịch vụ ứng dụng) EC2 Elastic Compute Cloud (Đám mây tính toán đàn hồi) SLA Service-Level Agreement (Thỏa thuận mức dịch vụ) NER Named Entity Recognition (Nhận dạng tên thực thể) POS Part of Speech (Từ loại) SVM Support Vector Machine (Máy vector hỗ trợ) HMM Hidden Markov Model (Mô hình Markov ẩn) CRF Conditional random Fields (Trường điều kiện ngẫu nhiên) pLSA Probabilistic Latent Semantic Analysis (Phân tích xác suất ngữ nghĩa tiềm ẩn) LDA Latent Dirichlet allocation (Phân bổ Dirichlet tiềm ẩn) Amazon S3 Amazon Simple Storage Service (Dịch vụ lưu trữ của Amazon) Từ viết tắt CRISP Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 6 DANH MỤC CÁC HÌNH ẢNH Hình 1: Quy trình khai phá dữ liệu ...................................................................... 14 Hình 2: Mạng nơ ron nhân tạo ............................................................................. 16 Hình 3: Kỹ thuật học có giám sát trong mạng nơ ron nhân tạo ........................... 17 Hình 4: Kỹ thuật học không giám sát trong mạng nơ ron nhân tạo ..................... 18 Hình 5: Kỹ thuật học tăng cường trong mạng nơ ron nhân tạo ........................... 18 Hình 6: Mô hình mạng nơ ron đơn giản .............................................................. 19 Hình 7: Entropy .................................................................................................... 20 Hình 8: Điện toán lưới ......................................................................................... 26 Hình 9: Điện toán theo yêu cầu ............................................................................ 27 Hình 10: Điện toán tự trị ...................................................................................... 27 Hình 11: Kiến trúc điện toán đám mây ................................................................ 28 Hình 12: Dịch vụ cơ sở hạ tầng............................................................................ 29 Hình 13: Dịch vụ nền tảng ................................................................................... 31 Hình 14: Dịch vụ phần mềm ................................................................................ 32 Hình 15: Mô hình của hệ thống phân tích cảm xúc khách hàng.......................... 63 Hình 16: Các chức năng chính của hệ thống ....................................................... 64 Hình 17: Chức năng thu thập dữ liệu ................................................................... 65 Hình 18: Chức năng trích xuất thực thể ............................................................... 66 Hình 19: Chức năng phân tích cảm xúc ............................................................... 68 Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 7 DANH MỤC CÁC BẢNG BIỂU Bảng 1: Đánh giá kết quả của hệ thống. .................................................... 73 Bảng 2: So sánh kết quả giữa dịch vụ của Google và IBM. ...................... 76 Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 8 LỜI MỞ ĐẦU Trong hoàn cảnh ngành công nghệ thông tin phát triển mạnh mẽ như hiện nay, các thiết bị thông tin trở thành một phần quan trọng trong đời sống cũng như giao tiếp của con người. Việc sử dụng rộng rãi các thiết bị thông tin trong đời sống và giao tiếp khiến cho lượng dữ liệu mà con người tạo ra ngày càng lớn. Với lượng dữ liệu khổng lồ đó, việc tìm kiếm thông tin trở nên khó khăn hơn. Vì vậy nhu cầu của việc khai phá dữ liệu để trích xuất được các thông tin hữu ích của người dùng từ một lượng dữ liệu khổng lồ là vô cùng cần thiết. Khai phá dữ liệu là một khái niệm trong đó bao gồm nhiều lĩnh vực khác nhau, khai thác ý kiến và phân tích cảm xúc là một trong số các lĩnh vực của khai phá dữ liệu. Việc khai thác ý kiến và phân tích cảm xúc đã được nghiên cứu và triển khai trên máy tính bởi một số các doanh nghiệp nhằm mục đích thu thập phản hồi từ khách hàng. Tuy nhiên, việc triển khai trên thiết bị di động còn gặp khó khăn do hạn chế về tài nguyên của thiết bị di động. Với sự phát triển công nghệ như hiện nay, việc triển khai khai thác ý kiến và phân tích cảm xúc trên thiết bị di động trở nên dễ dàng hơn dưới sự hỗ trợ của các dịch vụ đám mây. Do đó, sau thời gian nghiên cứu, em đã được nhận đề tài luận văn tốt nghiệp rất thực tế đó là: “Khai phá dữ liệu văn bản trên thiết bị di động sử dụng các dịch vụ đám mây” Lĩnh vực khai phá dữ liệu là một lĩnh vực rộng lớn và phức tạp, do giới hạn về thời gian và năng lực nên em xin tập trung vào bài toán khai thác ý kiến và phân tích cảm xúc trong khai phá dữ liệu văn bản. Luận văn đề xuất phương pháp khai phá dữ liệu sử dụng dịch vụ đám mây áp dụng cho các thiết bị di động nhằm khắc phục các hạn chế về bộ nhớ và tài nguyên. Để tiện theo dõi em xin trình bày đề tài theo 5 phần chính như sau: - Phần đầu là giới thiệu tổng quan về khai phá dữ liệu - Phần thứ hai là giới thiệu lý thuyết điện toán đám mây - Phần thứ ba là giới thiệu lý thuyết của khai thác ý kiến và phân tích cảm xúc - Phần thứ tư bao gồm bài toán đề xuất, cơ sở xây dựng và kết quả đạt được Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 9 - Phần cuối cùng là kết luận sau khi làm luận văn và định hướng phát triển Trong quá trình thực hiện, tuy được sự giúp đỡ nhiệt tình của thầy PGS.TS Cao Tuấn Dũng là giảng viên Viện công nghệ thông tin và truyền thông – giáo viên hướng dẫn nhưng với trình độ, thời gian có hạn, tài liệu tham khảo hạn chế nên có thể có nhiều thiếu sót, rất mong được các thầy cô và bạn bè góp ý để luận văn của em được tốt hơn. Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 10 CHƯƠNG 1: KHAI PHÁ DỮ LIỆU 1.1. Khái niệm về khai phá dữ liệu 1.1.1. Tiền đề cho sự phát triển của khai phá dữ liệu Khai phá dữ liệu đã thu hút rất nhiều sự chú ý trong ngành công nghệ thông tin và trong xã hội những năm gần đây, do số lượng dữ liệu khổng lồ trên nhiều lĩnh vực, yêu cầu cấp thiết là chuyển đổi những dữ liệu đó thành các thông tin hay tri thức hữu ích. Những thông tin và tri thức đó có thể được sử dụng trong các ứng dụng từ phân tích thị trường, phát hiện lỗi đến điều khiển sản xuất và trong các ngành khoa học. Khai phá dữ liệu có thể được xem như một kết quả của sự phát triển tự nhiên của ngành công nghệ thông tin. Chuỗi chức năng chính trong ngành công nghệ thông tin hiện nay: tổng hợp dữ liệu và kiến tạo cơ sở dữ liệu, quản lý dữ liệu (bao gồm nhận và lưu trữ dữ liệu, cơ sở dữ liệu cho xử lý các giao dịch), và phân tích dữ liệu nâng cao (bao gồm lưu trữ dữ liệu và khai phá dữ liệu). Ví dụ: sự phát triển của cơ chế tổng hợp dữ liệu và kiến tạo cơ sở dữ liệu có vai trò như một yêu cầu cho sự phát triển của cơ chế hiệu năng cho việc nhận và lưu trữ dữ liệu, xử lý truy vấn, giao dịch. Với nhiều hệ thống cơ sở dữ liệu cho phép xử lý truy vấn và giao dịch. Phân tích dữ liệu nâng cao là bước tiếp theo quá trình xử lý và truy vấn. Sự phát triển của công nghệ phần cứng máy tính trong vài thập niên gần đây đã tạo ra những máy tính, thiết bị tổng hợp dữ liệu, thiết bị lưu trữ đa phương tiện mạnh mẽ. Điều này cung cấp một lợi thế lớn cho công nghệ thông tin, tạo ra một số lượng lớn các kho dữ liệu và thông tin có sẵn cho quản lý ứng dụng. Sự phong phú của dữ liệu cũng đi đôi với nhu cầu về các công cụ phân tích dữ liệu mạnh mẽ để tránh tình trạng nghèo nàn về thông tin. Sự tăng trưởng nhanh chóng về kích thước của các kho dữ liệu đã vượt quá khả năng của con người nếu không có sự hỗ trợ của các công cụ khác. Kết quả là dữ liệu được lưu trữ trong các kho dữ liệu sẽ bị lãng quên. Do đó, những quyết định quan trọng thường được tạo ra mà không dựa trên thông tin được lưu trữ trong cơ sở dữ liệu, chỉ dự trên cảm tính chủ quan của Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 11 người đưa ra quyết định. Đơn giản là do người đưa ra quyết định không có công cụ để chiết xuất những tri thức cần thiết từ thông tin có được. Ngoài ra, các hệ thống điều tra thường dựa vào tri thức đầu vào do người dùng tự nhập vào cơ sở dữ liệu. Điều này dễ gây ra lỗi do sự chủ quan của người dùng và gây mất thời gian, chi phí. Các công cụ khai phá dữ liệu thực hiện phân tích dữ liệu, có thể phát hiện ra một số mô hình dữ liệu quan trọng đóng góp to lớn vào các chiến lược kinh doanh, cơ sở tri thức và các lĩnh vực y học, nghiên cứu khoa học. Khoảng trống giữa thông tin và tri thức ngày càng lớn yêu cầu sự phát triển mang tính hệ thống của các công cụ khai phá dữ liệu có thể biến dữ liệu thành tri thức. 1.1.2. Định nghĩa Khai phá dữ liệu được định nghĩa là một quá trình chắt lọc hay khai phá tri thức từ một lượng lớn dữ liệu [1]. Thuật ngữ khai phá dữ liệu chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lượng lớn các dữ liệu thô. Có nhiều thuật ngữ hiện tại được dùng cũng có nghĩa tương tự với Data Mining như Knowledge Mining, Knowledge Extraction, Data/Pattern Analysis đều được dùng để nhắc đến việc khai phá dữ liệu. Khai phá dữ liệu là một bước trong quy trình khai phá tri thức được mô tả dưới đây [1]: - Làm sạch dữ liệu: loại bỏ những dữ liệu nhiễu, thừa và không đồng nhất. - Kết hợp dữ liệu: nhiều nguồn dữ liệu có thể được kết hợp với nhau. - Chọn lọc dữ liệu: những dữ liệu liên quan đến các tác vụ phân tích được lấy ra từ cơ sở dữ liệu. - Chuyển đổi dữ liệu: dữ liệu có thể được chuyển đổi hay hợp nhất trong một dạng thích hợp cho việc khai phá dữ liệu dựa trên hoạt động tóm tắt hay kết hợp. - Khai phá dữ liệu: một quy trình cần thiết tại đó các phương thức khác nhau được áp dụng nhằm mục đích chiết xuất các mô hình dữ liệu. Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 12 - Đánh giá mô hình: xác định mô hình có thực sự phù hợp biểu diễn tri thức dựa trên một vài chuẩn cho trước hay không. - Biểu diễn tri thức: các công nghệ trình bày giả lập và tri thức được sử dụng để biểu diễn tri thức đã khai phá được cho người dùng. 1.2. Quy trình khai phá dữ liệu Nhằm mục đích hệ thống hóa việc phân tích khai phá dữ liệu, một quy trình chung thường được sử dụng. Có một vài quy trình chuẩn được đưa ra, 2 trong số đó là CRISP và SEMMA. CRISP là một quy trình công nghiệp chuẩn bao gồm một chuỗi các bước được sử dụng trong việc nghiên cứu khai phá dữ liệu. SEMMA là một quy trình riêng cho SAS, trong đó mỗi bước của cách tiếp cận không bắt buộc trong mỗi lần phân tích, quy trình này cung cấp một tập các bước cần thiết, bắt đầu từ khai thác dữ liệu, sưu tập dữ liệu, xử lý dữ liệu, phân tích, rút ra suy luận và thực thi. CRISP-DM được sử dụng rộng rãi bởi các nhân tố công nghiệp. Mô hình này bao gồm 6 pha riêng biệt như hình vẽ dưới đây [1]. Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 13 Tìm hiểu công việc Tìm hiểu dữ liệu Chuẩn bị dữ liệu Triển khai Nguồn dữ liệu Xây dựng mô hình Kiểm thử đánh giá và Hình 1: Quy trình khai phá dữ liệu CRISP-DM với 6 pha riêng biệt: tìm hiểu công việc, tìm hiểu dữ liệu, chuẩn bị dữ liệu, xây dựng mô hình, kiểm thử và đánh giá, triển khai được thực hiện lần lượt trên một nguồn dữ liệu có sẵn. - Pha đầu tiên - Tìm hiểu công việc (Business Understanding) [1] bao gồm xác định đối tượng của công việc, đánh giá tình hình hiện tại, đề xuất mục đích của khai phá dữ liệu và xây dựng kế hoạch dự án. - Pha thứ hai - Tìm hiểu dữ liệu (Data Understanding) [1]: khi các đối tượng của công việc và kế hoạch dự án được thiết lập, xem xét các yêu cầu dữ liệu. Pha này bao gồm: sưu tập dữ liệu ban đầu, mô tả dữ liệu, khai thác dữ liệu và đánh giá chất lượng dữ liệu. Khai phá dữ liệu được ví như việc xem xét bảng thống kê tóm tắt (trong đó bao gồm các biểu diễn ảo của các biến) có thể xảy ra vào cuối giai đoạn này. Mô hình phân tích cụm (Cluster analysis) cũng có thể được áp dụng trong giai đoạn này với mục đích xác định các mẫu trong dữ liệu. Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 14 - Pha thứ ba – Chuẩn bị dữ liệu (Data Preparation) [1]: khi nguồn dữ liệu có sẵn được xác định, nó cần phải được chọn lựa, làm sạch, kết hợp vào những hình thức mong muốn và định dạng lại. Làm sạch dữ liệu và chuyển đổi dữ liệu trong việc chuẩn bị mô hình dữ liệu cần phải được thực hiện trong bước này. Khai phá dữ liệu sâu hơn có thể được áp dụng trong giai đoạn này, và những mô hình khác được sử dụng để cung cấp cơ hội tìm thấy các mẫu dữ liệu dựa trên sự hiểu biết về công việc. - Pha thứ tư – Xây dựng mô hình (Modeling) [1]: các công cụ phần mềm khai phá dữ liệu như giả lập (biểu diễn thông tin và thiết lập các mối quan hệ) và phân tích cụm (để xác định những biến nào có thể đi cùng nhau) rất hữu ích cho việc phân tích ban đầu. Những công cụ như Generalized rule induction có thể phát triển những luật kết hợp ban đầu. Sau khi có được sự hiểu biết về những dữ liệu lớn hơn (thường qua các mô hình nhận được từ việc quan sát các mô hình đầu ra), những mô hình chi tiết hơn thích hợp cho các kiểu dữ liệu sẽ được áp dụng. Việc phân chia dữ liệu thành các tập training và test cũng cần thiết cho việc mô hình hóa. - Pha thứ năm – Đánh giá (Evaluation) [1]: các kết quả mô hình sẽ được đánh giá bởi các mục tiêu công việc được đưa ra ở giai đoạn đầu tiên. Điều này sẽ dẫn đến việc xác định các yêu cầu khác (thường qua việc xác nhận mô hình), và quay trở lại giai đoạn trước của mô hình CRISP-DM. Tìm hiểu công việc là một công việc được lặp đi lặp lại trong khai phá dữ liệu, sao cho các kết quả trực quan, thống kê và công cụ trí tuệ nhân tạo khác nhau biểu diễn cho người dùng các mối quan hệ mới cung cấp một sự hiểu biết sâu hơn về tổ chức của các hoạt động. - Pha cuối cùng – Triển khai (Deployment) [1]: khai phá dữ liệu có thể được sử dụng cho cả việc xác minh giả thiết trước đó hay khám phá tri thức mới (xác định các mối quan hệ bất ngờ và hữu ích). Qua việc tri thức được khám phá trong các giai đoạn trước của quy trình CRISP-DM, các mô hình có thể thu được sau đó áp dụng trong các hoạt động với mục đích khác nhau, bao Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 15 gồm dự đoán hay xác định các tình huống quan trọng. Những mô hình này cần phải được theo dõi thay đổi trong điều kiện hoạt động, do nó có thể là đúng trong hôm nay nhưng chưa đúng trong năm nay. Nếu một vài thay đổi xảy ra, mô hình cần được xây dựng lại. 1.3. Các kỹ thuật khai phá dữ liệu Có 3 kỹ thuật chính được sử dụng trong việc khai phá dữ liệu là: Mạng nơ ron nhân tạo ANN, cây quyết và giải thuật người hàng xóm gần nhất. Mỗi kỹ thuật thực hiện việc phân tích dữ liệu theo một cách khác nhau được mô tả như sau: 1.3.1. Mạng nơ ron nhân tạo Mạng nơ ron nhân tạo hay còn được gọi là mạng nơ ron là một mô hình toán học hay mô hình tính toán dựa trên mạng nơ ron sinh học, nói cách khác nó là một mô phỏng của hệ thống thần kinh [5]. Nó bao gồm một nhóm các nơ ron kết nối với nhau và thông tin về quy trình sử dụng cách tiếp cận kết nối để tính toán. Trong hầu hết các trường hợp, một mạng nơ ron là một hệ thống thích ứng với các thay đổi cấu trúc của nó dựa trên các thông tin bên trong hoặc bên ngoài chảy qua mạng trong suốt quá trình học tập. Trong nhiều thuật ngữ thực nghiệm các mạng nơ ron là các công cụ mô hình hóa dữ liệu thống kê phi tuyến tính. Nó có thể được sử dụng để mô hình hóa các mối quan hệ phức tạp giữa đầu vào và đầu ra hay để tìm các mẫu trong dữ liệu. Một mạng nơ ron là một nhóm kết nối bởi các nút, mô phỏng mạng nơ ron trong não bộ con người. Hình 2: Mạng nơ ron nhân tạo. Trong đó (A) là mô phỏng một nơ ron của con người, (B) là mô hình một nơ ron nhân tạo, (C) mô phỏng các kết nối sinh học Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 16 giữa các nơ ron trong não bộ con người, (D) thể hiện các kết nối trong mạng nơ ron nhân tạo. Việc huấn luyện trong mạng nơ ron nhân tạo: một mạng nơ ron phải được cấu hình sao cho việc áp dụng một bộ đầu vào sẽ tạo ra một bộ đầu ra theo đúng mong muốn. Các phương pháp khác nhau được sử dụng để xác định độ mạnh của các kết nối tồn tại. Một cách là đặt trọng số một cách rõ ràng, sử dụng các kiến thức tiên nghiệm. Một cách khác là đào tạo mạng nơ ron bằng cách cho nó các mô hình giảng dạy và để cho nó thay đổi trọng số theo các quy định huấn luyện. Chúng ta có thể phân loại các tình huống học tập như sau: - Học có giám sát: hay học có liên kết trong đó mạng nơ ron được huấn luyện bằng cách cung cấp cho nó các đầu vào và các mẫu đầu ra phù hợp. Những cặp đầu vào – đầu ra này có thể được cung cấp bởi một giáo viên bên ngoài hoặc bởi một hệ thống mà chứa các mạng thần kinh (tự giám sát). Hình 3: Kỹ thuật học có giám sát trong mạng nơ ron nhân tạo. Trong đó các mẫu đầu vào và đầu ra đã được cung cấp bởi một giáo viên hay một hệ thống. - Học không giám sát: hay tự tổ chức trong đó một đơn vị đầu ra được đào tạo để đáp ứng các nhóm mẫu của đầu vào. Trong mô hình này, hệ thống được dùng để khám phá các đặc điểm nổi bật về mặt thống kê của đầu vào. Không giống như mô hình học tập có giám sát, không có một tập hợp tiên đề các loại mà trong đó các mô hình được phân loại, thay vào đó hệ thống phải phát triển các đại diện của nó đáp ứng các đầu vào. Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 17 Hình 4: Kỹ thuật học không giám sát trong mạng nơ ron nhân tạo. Trong đó hệ thống sẽ dựa vào thông tin từ môi trường mà đưa ra các đầu ra phù hợp. - Học tăng cường: loại học này có thể được xem như một mô hình trung gian giữa 2 loại trên. Ở đó các máy học thực hiện một vài hành động trên môi trường và nhận được các phản hồi từ môi trường. Hệ thống học tập đánh giá hoạt động tốt (khen thưởng) hoặc xấu (phê phán) dựa trên các đáp ứng của môi trường và điều chỉnh các thông số của nó. Hình 5: Kỹ thuật học tăng cường trong mạng nơ ron nhân tạo. Là mô hình trung gian giữa học có giám sát và học không giám sát. Mô hình mạng nơ-ron đơn giản: một trong những mô hình mạng nơ-ron đơn giản nhất được mô tả trong hình gồm 3 tầng: tầng đầu vào, tầng ẩn và tầng đầu ra. Trong mỗi tầng có 1 hay nhiều yếu tố xử lý (PE). PE có nghĩa là để mô phỏng các tế bào nơ-ron trong não và đây là lý do tại sao nó thường được gọi là các nơ-ron hay các nút. Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 18 Hình 6: Mô hình mạng nơ ron đơn giản gồm 3 tầng là tầng đầu vào, tầng ẩn để xử lý và tầng đầu ra. Trong tầng ẩn có nhiều yếu tố xử lý hay các nơ ron để thực hiện nhiệm vụ. Một PE nhận các đầu vào từ thế giới bên ngoài. Quy trình xử lý của mạng nơron như sau: - Dữ liệu đầu vào được trình bày cho mạng và được truyền qua mạng cho đến khi nó đến tầng đầu ra. Quá trình chuyển tiếp này tạo ra một đầu ra dự đoán. - Đầu ra dự đoán này được loại ra khỏi đầu ra thực tế và một giá trị lỗi cho mạng được tính toán. - Mạng nơ-ron sau đó sử dụng phương pháp học có giám sát, trong nhiều trường hợp là sự truyền lại, để đào tạo cho mạng. Truyền lại là một thuật toán học tập dành cho việc điều chỉnh trọng số. Nó bắt đầu bằng trọng số giữa tầng PE đầu ra và tầng PE ẩn cuối cùng và hoạt động ngược trở lại thông qua mạng. - Khi quá trình truyền trở lại hoàn thành, quá trình chuyển tiếp bắt đầu và điều này được lặp lại cho đến khi lỗi giữa đầu ra dự đoán và thực tế là nhỏ nhất. 1.3.2. Cây quyết định Cây quyết định [6] xây dựng các mô hình phân loại hoặc hồi quy dưới hình thức cấu trúc cây. Nó chia nhỏ tập dữ liệu thành các tập con nhỏ hơn trong khi tại cùng thời điểm một cây kết hợp cũng được phát triển. Kết quả cuối cùng là một cây với các nút quyết định và các nút lá. Nút quyết định có 2 hoặc nhiều nhánh. Nút lá đại diện cho một phân lớp hay một quyết định. Nút quyết định trên cùng của một ây tương ứng với Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 19 dự đoán tốt nhất được gọi là nút gốc. Các cây quyết định có thể xử lý cả dữ liệu phân loại và dữ liệu số. Giải thuật để xây dựng một cây quyết định được gọi là ID3 được tạo bởi J.R. Quinlan. Giải thuật này thực hiện việc tìm kiếm vét cạn từ trên xuống qua các nhánh có thể. ID3 sử dụng một Entropy và một Information Gain để xây dựng một cây quyết định. - Entropy: một cây quyết định được xây dựng từ trên xuống từ một nút gốc và liên quan đến việc phân chia dữ liệu thành các tập con chứa các thể hiện với các giá trị tương tự. Giải thuật ID3 sử dụng entropy để tính toán tính đồng nhất của một mẫu. Nếu mẫu là hoàn toàn đồng nhất thì entropy của nó bằng 0 và nếu mẫu được chia đều thì nó có entropy bằng 1. Hình 7: Entropy. Entropy thể hiện tính đồng nhất của một mẫu. Nếu mẫu hoàn toàn đồng nhất thì entropy của nó nhỏ nhất bằng 0. Nếu mẫu được chia đều thì entropy của nó đạt giá trị lớn nhất bằng 1. Để xây dựng một cây quyết định, chúng ta cần tính toán 2 loại entropy sử dụng các bảng tần suất như sau:  Entropy sử dụng bảng tần suất của một thuộc tính: E(S) = ∑𝑐𝑖=1 - pilog2pi Học viên thực hiện: Nguyễn Thị Thúy Hằng-CB140147-2014B-KTPM 20