Luận Văn Thạc Sĩ: Phân Cụm Dữ Liệu Và Ứng Dụng Trong Lĩnh Vực Sinh Học Tại Trường THCS Chu Văn An

Luận văn thạc sĩ về : phân cụm dữ liệu & ứng dụng trong sinh học tại trường thcs chu văn a trình bày hệ thống lý thuyết, phương pháp nghiên cứu và

• Tác giả: Trịnh Anh Tuấn
• Người hướng dẫn: TS. Nguyễn Long Giang
• Trường học: Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phân cụm dữ liệu và ứng dụng phân cụm học sinh trường Trung học cơ sở Chu Văn An
• 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
• DANH MỤC CÁC BẢNG
• DANH MỤC CÁC HÌNH
• MỞ ĐẦU
• Sự cần thiết lựa chọn đề tài
• Mục tiêu đề tài
• Đối tượng và phạm vi nghiên cứu
• Phương pháp nghiên cứu
• Cấu trúc của luận văn
• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Quá trình khám phá tri thức
• 1.2. Khai phá dữ liệu
• 1.2.1. Khái niệm khai phá dữ liệu
• 1.2.2. Các kỹ thuật khai phá dữ liệu
• 1.3. Phân cụm dữ liệu
• 1.3.1. Khái niệm về phân cụm dữ liệu
• 1.3.2. Một số vấn đề trong phân cụm dữ liệu
• 1.3.3. Mục tiêu của phân cụm dữ liệu
• 1.3.4. Các bước cơ bản trong phân cụm dữ liệu
• 1.3.5. Yêu cầu của phân cụm dữ liệu
• 1.3.6. Ứng dụng của phân cụm dữ liệu
• 1.4. Kết luận chương
• 2. CHƯƠNG 2: CÁC PHƯƠNG PHÁP PHÂN CỤM DỮ LIỆU
• 2.1. Kiểu dữ liệu
• 2.1.1. Phân loại kiểu dữ liệu dựa trên kích thước miền
• 2.1.2. Phân loại kiểu dữ liệu dựa trên hệ đo
• 2.2. Phép đo độ tương tự và phép đo khoảng cách
• 2.2.1. Khái niệm tương tự và không tương tự
• 2.2.2. Phép đo khoảng cách
• 2.3. Phương pháp phân cụm phân hoạch
• 2.3.1. Giới thiệu phương pháp
• 2.3.2. Thuật toán K-MEANS
• 2.3.3. Thuật toán PAM
• 2.4. Phương pháp phân cụm phân cấp
• 2.4.1. Giới thiệu phương pháp
• 2.4.2. Thuật toán HERACHICAL
• 2.4.3. Thuật toán BIRCH
• 2.5. Phương pháp phân cụm dựa trên mật độ
• 2.5.1. Giới thiệu phương pháp
• 2.5.2. Thuật toán DBSCAN
• 2.6. Phương pháp phân cụm dựa trên lưới
• 2.6.1. Giới thiệu phương pháp
• 2.6.2. Thuật toán STING
• 2.7. Kết luận chương
• 3. CHƯƠNG 3: PHÂN CỤM KẾT QUẢ HỌC TẬP TẠI TRƯỜNG TRUNG HỌC CƠ SỞ CHU VĂN AN
• 3.1. Bài toán phân cụm kết quả học tập của học sinh tại trường Trung học cơ sở Chu Văn An
• 3.1.1. Giới thiệu trường Trung học cơ sở Chu Văn An
• 3.1.2. Bảng dữ liệu kết quả học tập của học sinh
• 3.1.3. Bài toán phân cụm kết quả học tập của học sinh
• 3.2. Lựa chọn phương pháp, công cụ
• 3.2.1. Lựa chọn ngôn ngữ R thực hiện phân cụm
• 3.2.2. Các bước thực hiện phân cụm bằng ngôn ngữ R
• 3.3. Kết quả phân cụm bằng thuật toán K-means
• 3.3.1. Phân cụm học sinh dựa trên kết quả học tập
• 3.3.2. Phân cụm học sinh dựa trên điểm trung bình các môn
• 3.3.3. Phân cụm dựa trên điểm trung bình môn toán và môn văn
• 3.4. Kết luận chương
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu tổng quan về khai phá dữ liệu và phân cụm dữ liệu

