Áp dụng kỹ thuật phân cụm dữ liệu để phân loại kết quả học tập của học sinh

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (4.78 MB, 25 trang )

Trang 1<div class="page_container" data-page="1">

HỌC VIỆN CƠNG NGHỆ BƯU CHÍNH VIỄN THÔNG

ÁP DỤNG KỸ THUẬT PHAN CUM DU LIEU

DE PHAN LOẠI KET QUA HỌC TẬP CUA HỌC SINH

CHUYEN NGANH: KHOA HỌC MAY TÍNH

MA SO _ : 60.48.01.01

TOM TAT LUAN VAN THAC Si

HA NOI - 2014

</div>Trang 2<div class="page_container" data-page="2">

Luận văn được hồn thành tại:

HỌC VIEN CƠNG NGHỆ BƯU CHÍNH VIỄN

Co thé tim hiéu luan van tai:

- Thu viện của Hoc viện Cơng nghệ Buu chính Viễn

thơng

</div>Trang 3<div class="page_container" data-page="3">

MỞ DAU

1. Ly do chọn đề tài

Sự phát triển của công nghệ thông tin và việc ứng dụng công nghệ thông tin trong nhiều lĩnh vực của đời sống, kinh tế xã

hội cũng đồng nghĩa với lượng đữ liệu đã được các cơ quan thu

thập và lưu trữ ngày một tích luỹ nhiều lên.

Các phương pháp quản trị và khai thác cơ sở dữ liệu

truyền thống ngay càng không đáp ứng được đã làm phát triển

một khuynh hướng kỹ thuật mới đó là Kỹ thuật phát hiện tri thứcvà khai phá dữ liệu. Khai phá dữ liệu giúp người sử dụng thuđược những tri thức hữu ích từ những cơ sở dữ liệu hoặc các

nguôn dữ liệu không lồ khác.

Phân cụm dit liệu là một trong những kỹ thuật để khai thác dir liệu có hiệu quả và được ứng dụng trong nhiều lĩnh vực khác nhau: kinh tế, bảo hiểm, quy hoạch đô thị, v.v... Tuy

nhiên, trong lĩnh vực giáo dục thì chưa được khai thác có hiệu

quả. Bản thân người thực hiện đề tài đang công tác trong ngành giáo dục, nên rất cần các phân tích, đánh giá kết quả học tập của học sinh để từ đó dé xuất các biện pháp nhằm nâng cao chất

lượng giáo duc học sinh phổ thơng.

Đó là lý do tác giả chon đề tài “Ap dung kỹ thuật phân cum dữ liệu để phân loại kết quả học tập của học sinh”.

</div>Trang 4<div class="page_container" data-page="4">

2. Mục đích của đề tài:

e Tìm hiểu tổng quan về khai phá dit liệu, các phương pháp và

kỹ thuật phân cụm dữ liệu.

e Tìm hiểu một số thuật toán cơ bản trong phân cụm dữ liệu.

e Ung dụng thuật toán K-Means trong bài toán phân loại kết

quả học tập của học sinh.

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

Nghiên cứu các tài liệu về khai phá dữ liệu, kỹ thuật

phân cụm của các tác gia trong và ngoài nước, các bài báo, thôngtin trên mạng.

4. Đối tượng và phạm vi nghiên cứu:

e Đối tượng nghiên cứu: Các thuật toán cơ bản trong Khai phá

dữ liệu, đi sâu nghiên cứu thuật toán phan cụm dữ liệu.

e Phạm vi nghiên cứu: Nghiên cứu thuật toán K-means, sử

dụng đữ liệu của học sinh trường THPT Hà Đơng để xây

dựng bai tốn.

5. Cau trúc luận văn gồm 3 chương:

Chương 1: Tổng quan về khai phá và phân cụm dit liệu

Ở Chương 1, luận văn giới thiệu một cách tổng quát về quá

trình khám phá tri thức và khai phá dữ liệu. Các phương pháp,

