MỞ ĐẦU Khám phá tri thức - Khai phá dữ liệu (Knowledge discovery - Data mining) là một lĩnh vực quan trọng của ngành Công nghệ thông tin, đã và đang thu hút sự quan tâm đông đảo các nhà khoa học trên thế giới và trong nƣớc tham\gia nghiên cứu. Khai phá dữ liệu ra đời vào những năm cuối thập kỷ 80 của thế kỷ XX, nó là lĩnh vực đƣợc nghiên cứu nhằm tự động khai thác thông tin, tri thức mới hữu ích, tiềm ẩn từ các CSDL lớn, kho dữ liệu,. Những vấn đề đƣợc quan tâm trong khai phá dữ liệu là phân lớp nhận dạng mẫu, luật kết hợp, phân cụm dữ liệu,. Trong đó, phân cụm dữ liệu (Data Clustering) là một trong những kỹ thuật khai thác dữ liệu có hiệu quả.
Phân cụm dữ liệu là quá trình tìm kiếm và phát hiện ra các cụm hoặc các mẫu dữ liệu tự nhiên trong cơ sở dữ liệu lớn. Phân cụm dữ liệu đã đƣợc ứng dụng trong nhiều lĩnh vực khác nhau nhƣ giáo dục, y tế, kinh tế, bảo hiểm, phân đoạn ảnh,. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com x Việc áp dụng phân cụm dữ liệu để phân tích trong ngành kế toán hiện nay là rất cần thiết, bởi lƣợng dữ liệu lƣu trữ lƣơng khá lớn, việc phân tích đánh giá lƣơng để đƣa ra các chiến lƣợc cân đối nguồn chi phí của đơn vị, dự báo quỹ lƣơng và có kế hoạch cân đối tài chính cho phù hợp cũng gặp nhiều khó khăn. Ngoài ra việc phân tích lƣơng còn phục vụ công tác quản lý nhân sự, giúp nắm đƣợc tình hình sử dụng con ngƣời của đơn vị từ đó đƣa ra các chính sách tuyển dụng phù hợp, có các giải pháp tạo động lực cho ngƣời lao động bằng các chính sách tài chính.
Việc phân cụm dữ liệu để phân tích lƣơng cho kết quả thu đƣợc sẽ phân loại theo giá trị lƣơng của mỗi cán bộ, phân loại ra các mức thu nhập cao thấp khác nhau từ đó đƣa ra các chính sách cân đối thu chi để có những chính sách ƣu đãi phù hợp mà vẫn đảm bảo tài chính của đơn vị. Với các lý do nhƣ vậy tôi chọn đề tài: “Một số phƣơng pháp phân cụm dữ liệu và ứng dụng trong phân tích lƣơng của cán bộ trƣờng Cao đẳng Nghề Hà Nam” làm đề tài luận văn tốt nghiệp. Bố cục luận văn gồm có 3 chƣơng: Chƣơng I: Tổng quan về khai phá dữ liệu và phân cụm dữ liệu. Chƣơng II: Một số thuật toán phân cụm dữ liệu điển hình Chƣơng III: Ứng dụng phƣơng pháp phân nhóm dữ liệu vào phân tích lƣơng của cán bộ trƣờng Cao đẳng Nghề Hà Nam.
Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 1 CHƢƠNG I: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM DỮ LIỆU 1.1 Khai phá dữ liệu 1.1 Giới thiệu về khai phá dữ liệu Khai phá dữ liệu (Data Mining) là một khái niệm ra đời vào những năm cuối thập kỉ 80 của thế kỉ XX. Khai phá dữ liệu là một lĩnh vực đƣợc nghiên cứu nhằm tự động khai thác thông tin, tri thức mới hữu ích, tiềm ẩn từ các CSDL lớn, kho dữ liệu,. Ngoài thuật ngữ khai phá dữ liệu ngƣời ta còn một số thuật ngữ khác có ý nghĩ tƣơng tự nhƣ: trích chọn dữ liệu (Knowledge extraction), nạo vét dữ liệu (Data dredging), phân tích dữ liệu mẫu (Pattern Analisys), phát hiện tri thức từ CSDL (Knowlegde Discovery in Databases. Các bƣớc cơ bản trong quá trình phát hiện tri thức từ CSDL là [6]: (1) Làm sạch dữ liệu: Loại bỏ dữ liệu nhiễu và không đồng nhất (2) Tích hợp dữ liệu: Các nguồn dữ liệu khác nhau đƣợc tích hợp với nhau (3) Trích chọn dữ liệu: Chọn các dữ liệu liên quan đến phân tích (4) Chuyển đổi dữ liệu: Chuyển dữ liệu sang phù hợp để khai phá (5) Khai phá dữ liệu: Bƣớc thiết yếu để tìm ra mẫu dữ liệu (6) Đánh giá các mẫu: Kiểm định dựa vào mục tiêu ban đầu của chúng (7) Biểu diễn tri thức: Hiển thị, biểu diễn kết quả sao có thể hiểu đƣợc Trong 7 giai đoạn của quá trình khám phá tri thức thì giai đoạn 5 (Khai phá dữ liệu) là giai đoạn quan trọng nhất.
Trong những năm gần đây, rất nhiều các phƣơng pháp và thuật toán mới về KPDL liên tục đƣợc công bố. Điều này chứng tỏ những ƣu thế, lợi ích và khả năng ứng dụng thực tế to lớn của KPDL.2 Quá trình khai phá dữ liệu Về bản chất khai phá dữ liệu là giai đoạn t tìm ra đƣợc những thông tin mới, tiềm ẩn trong CSDL và chủ yếu phục vụ cho quá trình mô tả và dự đoán. LUAN VAN CHATSốLUONG hóa bởi Trung download tâm Học liệu – ĐHTN http://www.vn : add luanvanchat@agmail.com 2 Mô tả dữ liệu là tổng kết hoặc diễn tả những tính chất hoặc đặc tính chung của những thuộc tính dữ liệu trong kho dữ liệu mà con ngƣời có thể hiểu đƣợc. Dự đoán là dựa trên những dữ liệu hiện thời để dự đoán những quy luật đƣợc phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu trên cơ sở đó chiết xuất ra các mẫu, dự đoán đƣợc những giá trị chƣa biết hoặc những giá trị tƣơng lai của các biến quan tâm.
Quá trình khai phá dữ liệu gồm các bƣớc chính nhƣ sau: - Xác định nhiệm vụ: Xác định các vấn đề chính cần giải quyết. - Xác định dữ liệu liên quan: Dùng để xây dựng giải pháp. - Thu thập và tiền xử lý dữ liệu: Thu thập các dữ liệu liên quan và tiền xử lý chúng sao cho thuật toán khai phá dữ liệu có thể hiểu đƣợc. - Giải thuật khai phá dữ liệu: Lựa chọn thuật toán khai phá dữ liệu và thực hiện việc khai phá dữ liệu để tìm đƣợc các mẫu có ý nghĩa.3 Các kỹ thuật khai phá dữ liệu - Khai phá dữ liệu thƣờng sử dụng các phƣơng pháp sau: + Luật kết hợp (AssoCi ation rules): Là phát hiện và đƣa ra mối liên hệ giữa các giá trị dữ liệu trong CSDL.
+ Phân cụm dữ liệu (Data Clustering): Sắp xếp các đối tƣợng theo từng cụm dữ liệu tự nhiên, tức là số lƣợng và tên cụm chƣa đƣợc biết trƣớc. Các đối tƣợng đƣợc gom cụm sao cho độ tƣơng đồng (similar) giữa các đối tƣợng trong cùng một cụm là lớn nhất và mức độ tƣơng đồng giữa các đối tƣợng nằm trong các cụm khác nhau là nhỏ nhất. Phân cụm còn đƣợc gọi là học không giám sát (Unsupervised Learning). - Khai phá dữ liệu dự đoán thƣờng sử dụng các phƣơng pháp sau: + Phân lớp (Classfication): Là quá trình xếp một đối tƣợng vào một trong những lớp đã biết trƣớc (Ví dụ: phân lớp các học sinh theo kết quả thi).
Phân lớp còn đƣợc gọi là học có giám sát (Supervised learning). LUAN VAN CHATSốLUONG hóa bởi Trung download tâm Học liệu – ĐHTN http://www.vn : add luanvanchat@agmail.com 3 + Hồi quy (Regression): Phƣơng pháp hồi quy tƣơng tự nhƣ phân lớp dữ liệu nhƣng khác ở chỗ nó dùng để dự đoán các giá trị liên tục còn phân lớp dữ liệu dùng để dự đoán các giá trị rời rạc - Ngoài các phƣơng pháp trên còn rất nhiều các phƣơng pháp khác nhƣ: + Cây quyết định (DeCi sion Trees) + Mạng nơ-ron (Neural Network) + Trực quan hóa (Visualization) + Biểu diễn mô hình (Model Evaluation) + Phƣơng pháp tìm kiếm (Search Method) + Phân tích theo trình tự thời gian (Time series Analysis) 1.4 Ứng dụng của Khai phá dữ liệu Khai phá dữ liệu đƣợc ứng dụng trong nhiều lĩnh vực khác nhau nhằm khai thác nguồn dữ liệu đƣợc lƣu trữ trong các hệ thống thông tin. Một số ứng dụng điển hình trong khai phá dữ liệu có thể liệt kê nhƣ sau: - Thƣơng mại: Nhƣ phân tích dữ liệu bán hàng và thi trƣờng, phân tích đầu tƣ, phát hiện gian lận, chứng thực hóa khách hàng, dự báo xu hƣớng phát triển,. - Thông tin khoa học: Quan sát thiên văn, dự báo thời tiết, dữ liệu gene, tìm kiếm so sánh các hệ gene và thông tin di truyền (sinh học),.
- Mạng viễn thông: Phân tích các cuộc gọi điện thoại và hệ thống giám sát lỗi, sự cố, chất lƣợng dịch vụ,. - Phân tích dữ liệu và hỗ trợ ra quyết định, điều trị y học, khai phá Web, tài chính và thị trƣờng chứng khoán, bảo hiểm, giáo dục, du lịch,.5 Các xu thế và vấn đề cần giải quyết trong khai phá dữ liệu Một số hƣớng nghiên cứu chính của Khai phá dữ liệu hiện nay [6]: Xu hƣớng khai phá dữ liệu đang nỗ lực hơn nữa đối với việc thăm dò các lĩnh vực ứng dụng mới, cải tiến phƣơng pháp mở rộng, tƣơng tác, tích hợp khai thác dữ liệu với dịch vụ web, cơ sở dữ liệu, kho dữ liệu, các hệ thống điện toán đám mây và khai thác mạng xã hội,. Các xu hƣớng khác bao gồm việc khai thác dữ liệu thời gian và không gian, dữ liệu sinh học, hệ thống dữ liệu kĩ thuật, các dữ liệu đa phƣơng tiện và khai phá dữ liệu văn bản, khai pha web, các dữ LUAN VAN CHATSốLUONG hóa bởi Trung download tâm Học liệu – ĐHTN http://www.vn : add luanvanchat@agmail.com 4 liệu phân tán, dữ liệu thời gian thực, dòng dữ liệu, khai thác dữ liệu hình ảnh, âm thanh và vấn đề an ninh trong khai thác dữ liệu. Việc khám phá đƣợc nhiều tri thức khác nhau từ các kiểu dữ liệu khác nhau, tính chính xác và hiệu quả, khả năng mở rộng và tích hợp, xử lý nhiễu và tính hữu ích của dữ liệu đƣợc khai phá.
Khai phá dữ liệu liên quan đến nhiều ngành, nhiều lĩnh vực trong thực tế, vì vậy các thách thức và khó khăn ngày càng nhiều, càng lớn hơn. Sau đây là một số các thách thức và khó khăn cần đƣợc quan tâm: - Các cơ sở dữ liệu lớn với hàng trăm trƣờng, hàng triệu bản ghi và kích thƣớc lên tới nhiều Gi-ga byte (GB) hoặc nhiều Tê-ra byte (TB). - Số lƣợng các trƣờng lớn (các thuộc tính, các biến) làm cho số chiều của bài toán trở nên cao. Đặc biệt lƣu ý đến dữ liệu không gian, số chiều cao có thể rất thƣa và bị lệch nhiều.
- Việc dữ liệu thay đổi nhanh có thể làm cho các mẫu phát hiện trƣớc đó không hợp lệ. Thêm vào đó các biến đã đo trong một cơ sở dữ liệu ứng dụng cho trƣớc có thể bị sửa đổi, xóa bỏ hay tăng thêm các phép đo mới. - Dữ liệu bị thiếu và bị nhiễu. - Mối quan hệ phức tạp giữa các trƣờng (dữ liệu hỗn hợp).
- Tính dễ hiểu của các mẫu. - Tích hợp với các hệ thống khác.2 Kỹ thuật phân cụm trong Khai phá dữ liệu 1.