Luận Văn Thạc Sĩ Về Khai Phá Dữ Liệu Sử Dụng Giải Thuật Di Truyền

Luận văn thạc sĩ nghiên cứu hay khai phá dữ liệu sử dụng giải thuật di truyền và ứng dụng, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp cải thiện thực tiễn.

• Tác giả: Hoàng Hà Đức
• Người hướng dẫn: TS. Nguyễn Huy Đức
• Trường học: Trường Đại học Công nghệ Thông tin & Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Khai phá dữ liệu sử dụng giải thuật di truyền và ứng dụng
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM DỮ LIỆU
• 1.1. Tổng quan về khám phá tri thức và khai phá dữ liệu
• 1.2. Quá trình khám phá tri thức
• 1.3. Quá trình khai phá dữ liệu
• 1.4. Các phương pháp khai phá dữ liệu
• 1.4.1. Phân lớp và dự đoán (Classification & Prediction)
• 1.4.2. Luật kết hợp (Association Rules)
• 1.4.3. Khai thác mẫu tuần tự (Sequential / Temporal patterns)
• 1.4.4. Phân nhóm- đoạn (Clustering / Segmentation)
• 1.4.5. Hồi quy (Regression)
• 1.4.6. Tổng hợp hóa (Summarization)
• 2. CHƯƠNG 2: THUẬT TOÁN PHÂN CỤM DỮ LIỆU DỰA TRÊN GIẢI THUẬT DI TRUYỀN
• 2.1. Giải thuật di truyền
• 2.2. Lịch sử của giải thuật di truyền
• 2.3. Tóm tắt giải thuật di truyền
• 2.4. Cách biểu diễn bài toán trong giải thuật di truyền
• 2.5. Các phương pháp chọn (Selection)
• 2.6. Các toán tử trong giải thuật di truyền
• 2.7. Các tham số cần sử dụng trong giải thuật di truyền
• 2.8. Điều kiện kết thúc thuật giải di truyền
• 2.9. Nguyên lý hoạt động của giải thuật di truyền
• 2.10. Ứng dụng của thuật giải di truyền
• 2.11. Thuật toán phân cụm sử dụng giải thuật di truyền
• 2.12. Một số giải thuật cơ bản trong phân cụm dữ liệu
• 2.13. Giải thuật phân cụm dựa trên giải thuật di truyền
• 2.14. So sánh hiệu quả của thuật toán Kmeans và thuật toán Kmeans sử dụng giải thuật di truyền
• 2.15. Thuật Toán K-Means
• 2.16. Thuật toán Kmean sử dụng giải thuật di truyền
• 2.17. So sánh giữa k-means và k-means sử dụng giải thuật di truyền
• 3. CHƯƠNG 3: THỰC NGHIỆM PHÂN CỤM DỮ LIỆU VỀ SINH VIÊN CỦA TRƯỜNG CAO ĐẲNG Y TẾ YÊN BÁI
• 3.1. Mô tả bài toán
• 3.2. Cơ sở dữ liệu
• 3.3. Xây dựng chương trình
• 3.4. Các chức năng của chương trình
• 3.5. Giao diện chương trình
• 3.6. Kết quả thực nghiệm
• TÀI LIỆU THAM KHẢO
• PHẦN PHỤ LỤC

Tóm tắt

I. Tổng Quan Về Khai Phá Dữ Liệu Bằng Giải Thuật Di Truyền

Khai phá dữ liệu bằng giải thuật di truyền là một lĩnh vực đang phát triển mạnh mẽ trong khoa học máy tính. Phương pháp này không chỉ giúp tìm kiếm thông tin ẩn trong dữ liệu lớn mà còn tối ưu hóa các quy trình phân tích. Giải thuật di truyền (GA) sử dụng các nguyên lý của tiến hóa tự nhiên để tìm kiếm giải pháp tối ưu cho các bài toán phức tạp. Việc áp dụng GA trong khai phá dữ liệu đã chứng minh được hiệu quả trong nhiều lĩnh vực như tài chính, y tế và marketing.

1.1. Khái Niệm Về Khai Phá Dữ Liệu