lĩnh vực và các hướng tiếp cận trong khai phá đữ liệu.

Phần tiếp theo của luận văn sẽ trình bay khái niệm và mục tiêu của phân cụm dữ liệu, các yêu cầu, ứng dụng cũng như các

thách thức mà phân cụm dữ liệu đang gặp phải.

</div>Trang 5<div class="page_container" data-page="5">

Chương 2: Thuật toán phần cụm K-means

Trong Chương 2, luận văn sẽ trình bày về thuật tốn phân cụm dữ liệu K-means, một số ví dụ minh họa về thuật toán, ứng dụng và một số bién thé của thuật toán

Chương 3: Ứng dụng phân cụm kết quả học tập của học

sinh trường THPT Hà Đơng

Chương 3 sẽ trình bày về bài toán phân cụm kết quả học tập

của học sinh trường THPT Hà Đông. Cài đặt và thử nghiệm

chương trình ứng dụng, từ đó luận văn đưa ra một số phân tích, đánh giá từ kết quả thu được sau phân cụm và hiệu quả của

chương trình.

</div>Trang 6<div class="page_container" data-page="6">

CHƯƠNG 1: TONG QUAN VE KHAI PHA VÀ PHAN

CUM DU LIEU

1.1. Khai pha dữ liệu và phát hiện tri thức

Khai phá dữ liệu bao hàm một loạt các kỹ thuật nhằm phát

hiện ra các thơng tin có giá trị tiềm ẩn trong các tập dit liệu lớn.

Về ban chất, khai pha dit liệu liên quan đến việc phân tích các dữ liệu và sử dụng các kỹ thuật để tìm ra các mẫu hình có tính chính

quy trong tập dữ liệu.

Khai phá tri thức là mục tiêu chính của khai phá dữ liệu,do vậy hai khái niệm đó được xem như hai lĩnh vực tương đương

nhau. Nhưng nếu phân chia một cách tách bạch thì khai phá dữ

liệu là một bước chính trong q trình Khai phá tri thức.

1.1.1. Quá trình khám pha tri thức và khai pha dữ liệu

Quá trình khám pha tri thức tiễn hành qua 6 giai đoạn

- Gom dt liệu.

- Trích lọc dtr liệu.

- _ Làm sạch, tiền xử lý và chuẩn bị trước đữ liệu.

- — Chuyên đổi dữ liệu.

- Khai pha dữ liệu.

- _ Đánh giá các luật và biểu diễn tri thức.

Quá trình khai phá dữ liệu bao gồm các bước chính được

thể hiện:

- _ Xác định nhiệm vu.

</div>Trang 7<div class="page_container" data-page="7">

- _ Xác định các dữ liệu liên quan.

- Thu thập và tiền xử lý dữ liệu.

- Thuật toán khai phá dữ liệu.

1.1.2. Chức năng chính của khai pha dit liệu

- M6 tả lớp và khái niệm: .

- Phan tích sự kết hợp

- Phan lớp và dự bao.- Phân cụm.

- Phan tích các đối tượng ngoại lai.

- Phan tích sự tiến hoá.

1.1.3. Các kỹ thuật áp dụng trong khai pha dữ liệu

+ Đứng trên quan điểm của học máy, bao gồm:

- Hoc có giám sat.

- Hoc khơng có giám sat.- Hoc nwa giam sat.

+ Nếu căn cứ vào lớp các bài toán cần giải quyết:

1.1.4. Ung dụng của khai phá dữ liệu

- Phan tích dữ liệu và hỗ trợ ra quyết định

- Phân lớp văn bản, tóm tắt văn bản, phân lớp các

trang Web và phân cụm ảnh màu

</div>Trang 8<div class="page_container" data-page="8">

- Chuan đoán triệu chứng, phương pháp trong điều trị y

- Tim kiếm, đối sánh các hệ Gene va thơng tin di

trun trong sinh hoc