Chương này trình bày tổng quan về quá trình khám phá tri thức từ dữ liệu, khai phá dữ liệu và bài toán phân cụm trong khai phá dữ liệu. Khai phá dữ liệu (Data mining) là quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong các cơ sở dữ liệu lớn. Phân cụm dữ liệu (PCDL) là một kỹ thuật trong khai phá dữ liệu nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn. Mục tiêu của phân cụm là nhóm các đối tượng tương tự nhau trong cơ sở dữ liệu vào các cụm sao cho các đối tượng trong cùng một cụm là tương đồng, còn các đối tượng thuộc các cụm khác nhau sẽ không tương đồng. Phân cụm dữ liệu có nhiều ứng dụng trong thực tiễn như phân đoạn thị trường, phân loại học sinh, và hỗ trợ ra quyết định trong giáo dục.

1.1. Khái niệm khai phá dữ liệu

Khai phá dữ liệu là một lĩnh vực quan trọng trong công nghệ thông tin, liên quan đến nhiều ngành khoa học khác nhau như hệ cơ sở dữ liệu, thống kê, và học máy. Các kỹ thuật khai phá dữ liệu bao gồm học có giám sát, học không có giám sát, và học nửa giám sát. Mỗi kỹ thuật có những ứng dụng và ưu điểm riêng, giúp phát hiện tri thức từ dữ liệu lớn. Việc áp dụng khai phá dữ liệu trong các lĩnh vực như tài chính, y tế, và giáo dục đã chứng minh tính hiệu quả và giá trị thực tiễn của nó.

1.2. Quá trình khám phá tri thức

Quá trình khám phá tri thức bao gồm các bước như trích chọn dữ liệu, tiền xử lý dữ liệu, biến đổi dữ liệu, khai phá dữ liệu, và đánh giá tri thức. Mỗi bước đều có vai trò quan trọng trong việc đảm bảo chất lượng và tính chính xác của thông tin được khai thác. Đặc biệt, việc tiền xử lý dữ liệu giúp loại bỏ nhiễu và các giá trị không đầy đủ, từ đó nâng cao độ tin cậy của kết quả khai phá. Quá trình này không chỉ giúp phát hiện các mẫu thông tin mà còn hỗ trợ ra quyết định trong nhiều lĩnh vực khác nhau.

II. Các phương pháp phân cụm dữ liệu

Chương này trình bày các phương pháp phân cụm dữ liệu, bao gồm phân cụm phân hoạch, phân cụm phân cấp, và phân cụm dựa trên mật độ. Mỗi phương pháp có những ưu điểm và nhược điểm riêng, phù hợp với từng loại dữ liệu và mục tiêu phân tích. Phân cụm phân hoạch sử dụng thuật toán K-means để nhóm các đối tượng thành các cụm dựa trên khoảng cách. Phân cụm phân cấp cho phép xây dựng cấu trúc phân cấp giữa các cụm, trong khi phân cụm dựa trên mật độ như DBSCAN giúp phát hiện các cụm có hình dạng phức tạp. Việc lựa chọn phương pháp phù hợp là rất quan trọng để đạt được kết quả phân cụm chính xác.

2.1. Phân cụm phân hoạch

Phân cụm phân hoạch là một trong những phương pháp phổ biến nhất trong khai phá dữ liệu. Thuật toán K-means là một ví dụ điển hình, hoạt động bằng cách phân chia dữ liệu thành K cụm dựa trên khoảng cách giữa các đối tượng. Phương pháp này dễ hiểu và dễ triển khai, nhưng có nhược điểm là cần xác định số lượng cụm K trước khi thực hiện. Điều này có thể dẫn đến kết quả không chính xác nếu K không được chọn đúng. Tuy nhiên, K-means vẫn được sử dụng rộng rãi nhờ vào tính hiệu quả và khả năng xử lý dữ liệu lớn.

2.2. Phân cụm phân cấp

Phân cụm phân cấp là phương pháp xây dựng cấu trúc phân cấp giữa các cụm, cho phép người dùng dễ dàng quan sát mối quan hệ giữa các cụm. Thuật toán phân cấp có thể chia thành hai loại: phân cụm từ dưới lên (agglomerative) và từ trên xuống (divisive). Phương pháp này rất hữu ích trong việc phân tích dữ liệu có cấu trúc phức tạp, nhưng thường tốn nhiều thời gian tính toán. Việc sử dụng phân cụm phân cấp giúp người dùng có cái nhìn tổng quan về dữ liệu và dễ dàng nhận diện các mẫu tiềm ẩn.

III. Phân cụm kết quả học tập tại trường Trung học cơ sở Chu Văn An