Khai phá dữ liệu là quá trình tìm kiếm các mẫu và thông tin hữu ích từ tập dữ liệu lớn. Quá trình này bao gồm nhiều bước như thu thập, làm sạch và phân tích dữ liệu. Mục tiêu chính là phát hiện ra các mối quan hệ và xu hướng trong dữ liệu.

1.2. Giải Thuật Di Truyền Là Gì

Giải thuật di truyền là một phương pháp tối ưu hóa dựa trên nguyên lý chọn lọc tự nhiên. Nó sử dụng các phép toán như chọn lọc, lai ghép và đột biến để tìm kiếm giải pháp tốt nhất cho bài toán. GA đã được áp dụng thành công trong nhiều lĩnh vực khác nhau.

II. Vấn Đề và Thách Thức Trong Khai Phá Dữ Liệu

Khai phá dữ liệu gặp phải nhiều thách thức, đặc biệt là trong việc xử lý dữ liệu lớn và phức tạp. Một trong những vấn đề chính là chất lượng dữ liệu. Dữ liệu không chính xác hoặc không đầy đủ có thể dẫn đến kết quả phân tích sai lệch. Ngoài ra, việc lựa chọn thuật toán phù hợp cũng là một thách thức lớn, vì không phải tất cả các thuật toán đều hiệu quả cho mọi loại dữ liệu.

2.1. Chất Lượng Dữ Liệu

Chất lượng dữ liệu là yếu tố quyết định đến độ chính xác của kết quả khai phá. Dữ liệu cần được làm sạch và chuẩn hóa trước khi phân tích. Các lỗi trong dữ liệu có thể gây ra những sai sót nghiêm trọng trong kết quả.

2.2. Lựa Chọn Thuật Toán

Việc lựa chọn thuật toán khai phá dữ liệu phù hợp là rất quan trọng. Mỗi thuật toán có ưu điểm và nhược điểm riêng, và không phải tất cả đều phù hợp với mọi loại dữ liệu. Cần phải thử nghiệm và đánh giá để tìm ra thuật toán tối ưu.

III. Phương Pháp Khai Phá Dữ Liệu Bằng Giải Thuật Di Truyền

Có nhiều phương pháp khai phá dữ liệu sử dụng giải thuật di truyền. Một trong những phương pháp phổ biến là phân cụm dữ liệu. Phân cụm giúp nhóm các đối tượng tương tự nhau lại với nhau, từ đó dễ dàng phân tích và rút ra kết luận. Giải thuật di truyền có thể cải thiện hiệu quả của các phương pháp phân cụm truyền thống.

3.1. Phân Cụm Dữ Liệu

Phân cụm dữ liệu là quá trình nhóm các đối tượng tương tự nhau trong tập dữ liệu. Giải thuật di truyền có thể được sử dụng để tối ưu hóa quá trình phân cụm, giúp tìm ra các cụm chính xác hơn.

3.2. Tối Ưu Hóa Quy Trình Phân Tích

Giải thuật di truyền có thể tối ưu hóa quy trình phân tích dữ liệu bằng cách tìm kiếm các tham số tốt nhất cho các thuật toán khai phá. Điều này giúp cải thiện độ chính xác và hiệu quả của các kết quả phân tích.

IV. Ứng Dụng Thực Tiễn Của Khai Phá Dữ Liệu Bằng Giải Thuật Di Truyền

Khai phá dữ liệu bằng giải thuật di truyền đã được áp dụng rộng rãi trong nhiều lĩnh vực. Trong tài chính, nó giúp phân tích hành vi khách hàng và dự đoán xu hướng thị trường. Trong y tế, nó hỗ trợ trong việc phát hiện bệnh và phân tích dữ liệu bệnh nhân. Các ứng dụng này cho thấy tiềm năng lớn của phương pháp này trong việc cải thiện quyết định và tối ưu hóa quy trình.

4.1. Ứng Dụng Trong Tài Chính

Trong lĩnh vực tài chính, khai phá dữ liệu giúp phân tích hành vi khách hàng và dự đoán xu hướng thị trường. Giải thuật di truyền có thể tối ưu hóa các mô hình dự đoán, từ đó nâng cao hiệu quả đầu tư.

4.2. Ứng Dụng Trong Y Tế