- Phan tích tinh hình tài chính, thị trường

- Phan tích dữ liệu marketing, khách hàng.

- _ Điều khiến và lập lịch trình - Bao hiểm

- Giáo duc...

1.2. Kỹ thuật phân cụm trong khai phá dữ liệu

1.2.1. Tổng quan về kỹ thuật phân cụm

Phan cum df liệu là qua trình nhóm một tập các đối tượng

tương tự nhau trong vào các cụm. Phân cụm dữ liệu khơng địi

hỏi phải định nghĩa trước các mẫu đữ liệu huấn luyện. Vì thế, có

thể coi phan cum dir liệu là một cách học băng quan sát, trong khi

phân lớp dữ liệu là học bằng ví dụ...

Mục tiêu của phân cụm là xác định được bản chất nhóm trong tập dữ liệu chưa có nhãn. Nó có thê được chỉ ra rằng khơng có tiêu chuẩn tuyệt đối “tốt” mà có thê khơng phụ thuộc vào kết quả phân cụm. Vì vậy, nó địi hỏi người sử dụng phải cung cấp tiêu chuẩn này, theo cách mà kết quả phân cụm sẽ đáp ứng yêu

`^

cau.

</div>Trang 9<div class="page_container" data-page="9">

1.2.2. Ứng dụng của phân cụm dữ liệu

- Thuong mai.- Sinh học.

- Thu viện.

- Bao hiém.

- Quy hoạch đô thi.

- Nghién cứu địa chấn.

- WWW.

1.2.3. Cac yêu cau doi với kỹ thuật phân cụm dữ liệu

- Có khả năng mở rộng.

- Khả năng thích nghi với các kiểu thuộc tính khác nhau. - Khám phá các cụm với hình dang bat kỳ.

- Tối thiểu lượng tri thức cần cho xác định các tham số đầu

- Khả năng thích nghi với dữ liệu nhiễu.

- It nhạy cảm với thứ tự của các dữ liệu vao.

- Số chiều lớn.

- Phân cụm ràng buộc.

- Dễ hiểu và dé sử dụng.

1.2.4. Các kiểu dữ liệu và độ do tuong tự

a. Phân loại 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 rạc.

</div>Trang 10<div class="page_container" data-page="10">

b. Phân loại kiểu dữ liệu dựa trên hệ đo

Tóm lại khai phá dữ liệu là một lĩnh vực khoa học mới

xuất hiện, nhằm tự động hóa khai thác những thơng tin, tri thức

hữu ích, tiềm ân trong các cơ sở dữ liệu, giúp chúng ta giải quyết

tình trạng ngày một gia tang trong những năm qua: “Ngập trong

dit liệu mà van đói tri thức”. Các kết quả nghiên cứu cùng với

những ứng dụng thành công trong khai pha dữ liệu, khám pha tri

thức cho thay khai phá dữ liệu là một lĩnh vực khoa học tiềm năng, mang lại nhiều lợi ích, đồng thời 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.

</div>Trang 11<div class="page_container" data-page="11">

CHƯƠNG 2: THUẬT TOÁN PHAN CUM K-MEANS

2.1. Giới thiệu về thuật toán

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 và được

xem như là trung tâm của cụm

Thuật toán K-means bao gôm các bước cơ bản sau:

INPUT : Số cụm k và các trọng tâm cụm {m¡}X~¡.

OUTPUT: Các cụm C[i] (1 < i < k) và hàm tiêu chuẩn E dat giá trị tối thiểu.

Bước 1: Khởi tạo

Chọn k trọng tâm {m;}*-¡ ban đầu trong không gian Ra (d là số

chiều của dt liệu). Việc lựa chọn này có thể là ngẫu nhiên hoặc

theo kinh nghiệm.

Bước 2: Tính tốn khoảng cách

Đối với mỗi điểm Xi (J <i <n), tính tốn khoảng cách của

nó tới mỗi

trọng tâm m; (¡ <j < #). Sau đó tìm trọng tâm gần nhất đối với

mỗi điểm.

Bước 3: Cập nhật lại trọng tâm

Đối với mỗi / < J <k, cập nhật trọng tam cụm mị băng cách xá c định trung bình cộng các véctơ đối tượng dtr liệu

</div>Trang 12<div class="page_container" data-page="12">

Đ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.

2.2. Đánh gia về thuật tốn e© Uu điểm:

- K-means phân tích phân cụm đơn giản nên có thê áp dụng

đối với tap dé liệu lớn.

- Đơn giản, đễ hiểu, tương đối hiệu quả.

- Các đối tượng tự động gán vào các nhóm

- Thường đạt được tối ưu cục bộ.

e Nhược điểm:

- K-means không khắc phục được nhiễu và giá trị k phải

được cho bởi người dùng.

- Chỉ thích hop áp dụng với dữ liệu có thuộc tính số và khám phá ra các cụm có dang hình cầu.

2.3. Một số biến thé của thuật tốn K-MEANS

2.4.1. Thuật tốn K-Medoids

Thuật tốn K-Medoids [1]: có kha năng khắc phục được

nhiều băng cách chọn đỗi tượng ở gần tâm cụm nhất làm đại diện

cho cụm đó. K - medoid tỏ ra hiệu quả hơn K-means trong trường

hợp đữ liệu có nhiễu hoặc đối tượng ngoại lai. Nhưng so với

K-means thì K-medoid có độ phức tạp tính tốn cao hơn. Cả hai

thuật tốn trên đều có nhược điểm chung là số cụm được cung

câp bới người dùng.

</div>Trang 13<div class="page_container" data-page="13">

2.4.2. Thuật toán Fuzzy C- Mean

= Fuzzy C-Means (FCM ) [1]: là một phương pháp của

phân nhóm cho phép một phan dữ liệu thuộc về hai hoặc nhiều

= Thường được sử dung trong nhận dạng mẫu

2.4.3. Thuật toán Incremental K - Means

Thuật toán Incremental K-means cơ bản van dựa trên

thuật tốn K-means nhưng sẽ khơng chọn k điểm làm trọng tâm cho k cụm mà sẽ tăng số cụm từ 1 lên k cụm bằng cách đưa trung tâm cụm mới vào cụm có độ méo dạng lớn nhất (tăng SỐ cụm) và

tính lại trọng tâm các cụm.

2.4. Kết luận

Qua phân tích ta có thể rút ra kết luận: thuật toán phân

cụm dữ liệu K-means, dựa trên độ đo khoảng cách Euclide giữa

các đối tượng dữ liệu trong cụm. Trong thực té, khoảng cach tới giá tri trung bình của các đối tượng dữ liệu trong cụm được xem như là trung tâm của cụm. 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à trung tâm gần và tính tốn tại tung tâm của mỗi cụm trên cơ sở gán mới cho các đối tượng.

Chương 2 cũng nêu lên ưu nhược điểm của thuật toán K-means và một số biến thê của thuận toán như: K-Medoids, Fuzzy

C-Mean, Incremental K-means.

</div>Trang 14<div class="page_container" data-page="14">

CHƯƠNG 3: UNG DUNG PHAN CUM KET QUA

HOC TAP CUA HOC SINH TRUONG THPT HA DONG

3.1. Mô tả bài tốn

Dựa trên điểm trung bình của từng mơn học, điểm trung

bình từng học kỳ, cả năm của từng học sinh, từng lớp, từng

khối. Chương trình sẽ tiến hành gom cum di liệu nhằm phân tích điểm số để giúp cho Ban giám hiệu, các nhà quản lý giáo dục có thêm cơ sở để đánh giá đúng dan nhất, chính xác nhất ... về tình hình học tập của học sinh, hoạt động giảng dạy của giáo viên từ đó dé ra định hướng, hoạch định cho nhà trường trong việc nâng cao chất lượng giáo dục.

Với bài toán đặt ra, việc phân tích, thiết kế và xây dựng

CSDL phải đáp ứng các chủ đề như trên nhưng điểm trung bình

mơn học của học sinh là quan trọng nhất vì học sinh có kết quả học tập tốt sẽ thúc đây sự phát triển của nhà trường, động cơ học

tập của học sinh và giảng dạy của giáo viên.

Yêu cầu của hệ thống

Bài toán đặt ra đối với hệ thơng cơ sở đữ liệu là phân tích số

liệu theo một số chủ đề quan tâm, nhằm nâng cao chất lượng

giảng dạy và học tập của học sinh như :

+ Kết quả học tập của học sinh: Giỏi, khá, trung bình, yếu,

+ Sự phân cơng giáo viên ảnh hưởng đến kết quả đó như thế

nào.

</div>Trang 15<div class="page_container" data-page="15">

+ So sánh kết quả học tập của từng Khối, Lớp để đưa ra

những giải pháp nâng cao chất lượng dạy và học.

+ Định hướng cho học sinh Khối 12 thi tốt nghiệp cũng như

chọn khối thi đại học...

Mô tả về chương trình

Chương trình được xây dựng bằng ngơn ngữ ngơn ngữ lập

trình C#, hệ quan tri cơ sở dữ liệu SQL Server 2012 và cơng cụ hỗ

trợ lập trình Microsoft Visual Studio 2012.

+ Dữ liệu dau vao: là các tệp kết quả hoc tập của các lớp

trong trường được lưu trữ ở dạng bảng tính Excel.

+ Dữ liệu đâu ra: kêt quả phân cụm được hiện thị trên man

hình hoặc xuât ra Excel đê tiện cho việc phân tích và báo cáo.

Một số tệp mã nguồn của chương trình:

- Main.cs: Giao diện chính của chương trình.

- ImportData.cs: Xử lý việc cập nhật các tệp dữ liệu vào

cơ sở dữ liệu chung

- Phancum.cs: Phân cụm băng thuật toán K-Means - Ketqua.cs: Dua ra kết quả sau khi phân cum

- ExcelTool : Dua kết quả bằng tệp excel

Chương trình sẽ tiễn hành cập nhật dữ liệu từ các tệp kết quả

học tập của học sinh sau đó sẽ tiễn hành việc phân cụm rỗi đưa ra

kết quả.

Tâm cụm sẽ được gan lân lượt tăng dân cho đên khi lựa chọn

được kết quả tốt nhất, phù hợp với yêu cầu của việc đánh giá.

</div>Trang 16<div class="page_container" data-page="16">

3.2. Cac bước áp dụng thuật toán K-means vào bài tốn

Hình 3.1 Các bước phân cụm kết quả học tập của học sinh

3.2.1. Tiền xử lý dữ liệu

Cập nhật và bồ Sung điểm của học sinh: Được thực hiện sau khi giáo viên chủ nhiệm hoàn thành việc tổng kết điểm học

kỳ cho học sinh. Dữ liệu sẽ được tập hợp và cập nhật vào cơ sở

dir liệu chung.

Loại bỏ đữ liệu thừa: Đối với những môn hoc khơng thực

hiện phân cụm có thé được loại bỏ, ví dụ: Cơng nghệ, Thể dục,

Quan sự ...

Các bước thục hiện :

+ Bước 1 : Nhận kết qua học tập của học sinh (của từng

giáo viên bộ môn hoặc giáo viên chủ nhiệm).

+ Bước 2 : Tiến hành kiểm tra tính chính xác của dữ liệu. VD: ngày sinh, lớp, điểm Trung bình của mơn học. Có 2 trường

hợp thường xảy ra :

</div>Trang 17<div class="page_container" data-page="17">

- _ Ngày sinh : phải được nhập đúng định dạng : dd/mm/yyyy.

- Thiéu điểm trung bình: trường hợp này có thé u cầu Giáo

viên bộ môn trực tiêp bô xung.

+ Bước 3 : Tính điểm Trung bình học kỳ hoặc năm học cho

tất cả các lớp. Tiến hành loại bỏ các môn học khơng thực

hiện phân cụm.

3.2.2. Biểu diễn dữ liệu

Sau khi có Bảng điểm của các lớp học. Chúng ta sẽ tiễn

hành cập nhật vào CSDL chung.

` a...