Chương này tập trung vào việc áp dụng các phương pháp phân cụm để phân tích kết quả học tập của học sinh tại trường Trung học cơ sở Chu Văn An. Dữ liệu được thu thập từ bảng điểm của học sinh, và các phương pháp phân cụm như K-means và phân cụm phân cấp được áp dụng để nhóm học sinh theo kết quả học tập. Kết quả phân tích cho thấy có sự khác biệt rõ rệt giữa các nhóm học sinh, từ đó giúp giáo viên có thể đưa ra các biện pháp hỗ trợ học tập phù hợp. Việc phân cụm không chỉ giúp đánh giá kết quả học tập mà còn hỗ trợ trong việc phát triển chương trình giảng dạy.

3.1. Giới thiệu trường Trung học cơ sở Chu Văn An

Trường Trung học cơ sở Chu Văn An là một trong những cơ sở giáo dục nổi bật tại thành phố Thái Nguyên. Trường có đội ngũ giáo viên chất lượng và cơ sở vật chất hiện đại, tạo điều kiện thuận lợi cho việc học tập của học sinh. Việc áp dụng công nghệ thông tin trong giáo dục tại trường đã giúp nâng cao hiệu quả giảng dạy và học tập. Dữ liệu về kết quả học tập của học sinh được thu thập và lưu trữ một cách hệ thống, tạo cơ sở cho việc phân tích và đánh giá.

3.2. Kết quả phân cụm học sinh

Kết quả phân cụm học sinh dựa trên điểm trung bình các môn học cho thấy có sự phân hóa rõ rệt giữa các nhóm học sinh. Các nhóm học sinh có kết quả học tập tốt, trung bình và yếu được xác định, từ đó giúp giáo viên có thể đưa ra các biện pháp can thiệp kịp thời. Việc phân tích này không chỉ giúp nâng cao chất lượng giáo dục mà còn tạo điều kiện cho học sinh phát triển toàn diện. Kết quả phân cụm cũng cho thấy mối liên hệ giữa kết quả học tập và các yếu tố khác như hoàn cảnh gia đình và giới tính.

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

Chương 1: Giới thiệu tổng quan về khai phá dữ liệu và phân cụm dữ liệu. Chương 2: Trình bày một số phƣơng pháp và thuật toán phân cụm dữ liệu, bao gồm phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ, phân cụm dựa trên lƣới, phân cụm dựa trên mô hình, phân cụm mờ… Chương 3: Trình bày kết quả thử nghiệm một số thuật toán phân cụm để giải quyết bài toán phân cụm học sinh trƣờng Trung học cơ sở Chu Văn An, bao gồm phát biểu bài toán, lựa chọn thuật toán, công cụ phát triển (lập trình, cơ sở dữ liệu), đánh giá kết quả thử nghiệm. Phần kết luận: Tóm tắt các kết quả đạt đƣợc và hƣớng phát triển tiếp của đề tài. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 4 Chƣơng 1.

TỔNG QUAN Chƣơng này giới thiệu tổng quan về quá trình khám phá tri thức từ dữ liệu, khai phá dữ liệu và bài toán phân cụm trong khai phá dữ liệu. Quá trình khám phá tri thức Cùng với sự phát triển vƣợt bậc của các công nghệ điện tử và truyền thông đã làm cho khả năng thu thập, lƣu trữ và xử lý dữ liệu cho các hệ thống tin học không ngừng nâng cao. Bên cạnh đó, việc tin học hoá nhiều lĩnh vực của cuộc sống đã tạo ra cho chúng ta một kho dữ liệu khổng lồ. Quá trình khám phá tri thức trong Cơ sở dữ liệu (Knowledge Discovery in Databases) đang là một vấn đề thời sự của nền công nghệ thông tin thế giới hiện nay.

Nó đƣợc ứng dụng vào nhiều lớp bài toán thực tế khác nhau và thu đƣợc nhiều thành quả to lớn. Khám phá tri thức trong cơ sở dữ liệu là một quá trình nhận biết đúng đắn, mới, hữu ích và cuối cùng là có thể hiểu đƣợc mẫu hoặc mô hình trong dữ liệu. Quá trình khám phá tri thức có thể bao gồm các bƣớc nhƣ Hình 1.1 [7] Trích chọn Tiền xử lý Biến đổi Dữ liệu dữ liệu dữ liệu dữ liệu thô Tri thức Đánh giá và Khai phá giải thích dữ liệu Hình 1. Quá trình khám phá tri thức - Trích chọn dữ liệu: Là bƣớc trích chọn những tập dữ liệu cần đƣợc khai phá từ tập dữ liệu lớn ban đầu theo một tiêu chí nhất định.