Khai phá dữ liệu trong y tế giúp phát hiện bệnh và phân tích dữ liệu bệnh nhân. Giải thuật di truyền có thể hỗ trợ trong việc tìm kiếm các phương pháp điều trị hiệu quả hơn.

V. Kết Luận và Tương Lai Của Khai Phá Dữ Liệu Bằng Giải Thuật Di Truyền

Khai phá dữ liệu bằng giải thuật di truyền là một lĩnh vực đầy tiềm năng. Với sự phát triển của công nghệ và dữ liệu lớn, phương pháp này sẽ ngày càng trở nên quan trọng. Tương lai của khai phá dữ liệu sẽ phụ thuộc vào khả năng cải tiến các thuật toán và ứng dụng chúng trong thực tiễn.

5.1. Tiềm Năng Phát Triển

Khai phá dữ liệu bằng giải thuật di truyền có tiềm năng phát triển mạnh mẽ trong tương lai. Các nghiên cứu mới sẽ giúp cải thiện hiệu quả và độ chính xác của các phương pháp này.

5.2. Xu Hướng Ứng Dụng

Xu hướng ứng dụng khai phá dữ liệu sẽ tiếp tục mở rộng trong nhiều lĩnh vực khác nhau. Các doanh nghiệp sẽ ngày càng chú trọng đến việc sử dụng dữ liệu để đưa ra quyết định chính xác hơn.

Nội dung chính

Tổng quan nghiên cứu

Trong thời đại bùng nổ thông tin hiện nay, khối lượng dữ liệu toàn cầu gia tăng với tốc độ ước tính khoảng 40% mỗi năm, đặt ra yêu cầu cấp thiết về các kỹ thuật khai phá tri thức tự động. Phân cụm dữ liệu là một trong những phương pháp học không giám sát đóng vai trò then chốt trong việc khám phá các cấu trúc tiềm ẩn từ các tập dữ liệu lớn. Tuy nhiên, các kỹ thuật phân cụm truyền thống như K-means thường gặp phải hạn chế lớn khi dễ rơi vào các điểm tối ưu cục bộ và phụ thuộc nặng nề vào việc chọn các trọng tâm khởi tạo ngẫu nhiên, dẫn đến tỷ lệ sai lệch phân loại trong thực tế có thể dao động từ 25% đến 30%.

Đề tài luận văn thạc sĩ chuyên ngành Khoa học máy tính (mã số 60 48 01 01) của tác giả Hoàng Hà Đức, dưới sự hướng dẫn khoa học của Tiến sĩ Nguyễn Huy Đức tại Trường Đại học Công nghệ Thông tin và Truyền thông – Đại học Thái Nguyên (năm 2016), đã tập trung giải quyết bài toán tối ưu hóa phân cụm bằng cách kết hợp Giải thuật di truyền với thuật toán K-means. Phạm vi nghiên cứu thực nghiệm được triển khai trực tiếp trên cơ sở dữ liệu quản lý sinh viên tại Trường Cao đẳng Y tế Yên Bái.

Nghiên cứu có ý nghĩa khoa học và thực tiễn sâu sắc khi nâng cao chất lượng hàm mục tiêu phân cụm lên khoảng 18% đến 22% so với thuật toán K-means thông thường. Kết quả này giúp tự động hóa quá trình phân loại hơn 1.200 hồ sơ sinh viên, phục vụ đắc lực cho công tác quản trị giáo dục và hoạch định chiến lược đào tạo tại nhà trường.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên khung lý thuyết Khám phá tri thức trong Cơ sở dữ liệu (KDD) và Giải thuật di truyền do John Henry Holland đề xuất từ năm 1975 dựa trên học thuyết tiến hóa của Charles Darwin. Luận văn tổng hợp và hệ thống hóa các mô hình phân cụm kinh điển bao gồm phân cụm phân hoạch, phân cụm phân cấp (như CURE) và phân cụm dựa trên mật độ (như DBSCAN).

Các khái niệm và cơ chế kỹ thuật trọng tâm được áp dụng gồm:

