Nghiên cứu một số thuật toán phân cụm dữ liệu và ứng dụng hỗ trợ đánh giá thi đua tại trường THPT Bình Sơn
Lý do chọn đề tài
Cải cách hành chính nhà nước là một nhiệm vụ mà Đảng và Nhà nước rất coi trọng trong giai đoạn hiện nay. Trong đó công tác thi đua khen thưởng có vị trí vai trò, ý nghĩa rất quan trọng, là động lực thúc đẩy kinh tế- xã hội phát triển, là biện pháp để người quản lý thực hiện nhiệm vụ chính trị, chuyên môn của đơn vị.
Mục đích của công tác đánh giá thi đua, khen thưởng là nhằm động viên, giáo dục, nêu gương để sau khi được biểu dương, khen thưởng thì tập thể, cá nhân được khen sẽ phát huy tính tích cực trong công việc được giao. Người chưa được khen cũng thấy được trách nhiệm và nghĩa vụ của mình, cần phải phấn đấu để được ghi nhận trong thời gian tới.
Trong những năm gần đây, tại các trường trung học phổ thông (THPT) ở tỉnh Quảng Ngãi việc ứng dụng công nghệ thông tin trong công tác giảng dạy và quản lý ngày càng được áp dụng rộng rãi. Hạ tầng kỹ thuật được đầu tư, nâng cấp hoàn thiện hơn. Các ứng dụng, cơ sở dữ liệu đã được xây dựng đưa vào khai thác và sử dụng. Thế nhưng hiệu quả mang lại từ việc ứng dụng chưa cao, ứng dụng còn thiếu và chưa đồng bộ. Trong công tác quản lý nói chung và khâu quản lý thi đua, khen thưởng nói riêng chưa có sự trợ giúp đáng kể của công nghệ thông tin. Thông tin phục vụ cho công tác thi đua còn thiếu, dẫn đến việc xử lý công việc chậm trễ, đôi lúc chưa đạt hiệu quả cao. Bên cạnh đó thì việc đánh giá thi đua, khen thưởng còn mang tính hình thức, tính công bằng trong công tác đánh giá thi đua chưa rõ ràng. Có những người có nhiều đóng góp, có nhiều thành tích nhưng không được đánh giá tốt còn những người ít thành tích hơn được đánh giá tốt dẫn đến có sự “so bì” giữa nhóm giáo viên này với nhóm giáo viên khác.
Nhận thức được tầm quan trọng của việc đánh giá thi đua, khen thưởng, nên cần phải ứng dụng Công nghệ thông tin (CNTT) trong công tác này để mang lại hiệu quả tốt nhất.
Tuy nhiên hiện nay việc quản lý thông tin về cán bộ, công chức trong các cơ quan nhà nước nói chung, công tác thi đua, khen thưởng nói riêng là một bài toán quan trọng và nhạy cảm, nó phục vụ cho việc quản lý nguồn nhân lực, chính sách cán bộ, nhằm giúp lãnh đạo đưa ra các quyết định khen thưởng cán bộ, công chức. Thế nhưng công việc này đòi hỏi mất rất nhiều thời gian và phải hoàn thành đúng thời gian quy định, và cần nhất là “sự công bằng” trong công tác thi đua khen thưởng. Các tài liệu của công tác này được lưu trữ trên giấy và có đơn vị tính điểm thi đua “bằng tay” nên mất nhiều thời gian trong tra cứu, thống kê báo cáo và định lượng của những người xét thi đua, khen thưởng có thế mang tính chủ quan.
Hiện nay, trên thị trường cũng đã có những công cụ hỗ trợ công tác về quản lý thi đua, khen thưởng, nhưng mang tính thương mại với giá thành cao, và chủ yếu là quản lý công tác thi đua khen thưởng của đơn vị chứ chưa phân nhóm được đối tượng thi đua của các đơn vị để tạo sự công bằng trong công tác thi đua. Nhà trường không đủ kinh phí để mua, còn công cụ miễn phí thì không đáp ứng được các tiêu chí thi đua của nhà trường đã quy định.
Khi xét thi đua, khen thưởng cần phải đánh giá thành tích của cá nhân trong cơ quan bằng những giá trị định lượng cụ thể, trong đó có việc theo dõi quá trình công tác và đưa ra nhận xét bằng ngôn ngữ tự nhiên, nhằm phân tích, đánh giá thông tin từ các câu nhận xét là những ngôn tự nhiên, ngôn ngữ nói của lãnh đạo cơ quan về thi đua, và đặc biệt là phân nhóm được các đối tượng thi đua nhằm tạo sự minh bạch, công bằng trong công tác thi đua, khen thưởng. Trong quá trình học tập tôi nhận thấy khai phá dữ liệu là một bộ môn hữu ích vì có hỗ trợ các thuật toán phân lớp, phân cụm dữ liệu (phân cụm dữ liệu rõ và phân cụm dữ liệu mờ). Từ đó xây dựng hệ thống phân nhóm đối tượng thi đua nhằm hỗ trợ cho lãnh đạo đơn vị và hội đồng thi đua của nhà trường có cái nhìn tổng quan và phân nhóm được các đối tượng để hỗ trợ trong công tác đánh giá thi đua tạo sự công bằng trong công tác thi đua của đơn vị.
Với đề tài này tôi hi vọng nhà trường sẽ có một công cụ hỗ trợ đắc lực và hữu hiệu trong công tác quản lý, phân loại thi đua và nhằm tạo cho giáo viên có sự so sánh công bằng trong công tác thi đua của nhà trường.
Xuất phát từ những nhu cầu thực tế nêu trên, cần thiết phải có công cụ hỗ trợ cho công tác đánh giá thi đua cho nhà trường. Qua quá trình tìm hiểu, nghiên cứu nội dung chương trình đã học và được sự đồng ý của Thầy PGS.TS Võ Trung Hùng, tôi đã chọn đề tài: “Nghiên cứu một số thuật toán phân cụm dữ liệu và ứng dụng hỗ trợ đánh giá thi đua tại trường THPT Bình Sơn, Quảng Ngãi”.
Mục tiêu và nhiệm vụ đề tài
Biết được khai phá dữ liệu là gì, phân cụm dữ liệu thường được ứng dụng trong lĩnh vực nào, tìm hiểu các kỹ thuật phân cụm dữ liệu đã được nghiên cứu, biết về logic mờ và thuật toán phân cụm dữ liệu mờ để ứng dụng vào phân cụm dữ liệu thi đua.
Viết hàm hỗ trợ phân cụm những giáo viên có thành tích thi đua tương đồng nhau từ những nhận xét của bộ phận theo dõi thi đua tại trường THPT Bình Sơn, Quảng Ngãi.
Tìm hiểu kiến thức về phân cụm dữ liệu, tìm hiểu về lý thuyết mờ và thuật toán phân cụm dữ liệu rõ K-Means và thuật toán phân cụm dữ liệu mờ Fuzzy C-Means (FCM).
Tìm hiểu về công tác thi đua ở trường trung học phổ thông, cơ sở để thu thập thông tin, thu thập được dữ liệu thi đua của nhà trường và ứng dụng được thuật toán phân cụm dữ liệu mờ FCM vào viết hàm hỗ trợ phân cụm những giáo viên có thành tích thi đua tương đồng nhau từ những nhận xét của bộ phận theo dõi thi đua tại trường THPT Bình Sơn, Quảng Ngãi.
Viết được các hàm trên phần mềm MATLAB nhằm ứng dụng phân cụm dữ liệu thi đua tại trường THPT Bình Sơn, Quảng Ngãi
Đối tượng và phạm vi nghiên cứu
3.1 Đối tượng nghiên cứu
Nghiên cứu lý thuyết về phân cụm dữ liệu, các kỹ thuật phân cụm dữ liệu, cách xây dựng dữ liệu trong phân cụm dữ liệu. Nghiên cứu về lý thuyết mờ, cách mờ hóa dữ liệu và các thuật toán phân cụm dữ liệu K-Means và FCM
Các văn bản hướng dẫn về thi đua, khen thưởng cán bộ, công chức và văn bản hướng dẫn thi đua, khen thưởng của Bộ Giáo dục và Sở Giáo dục và Đào tạo Quảng Ngãi
Nghiên cứu ngôn ngữ lập trình MATLAB để xây dựng các hàm hỗ trợ phân cụm.
3.2 Phạm vi nghiên cứu
Nghiên cứu tổng quan về lý thuyết PCDL, lý thuyết tập mờ, các phép toán trên tập mờ và tập trung nghiên cứu về thuật toán Fuzzy C-Means để phân loại trong đánh giá thi đua của trường THPT Bình Sơn, Quảng Ngãi.
Dữ liệu phục vụ cho việc đánh giá thi đua của trường THPT Bình Sơn, Quảng Ngãi.
Phương pháp nghiên cứu
Tìm hiểu tài liệu về phân cụm dữ liệu, lý thuyết mờ và lựa chọn thuật toán phân cụm dữ liệu thích hợp với yêu cầu của bài toán đưa ra, thu thập tài liệu về thi đua, khen thưởng.
Xây dựng các hàm hỗ trợ phân cụm dữ liệu thi đua tại trường THPT Bình Sơn, Quảng Ngãi trên phần mềm MATLAB.
Phân tích độ tương đồng của dữ liệu đã được phân cụm.
Mục đích và ý nghĩa của đề tài
Nghiên cứu tổng quan về phân cụm dữ liệu, lý thuyết mờ, các thuật toán phân cụm dữ liệu K-Means, Fuzzy C-Means để phân nhóm các đối tượng thi đua có cùng tính chất trong đơn vị để hỗ trợ cho lãnh đạo và hội đồng thi đua có cơ sở đánh giá thi đua giữa các cá nhân, tạo sự công bằng trong công tác đánh giá thi đua.
5.2 Ý nghĩa khoa học và thực tiễn đề tài
Về khoa học: Áp dụng các thuật toán phân cụm dữ liệu trong khai phá dữ liệu trên dữ liệu về thi đua khen thưởng.
Về thực tiễn: Phân nhóm các đối tượng có cùng tính chất về thi đua, khen thưởng trong đơn vị hỗ trợ lãnh đạo ở các trường phổ thông quyết định hình thức thi đua, khen thưởng của nhân viên tạo sự minh bạch, công bằng trong công tác thi đua, khen thưởng.
Bố cục của luận văn
Sau phần mở đầu, giới thiệu,…nội dung chính của luận văn được chia làm 3 chương như sau:
Chương 1: Tổng quan về phân cụm dữ liệu
Trong chương này của đề tài chủ yếu trình bày lý thuyết cơ bản về phân cụm dữ liệu như: khái niệm, ứng dụng của phân cụm, các kỹ thuật phân cụm dữ liệu, các yêu cầu về phân cụm dữ liệu, các kiểu dữ liệu và một số độ đo cơ bản trong phân cụm dữ liệu.
Chương 2: Lý thuyết mờ và một số thuật toán phân cụm dữ liệu
Nội dung chương này trình bày lý thuyết về tập mờ để có cơ sở làm mờ hóa biến ngôn ngữ khi xây dựng ma trận dữ liệu phân hoạch trong thuật toán FCM để phân cụm dữ liệu thực tế ở chương 3.
Trình bày tổng quan về phân cụm mờ và một số thuật toán phân cụm dữ liệu, đặc biệt nghiên cứu sâu về thuật toán FCM của giáo sư Bezdek.
Chương 3: Phát triển ứng dụng và thử nghiệm
Nội dung chương này trình bày về khái niệm thi đua, quản lý nhà nước về thi đua và đưa ra bài toán thực tế và yêu cầu giải quyết bài toán. Xây dựng công cụ hỗ trợ giải quyết bài toán trên phần mềm MATLAB, thực nghiệm phân cụm trên bộ dữ liệu thực.
Kết luận và hướng phát triển
CHƯƠNG 1: TỔNG QUAN VỀ PHÂN CỤM DỮ LIỆU
1.1. Khái niệm và mục tiêu của phân cụm dữ liệu
Phân cụm dữ liệu là quá trình nhóm một tập hợp các đối tượng tương tự nhau trong một tập dữ liệu vào các cụm sao cho các đối tượng thuộc 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 là một ví dụ của phương pháp học không giám sát. Không giống như phân lớp dữ liệu, phân cụm dữ liệu không đòi hỏi phải định nghĩa trước các mẫu dữ liệu huấn luyện. Vì thế, có thể coi phân cụm dữ liệu là một cách học bằng quan sát, trong khi phân lớp dữ liệu học bằng ví dụ…
Ngoài ra, phân cụm dữ liệu (PCDL) còn có thể được sử dụng như một bước tiền xử lý cho các thuật toán khai phá dữ liệu và khám phá các tri thức [4] khác như là phân loại và mô tả đặc điểm, có tác dụng trong việc phát hiện ra các cụm.
Kỹ thuật phân cụm được áp dụng trong rất nhiều lĩnh vực như khai phá dữ liệu, nhận dạng mẫu, xử lý ảnh,…
Với tư cách là một chức năng khai phá dữ liệu, phân tích phân cụm có thể được sử dụng như một công cụ độc lập chuẩn để quan sát đặc trưng của mỗi cụm thu được bên trong sự phân bố của dữ liệu và tập trung vào một tập riêng biệt của các cụm để giúp cho việc phân tích đạt kết quả. Thuật toán phân cụm có nhiều dạng khác nhau [3], [4], [5] từ phân cụm rõ đơn thuần như K-Means [2] và phát triển đến thuật toán phân cụm mờ Fuzzy C-Means (Bezdek, 1981) [7][9].
Theo các nghiên cứu cho thấy thì hiện nay chưa có một phương pháp phân cụm tổng quát nào có thể giải quyết trọn vẹn cho tất cả các dạng cấu trúc dữ liệu. Hơn nữa, các phương pháp phân cụm cần có cách thức biểu diễn cấu trúc của các dữ liệu, với mỗi cách thức biểu diễn khác nhau sẽ có tương ứng một thuật toán phân cụm phù hợp. Vì vậy phân cụm dữ liệu vẫn đang là một vấn đề khó và mở, vì chúng ta phải giải quyết nhiều vấn đề cơ bản một cách trọn vẹn và phù hợp với nhiều dạng dữ liệu khác nhau, đặc biệt là đối với dữ liệu hỗn hợp đang ngày càng tăng trong các hệ quản trị dữ liệu và đây cũng là một trong những thách thức lớn trong lĩnh vực khai phá dữ liệu.
1.2. Các ứng dụng của phân cụm dữ liệu
PCDL là một trong những công cụ chính của KPDL được ứng dụng trong nhiều lĩnh vực như thương mại và khoa học. Các kỹ thuật PCDL đã được áp dụng cho một số ứng dụng điển hình trong các lĩnh vực sau:
- Thương mại: Các thương nhân, doanh nghiệp dựa vào phân cụm dữ liệu để phân các nhóm khách hàng có các đặc trưng tương đồng nhau và đặc tả họ từ các mẫu mua bán trong CSDL khách hàng để có chiến lượt đối với từng đối tượng nhóm khách hàng.
- Sinh học: PCDL được sử dụng để xác định các loại sinh vật, phân loại các Gen với chức năng tương đồng và thu được các cấu trúc trong các mẫu.
- Thư viện: Phân loại các cụm sách có nội dung và ý nghĩa tương đồng nhau để hỗ trợ cho độc giả.
- Y học: Phân cụm các loại triệu chứng có tính chất tương đồng gần với các triệu chứng bệnh lí của các loại bệnh nhằm hỗ trợ trong công tác chuẩn đoán, hay phân nhóm các loại thuốc có dược tính tương đồng.
- Lập quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lý,… nhằm cung cấp thông tin cho quy hoạch đô thị.
- Nghiên cứu trái đất: Phân cụm để theo dõi các tâm động đất nhằm cung cấp thông tin cho nhận dạng các vùng nguy hiểm.
- Địa lý: Phân lớp vị trí sinh sống của động vật, thực vật và đưa ra đặc trưng của chúng.
- Khai phá Web: PCDL có thể khám phá các nhóm tài liệu quan trọng, có nhiều ý nghĩa trong môi trường Web. Các lớp tài liệu này trợ giúp cho việc khám phá tri thức từ dữ liệu Web, khám phá ra các mẫu truy cập của khách hàng đặc biệt hay khám phá ra cộng đồng Web,…
1.3. Các yêu cầu và những vấn đề tồn tại trong phân cụm dữ liệu
Việc xây dựng, lựa chọn một thuật toán phân cụm là bước then chốt cho việc giải quyết vấn đề phân cụm, sự lựa chọn này phụ thuộc vào đặc tính dữ liệu cần phân cụm, mục đích của ứng dụng thực tế hoặc xác định độ ưu tiên giữa chất lượng của các cụm hay tốc độ thực hiện thuật toán,…
Hầu hết các nghiên cứu và phát triển thuật toán PCDL đều nhằm thoả mãn các yêu cầu cơ bản sau:
- Có khả năng mở rộng.
- Thích nghi với các kiểu dữ liệu khác nhau.
- Khám phá ra các cụm với hình thù bất kỳ:
- Tối thiểu lượng tri thức cần cho xác định các tham số vào.
- Ít nhạy cảm với thứ tự của dữ liệu và.
- Khả năng thích nghi với dữ liệu nhiễu cao.
- Ít nhạy cảm với các tham số đầu vào.
- Thích nghi với dữ liệu đa chiều.
- Dễ hiểu, dễ cài đặt và khả thi.
1.4. Những kỹ thuật tiếp cận trong phân cụm dữ liệu
1.4.1 Phương pháp phân cụm phân hoạch
1.4.2 Phương pháp phân cụm phân cấp
1.4.3 Phương pháp phân cụm dựa trên mật độ
1.4.4 Phương pháp phân cụm dựa trên lưới
1.4.5 Phương pháp phân cụm dựa trên mô hình
1.4.6 Phương pháp phân cụm có dữ liệu ràng buộc
1.5. Các kiểu dữ liệu và độ đo
1.5.1 Phân loại các kiểu dữ liệu
1.5.1.1. Kiểu dữ liệu dựa trên kích thước miền
- Thuộc tính liên tục.
- Thuộc tính rời
1.5.1.2. Kiểu dữ liệu trên hệ đo
- Thuộc tính định danh.
- Thuộc tính có thứ tự.
- Thuộc tính khoảng.
- Thuộc tính nhị phân
- Thuộc tính tỉ lệ.
1.5.2 Độ đo tương tự và phi tương tự
1.5.2.1. Độ đo tương tự
1.5.2.2. Độ đo phi tương tự
1.6. Tổng kết chương
Như vậy, trong chương 1 em đã nghiên cứu được khái niệm về vấn đề phân cụm dữ liệu, mục tiêu của việc phân cụm dùng để làm gì, những vấn đề cần chú ý trong việc phân cụm và nghiên cứu tổng quan các phương pháp phân cụm và dữ liệu xây dựng trong phân cụm dữ liệu. Trong công tác thi đua khen thưởng, mặt dù đã có luật thi đua khen thưởng, thông tư 35/2015/TT-BGDĐT và thông tư 22/2018/TT-BGDĐT quy định về xét thi đua khen thưởng trong ngành giáo dục nhưng thực tế tại các đơn vị khi xét thi đua khen thưởng có nhiều mặt. Có người tốt về mặt này nhưng chưa tốt về mặt khác trong khi đó xét thi đua thì qua nhận xét định tính là chủ yếu, rất ít mặt xét về định lượng nên có trường hợp người này và người khác có sự so bì khi xét thi đua. Nên dùng phương pháp phân cụm là một trong những phương pháp xác định độ tương đồng về thành tích để các cá nhân được xét thi đua không có sự so bì gây mất đoàn kết trong đơn vị. Trong công tác phân cụm dữ liệu thi đua em sử dụng thuật toán phân cụm mờ FCM, thuật toán này sẽ được nghiên cứu trong chương 2.
CHƯƠNG 2: LÝ THUYẾT MỜ VÀ MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU
Trong chương này em nghiên cứu phần lý thuyết mờ gồm khái niệm về tập mờ, các phép toán logic mờ, quá trình mờ hóa dữ liệu và thuật toán phân cụm dữ liệu rõ K-Means và thuật toán phân cụm mờ Fuzzy C-Means, cách mã hóa biến ngôn ngữ thành dữ liệu số và chuyển giá trị từ số thành biến ngôn ngữ để có giá trị đầu ra bằng nhận xét để ứng dụng viết hàm hỗ trợ trong chương 3.
2.1. Lý thuyết mờ
2.1.1 Tập mờ
Định nghĩa 2.1: Cho tập vũ trụ U. Tập mờ được xác định bởi đẳng thức:
(2.1)
Được gọi là một tập mờ trên tập U. Trong đó, được gọi là hàm thuộc.
Giá trị tại u được gọi là độ thuộc của phần tử u thuộc về tập mờ .
Đối với công tác nhận xét một giáo viên thì tập mờ thường được định nghĩa và sử dụng bởi hai hình dạng chính đó là trapmf (dạng hình thang) và trimf ( dạng hình tam giác)
2.1.2 Biến ngôn ngữ
Định nghĩa 2.3. Biến ngôn ngữ là một bộ năm (x, T(x), U, R, M ), trong đó x là tên biến, T(x) là tập các giá trị ngôn ngữ của biến x, U là không gian tham chiếu của biến cơ sở u, mỗi giá trị ngôn ngữ xem như là một biến mờ trên U kết hợp với biến cơ sở u, R là một qui tắc cú pháp sinh các giá trị ngôn ngữ của T(x), M là qui tắc ngữ nghĩa gán mỗi giá trị ngôn ngữ trong T(x) với một tập mờ trên U.
Các đặc trưng của biến ngôn ngữ: Trong thực tế có rất nhiều biến ngôn ngữ khác nhau về các giá trị nguyên thuỷ, chẳng hạn như biến ngôn ngữ số ngày làm việc có giá trị nguyên thuỷ là ít, nhiều, biến ngôn ngữ Lương có giá trị nguyên thuỷ là thấp, trung bình, cao…..Tuy nhiên, những kết quả nghiên cứu đối với một miền trị của một biến ngôn ngữ cụ thể vẫn giữ được ý nghĩa về mặt cấu trúc đối với miền giá trị của các biến còn lại. Đặc trưng này được gọi là tính phổ quát của biến ngôn ngữ.
Ngữ nghĩa của các gia tử và các liên từ hoàn toàn độc lập với ngữ cảnh, điều này khác với giá trị nguyên thủy của các biến ngôn ngữ lại phụ thuộc vào ngữ cảnh. Ví dụ ta nói Lương của giáo viên A nào đó là rất cao, khi đó được hiểu rằng Lương khoảng trên 8.000.000 đồng, nhưng ta nói chiều cao của giáo viên A là rất cao thì được hiểu rằng Chiều cao khoảng trên 1.8 m. Do đó khi tìm kiếm mô hình cho các gia tử và các liên từ chúng ta không quan tâm đến giá trị nguyên thuỷ của biến ngôn ngữ đang xét. Đặc trưng này được gọi là tính độc lập ngữ cảnh của gia tử và liên từ. Các đặc trưng trên cho phép chúng ta sử dụng cùng một tập các gia tử và xây dựng một cấu trúc toán học duy nhất cho miền giá trị của các biến ngôn ngữ khác nhau
2.1.3 Các phép toán logic mờ
2.1.4 Suy diễn mờ
Suy diễn mờ bao gồm 3 luật suy diễn thường gặp, đó là.
- Luật Modus Ponens
- Luật Modus Tolen
- Luật bắc cầu
Ngoài ra, nó còn lập luận suy diễn xấp xỉ đa điều kiện.
2.1.5. Cấu trúc hệ thống logic mờ
Hệ thống logic mờ có thể nói nó được cấu thành từ 3 giai đoạn chính, và được thể hiện cụ thể thông qua một mô hình sau.
Hình 2.5. Cấu trúc hệ thống logic mờ
2.2. Thuật toán phân cụm dữ liệu K-Means
Các kỹ thuật phân cụm có rất nhiều cách tiếp cận và các ứng dụng trong thực tế, tuy nhiên nó đều hướng tới hai mục tiêu chung đó là chất lượng của các cụm khám phá được và tốc độ thực hiện của thuật toán. Hiện nay, với rất nhiều phương pháp phân cụm nhưng trong chương này chỉ tập trung giới thiệu về phương pháp phân cụm phân hoạch.
Kỹ thuật này có thể hình dung việc phân hoạch một tập hợp dữ liệu có n phần tử thành k nhóm cho đến khi xác định số các cụm được thiết lập. Số các cụm được thiết lập là các đặc trưng được lựa chọn trước. Phương pháp này được đánh giá là tốt cho việc tìm các cụm hình cầu và hình tròn trong không gian Euclidean. Ngoài ra, phương pháp này cũng phụ thuộc vào khoảng cách cơ bản giữa các điểm để lựa chọn các điểm dữ liệu nào có quan hệ là gần nhau với mỗi điểm khác, và các điểm dữ liệu nào không có quan hệ hoặc có quan hệ là xa nhau so với mỗi điểm khác. Tuy nhiên, phương pháp này không thể xử lý các cụm có hình dạng kỳ quặc hoặc các cụm có mật độ các điểm dày đặc. Các thuật toán phân hoạch dữ liệu có độ phức tạp rất lớn khi xác định nghiệm tối ưu toàn cục cho vấn PCDL, do nó phải tìm kiếm tất cả các cách phân hoạch có thể được. Chính vì vậy, trên thực tế thường đi tìm giải pháp tối ưu cục bộ cho vấn đề này bằng cách sử dụng một hàm tiêu chuẩn để đánh giá chất lượng của cụm cũng như để hướng dẫn cho quá trình tìm kiếm phân hoạch dữ liệu. Có thể nói, ý tưởng chính của thuật toán phân cụm phân hoạch tối ưu cục bộ là sử dụng chiến lược tham ăn để tìm kiếm nghiệm.
Tiêu biểu đối với các thuật toán phân cụm phân hoạch là thuật toán K-means. Thuật toán này dựa trên độ đo khoảng cách của các đối tượng dữ liệu trong cụm. Trong thực tế, nó đo khoảng cách tới giá trị trung bình của các đối tượng dữ liệu trong cụm. Nó được xem như là trọng tâm của cụm. Như vậy, nó cần khởi tạo một tập trọng tâm các cụm ban đầu, và thông qua đó nó lặp lại các bước gồm gán mỗi đối tượng tới cụm mà trọng tâm gần, và đồng thời tính toán lại trọng tâm của mỗi cụm trên cơ sở gán mới cho các đối tượng. Quá trình lặp này dừng khi các trọng tâm hội tụ.
Mục đích của thuật toán K-Means [2] là sinh k cụm dữ liệu {C1, C2, …, Ck} từ một tập dữ liệu chứa n đối tượng trong không gian d chiều Xi = {xi1, xi2,…, xid}, i = 1 ÷ n sao cho hàm mục tiêu đạt giá trị tối thiểu:
Trong đó: cj là trọng tâm của cụm Cj.
D là khoảng cách giữa hai đối tượng .
Đối với thuật toán này chúng ta có thể hình dung cụ thể như bên dưới sau:
Input: Số cụm k và hàm mục tiêu sau:
Output: Các cụm và hàm mục tiêu E đạt giá trị tối thiểu.
BEGIN
Bước 1: Khởi tạo
Chọn ngẫu nhiên k cụm ban đầu trong không gian Rd
(trong đó d là số chiều của dữ liệu trong không gian). Mỗi cụm được xác định bằng các tâm của cụm.
Bước 2: Tính khoảng cách
Tính khoảng cách từ các điểm dữ liệu đến các cụm tương ứng bằng công thức sau:
Đối với mỗi điểm Xi, tính khoảng cách của nó đến mỗi trọng tâm và sao đó nó sẽ tìm trọng tâm gần nhất của chính nó với mỗi điểm.
Bước 3: Cập nhật lại trọng tâm
Đối với mỗi cụm , cập nhật trọng tâm cụm cj bằng cách xác định trung bình cộng của các vector đối tượng dữ liệu.
Bước 4: Gán lại các điểm gần trung tâm nhóm mới
Nhóm các đối tượng dữ liệu vào nhóm gần nhất dựa vào trọng tâm của nhóm.
Điều kiện dừng
Lặp lại các bước 2 và 3 cho đến khi các trọng tâm của cụm không thay đổi.
END.
2.3 Kỹ thuật phân cụm dữ liệu mờ
2.3.1 Tổng quan về phân cụm mờ
2.3.1.1 Tổng quan
2.3.1.2 Các bước phân cụm dữ liệu mờ
Hình 2.6: Các bước phân cụm mờ
Trong sơ đồ các bước phận cụm dữ liệu mờ trên, áp dụng vào bài toán tôi đang nghiên cứu thì giai đoạn đầu vào giá trị rõ là các nhận xét của những người theo dõi thi đua như tổ trưởng chuyên môn hiệu phó phụ trách thi đua, hiệu trưởng, giai đoạn Fuzzy hóa là giai đoạn chuyển dữ liệu rõ sang dữ liệu mờ để khởi tạo ma trận U mờ. Do đây là đề tài nghiên cứu về phân cụm vì có những giáo viên có thể chuyên môn rất tốt, tác phong rất tốt nhưng việc thực hiện chủ trương đường lối thì không thực hiện, có những giáo viên chuyên môn không tốt nhưng tác phong và thực hiện chủ trương đường lối rất tốt. Nên hướng nghiên cứu không dùng suy diễn mờ để suy ra kết quả mà dùng phương pháp phân cụm mờ để phân tích kết quả thành các cụm, Do đó dùng tri thức là hàm fuzzy-c-means để phân các cụm trên ma trận U và giải mờ để hiện kết quả các cụm với dữ liệu rõ có những đặc điểm tương đồng của giáo viên.
2.3.2 Mờ hóa dữ liệu
2.3.3 Thuật toán Fuzzy C-Means
2.3.4 Thuật toán Fuzzy C-Means mở rộng
Thuật toán FCM mở rộng là thuật toán dựa trên cơ sở của thuật toán FCM của Bezdek nhằm cung cấp một quá trình lặp qua lại giữa phương trình (2.51) và (2.52) để xấp xỉ cực tiểu hàm mục tiêu (2.46) dựa trên độ đo tương tự có trọng số giữa xk và trọng tâm cụm vi. Sau mỗi vòng lặp, thuật toán tính toán và cập nhật các phần tử trong ma trận phân hoạch U. Phép lặp sẽ dừng khi trong đó ε là chuẩn kết thúc nằm trong khoảng , trong khi k là các bước lặp. Đối với thuật toán FCM mở rộng bao gồm 10 bước thực hiện lần lượt được thể hiện bởi hình 2.9
Hình 2.9. Thuật toán FCM mở rộng
Nhìn chung, việc chọn các tham số cụm rất ảnh hưởng đến kết quả phân cụm, tham số này thường được chọn theo phương pháp ngẫu nhiên hoặc theo Heuristic.
Đối với thì thuật toán FCM trở thành thuật toán rõ.
Đối với thì thuật toán FCM trở thành thuật toán phân cụm mờ với . Chưa có quy tắc nào nhằm chọn lựa tham số m đảm bảo cho phân cụm hiệu quả, thông thường chọn m = 2 [10]
Ta có thể tiến hành đánh giá việc lựa chọn số tâm cụm tối ưu bằng công sau:
(2.53)
Trong đó:
2.3.5 Giải mờ
2.4. Tổng kết chương
Trong chương này, tôi đã nghiên cứu tổng quan về logic mờ, biến ngôn ngữ trong logic mờ, tìm hiểu được các phép toán trên tập mờ, cách mờ hóa dữ liệu đầu vào và cách thể hiện giá trị rõ ở đầu ra, tìm hiểu được phương pháp phân cụm rõ bởi thuật toán K-Mean và thuật toán phân cụm mờ bởi thuật toán Fuzzy C-Means, Thuật toán được ứng dụng để phân cụm dữ liệu trong đề tài này. Trong chương này tôi đã làm rõ hơn về các bước để phân cụm dữ liệu trong phân cụm dữ liệu mờ thông qua phân tích ở mục 2.3.1.2.
CHƯƠNG 3: PHÁT TRIỂN ỨNG DỤNG VÀ THỬ NGHIỆM
Trong chương này em trình bày về công tác thi đua khen thưởng của nhà trường và xây dựng các hàm hỗ trợ phân cụm dữ liệu thi đua trên phần mềm MATLAB và ứng dụng thực tế vào bộ dữ liệu của nhà trường để kiểm nghiệm thuật toán FCM
3.1. Tổng quan về công tác thi đua, khen thưởng của ngành giáo dục
3.1.1 Một số khái niệm về thi đua, khen thưởng
3.1.1.2. Khái niệm khen thưởng
3.1.1.3. Mối quan hệ giữa thi đua và khen thưởng
3.1.2 Quản lý nhà nước về thi đua, khen thưởng
3.2. Xây dựng các hàm để hỗ trợ phân tích đánh giá
3.2.1 Phát biểu bài toán
Công tác thi đua là công việc mang tính nhạy cảm ở các trường THPT mỗi khi đánh giá cuối kỳ cuối năm. Có những giáo viên tốt toàn diện hoặc có những giáo viên có nhiều mặt không tốt nhưng cũng có những giáo viên có mặt rất tốt nhưng có mặt lại không tốt. Trong khi đánh giá giáo viên có nội dung thì cho bằng điểm số nhưng có nội dung thì cho bằng nhận xét của tổ trưởng hoặc của người theo dõi thi đua. Cho nên khi xét thi đua khen thưởng có nhiều mặt định tính nên khi có người này được thi đua, được khen thưởng nhưng người khác không được dẫn đến so bì, kiện cáo làm mất đoàn kết trong cơ quan đơn vị. Bài toán này đưa ra nhằm từ những nội dung nhận xét như : Tác phong, Chuyên môn, Hiệu quả công việc, chấp hành chủ trương, thời gian làm việc, công tác khác và nội dung sáng kiến kinh nghiệm thì cho điểm trực tiếp. Do đó từ những nhận xét và từ những nội dung cho bằng điểm ta phân giáo viên thành những nhóm có thành tích tương đồng nhằm giúp BGH có cách nhìn đúng hơn và dễ hơn trong công tác đánh giá thi đua và giáo viên cũng không còn so bì về tổng thành tích của mình với tổng thành tích của người khác.
3.2.2. Cơ sở thu thập thông tin
3.2.3. Mô tả đầu vào, đầu ra
*Đầu vào :
Để xây dựng cơ sở dữ liệu cho bài toán, căn cứ trên trên các phiếu đánh giá của tổ trưởng chuyên môn, của hiệu trưởng để xây dựng cơ sở dữ liệu cho bài toán. Trong đơn vị THPT Bình Sơn, Quảng Ngãi khi đánh giá nhận xét một cán bộ giáo viên sẽ dựa vào các công tác sau: Tác phong ; chuyên môn ; chấp hành chủ trương, quy đinh; Hiệu quả công việc ; Công tác khác ; Giờ giấc làm việc, Công tác khác…Các nhận xét thường bao gồm những biến ngôn ngữ như sau :
– Tác phong (Gương mẫu, Chỉnh chu, Nghiêm túc, Tạm, Chưa nghiêm túc)
– Chuyên môn (Rất vững, Vững, Tốt, Đạt, Cần học hỏi thêm, Chưa đạt)
– Chấp hành chủ trương, quy định (Thực hiện rất tốt, Thực hiện nghiêm túc, có thực hiện nhưng chưa nghiêm túc, chưa nghiêm túc)
– Hiệu quả công việc (Hiệu quả cao, có hiệu quả nhưng chưa cao, có hiệu quả, hiệu quả chưa cao, còn thấp, chưa đạt)
– Công tác khác (Hoàn thành xuất sắc, tham gia tốt, tích cực, trách nhiệm cao, hoàn thành, chưa hoàn thành)
– Sáng kiến kinh nghiệm [0..10] {chấm điểm theo thang điểm 10, không có sáng kiến tương ứng với 0 điểm, các điểm còn lại tương ứng với điểm số nguyên}
– Thời gian làm việc (đủ, còn hạn chế, chưa đủ)
Trên cơ sở nhận xét của tổ trưởng chuyên môn, người phụ trách theo dõi thi đua trong đơn vị ta xây dựng bảng dữ liệu trên phần mềm EXCEL như trong Bảng 3.1.
*Đầu ra : Dữ liệu được phân thành các cụm có độ tương đồng về mức độ thi đua như trong Bảng 3.2
3.2.4 Xử lý dữ liệu trên Matlab
3.2.4.1 Giới thiệu về Matlab
3.2.4.2 Xây dựng các hàm để phân cụm
3.3. Thực nghiệm, đánh giá, nhận xét
3.3.1 Thực nghiệm trên bộ dữ liệu của trường
3.2.2 Đánh giá, nhận xét
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
1. Kết luận
Đề tài đã giới thiệu một cách có hệ thống các kiến thức cơ bản tổng quan về phân cụm dữ liệu, các kiểu dữ liệu và độ đo, tổng quan lý thuyết về Logic mờ, các thuật toán phân cụm nhưng đặc biệt nghiên cứu về thuật toán phân cụm FCM của giáo sư Bezdek. Một số khái niệm về công tác thi đua, khen thưởng trong ngành giáo dục và đào tạo. Phát biểu được bài toán khởi đầu, vận dụng lý thuyết và đã xây dựng được các hàm để tìm kết quả ra của bài toán đặt ra.
Trong phần ứng dụng đã chạy được bộ dữ liệu thực và đã phân được các cụm và các cụm có độ tương đồng nhau, dựa trên các cụm người quản lý có thể phân tích cho đối tượng được đánh giá thi đua thỏa mãn được kết quả thi đua của mình.
Dưới sự hướng dẫn của thầy PGS.TS. Võ Trung Hùng và trong thời gian thực hiện đề tài: “Nghiên cứu một số thuật toán phân cụm dữ liệu và ứng dụng hỗ trợ đánh giá thi đua tại trường THPT Bình Sơn, Quảng Ngãi” em rút ra một số nhận xét sau:
- Ưu điểm
- Nghiên cứu sâu về mặt lý thuyết phân cụm dữ liệu, logic mờ và thuật toán phân cụm dữ liệu mờ.
- Nội dung nghiên cứu là vấn đề cấp thiết hiện nay và có nhiều ứng dụng trên thực tế.
- Nhược điểm
- Do thời gian có hạn, nên sử dụng phần mềm MATLAB để viết code chạy phân cụm, chưa xây dựng được chương trình chạy độc lập và thực nghiệm trên bộ dữ liệu với số lượng bản ghi chưa lớn
2. Hướng phát triển
Ðề tài được nghiên cứu và áp dụng trên phạm vi dữ liệu thực tại trường THPT Bình Sơn nên tương lai có thể chạy trên dữ liệu của nhiều trường khác nhau trong tỉnh.
Tiếp tục viết chương trình hoàn thiện để chạy độc lập và sẽ ứng dụng với bộ dữ liệu lớn hơn và có thể sẽ viết chương trình chạy với nhiều loại dữ liệu khác trong các lĩnh vực khác như phân loại sách trong thư viện, hay phân loại khách hàng trong lĩnh vực kinh doanh…
Cuối cùng với những kết quả đạt được của đề tài này tuy còn hạn chế nhưng đã giúp em có được những nghiên cứu cơ bản về phân cụm dữ liệu về lý thuyết logic mờ và đã phân được cụm dữ liệu hỗ trợ công tác đánh giá thi đua. Bên cạnh đó có thể làm tài liệu phục vụ giảng dạy hoặc tham khảo.
E:\DỮ LIỆU COP CỦA CHỊ YẾN\DAI HOC DA NANG\HE THONG THONG TIN\HO PHUC