Đây là bƣớc quan trọng để rút ra những tri thức hữu ích và chọn phƣơng pháp khai phá dữ liệu phù hợp với mục đích ứng dụng và bản chất dữ liệu. - Tiền xử lý dữ liệu: Là bƣớc làm sạch dữ liệu: lựa chọn dữ liệu nguồn, loại bỏ các dữ liệu nhiễu hoặc ngoại lai, xử lý các giá trị không đầy đủ, biến đổi và rút gọn dữ liệu, sửa các lỗi mang tính hệ thống, tập hợp các thông tin cần Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 5 thiết để mô hình hoặc tính toán nhiễu, quyết định các chiến lƣợc xử lý các trƣờng dữ liệu bị lỗi. Sau bƣớc này dữ liệu sẽ nhất quán, đầy đủ, đƣợc rút gọn và đƣợc rời rạc hoá. - Biến đổi dữ liệu: Đây là bƣớc chuẩn hoá và làm mịn dữ liệu để đƣa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho kỹ thuật khai phá ở bƣớc sau.

- Khai phá dữ liệu: Áp dụng các kỹ thuật phân tích nhằm để khai thác dữ liệu, trích chọn các mẫu ẩn hoặc mô hình trong dữ liệu. Một mô hình có thể xem nhƣ là một biểu diễn tổng thể của cấu trúc nhằm tóm lƣợc các thành phần mang tính hệ thống có trong dữ liệu hoặc mô tả dữ liệu phát sinh. Ngƣợc lại, một mẫu là một cấu trúc cục bộ có khi chỉ liên quan tới một nhóm các biến và một số trƣờng hợp. - Đánh giá và biểu diễn tri thức: Những mẫu thông tin và mối liên hệ trong dữ liệu đã đƣợc khám phá ở bƣớc trên đƣợc chuyển dạng và đƣợc biểu diễn ở một dạng gần gũi với ngƣời sử dụng, đồng thời đánh giá những tri thức khám phá đƣợc theo những tiêu chí nhất định.

Đặc biệt là làm sáng tỏ các mô tả và dự đoán, hai mục tiêu chính của các hệ thống khám phá trong thực tế. Kinh nghiệm cho thấy rằng các mẫu hoặc mô hình phát hiện đƣợc từ các dữ liệu không phải lúc nào cũng đáng quan tâm và có thể trực tiếp sử dụng đƣợc ngay, quy trình khám phá tri thức đƣợc lặp đi lặp lại có điều chỉnh theo các tri thức phát hiện đƣợc. Để đánh giá đƣợc các luật áp dụng trong quy trình khám phá tri thức, dữ liệu thƣờng đƣợc chia thành hai tập, huấn luyện trên tập thứ nhất và kiểm chứng trên tập thứ hai. Có thể lặp lại quy trình này với một số lần với các phần chia khác nhau, sau đó lấy trung bình các kết quả để ƣớc lƣợng các luật thi hành.

Khai phá dữ liệu 1. Khái niệm khai phá dữ liệu Khai phá dữ liệu (Data mining) là quá trình tìm kiếm, phát hiện các tri thức mới, tiềm ẩn, hữu dụng trong các cơ sở dữ liệu lớn, các kho dữ liệu.Các kết quả Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 6 khoa học cùng những thành công trong khám phá tri thức cho thấy khai phá dữ liệu là một lĩnh vực mang lại nhiều lợi ích và có triển vọng, có ƣu thế hơn hẳn so với các công cụ phân tích dữ liệu truyền thống. Khai phá dữ liệu là một lĩnh vực có liên quan đến rất nhiều ngành khoa học khác nhƣ: Hệ cơ sở dữ liệu, thống kê, học máy, trực quan hoá.Tuỳ vào cách tiếp cận đƣợc sử dụng thì khai phá dữ liệu còn áp dụng một số kỹ thuật khác nhƣ mạng nơron, lý thuyết tập thô hoặc tập mờ, biểu diễn tri thức .So với các phƣơng pháp này, khai phá dữ liệu có một số ƣu thế rõ rệt. So với phƣơng pháp học máy, khai phá dữ liệu có thể sử dụng dữ liệu có nhiều nhiễu, dữ liệu không đầy đủ hoặc biến đổi liên tục.