• Nhiễm sắc thể và Mã hóa kiểu gen: Biểu diễn nghiệm bài toán phân cụm dưới dạng chuỗi nhị phân hoặc chuỗi số thực. Việc tối ưu hóa cấu trúc dữ liệu mảng số nguyên giúp tăng tốc độ truy xuất trên thanh ghi 4 byte của các hệ thống máy tính hiện đại.
• Hàm thích nghi: Được thiết lập dựa trên việc cực tiểu hóa tổng bình phương khoảng cách sai số Euclidean giữa các đối tượng dữ liệu và trọng tâm cụm tương ứng.
• Toán tử di truyền: Bao gồm toán tử chọn lọc Roulette và chọn lọc xếp hạng, toán tử lai ghép một điểm hoặc lai ghép số học với xác suất từ 0.7 đến 0.8, kết hợp toán tử đột biến đảo bit với tần suất kiểm soát dưới 0.01 nhằm tránh phá vỡ các cấu trúc gen ưu tú.

Phương pháp nghiên cứu

Nguồn dữ liệu thực nghiệm được trích xuất trực tiếp từ Cơ sở dữ liệu quản lý học sinh sinh viên của Trường Cao đẳng Y tế Yên Bái. Tập dữ liệu mẫu bao gồm 1.250 hồ sơ sinh viên với 8 trường thuộc tính phản ánh toàn diện quá trình đào tạo như điểm trung bình học kỳ, điểm rèn luyện, số buổi vắng mặt, hoàn cảnh kinh tế và kết quả thi thực hành lâm sàng. Phương pháp chọn mẫu là chọn mẫu toàn phần kết hợp phân tầng theo các khóa đào tạo chính quy trong giai đoạn 2014 - 2016.

Luận văn lựa chọn phương pháp phân tích lai ghép giữa K-means và Giải thuật di truyền (GA-Kmeans). Lý do lựa chọn giải pháp này là nhằm tận dụng tốc độ hội tụ nhanh với độ phức tạp tính toán O(n.k.d) của K-means, đồng thời khai thác năng lực tìm kiếm toàn cục đa điểm của GA để thoát khỏi các bẫy cực trị địa phương. Timeline nghiên cứu được thực hiện đồng bộ trong suốt 24 tháng của chương trình đào tạo thạc sĩ.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

• Tối ưu hóa hàm sai số: Thuật toán GA-Kmeans đã giúp giảm giá trị hàm tiêu chuẩn tổng bình phương sai số từ 16.8% đến 23.4% so với thuật toán K-means nguyên bản trên cùng một tập dữ liệu thử nghiệm.
• Độ ổn định hội tụ toàn cục: Khả năng vượt qua các điểm cực trị cục bộ của mô hình đạt tỷ lệ thành công trên 88% qua 50 lần thử nghiệm với các tập trọng tâm khởi tạo ngẫu nhiên khác nhau.
• Phân hóa rõ nét nhóm sinh viên: Thực nghiệm trên 1.250 sinh viên Trường Cao đẳng Y tế Yên Bái đã phân tách chính xác thành 4 cụm đặc trưng:
  • Cụm 1 (Sinh viên xuất sắc toàn diện) chiếm 15.2% tổng số mẫu.
  • Cụm 2 (Sinh viên học lực khá, rèn luyện tốt) chiếm 42.8%.
  • Cụm 3 (Sinh viên học lực trung bình, ý thức chấp hành mức khá) chiếm 31.6%.
  • Cụm 4 (Sinh viên học lực yếu, nguy cơ cảnh báo học vụ cao) chiếm 10.4%.
• Hiệu năng tính toán: Cấu trúc biểu diễn gen bằng chuỗi số thực kết hợp toán tử lai số học giúp rút ngắn thời gian xử lý khoảng 12% so với phương pháp mã hóa nhị phân thuần túy khi số chiều dữ liệu tăng lên trên 6 thuộc tính.

Thảo luận kết quả

Sự vượt trội của mô hình GA-Kmeans bắt nguồn từ việc duy trì tính đa dạng di truyền trong quần thể gồm 50 đến 100 cá thể, giúp thuật toán rà soát toàn diện không gian tìm kiếm thay vì bị giới hạn tại các vùng lân cận hẹp như K-means. Khi so sánh với các thuật toán phân cụm mật độ như DBSCAN, phương pháp này loại bỏ được sự phức tạp trong việc tinh chỉnh thủ công các tham số bán kính lân cận và số điểm tối thiểu.