DỮ LIỆU PHÂN TÍCH Khối: +

1 of 319 | bị

| sr MaHs Ho Ten Lop Khoi Gi*

> hi HD13001 | BÙI TRANG | ANH |A1 l1o [NC

2 | HD13002 ĐỒ THỊ HOÀ... | ANH A1 10 No

3 | HD13003 | HOANG PHU... LẠNH |A1 lio [Nữ4 | HD13004_ |LÊ Đức LANH lai l1o EE5 | HD13005 | Tạ THỊ PHUq TA THỊ PHƯƠNG | laa lo [Ne

6 | HD13006 [Lưu NGOC BÍCH lat [10 [Ne

|7 (HD13007 | NGUYEN HAD | CHI [At l1o [Ne

8 |HD13008 |NGUYEN THI DỤNG [A1 |10 [Ne

9 HD13009 LE TRUNG DŨNG A1 10 Ne

10 | HD13010 | TRẦN VĂN |DŨNG laa lo [Ne11 (HD13011 ¡VŨ THÀNH (ĐẠT Ï |A1 lio ÍN¿12 (HD13012 ¡DƯƠNG CẦN [puc lAi lo [Ne

; 1¬ _ liimian12a "M-. WER Tor Í mi aq 3n Kell

4 | THỊ | l2

Tập tin dữ liệu: [⁄i xóa dữ liệu cũ | Cập nhật vào CSDL | | ThoátE\LUAN_VAN\Diem_TK_10.xIsx

Trong phân này tác giả sẽ đưa ra một sô kêt quả phân cụmtheo năm học và môn học của học sinh.

3.3.1. Một số kết qua phân cụm theo năm học - Khối 10

</div>Trang 18<div class="page_container" data-page="18">

HD13017 | NGUYEN VIỆT HOA A1 78HD13020 |NGUYỄN NGỌC LINH |AL 78

HD13024 |NGHIEM MINH PHƯƠNG | AL 8

Hình 3.5 Màn hình Kết quả phân cụm - Khối 10

(SỐ lượng hoc sinh Khoi 10: 319 học sinh, chia thành 6 cum)

KET QUA PHAN CUM

THONG SỐ CÁC CUM Tổng số lần lặp: 4 CHI TIẾT CỤM

Hình 3.6 Màn hình Kết quả phân cụm - Khối II

(Số lượng học sinh Khối 11: 334 học sinh, chia thành 7 cụm.) * Khối 12

</div>Trang 19<div class="page_container" data-page="19">

HD11033 | NGUYEN ĐỨC TÀI |A1 6.2HD11037 | DOAN THU THUY A1 6

HD11043 | PHAM THANH TÙNG A1 61

HD11045 | NGUYEN THỊ QUỲNH ANH | [5.9

HD11046 | PHAM VAN ANH Ệ 6.1

HD11057 _ LE THỊ THANH GIANG 6HD11061 BÙI ĐỨC HUNG 58

unting? — ÍNESLIVỄNE niqac VLIARILL 5a

HOP THEO LOP

Tổng số HS 374

Số HS của cụm 51

Tổng TB nhỏ nhất 5.4Tổng TB lớn nhất 6.2

Hình 3.7 Màn hình Kết quả phân cụm - Khối 12

(Số lượng học sinh Khối 12: 374 học sinh, chia thành 6 cụm) 3.3.2. Một số kết qua phân cụm theo mụn hc

Â Khụi T0

3G) Kt que phon cum ơ ee