Trong khi đó, phƣơng pháp học máy đòi hỏi tập dữ liệu phải đầy đủ, ít biến động và không quá lớn. Phƣơng pháp hệ chuyên gia, các ví dụ của chuyên gia thƣờng phải đòi hỏi chất lƣợng cao hơn nhiều so với dữ liệu trong cơ sở dữ liệu. Phƣơng pháp thống kê là một trong những nền tảng lý thuyết của khai phá dữ liệu nhƣng khai phá dữ liệu đã khắc phục đƣợc một số tồn tại của phƣơng pháp thống kê nhƣ: Các phƣơng pháp thống kê chuẩn không phù hợp với các kiểu dữ liệu có cấu trúc trong rất nhiều kiểu cơ sở dữ liệu, nó hoạt động hoàn toàn theo dữ liệu, nó không sử dụng tri thức sẵn có của lĩnh vực, kết quả phân tích của thống kê rất nhiều và khó có thể làm rõ đƣợc, phƣơng pháp thống kê cần có sự hƣớng dẫn của ngƣời dùng để xác định phân tích dữ liệu nhƣ thế nào và ở đâu. Với những ƣu điểm đó, khai phá dữ liệu đang đƣợc áp dụng vào nhiều lĩnh vực nhƣ tài chính, ngân hàng, bảo hiểm, y tế, an ninh, internet.Các công ty phần mềm lớn trên thế giới cũng đã rất quan tâm chú trọng việc nghiên cứu và phát triển các kỹ thuật khai phá dữ liệu: Oracle tích hợp các công cụ khai phá dữ liệu vào bộ Oracle9i, IBM phát triển khai phá dữ liệu với các ứng dụng nhƣ Intelligence Miner…[5].

Các kỹ thuật khai phá dữ liệu Nếu đứng trên quan điểm của học máy (Machine learning) thì kỹ thuật khai phá dữ liệu bao gồm: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn 7 - Học có giám sát (supervised learning): là quá trình gán nhãn lớp cho các phần tử trong cơ sở dữ liệu dựa trên một tập các ví dụ huấn luyện và các thông tin về nhãn lớp đã biết. Đây là một kỹ thuật của ngành học máy để xây dựng một hàm từ dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm các cặp gồm đối tƣợng đầu vào và đầu ra mong muốn. Đầu ra của một hàm có thể là một giá trị liên tục (gọi là hồi qui), hay có thể là dự đoán một nhãn phân loại cho một đối tƣợng đầu vào (gọi là phân loại).

Nhiệm vụ của chƣơng trình học có giám sát là dự đoán giá trị của hàm cho một đối tƣợng bất kì là đầu vào hợp lệ, sau khi đã xem xét một số ví dụ huấn luyện (các cặp đầu vào và đầu ra tƣơng ứng). Để đạt đƣợc điều này, chƣơng trình học phải tổng quát hóa từ các dữ liệu sẵn có để dự đoán đƣợc những tình huống chƣa gặp phải theo một cách “hợp lý”. - Học không có giám sát (unsupervised learning): là quá trình phân chia một tập dữ liệu thành các lớp hay là cụm (clustering) dữ liệu tƣơng tự nhau mà chƣa biết trƣớc các thông tin về lớp một phƣơng pháp của ngành học máy nhằm tìm ra một mô hình mà phù hợp với các quan sát. Nó khác biệt với học có giám sát ở chỗ là đầu ra đúng tƣơng ứng cho mỗi đầu vào là không biết trƣớc.

Trong học không có giám sát, một tập dữ liệu đầu vào đƣợc thu thập. Học không có giám sát thƣờng đối xử với các đối tƣợng đầu vào nhƣ là một tập các biến ngẫu nhiên. Sau đó, một mô hình mật độ kết hợp sẽ đƣợc xây dựng cho tập dữ liệu đó [4]. - Học nửa giám sát (semi-supervised learning): là quá trình phân chia một tập dữ liệu thành các lớp dựa trên một tập dữ liệu nhỏ các ví dụ huấn luyện và một số các thông tin về một số nhãn lớp đã biết trƣớc.

Nếu căn cứ vào lớp các bài toán cần giải quyết thì kỹ thuật khai phá dữ liệu gồm các kỹ thuật sau: - Kỹ thuật khai phá dữ liệu 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 cơ sở dữ liệu hiện có. Các kỹ thuật loại này gồm có: Phân cụm (Clustering), tóm tắt (Summarization), trực quan hoá Số hóa bởi Trung tâm Học liệu – ĐHTN http://www. - Kỹ thuật khai phá dữ liệu 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 tại. Các kỹ thuật loại này gồm có: Phân lớp (Classification), hồi quy (Regression),.

Phân cụm dữ liệu 1. Khái niệm về phân cụm dữ liệu Phân cụm dữ liệu (PCDL) là một kỹ thuật trong khai phá dữ liệu nhằm tìm kiếm, phát hiện các cụm, các mẫu dữ liệu tự nhiên tiềm ẩn, quan tâm trong tập dữ liệu lớn, từ đó cung cấp thông tin hữu ích cho việc ra quyết định.