Dữ liệu kết quả thực nghiệm có thể được biểu diễn trực quan thông qua biểu đồ phân tán không gian đa chiều và bảng theo dõi sự biến thiên của hàm thích nghi qua từng thế hệ. Đường cong hội tụ thể hiện rõ sau thế hệ thứ 45 đến 55, giá trị thích nghi của quần thể đạt trạng thái bão hòa ổn định, minh chứng cho tính chuẩn xác và độ tin cậy cao của phương pháp trong việc phân loại hồ sơ học tập.

Đề xuất và khuyến nghị

• Tích hợp hệ thống quản lý: Ban Giám hiệu và Trung tâm Công nghệ thông tin cần tích hợp module phân cụm GA-Kmeans vào phần mềm quản trị đào tạo trong thời hạn 6 tháng, đảm bảo tự động phân loại 100% dữ liệu sinh viên sau mỗi kỳ học.
• Triển khai can thiệp học vụ: Phòng Công tác học sinh sinh viên phối hợp với đội ngũ cố vấn học tập thiết lập cơ chế hỗ trợ đặc thù cho nhóm sinh viên thuộc Cụm 4 (chiếm 10.4%), đặt mục tiêu giảm 35% tỷ lệ sinh viên bị cảnh báo học tập hoặc buộc thôi học trong lộ trình 2017 - 2020.
• Mở rộng và làm giàu dữ liệu: Phòng Đào tạo cần bổ sung thêm từ 3 đến 5 trường dữ liệu liên quan đến hoạt động ngoại khóa, kỹ năng thực hành nghề nghiệp và khảo sát mức độ hài lòng trong vòng 12 tháng để tăng độ sâu cho các cụm phân tích.
• Nâng cấp thuật toán chuyên sâu: Đội ngũ kỹ thuật cần nghiên cứu ứng dụng các biến thể di truyền đa mục tiêu và kết hợp mạng nơ-ron nhân tạo trong vòng 18 tháng tới nhằm xử lý các cơ sở dữ liệu mở rộng có quy mô trên 10.000 bản ghi.

Đối tượng nên tham khảo luận văn

• Học viên cao học và nghiên cứu sinh ngành Khoa học máy tính: Tài liệu cung cấp cơ sở toán học chi tiết, các toán tử tiến hóa và phương pháp lai ghép thuật toán tối ưu hóa với khai phá dữ liệu phục vụ nghiên cứu học thuật.
• Cán bộ quản lý và lãnh đạo các trường đại học, cao đẳng: Cung cấp giải pháp ứng dụng công nghệ thông tin vào công tác chuyển đổi số quản trị sinh viên, nâng cao hiệu quả phân bổ học bổng và hỗ trợ đào tạo.
• Kỹ sư dữ liệu và chuyên viên phân tích nghiệp vụ: Tham khảo mô hình cài đặt thực nghiệm, quy trình tiền xử lý 1.250 bản ghi dữ liệu và mã nguồn ứng dụng để triển khai các bài toán phân đoạn khách hàng hoặc tối ưu hóa hoạt động doanh nghiệp.
• Giảng viên giảng dạy bộ môn Trí tuệ nhân tạo và Khai phá dữ liệu: Sử dụng toàn bộ cấu trúc luận văn và các bảng đối sánh hiệu năng thuật toán như một nghiên cứu tình huống sinh động phục vụ bài giảng chuyên ngành.

Câu hỏi thường gặp

• Tại sao cần kết hợp Giải thuật di truyền với K-means thay vì sử dụng K-means độc lập?
  K-means chạy nhanh nhưng phụ thuộc nhiều vào tâm ban đầu và dễ rơi vào cực trị địa phương. Giải thuật di truyền cung cấp cơ chế tìm kiếm toàn cục, giúp xác định các tâm cụm tối ưu, từ đó giảm sai số hàm mục tiêu từ 16.8% đến 23.4% và nâng cao độ chính xác phân cụm.

• Cỡ quần thể và số thế hệ dừng tối ưu trong nghiên cứu được xác định như thế nào?
  Qua các vòng chạy thực nghiệm trên dữ liệu đào tạo, cỡ quần thể tối ưu được thiết lập từ 50 đến 80 cá thể và số thế hệ dừng dao động từ 60 đến 100 thế hệ. Cấu hình này bảo đảm độ chính xác hội tụ đạt trên 90% mà vẫn duy trì thời gian thực thi dưới 15 giây.

• Mô hình xử lý dữ liệu nhiễu và các điểm ngoại lai bằng cách nào?
  Nghiên cứu áp dụng quy trình tiền xử lý 4 giai đoạn để làm sạch và chuẩn hóa dữ liệu trước khi phân cụm. Ngoài ra, việc duy trì xác suất đột biến ở mức 0.01 giúp mô hình tự điều chỉnh và hạn chế sự sai lệch do các đối tượng bất thường gây ra.

• Thuật toán có thể mở rộng cho các cơ sở đào tạo quy mô lớn hơn không?
  Mô hình hoàn toàn có khả năng mở rộng. Khi áp dụng cho các trường đại học có quy mô từ 10.000 đến 50.000 sinh viên, hệ thống chỉ cần áp dụng cơ chế mã hóa số thực và tăng cường tài nguyên bộ nhớ đệm để duy trì tốc độ xử lý ổn định.

• Điểm khác biệt cốt lõi giữa phân lớp và phân cụm dữ liệu trong luận văn là gì?
  Phân lớp là học có giám sát đòi hỏi nhãn dữ liệu huấn luyện được định nghĩa trước 100%. Ngược lại, phân cụm trong đề tài là học không giám sát, tự động khám phá các nhóm sinh viên có đặc tính tương đồng mà không cần nhãn mẫu phân loại từ trước.

Kết luận

• Xây dựng thành công thuật toán lai ghép GA-Kmeans, giải quyết triệt để bài toán rơi vào cực trị địa phương của phương pháp phân cụm K-means truyền thống.
• Cải thiện chất lượng phân cụm với giá trị hàm mục tiêu giảm sai số từ 16.8% đến 23.4% so với các giải thuật phân hoạch tiêu chuẩn.
• Triển khai ứng dụng thực nghiệm hiệu quả trên tập dữ liệu 1.250 sinh viên tại Trường Cao đẳng Y tế Yên Bái, nhận diện chính xác 4 nhóm học lực và rèn luyện.
• Đề xuất hệ thống giải pháp ứng dụng công nghệ thông tin giúp giảm 35% nguy cơ sinh viên bị cảnh báo học vụ và nâng cao chất lượng quản lý đào tạo.
• Đóng góp nguồn học liệu tham khảo quan trọng về sự kết hợp giữa giải thuật tiến hóa và khai phá dữ liệu trong lĩnh vực giáo dục.

Công trình nghiên cứu đã khẳng định giá trị thực tiễn to lớn trong việc ứng dụng trí tuệ nhân tạo vào công tác quản trị đại học số. Trong giai đoạn 12 đến 24 tháng tới, việc phát triển thuật toán trên nền tảng điện toán phân tán sẽ là hướng đi triển vọng. Các nhà nghiên cứu, nhà quản lý và kỹ sư phân tích dữ liệu hãy khai thác ngay tài liệu luận văn này để ứng dụng các kỹ thuật phân cụm tối ưu vào thực tế đơn vị.

Trích đoạn nội dung tài liệu

CHƯƠNG 1 TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM DỮ LIỆU 1. Tổng quan về khám phá tri thức và khai phá dữ liệu. Giới thiệu chung về khám phá tri thức và khai phá dữ liệu Nếu cho rằng, điện tử và truyền thông chính là bản chất của khoa học điện tử, thì dữ liệu, thông tin, và tri thức hiện đang là tiêu điểm của một lĩnh vực mới để nghiên cứu và ứng dụng, đó là khám phá tri thức và khai phá dữ liệu [8]. Thông thường, chúng ta coi dữ liệu như là một chuỗi các bits, hoặc các số và các ký hiệu hay là các “đối tượng” với một ý nghĩa nào đó khi được gửi cho một chương trình dưới một dạng nhất định.

Các bits thường được sử dụng để đo thông tin, và xem nó như là dữ liệu đã được loại bỏ phần tử thừa, lặp lại, và rút gọn tới mức tối thiểu để đặc trưng một cách cơ bản cho dữ liệu. Tri thức được xem như là các thông tin tích hợp, bao gồm các sự kiện và mối quan hệ giữa chúng, đã được nhận thức, khám phá, hoặc nghiên cứu. Nói cách khác, tri thức có thể được coi là dữ liệu ở mức độ cao của sự trừu tượng và tổng quát. Khám phá tri thức hay phát hiện tri thức trong CSDL là một quy trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: Phân tích, tổng hợp, hợp thức, khả ích và có thể hiểu được.

Khai phá dữ liệu là một bước trong quá trình khám phá tri thức, gồm các giải thuật khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu. Nói cách khác, mục tiêu của Khai phá dữ liệu là tìm kiếm các mẫu hoặc mô hình tồn tại trong CSDL nhưng ẩn trong khối lượng lớn dữ liệu. Quá trình khám phá tri thức. Quy trình khám phá tri thức tiến hành qua 6 giai đoạn, xem hình 1.

Gom dữ liệu: Tập hợp dữ liệu là bước đầu tiên trong quá trình khai phá dữ liệu. Đây là bước được khai thác trong một cơ sở dữ liệu, một kho dữ liệu và thậm chí các dữ liệu từ các nguồn ứng dụng Web. Trích lọc dữ liệu: Ở giai đọan này dữ liệu được lựa chọn hoặc phân chia theo một số tiêu chuẩn nào đó phục vụ mục đích khai thác, ví dụ chọn tất cả những em học sinh có điểm Trung bình học kỳ lớn hơn 8.0 và có giới tính nữ. Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu: Giai đoạn thứ ba này là giai đoạn hay bị sao lãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình khai phá dữ liệu.

Một số lỗi thường mắc phải trong khi gom dữ liệu là tính không đủ 11 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] chặt chẽ, logíc. Vì vậy, dữ liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối dữ liệu. Ví dụ : Điểm Trung bình = 12. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẻ nói trên.

Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không được “làm sạch – tiền xử lý – chuẩn bị trước” thì sẽ gây nên những kết quả sai lệch nghiêm trọng. Chuyển đổi dữ liệu: Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu đưa ra có thể sử dụng và điều khiển được bởi việc tổ chức lại nó, tức là dữ liệu sẽ được chuyển đổi về dạng phù hợp cho việc khai phá bằng cách thực hiện các thao tác nhóm hoặc tập hợp. Khai phá dữ liệu: Đây là bước mang tính tư duy trong khai phá dữ liệu.

Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng để trích ra các mẫu từ dữ liệu. Thuật toán thường dùng là nguyên tắc phân loại, nguyên tắc kết, v. Đánh giá các luật và biểu diễn tri thức: Ở giai đoạn này, các mẫu dữ liệu được chiết xuất ra bởi phần mềm khai phá dữ liệu. Không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi nó còn bị sai lệch.

Vì vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức (Knowlege) cần chiết xuất ra. Đánh giá sự hữu ích của các mẫu biểu diễn tri thức dựa trên một số phép đo. Sau đó sử dụng các kỹ thuật trình diễn và trực quan hoá dữ liệu để biểu diễn tri thức khai phá được cho người sử dụng.1: Quá trình khám phá tri thức 12 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Quá trình khai phá dữ liệu Khai phá dữ liệu là một giai đoạn quan trọng trong quá trình khám phá tri thức.

Về bản chất là giai đoạn duy nhất tìm ra được thông tin mới, thông tin tiềm ẩn có trong cơ sở dữ liệu chủ yếu phục vụ cho mô tả và dự đoán [8]. Mô tả dữ liệu là tổng kết hoặc diễn tả những đặc điểm 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.2: Quá trình khai phá dữ liệu - Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết. - Xác định các 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. Đây là một quá trình rất khó khăn, có thể gặp phải rất nhiều các vướng mắc như: dữ liệu phải được sao ra nhiều bản (nếu được chiết xuất vào các tệp), quản lý tập các dữ liệu, phải lặp đi lặp lại nhiều lần toàn bộ quá trình (nếu mô hình dữ liệu thay đổi), v. - Thuật toán 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, các mẫu này được biểu diễn dưới dạng luật kết hợp, cây quyết định. tương ứng với ý nghĩa của nó.

Các phương pháp khai phá dữ liệu. Các kỹ thuật KPDL được có thể chia làm 2 nhóm chính [8]: - Kỹ thuật KPDL mô tả: có nhiệm vụ mô tả về các tính chất hoặc các đặc tính chung của dữ liệu trong CSDL hiện có. Nhóm kỹ thuật này gồm các phương pháp: phân nhóm (Clustering), tổng hợp hóa (Summerization), phát hiện sự biến đổi và độ lệch (Change and deviation detection), phân tích luật kết hợp (Association Rules),. 13 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] - Kỹ thuật KPDL dự đoán: có nhiệm vụ đưa ra các dự đoán dựa vào các suy diễn trên dữ liệu hiện thời.

Nhóm kỹ thuật này gồm các phương pháp: phân lớp (Classification), hồi quy (Regression),. Phân lớp và dự đoán (Classification & Prediction) Là đặt các mẫu vào các lớp được xác định trước. Nhiệm vụ chính là tìm các hàm ánh xạ các mẫu dữ liệu một cách chính xác vào trong các lớp.Ví dụ một ngân hàng muốn phân loại các khách hành của họ vào trong hai nhóm có nợ hay không nợ, từ đó giúp họ ra quyết định cho vay hay không cho vay. Quá trình phân lớp dữ liệu thường gồm 2 bước: xây dựng mô hình và sử dụng mô hình để phân lớp dữ liệu.

- Bước 1: một mô hình sẽ được xây dựng dựa trên việc phân tích các mẫu dữ liệu sẵn có. Mỗi mẫu tương ứng với một lớp, được quyết định bởi một thuộc tính gọi là thuộc tính lớ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 đều phải được xác định 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) khác với phân nhóm dữ liệu là học không có giám sát (unsupervised learning).

- Bước 2: sử dụng mô hình để phân lớp dữ liệu. Trước hết chúng ta phải tính độ chính xác của mô hình. Nếu độ chính xác là chấp nhận được, mô hình sẽ được sử dụng để dự đoán nhãn lớp cho các mẫu dữ liệu khác trong tương lai. Trong kỹ thuật phân lớp chúng ta có thể sử dụng các phương pháp như: Cây quyết định (Decision Tree), K-Láng giềng gần nhất (k-Nearest Neighbor), Mạng Nơron (Neural networks), Giải thuật di truyền (Genetic algorithms), Mạng Bayesian (Bayesian networks), Tập mờ và tập thô (Rough and Fuzzy Sets).

Luật kết hợp (Association Rules) Luật kết hợp là dạng luật biểu diễn tri thức ở dạng tương đối đơn giản. Mục tiêu của phương pháp này là phát hiện và đưa ra các mối liên hệ giữa các giá trị dữ liệu trong CSDL. Mẫu đầu ra của giải thuật KPDL là tập luật kết hợp tìm được. Tuy luật kết hợp là một dạng luật khá đơn giản nhưng lại mang rất nhiều ý nghĩa.

Thông tin mà dạng luật này đem lại rất có lợi trong các hệ hỗ trợ ra quyết định. Tìm kiếm được những luật kết hợp đặc trưng và mang nhiều thông tin từ CSDL tác nghiệp là một trong những hướng tiếp cận chính của lĩnh vực khai phá dữ liệu. Khai thác mẫu tuần tự (Sequential / Temporal patterns) Tương tự như khai thác luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Một luật mô tả mẫu tuần tự có dạng tiêu biểu X  Y phản ánh sự xuất hiện của 14 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] biến cố X sẽ dẫn đến việc xuất hiện kế tiếp biến cố Y.

Hướng tiếp cận này có tính dự báo cao. Phân nhóm- đoạn (Clustering / Segmentation) Mục tiêu chính của việc phân nhóm dữ liệu là nhóm các đối tượng tương tự nhau trong tập dữ liệu vào các nhóm sao cho mức độ tương tự giữa các đối tượng trong cùng một nhóm là lớn nhất và mức độ tương tự giữa các đối tượng nằm trong các nhóm khác nhau là nhỏ nhất. Các nhóm có thể tách nhau hoặc phân cấp gối lên nhau và số lượng các nhóm là chưa biết trước. Một đối tượng có thể vừa thuộc nhóm này, nhưng cũng có thể vừa thuộc nhóm khác.