ỨNG DỤNG PHÂN CỤM DỮ LIỆU TRONG PHÂN TÍCH, ĐÁNH GIÁ KẾT QUẢ ĐIỂM CỦA HỌC SINH

ỨNG DỤNG PHÂN CỤM DỮ LIỆU TRONG PHÂN TÍCH, ĐÁNH GIÁ KẾT QUẢ ĐIỂM 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 (612.71 KB, 26 trang )

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

Đỗ Văn Minh

ỨNG DỤNG PHÂN CỤM DỮ LIỆU TRONG PHÂN TÍCH,
ĐÁNH GIÁ KẾT QUẢ ĐIỂM CỦA HỌC SINH

Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01.01

TÓM TẮT LUẬN VĂN THẠC SĨ

HÀ NỘI – 2013

Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

Người hướng dẫn khoa học: GS.TS. Vũ Đức Thi

Phản biện 1: …………………………………………

Phản biện 2: …………………………………………

Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn
thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông
Vào lúc: giờ ngày tháng năm

Có thể tìm hiểu luận văn tại:
– Thư viện của Học viện Công nghệ Bưu
chính Viễn thông
1

MỞ ĐẦU
Khai phá dữ liệu đã và đang được nghiên cứu, ứng dụng nhiều
trong các lĩnh vực khác nhau và mang lại những lợi ích to lớn. Những vấn
đề được quan tâm trong khai phá dữ liệu là phân lớp, luật kết hợp, phân cụm
dữ liệu…
Phân cụm dữ liệu (PCDL) là quá trình tìm kiếm để phân ra các
cụm dữ liệu, các mẫu dữ liệu từ tập CSDL lớn. PCDL là một trong những
kỹ thuật để khai thác dữ liệu có hiệu quả. PCDL đã được ứng dụng trong
nhiều lĩnh vực khác nhau: kinh tế, y học, sinh học, bảo hiểm, quy hoạch đô
thị, phân đoạn ảnh …

Ngành giáo dục nói chung và các trường học nói riêng có lượng dữ
liệu lưu trữ khá lớn nhưng việc phân tích, đánh giá để đưa ra các chiến lược
phát triển phù hợp, cung cấp chất lượng giáo dục tốt hơn và hỗ trợ các hoạt
động quản lí hiện nay chưa thực sự được quan tâm đúng mức và khai thác
có hiệu quả.
Với những lý do như vậy tôi chọn đề tài “Ứng dụng phân cụm dữ
liệu trong phân tích, đánh giá kết quả điểm của học sinh” làm đề tài luận
văn tốt nghiệp.
Bố cục luận văn gồm 3 chương:
Chương 1: Tìm hiểu tổng quan về khai phá dữ liệu và kỹ thuật
phân cụm dữ liệu trong KPDL.
Chương 2: Tìm hiểu một số thuật toán điển hình trong phân cụm
dữ liệu.
Chương 3: Ứng dụng thuật toán k-means để thử nghiệm phân cụm
trên dữ liệu điểm của học sinh.

2

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.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…
Khai phá dữ liệu là lĩnh vực đã và đang trở thành một trong những
hướng nghiên cứu thu hút được sự quan tâm của nhiều chuyên gia về CNTT
trên thế giới. 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 khai phá dữ liệu.
1.1.2 Quá trình khai phá dữ liệu
Về bản chất khai phá dữ liệu là giai đoạn duy nhấ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.
Quá trình khai phá dữ liệu gồm các bước chính được thể hiện như
hình sau:
Hình 1.2 Quá trình khai phá dữ liệu

3

1.1.3 Các kỹ thuật khai phá dữ liệu
Với mục đích mô tả và dự đoán, các kỹ thuật thường sử dụng là:
– Luật kết hợp (Association rules)
– Phân cụm (Clustering)
– Phân lớp (Classfication)
– Hồi quy (Regression)
– Cây quyết định (Decision 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.1.4 Ứng dụng của Khai phá dữ liệu
1.1.5 Các xu thế và vấn đề cần giải quyết trong khai phá
dữ liệu
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
Phân cụm dữ liệu là quá trình nhóm một tập các đối tượng tương tự
nhau trong 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 kỹ thuật trong KPDL 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 và quan trọng trong tập
dữ liệu lớn để từ đó cung cấp thông tin, tri thức cho việc ra quyết định.
4

Phân cụm dữ liệu 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 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.
1.2.2 Một số khái niệm cần thiết khi tiếp cận phân cụm dữ
liệu
1.2.2.1 Các kiểu dữ liệu và thuộc tính trong phép phân cụm
1.2.2.2 Đo độ tương đồng

1.2.3 Các yêu cầu đối với kỹ thuật phân cụm dữ liệu
– 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
– 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.2.4 Các hướng tiếp cận trong phân cụm dữ liệu
1.2.4.1 Phương pháp phân hoạch (Partitioning Methods) chia 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 là tốt cho việc tìm các cụm hình cầu trong không
gian Euclid.

1.2.4.2 Phương pháp phân cụm phân cấp
(Hierarchical
Methods) xây dựng một phân cấp trên cơ sở các đối tượng dữ liệu đang xem
5

xét. Phương pháp này là có thể làm việc tốt với các tập dữ liệu lớn nhưng
khó khăn với các cụm có hình dạng lồi.
1.2.4.3 Phương pháp phân cụm dựa trên mật độ
(Density-
Based Methods) nhóm các đối tượng dữ liệu dựa trên hàm mật độ xác định,
mật độ là số các đối tượng lân cận của một đối tượng dữ liệu theo một nghĩa
nào đó. Phương pháp phân cụm dựa trên mật độ của các đối tượng để xác
định các cụm dữ liệu có thể phát hiện ra các cụm dữ liệu với hình thù bất
kỳ.
1.2.4.4 Phương pháp phân cụm dựa trên lưới
(Grid-Based
Methods) thích hợp với dữ liệu nhiều chiều, dựa trên cấu trúc dữ liệu lưới
để phân cụm, phương pháp này chủ yếu tập trung áp dụng cho lớp dữ liệu
không gian
1.2.4.5 Phương pháp phân cụm dựa trên mô hình
(Model-
Based Clustering Methods) khám phá các phép xấp xỉ tốt của các tham số
mô hình sao cho khớp với dữ liệu một cách tốt nhất
Kết luận chương
Chương 1 tìm hiểu những kiến thức cơ bản về khai phá dữ liệu và
các kỹ thuật áp dụng trong KPDL, những ứng dụng và xu thế của KPDL,
Chương này cũng tìm hiểu một hướng nghiên cứu và ứng dụng
trong KPDL là phân cụm dữ liệu, gồm tổng quan về kỹ thuật phân cụm, các
yêu cầu đối với kỹ thuật phân cụm, các hướng tiếp cận trong phân cụm dữ
liệu, các kiểu dữ liệu, độ đo tương tự, v.v

6

CHƯƠNG II. MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆU
ĐIỂN HÌNH
2.1 Các thuật toán phân cụm phân hoạch
2.1.1 Thuật toán K-means
Đầu vào: Một CSDL gồm n đối tượng và số các cụm k.
Đầu ra: Các cụm C
i
(i=1, ,k) sao cho hàm tiêu chuẩn E đạt giá trị tối thiểu.
Bước 1: Khởi tạo
Chọn k đối tượng m
j
(j=1 k) là trọng tâm ban đầu của k cụm từ tập dữ liệu

Bước 2: Tính toán khoảng cách
Đối với mỗi đối tượng X
i
(i=1, ,n), tính toán khoảng cách từ nó tới mỗi
trọng tâm m
j
với j=1, ,k; sau đó tìm trọng tâm gần nhất đối với mỗi đối
tượng.
Bước 3: Cập nhật lại trọng tâm
Đối với mỗi j=1, ,k; cập nhật trọng tâm cụm m
j
bằng cách xác định trung
bình
cộng của các véc-tơ đối tượng dữ liệu.
Bước 4: Điều kiện dừng

Lặp 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.1.2 Thuật toán PAM
Đầu vào: Số cụm k và một cơ sở dữ liệu D chứa n đối tượng
Đầu ra: Một tập k cụm đã tối thiểu hoá tổng các độ đo không tương đồng
của tất cả các đối tượng tới medoid gần nhất của chúng
7

Bắt đầu
1. Chọn tuỳ ý k đối tượng đại diện ban đầu;
2. Repeat
3. Ấn định mỗi đối tượng vào cụm có các đối tượng đại diện (medoid) gần
nó nhất;
4. Lựa chọn ngẫu nhiên một đối tượng không điển hình o
random
5. Tính hàm mục tiêu S (tổng các độ đo tương đồng của tất cả các đối tượng
tới medoid gần nhất cùa chúng) bằng việc tráo đổi o
j
với o
random
;
6. Nếu S<0 tráo đổi o
j
với o
random
để tạo thành các tập mới của k đối tượng
đại diện;
7. Until không có sự thay đổi nào
Kết thúc

2.1.3 Thuật toán CLARANS

For i=1 to numlocal do
Begin
Khởi tạo ngẫu nhiên k đối tượng medois
j = 1;
while j < maxneighbor do
Begin
Chọn ngẫu nhiên một láng giềng R của S.
Tính toán độ phi tương tự về khoảng cách giữa 2 láng giềng S và R.
Nếu R có chi phí thấp hơn thì hoán đối R cho S và j=1
ngược lại j++;
End;
8

Kiểm tra khoảng cách của phân hoạch S có nhỏ hơn khoảng cách nhỏ nhất
không, nếu nhỏ hơn thì lấy giá trị này để cập nhật lại khoảng cách nhỏ nhất
và phân hoạch S là phân hoạch tốt nhất tại thời điểm hiện tại.
End.

2.2 Các thuật toán phân cụm phân cấp
2.2.1 Thuật toán BIRCH
Bước 1: Duyệt tất cả các đối tượng trong CSDL và xây dựng một cây CF
khởi tạo. Một đối tượng được chèn vào nút lá gần nhất tạo thành cụm con.
Nếu đường kính của cụm con này lớn hơn T thì nút lá được tách. Khi một
đối tượng thích hợp được chèn vào nút lá, tất cả các nút trỏ tới gốc của cây
được cập nhật với các thông tin cần thiết.
Bước 2: Nếu cây CF hiện thời không có đủ bộ nhớ trong thì tiến hành xây
dựng một cây CF nhỏ hơn bằng cách điều khiển bởi tham số T (vì tăng T
sẽ làm hoà nhập một số các cụm con thành một cụm, điều này làm cho cây
CF nhỏ hơn). Bước này không cần yêu cầu bắt đầu đọc dữ liệu lại từ đầu
nhưng vẫn đảm bảo hiệu chỉnh cây dữ liệu nhỏ hơn.

Bước 3: Thực hiện phân cụm: Các nút lá của cây CF lưu giữ các đại
lượng thống kê của các cụm con. Trong bước này, BIRCH sử dụng các đại
lượng thống kê này để áp dụng một số kỹ thuật phân cụm thí dụ như k-
means và tạo ra một khởi tạo cho phân cụm.
Bước 4: Phân phối lại các đối tượng dữ liệu bằng cách dùng các đối tượng
trọng tâm cho các cụm đã được khám phá từ bước 3: Đây là một bước tuỳ
chọn để duyệt lại tập dữ liệu và gán nhãn lại cho các đối tượng dữ liệu tới
các trọng tâm gần nhất. Bước này nhằm để gán nhãn cho các dữ liệu khởi
tạo và loại bỏ các đối tượng ngoại lai
9

2.2.2 Thuật toán CURE
Bước 1. Chọn một mẫu ngẫu nhiên từ tập dữ liệu ban đầu;
Bước 2. Phân hoạch mẫu này thành nhiều nhóm dữ liệu có kích thước bằng
nhau: Ý tưởng chính ở đây là phân hoạch mẫu thành p nhóm dữ liệu bằng
nhau, kích thước của mỗi phân hoạch là n’/p (với n’ là kích thước của mẫu);
Bước 3. Phân cụm các điểm của mỗi nhóm: Ta thực hiện PCDL cho các
nhóm cho đến khi mỗi nhóm được phân thành n’/(pq)cụm (với q>1);
Bước 4. Loại bỏ các phần tử ngoại lai: Trước hết, khi các cụm được hình
thành cho đến khi số các cụm giảm xuống một phần so với số các cụm ban
đầu. Sau đó, trong trường hợp các phần tử ngoại lai được lấy mẫu cùng với
quá trình pha khởi tạo mẫu dữ liệu, thuật toán sẽ tự động loại bỏ các nhóm
nhỏ.
Bước 5. Phân cụm các cụm không gian: Các đối tượng đại diện cho các
cụm di chuyển về hướng trung tâm cụm, nghĩa là chúng được thay thế bởi
các đối tượng gần trung tâm hơn.
Bước 6. Đánh dấu dữ liệu với các nhãn tương ứng.

2.3 Các thuật toán phân cụm dựa trên mật độ

2.3.1 Thuật toán DBSCAN
Input: Tập dữ liệu D chứa n đối tượng, ε là tham số bán kính và MinPts
ngưỡng mật độ láng giềng.
Output: Tập các cụm dựa trên mật độ.
(1) đánh dấu tất cả các đối tượng là chưa thăm;
(2) lặp
(3) lựa chọn ngẫu nhiên một đối tượng chưa thăm p;
10

(4) đánh dấu đã thăm p;
(5) nếu các ε láng giềng của p có ít nhất MinPts đối tượng
(6) tạo mới một cụm C và thêm p vào C;
(7) cho N là tập các đối tượng trong ε láng giềng của p;
(8) lặp: với mỗi điểm p’ trong N
(9) nếu p’chưa thăm
(10) đánh dấu p’ đã thăm;
(11) nếu ε láng giềng của p’ có ít nhất MinPts điểm,
thêm những điểm này đến N;
(12) nếu p’không phải là thành viên của bất kỳ cụm nào, thêm p’ vào C;
(13) kết thúc lặp
(14) đưa ra C;
(15) ngược lại đánh dấu p như là nhiễu;
(16) cho đến khi thăm hết các đối tượng;

2.3.2 Thuật toán DENCLUDE
DENCLUDE là phương pháp dựa trên một tập các hàm phân phối
mật độ và được xây dựng trên các ý tưởng như sau :
– Sự ảnh hưởng của mỗi điểm dữ liệu có thể biểu diễn dưới dạng
mô hình qua hàm toán học, được gọi là hàm ảnh hưởng (influence fuction),
dùng để mô tả tác động của điểm dữ liệu với các đối tượng láng giềng của

nó; – Mật độ toàn cục của không gian dữ liệu có thể được mô hình hóa
là tổng các hàm ảnh hưởng của tất cả các điểm dữ liệu;
– Các cụm có thể xác định theo toán học bằng việc xác định các
điểm mật độ cao (density attractors), trong đó điểm mật độ cao là các điểm
cực đại hàm mật độ toàn cục.
11

2.4 Các thuật toán phân cụm dựa trên lưới
2.4.1 Thuật toán STING
Bước 1. Xác định tầng để bắt đầu.
Bước 2. Với mỗi cái của tầng này, tính toán khoảng tin cậy (hoặc ước
lượng khoảng) của xác suất mà ô này liên quan tới truy vấn.
Bước 3. Từ khoảng tin cậy của tính toán trên, gán nhãn cho là có liên
quan hoặc không liên quan.
Bước 4. Nếu lớp này là lớp cuối cùng, chuyển sang Bước 6; nếu khác thì
chuyển sang Bước 5.
Bước 5. Duyệt xuống dưới của cấu trúc cây phân cấp một mức. Chuyển
sang bước 2 cho các ô mà hình thành các ô liên quan của lớp có mức cao
hơn.
Bước 6. Nếu đặc tả được câu truy vấn, chuyển sang bước 8; nếu không
thì chuyển sang bước 7.
Bước 7. Truy lục lại dữ liệu vào trong các ô liên quan và thực hiện xử lý.
Trả lại kết quả phù hợp yêu cầu của truy vấn. Chuyển sang Bước 9.
Bước 8. Tìm thấy các miền có các ô liên quan. Trả lại miền mà phù hợp
với yêu cầu của truy vấn. Chuyển sang bước 9.
Bước 9. Dừng

2.4.2 Thuật toán CLIQUE
Bước 1: Phân hoạch tập dữ liệu thành các hình hộp chữ nhật và tìm các
hình hộp chữ nhật đặc (nghĩa là các hình hộp này chứa một số các đối

tượng dữ liệu trong số các đối tượng láng giềng cho trước).
Bước 2: Xác định không gian con chứa các cụm được sử dụng nguyên lý
Apriori.
12

Bước 3: Hợp các hình hộp này tạo thành các cụm dữ liệu.
Bước 4: Xác định các cụm: Trước hết nó tìm các ô đặc đơn chiều, tiếp
đến chúng tìm các hình chữ nhật 2 chiều, rồi 3 chiều,…, cho đến khi
hình hộp chữ nhật đặc k chiều được tìm thấy.

2.5 Các thuật toán phân cụm dựa trên mô hình
2.5.1 Thuật toán EM
1. Khởi tạo tham số
(0) (0) (0) (0) (0) (0)
0 1 2 1 2
{, ,, ,, ,, }
k k
p p p
   

2. Bước E
( ) 2 ( )
( ) 2 ( )
(x |, ) (, )
( |, , )P
( |, )
(, ) ( |, , )P
t t
k j t j t

k i i i
j k t
t t
k t k i i j
k
P P
P x
P x
P x P x
   
  
 
   
 

3. Bước M

( 1)
( |, )
( |, )
i k t k
t
k
i
i k t
k
P x x
P x
 


 



( 1)
( |, )
i k t
t
k
i
P x
p
R
 


4. Lặp lại bước 2, 3 cho đến khi đạt kết quả

13

2.5.2 Thuật toán COBWEB
1) Khởi tạo cây bắt đầu bằng một nút rỗng.
2) Sau khi thêm vào từng nút một và cập nhật lại cây cho phù hợp tại

mỗi
thời điểm.
3) Cập nhật cây bắt đầu từ lá bên phải trong mỗi trường hợp, sau đó cấu
trúc lại cây.
4) Quyết định cập nhật dựa trên sự phân hoạch và các hàm tiêu chuẩn
phân loại.
2.5.3 Thuật toán SOM
Bước 1: Khởi tạo
Chọn giá trị ngẫu nhiên cho các véc-tơ trọng lượng ban đầu w
j

Bước 2: Lấy mẫu
Lấy một mẫu huấn luyện véc-tơ x từ tập huấn luyện.
Bước 3: Ghép mẫu
Tìm nơ-ron I(x) tốt nhất có véc-tơ trọng số gần nhất với giá trị của véc-tơ
đầu vào, ví dụ giá trị nhỏ nhất
2
1
( ) ( w )
D
j i ji
i
d x x

 

Bước 4: Cập nhật
Cập nhật phần tử trọng số
, ( ) )

w ( ) ( )( w
ji j I x i ji
t T t x

  
với
, ( )
( )
j I x
T t
là Gauss lân cận và
( )t

là tỷ lệ học.
Bước 5: Lặp lại
Lặp lại bước 2 cho đến khi giải thuật tối ưu hoặc đạt đến số lần lặp xác
định N cho trước.
14

2.6 Các thuật toán phân cụm có dữ liệu ràng buộc
2.6.1 Thuật toán K-Prototype
Input: Tập dữ liệu ban đầu X và số cụm k.
Output: k đối tượng mẫu sao cho hàm tiêu chuẩn đạt giá trị tối thiểu.
Bước 1: Khởi tạo k đối tượng mẫu ban đầu cho X, mỗi đối tượng mẫu
đóng vai trò là tâm đại diện của mỗi cụm.
Bước 2: Phân phối mỗi đối tượng trong X cho mỗi cụm sao cho chúng
gần nhất với đối tượng mẫu trong cụm, đồng thời cập nhật lại đối
tượng mẫu cho mỗi cụm.
Bước 3: Sau khi tất cả các đối tượng đã được phân phối hết cho các

cụm, kiểm tra lại độ tương tự của các đối tượng trong mỗi cụm với các
đối tượng mẫu, nếu có một đối tượng mẫu tương tự nhất với nó mà
khác với đối tượng mẫu của cụm hiện thời thì di chuyển đối tượng
đang xét này sang cụm tương ứng với đối tượng mẫu mà nó gần nhất
và đồng thời cập nhật các đối tượng mẫu cho hai cụm này.
Bước 4: Lặp bước 3 cho đến khi không có đối tượng nào thay đổi sau
khi đã kiểm tra toàn bộ các đối tượng.

2.6.2 Thuật toán COP-KMeans
Input: – Tập các đối tượng dữ liệu
– Số lượng cụm: K
– Tập ràng buộc must-link và cannot-link
Output: K phân hoạch tách rời sao cho hàm mục tiêu được tối ưu.
Bước 1. Khởi tạo các cụm: các tâm ban đầu được chọn ngẫu nhiên sao
cho không vi phạm ràng buộc đã cho.
15

Bước 2. Lặp cho tới khi hội tụ
Bước 2.1 Gán cụm : gán mỗi đối tượng dữ liệu vào trong cụm gần
nhất sao cho không vi phạm ràng buộc
Bước 2.2 Ước lượng tâm: cập nhật lại tâm là trung bình của tất cả
đối tượng nằm trong cụm của tâm đó.
Bước 2.3 t = t+1

Kết luận chương
Chương 2 tìm hiểu về một số thuật toán điển hình trong phân cụm
dữ liệu. Mỗi một thuật toán có độ chính xác riêng và khả năng thực hiện
trên từng kích thước dữ liệu là khác nhau. Điều này còn tùy thuộc vào cách
tổ chức dữ liệu ở bộ nhớ chính, bộ nhớ ngoài,… của các thuật toán. Khai
phá dữ liệu sẽ hiệu quả hơn khi bước tiền xử lý, lựa chọn thuộc tính, mô

hình được giải quyết tốt.
Sau đây là tổng hợp các đặc tính của các phương pháp và các thuật
toán PCDL nhằm làm căn cứ cho việc lựa chọn phương pháp khi phát triển
các ứng dụng khác. Tùy vào từng ứng dụng và căn cứ vào các đặc tính của
thuật toán ta có thể tìm được các thuật toán phù hợp để áp dụng cho bài toán
thực tế.
16

CHƯƠNG 3. ỨNG DỤNG THUẬT TOÁN PHÂN CỤM
K-MEANS TRONG PHÂN TÍCH, ĐÁNH GIÁ KẾT QUẢ
ĐIỂM CỦA HỌC SINH.
3.1 Đặt vấn đề
Cuối mỗi học kì, mỗi năm học dựa trên kết quả điểm trung bình
(ĐTB) của học sinh các thầy, cô giáo, các nhà quản lý giáo dục đều muốn
có được những thông tin tổng hợp về tình hình học tập của trường, của lớp.
Những cách thống kê thường thấy như:
– Tính ĐTB theo bộ môn của từng giáo viên, từng lớp, từng khối
hoặc toàn trường …
– Đếm số lượng ĐTB trong ngưỡng nào đó. Ví dụ, số học sinh đạt
ĐTB dưới 5.0, số học sinh đạt ĐTB trên 8.0 …
Những cách thống kê đó chưa thể đánh giá chính xác kết quả học
tập của học sinh và từ đó các nhà trường chưa có được các các biện pháp
giáo dục phù hợp nhất. Vì vậy, tôi có ý tưởng áp dụng kỹ thuật phân cụm
trong khai phá dữ liệu để phân tích, đánh giá dữ liệu điểm của học sinh.
3.2 Giải quyết vấn đề
3.2.1 Xác định bài toán
Dữ liệu vào (Input): Dữ liệu được thu thập từ ĐTB, điểm tổng kết
cuối học kì, cuối năm học của học sinh.
Dữ liệu ra (Output): Các cụm học sinh được phân nhóm theo kết
quả ĐTB của một hay một số bộ môn, hoặc phân cụm theo ĐTB học kỳ,

ĐTB cả năm.
17

Dựa vào những kết quả phân cụm người quản lí sẽ có những định
hướng cho việc dạy và học của giáo viên và học sinh, đánh giá được năng
lực học tập hiện tại của các nhóm học sinh dựa trên CSDL đưa vào.
3.2.2 Lựa chọn thuật toán
Trong các thuật toán phân cụm dữ liệu đã tìm hiểu ở Chương 2 thì
thuật toán k-means có tốc độ tương đối nhanh, thích hợp với dữ liệu số khi
không có phần tử nhiễu. Dữ liệu điểm của học sinh trong trường phổ thông
hiện nay đáp ứng tốt yêu cầu của thuật toán k-means (dữ liệu số, điểm số
trong khoảng từ 0-10, không có phẫn tử nhiễu). Vì vậy, tôi đã chọn thuật
toán k-means để áp dụng cho bài toán này.
3.2.3 Chương trình ứng dụng
Các chức năng chính của chương trình:
– Nhập và xem dữ liệu: Dữ liệu ĐTB trên các tệp Excel được nhập
(Import) và được lưu trữ trên SQL-Server để tiện sử dụng. Sau khi nhập dữ
liệu người sử dụng có thể xem lại dữ liệu theo từng năm học và từng khối
lớp.
– Phân cụm dữ liệu theo ĐTB cả năm hoặc phân cụm theo ĐTB
một hoặc nhiều môn học: Chương trình cho phép chọn năm học, khối lớp
cần phân tích, số cụm muốn phân tích, các môn học được phân tích … trong
phần Tùy chọn phân cụm. Phần hiển thị kết quả phân cụm đưa ra thông tin
các cụm: tên cụm, số phần tử, tỷ lệ, biểu đồ của các cụm và thông tin chi tiết
cụm (tên học sinh trong cụm, các dữ liệu điểm tương ứng của từng học sinh,
thống kê số lượng theo từng lớp) … các kết quả phân cụm có thể xuất ra tệp
Excel để tiện sử dụng cho nhiều công việc khác.

18

Hình 3.2 Giao diện nhập và xem dữ liệu
3.3 Kết quả thử nghiệm
Trên thực tế, kết quả học tập của học sinh được đánh giá dựa trên
học lực và hạnh kiểm. Trong luận văn này chỉ phân tích các dữ liệu về ĐTB
của học sinh (đánh giá về học lực). Có 5 mức xếp loại học lực của học sinh:
Giỏi, Khá, Trung bình, Yếu, Kém. Vì vậy, trong quá trình thử nghiệm tôi
chọn số cụm để phân tích từ 3 đến 5 cụm và có thể phân tích theo ĐTB cuối
mỗi học kì hoặc ĐTB cuối năm học.
19

3.3.1 Phân cụm theo ĐTB cả năm

Hình 3.3 Phân cụm dữ liệu theo điểm trung bình cả năm

Ví dụ, từ kết quả phân cụm với dữ liệu khối 12 năm 2012 có thể
đưa ra một vài đánh giá và nhận xét như sau:
– Kết quả học tập của học sinh khối 12 không có em nào học lực
yếu (100% học sinh đủ điều kiện dự thi tốt nghiệp). Số học sinh học có học
lực trung bình là 237 học sinh (chiếm tỷ lệ 38.85%), số học sinh có học lực
khá giỏi là 373 em (chiếm tỷ lệ 61.15%).
20

– Ban giám hiệu nhà trường cần rút kinh nghiệm với công tác chủ
nhiệm và việc dạy-học với một số lớp như 12A12 (có 25 em xếp loại trung
bình, 15 em khá giỏi), lớp 12A1 có sự phân cấp quá rõ ràng giữa 2 loại học
sinh khá giỏi và yếu kém, cần có biện pháp hay kế hoạch phụ đạo các học
sinh yếu kém.
– So sánh với kết quả phân cụm trên dữ liệu điểm của học kì 1 và

kết quả phân cụm học sinh năm học trước (năm 2011) cho thấy sự ổn định
và tiến bộ trong việc học tập của học sinh.
3.3.2 Phân cụm theo ĐTB môn học
Với chức năng Phân cụm theo ĐTB các môn học, ta có thể chọn
một hoặc một vài môn học để phân tích.
Dựa trên kết quả phân cụm khi sử dụng chức năng Phân cụm theo
ĐTB môn người sử dụng có thể thực hiện các yêu cầu như:
– Chọn đội tuyển học sinh giỏi các bộ môn: chọn một môn học để
phân cụm và lấy danh sách học sinh trong cụm có ĐTB cao nhất (các học
sinh khá giỏi).
– Chọn danh sách học sinh cần học phụ đạo: lấy danh sách trong
cụm có ĐTB thấp nhất (các học sinh có học lực yếu, kém và trung bình).
– Định hướng khối thi Đại học cho học sinh: phân cụm các môn thi
theo khối thi và chọn ra danh sách học sinh trong các cụm có tổng ĐTB cao
nhất.
– Đánh giá việc giảng dạy, học tập của giáo viên và học sinh. Có kế
hoạch điều chuyển học sinh giữa các lớp để các em có môi trường học tập
tốt nhất.
21

Hình 3.4 Phân cụm dữ liệu theo điểm trung bình môn học
3.3.3 Phân cụm dữ liệu điểm trên phần mềm WEKA và
SPSS
Phân cụm dữ liệu điểm trên phần mềm WEKA:
– Các học sinh có học lực khá tập trung ở cụm 0 và cụm 3
– Các học sinh có học lực trung bình tập trung ở các cụm 1, cụm 2
và cụm 4
22

Số học sinh có học lực trung bình chiếm tỷ lệ tương đối cao
(khoảng 60%), từ đó cho thấy Nhà trường cần có các biện pháp thúc đẩy
việc dạy và học để đạt kết quả cao hơn nữa.
Phần mềm WEKA ngoài việc đưa ra trọng tâm các cụm, thống kê
số lượng và tỷ lệ phần tử trong từng cụm còn cung cấp công cụ đưa ra hình
ảnh trực quan của các cụm dữ liệu.
– Phân cụm dữ liệu điểm trên phần mềm SPSS:
– Số học sinh có học lực khá khoảng gần 600 em và tập trung ở
cụm 3, cụm 5 (khoảng 35%). Kết quả phân cụm trên SPSS cũng tương
đương với kết quả phân cụm trên WEKA.
+ Đánh giá kết quả thử nghiệm:
Các chương trình như WEKA, SPSS thường chỉ đưa ra trọng tâm
các cụm và thống kê số phần tử và tỷ lệ trong từng cụm. Kết quả đó chưa hỗ
trợ tốt cho việc phân tích và đánh giá kết quả học tập của học sinh. Với
chương trình ứng dụng tôi xây dựng phần nào đã hỗ trợ tốt hơn khi đưa ra
được thông tin các cụm, đồ thị tương ứng và danh sách học sinh tương ứng
trong từng cụm.
Kết luận chương
Việc phân cụm các học sinh chính là việc nhóm các học sinh có
khả năng học tốt hay học yếu ở cùng một số môn học vào một cụm. Nói
cách khác, phân cụm học sinh là quá trình nhóm các học sinh có sự tương
đồng về điểm số vào một cụm. Các học sinh ở các cụm khác nhau thì có đặc
tính điểm số khác nhau.
Từ những kết quả phân cụm, các nhà quản lí, các giáo viên có thể
đưa ra các chiến lược đào tạo để bồi dưỡng học sinh khá giỏi, phụ đạo học
sinh yếu kém và điều phối phân công giảng dạy hợp lí.
23

KẾT LUẬN

Luận văn nghiên cứu, tổng hợp những nét đặc trưng nhất trong lĩnh
vực Khai phá dữ liệu nói chung và phương pháp Phân cụm dữ liệu nói
riêng. Luận văn đã nghiên cứu, tìm hiểu và trình bày được một số kỹ thuật
và thuật toán phân cụm dữ liệu điển hình, dựa trên các phương pháp đã có,
cài đặt thử nghiệm thuật toán k-means trong chương trình phân cụm học
sinh theo kết quả điểm trung bình môn học và điểm trung bình cuối kì, cuối
năm học nhằm hỗ trợ phân tích, đánh giá kết quả học tập của học sinh đa
chiều hơn, đa dạng hơn và giúp Ban giám hiệu Nhà trường, các nhà quản lý
giáo dục có thêm cơ sở để đánh giá đúng đắn 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ừ đó đề 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 những gì mà luận văn đã thực hiện và đạt được, hướng phát
triển sau này của luận văn như sau:
Về lý thuyết: tiếp tục nghiên cứu các phương pháp, các cách tiếp
cận mới trong lĩnh vực Khai phá dữ liệu như KPDL thời gian thực, khai phá
dựa trên tìm kiếm … và các phương pháp Phân cụm dữ liệu như: phân cụm
mờ, phân cụm thống kê, phân cụm dựa trên đồ thị, phân cụm không gian …
tìm kiếm, so sánh và chọn lựa thuật toán tối ưu nhất để giải quyết bài toán
đã đưa ra.
Về thực tiễn: sẽ phát triển thành bài toán với dữ liệu lớn hơn, quan
tâm đến nhiều chọn lựa hơn như phân cụm dựa trên: đạo đức (hạnh kiểm)
của học sinh, vùng miền địa phương học sinh cư trú, hoàn cảnh gia đình của
học sinh, … và vấn đề nhập dữ liệu từ nhiều hệ quản trị CSDL khác nhau.
Người hướng dẫn khoa học : GS.TS. Vũ Đức ThiPhản biện 1 : … … … … … … … … … … … … … … … … Phản biện 2 : … … … … … … … … … … … … … … … … Luận văn sẽ được bảo vệ trước Hội đồng chấm luận vănthạc sĩ tại Học viện Công nghệ Bưu chính Viễn thôngVào lúc : giờ ngày tháng nămCó thể khám phá luận văn tại : – Thư viện của Học viện Công nghệ Bưuchính Viễn thôngMỞ ĐẦUKhai phá dữ liệu đã và đang được nghiên cứu và điều tra, ứng dụng nhiềutrong những nghành nghề dịch vụ khác nhau và mang lại những quyền lợi to lớn. Những vấnđề được chăm sóc trong khám phá dữ liệu là phân lớp, luật phối hợp, phân cụmdữ liệu … Phân cụm dữ liệu ( PCDL ) là quy trình tìm kiếm để phân ra cáccụm dữ liệu, những mẫu dữ liệu từ tập CSDL lớn. PCDL là một trong nhữngkỹ thuật để khai thác dữ liệu có hiệu suất cao. PCDL đã được ứng dụng trongnhiều nghành nghề dịch vụ khác nhau : kinh tế tài chính, y học, sinh học, bảo hiểm, quy hoạch đôthị, phân đoạn ảnh … Ngành giáo dục nói chung và những trường học nói riêng có lượng dữliệu tàng trữ khá lớn nhưng việc nghiên cứu và phân tích, nhìn nhận để đưa ra những chiến lượcphát triển tương thích, cung ứng chất lượng giáo dục tốt hơn và tương hỗ những hoạtđộng quản lí lúc bấy giờ chưa thực sự được chăm sóc đúng mức và khai tháccó hiệu suất cao. Với những nguyên do như vậy tôi chọn đề tài “ Ứng dụng phân cụm dữliệu trong nghiên cứu và phân tích, nhìn nhận hiệu quả điểm của học viên ” làm đề tài luậnvăn tốt nghiệp. Bố cục luận văn gồm 3 chương : Chương 1 : Tìm hiểu tổng quan về khám phá dữ liệu và kỹ thuậtphân cụm dữ liệu trong KPDL.Chương 2 : Tìm hiểu 1 số ít thuật toán nổi bật trong phân cụmdữ liệu. Chương 3 : Ứng dụng thuật toán k-means để thử nghiệm phân cụmtrên dữ liệu điểm của học viên. CHƯƠNG I. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀPHÂN CỤM DỮ LIỆU1. 1 Khai phá dữ liệu1. 1.1. Giới thiệu về Khai phá dữ liệuKhai phá dữ liệu ( Data Mining ) là một khái niệm sinh ra vào nhữngnăm cuối thập kỷ 80 của thế kỉ XX. Khai phá dữ liệu là một nghành đượcnghiên cứu nhằm mục đích tự động hóa khai thác thông tin, tri thức mới có ích, tiềm ẩntừ những CSDL lớn, kho dữ liệu … Khai phá dữ liệu là nghành đã và đang trở thành một trong nhữnghướng nghiên cứu và điều tra lôi cuốn được sự chăm sóc của nhiều chuyên viên về CNTTtrên quốc tế. Trong những năm gần đây, rất nhiều những giải 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ế, quyền lợi và năng lực ứng dụng thực tiễn to lớn của khám phá dữ liệu. 1.1.2 Quá trình tìm hiểu và khám phá dữ liệuVề thực chất khám phá dữ liệu là quy trình tiến độ duy nhất tìm ra đượcnhững thông tin mới, tiềm ẩn trong CSDL và hầu hết ship hàng cho quá trìnhmô tả và Dự kiến. Quá trình khám phá dữ liệu gồm những bước chính được biểu lộ nhưhình sau : Hình 1.2 Quá trình khám phá dữ liệu1. 1.3 Các kỹ thuật khám phá dữ liệuVới mục tiêu miêu tả và Dự kiến, những kỹ thuật thường sử dụng là : – Luật phối hợp ( Association rules ) – Phân cụm ( Clustering ) – Phân lớp ( Classfication ) – Hồi quy ( Regression ) – Cây quyết định hành động ( Decision Trees ) – Mạng nơ-ron ( Neural Network ) – Trực quan hóa ( Visualization ) – Biểu diễn quy mô ( Model Evaluation ) – Phương pháp tìm kiếm ( Search Method ) – Phân tích theo trình tự thời hạn ( Time series Analysis ) 1.1.4 Ứng dụng của Khai phá dữ liệu1. 1.5 Các xu thế và yếu tố cần xử lý trong khai phádữ liệu1. 2 Kỹ thuật phân cụm trong Khai phá dữ liệu1. 2.1 Tổng quan về kỹ thuật phân cụmPhân cụm dữ liệu là quy trình nhóm một tập những đối tượng người dùng tương tựnhau trong tập dữ liệu vào những cụm sao cho những đối tượng người dùng thuộc cùng mộtcụm là tương đương còn những đối tượng người tiêu dùng thuộc những cụm khác nhau sẽ khôngtương đồng. Phân cụm dữ liệu là một kỹ thuật trong KPDL nhằm mục đích tìm kiếm, phát hiện những cụm, những mẫu dữ liệu tự nhiên tiềm ẩn và quan trọng trong tậpdữ liệu lớn để từ đó cung ứng thông tin, tri thức cho việc ra quyết định hành động. Phân cụm dữ liệu còn hoàn toàn có thể được sử dụng như một bước tiền xử lícho những thuật toán tìm hiểu và khám phá dữ liệu khác như thể phân loại và miêu tả đặcđiểm, có tính năng trong việc phát hiện ra những cụm. 1.2.2 Một số khái niệm thiết yếu khi tiếp cận phân cụm dữliệu1. 2.2.1 Các kiểu dữ liệu và thuộc tính trong phép phân cụm1. 2.2.2 Đo độ tương đồng1. 2.3 Các nhu yếu so với kỹ thuật phân cụm dữ liệu – Có năng lực lan rộng ra – Thích nghi với những kiểu dữ liệu khác nhau – Khám phá ra những cụm với hình thù bất kể – Tối thiểu lượng tri thức cần cho xác lập những tham số vào – Khả năng thích nghi với dữ liệu nhiễu cao – Ít nhạy cảm với những tham số nguồn vào – Thích nghi với dữ liệu đa chiều – Dễ hiểu, dễ setup và khả thi1. 2.4 Các hướng tiếp cận trong phân cụm dữ liệu1. 2.4.1 Phương pháp phân hoạch ( Partitioning Methods ) chia mộttập hợp dữ liệu có n thành phần thành k nhóm cho đến khi xác lập số những cụmđược thiết lập. Số những cụm được thiết lập là những đặc trưng được lựa chọntrước. Phương pháp này là tốt cho việc tìm những cụm hình cầu trong khônggian Euclid. 1.2.4. 2 Phương pháp phân cụm phân cấp ( HierarchicalMethods ) kiến thiết xây dựng một phân cấp trên cơ sở những đối tượng người tiêu dùng dữ liệu đang xemxét. Phương pháp này là hoàn toàn có thể làm việc tốt với những tập dữ liệu lớn nhưngkhó khăn với những cụm có hình dạng lồi. 1.2.4. 3 Phương pháp phân cụm dựa trên tỷ lệ ( Density-Based Methods ) nhóm những đối tượng người dùng dữ liệu dựa trên hàm tỷ lệ xác lập, tỷ lệ là số những đối tượng người dùng lân cận của một đối tượng người dùng dữ liệu theo một nghĩanào đó. Phương pháp phân cụm dựa trên tỷ lệ của những đối tượng người tiêu dùng để xácđịnh những cụm dữ liệu hoàn toàn có thể phát hiện ra những cụm dữ liệu với hình thù bấtkỳ. 1.2.4. 4 Phương pháp phân cụm dựa trên lưới ( Grid-BasedMethods ) thích hợp với dữ liệu nhiều chiều, dựa trên cấu trúc dữ liệu lướiđể phân cụm, chiêu thức này đa phần tập trung chuyên sâu vận dụng cho lớp dữ liệukhông gian1. 2.4.5 Phương pháp phân cụm dựa trên quy mô ( Model-Based Clustering Methods ) mày mò những phép xê dịch tốt của những tham sốmô hình sao cho khớp với dữ liệu một cách tốt nhấtKết luận chươngChương 1 khám phá những kỹ năng và kiến thức cơ bản về tìm hiểu và khám phá dữ liệu vàcác kỹ thuật vận dụng trong KPDL, những ứng dụng và xu thế của KPDL, Chương này cũng tìm hiểu và khám phá một hướng điều tra và nghiên cứu và ứng dụngtrong KPDL là phân cụm dữ liệu, gồm tổng quan về kỹ thuật phân cụm, cácyêu cầu so với kỹ thuật phân cụm, những hướng tiếp cận trong phân cụm dữliệu, những kiểu dữ liệu, độ đo tương tự như, v.v CHƯƠNG II. MỘT SỐ THUẬT TOÁN PHÂN CỤM DỮ LIỆUĐIỂN HÌNH2. 1 Các thuật toán phân cụm phân hoạch2. 1.1 Thuật toán K-meansĐầu vào : Một CSDL gồm n đối tượng người tiêu dùng và số những cụm k. Đầu ra : Các cụm C ( i = 1, , k ) sao cho hàm tiêu chuẩn E đạt giá trị tối thiểu. Bước 1 : Khởi tạoChọn k đối tượng người tiêu dùng m ( j = 1 k ) là trọng tâm bắt đầu của k cụm từ tập dữ liệuBước 2 : Tính toán khoảng chừng cáchĐối với mỗi đối tượng người dùng X ( i = 1, , n ), thống kê giám sát khoảng cách từ nó tới mỗitrọng tâm mvới j = 1, , k ; sau đó tìm trọng tâm gần nhất so với mỗi đốitượng. Bước 3 : Cập nhật lại trọng tâmĐối với mỗi j = 1, , k ; update trọng tâm cụm mbằng cách xác lập trungbìnhcộng của những véc-tơ đối tượng người dùng dữ liệu. Bước 4 : Điều kiện dừngLặp những bước 2 và 3 cho đến khi những trọng tâm của cụm không thay đổi2. 1.2 Thuật toán PAMĐầu vào : Số cụm k và một cơ sở dữ liệu D chứa n đối tượngĐầu ra : Một tập k cụm đã tối thiểu hoá tổng những độ đo không tương đồngcủa tổng thể những đối tượng người tiêu dùng tới medoid gần nhất của chúngBắt đầu1. Chọn tuỳ ý k đối tượng người tiêu dùng đại diện thay mặt bắt đầu ; 2. Repeat3. Ấn định mỗi đối tượng người tiêu dùng vào cụm có những đối tượng người tiêu dùng đại diện thay mặt ( medoid ) gầnnó nhất ; 4. Lựa chọn ngẫu nhiên một đối tượng người dùng không nổi bật orandom5. Tính hàm mục tiêu S ( tổng những độ đo tương đương của toàn bộ những đối tượngtới medoid gần nhất cùa chúng ) bằng việc tráo đổi ovới orandom6. Nếu S < 0 tráo đổi ovới orandomđể tạo thành những tập mới của k đối tượngđại diện ; 7. Until không có sự đổi khác nàoKết thúc2. 1.3 Thuật toán CLARANSFor i = 1 to numlocal doBeginKhởi tạo ngẫu nhiên k đối tượng người tiêu dùng medoisj = 1 ; while j < maxneighbor doBeginChọn ngẫu nhiên một láng giềng R của S.Tính toán độ phi tựa như về khoảng cách giữa 2 láng giềng S và R.Nếu R có ngân sách thấp hơn thì hoán đối R cho S và j = 1 ngược lại j + + ; End ; Kiểm tra khoảng cách của phân hoạch S có nhỏ hơn khoảng cách nhỏ nhấtkhông, nếu nhỏ hơn thì lấy giá trị này để update lại khoảng cách nhỏ nhấtvà phân hoạch S là phân hoạch tốt nhất tại thời gian hiện tại. End. 2.2 Các thuật toán phân cụm phân cấp2. 2.1 Thuật toán BIRCHBước 1 : Duyệt toàn bộ những đối tượng người tiêu dùng trong CSDL và thiết kế xây dựng một cây CFkhởi tạo. Một đối tượng người dùng được chèn vào nút lá gần nhất tạo thành cụm con. Nếu đường kính của cụm con này lớn hơn T thì nút lá được tách. Khi mộtđối tượng thích hợp được chèn vào nút lá, toàn bộ những nút trỏ tới gốc của câyđược update với những thông tin thiết yếu. Bước 2 : Nếu cây CF hiện thời không có đủ bộ nhớ trong thì triển khai xâydựng một cây CF nhỏ hơn bằng cách tinh chỉnh và điều khiển bởi tham số T ( vì tăng Tsẽ làm hoà nhập một số ít những cụm con thành một cụm, điều này làm cho câyCF nhỏ hơn ). Bước này không cần nhu yếu khởi đầu đọc dữ liệu lại từ đầunhưng vẫn bảo vệ hiệu chỉnh cây dữ liệu nhỏ hơn. Bước 3 : Thực hiện phân cụm : Các nút lá của cây CF lưu giữ những đạilượng thống kê của những cụm con. Trong bước này, BIRCH sử dụng những đạilượng thống kê này để vận dụng một số ít kỹ thuật phân cụm thí dụ như k-means và tạo ra một khởi tạo cho phân cụm. Bước 4 : Phân phối lại những đối tượng người dùng dữ liệu bằng cách dùng những đối tượngtrọng tâm cho những cụm đã được mày mò từ bước 3 : Đây là một bước tuỳchọn để duyệt lại tập dữ liệu và gán nhãn lại cho những đối tượng người tiêu dùng dữ liệu tớicác trọng tâm gần nhất. Bước này nhằm mục đích để gán nhãn cho những dữ liệu khởitạo và vô hiệu những đối tượng người dùng ngoại lai2. 2.2 Thuật toán CUREBước 1. Chọn một mẫu ngẫu nhiên từ tập dữ liệu khởi đầu ; Bước 2. Phân hoạch mẫu này thành nhiều nhóm dữ liệu có size bằngnhau : Ý tưởng chính ở đây là phân hoạch mẫu thành p nhóm dữ liệu bằngnhau, kích cỡ của mỗi phân hoạch là n ' / p ( với n ' là kích cỡ của mẫu ) ; Bước 3. Phân cụm những điểm của mỗi nhóm : Ta thực thi PCDL cho cácnhóm cho đến khi mỗi nhóm được phân thành n ' / ( pq ) cụm ( với q > 1 ) ; Bước 4. Loại bỏ những thành phần ngoại lai : Trước hết, khi những cụm được hìnhthành cho đến khi số những cụm giảm xuống một phần so với số những cụm banđầu. Sau đó, trong trường hợp những thành phần ngoại lai được lấy mẫu cùng vớiquá trình pha khởi tạo mẫu dữ liệu, thuật toán sẽ tự động hóa vô hiệu những nhómnhỏ. Bước 5. Phân cụm những cụm khoảng trống : Các đối tượng người tiêu dùng đại diện thay mặt cho cáccụm vận động và di chuyển về hướng TT cụm, nghĩa là chúng được sửa chữa thay thế bởicác đối tượng người dùng gần TT hơn. Bước 6. Đánh dấu dữ liệu với những nhãn tương ứng. 2.3 Các thuật toán phân cụm dựa trên mật độ2. 3.1 Thuật toán DBSCANInput : Tập dữ liệu D chứa n đối tượng người dùng, ε là tham số nửa đường kính và MinPtsngưỡng tỷ lệ láng giềng. Output : Tập những cụm dựa trên tỷ lệ. ( 1 ) lưu lại toàn bộ những đối tượng người dùng là chưa thăm ; ( 2 ) lặp ( 3 ) lựa chọn ngẫu nhiên một đối tượng người tiêu dùng chưa thăm p ; 10 ( 4 ) ghi lại đã thăm p ; ( 5 ) nếu những ε láng giềng của p có tối thiểu MinPts đối tượng người dùng ( 6 ) tạo mới một cụm C và thêm p vào C ; ( 7 ) cho N là tập những đối tượng người tiêu dùng trong ε láng giềng của p ; ( 8 ) lặp : với mỗi điểm p ’ trong N ( 9 ) nếu p’chưa thăm ( 10 ) lưu lại p ’ đã thăm ; ( 11 ) nếu ε láng giềng của p ’ có tối thiểu MinPts điểm, thêm những điểm này đến N ; ( 12 ) nếu p’không phải là thành viên của bất kể cụm nào, thêm p ’ vào C ; ( 13 ) kết thúc lặp ( 14 ) đưa ra C ; ( 15 ) ngược lại ghi lại p như là nhiễu ; ( 16 ) cho đến khi thăm hết những đối tượng người tiêu dùng ; 2.3.2 Thuật toán DENCLUDEDENCLUDE là giải pháp dựa trên một tập những hàm phân phốimật độ và được kiến thiết xây dựng trên những sáng tạo độc đáo như sau : – Sự ảnh hưởng tác động của mỗi điểm dữ liệu hoàn toàn có thể trình diễn dưới dạngmô hình qua hàm toán học, được gọi là hàm ảnh hưởng tác động ( influence fuction ), dùng để miêu tả tác động ảnh hưởng của điểm dữ liệu với những đối tượng người dùng láng giềng củanó ; – Mật độ toàn cục của khoảng trống dữ liệu hoàn toàn có thể được quy mô hóalà tổng những hàm tác động ảnh hưởng của tổng thể những điểm dữ liệu ; – Các cụm hoàn toàn có thể xác lập theo toán học bằng việc xác lập cácđiểm tỷ lệ cao ( density attractors ), trong đó điểm tỷ lệ cao là những điểmcực đại hàm tỷ lệ toàn cục. 112.4 Các thuật toán phân cụm dựa trên lưới2. 4.1 Thuật toán STINGBước 1. Xác định tầng để mở màn. Bước 2. Với mỗi cái của tầng này, giám sát khoảng chừng đáng tin cậy ( hoặc ướclượng khoảng chừng ) của Tỷ Lệ mà ô này tương quan tới truy vấn. Bước 3. Từ khoảng chừng an toàn và đáng tin cậy của thống kê giám sát trên, gán nhãn cho là có liênquan hoặc không tương quan. Bước 4. Nếu lớp này là lớp sau cuối, chuyển sang Bước 6 ; nếu khác thìchuyển sang Bước 5. Bước 5. Duyệt xuống dưới của cấu trúc cây phân cấp một mức. Chuyểnsang bước 2 cho những ô mà hình thành những ô tương quan của lớp có mức caohơn. Bước 6. Nếu đặc tả được câu truy vấn, chuyển sang bước 8 ; nếu khôngthì chuyển sang bước 7. Bước 7. Truy lục lại dữ liệu vào trong những ô tương quan và triển khai giải quyết và xử lý. Trả lại hiệu quả tương thích nhu yếu của truy vấn. Chuyển sang Bước 9. Bước 8. Tìm thấy những miền có những ô tương quan. Trả lại miền mà phù hợpvới nhu yếu của truy vấn. Chuyển sang bước 9. Bước 9. Dừng2. 4.2 Thuật toán CLIQUEBước 1 : Phân hoạch tập dữ liệu thành những hình hộp chữ nhật và tìm cáchình hộp chữ nhật đặc ( nghĩa là những hình hộp này chứa 1 số ít những đốitượng dữ liệu trong số những đối tượng người tiêu dùng láng giềng cho trước ). Bước 2 : Xác định khoảng trống con chứa những cụm được sử dụng nguyên lýApriori. 12B ước 3 : Hợp những hình hộp này tạo thành những cụm dữ liệu. Bước 4 : Xác định những cụm : Trước hết nó tìm những ô đặc đơn chiều, tiếpđến chúng tìm những hình chữ nhật 2 chiều, rồi 3 chiều, …, cho đến khihình hộp chữ nhật đặc k chiều được tìm thấy. 2.5 Các thuật toán phân cụm dựa trên mô hình2. 5.1 Thuật toán EM1. Khởi tạo tham số ( 0 ) ( 0 ) ( 0 ) ( 0 ) ( 0 ) ( 0 ) 0 1 2 1 2 {, ,, ,, ,, } k kp p p     2. Bước E ( ) 2 ( ) ( ) 2 ( ) ( x |, ) (, ) ( |, , ) P ( |, ) (, ) ( |, , ) Pt tk j t j tk i i ij k tt tk t k i i jP PP xP xP x P x                3. Bước M ( 1 ) ( |, ) ( |, ) i k t ki k tP x xP x     ( 1 ) ( |, ) i k tP x   4. Lặp lại bước 2, 3 cho đến khi đạt kết quả132. 5.2 Thuật toán COBWEB1 ) Khởi tạo cây khởi đầu bằng một nút rỗng. 2 ) Sau khi thêm vào từng nút một và update lại cây cho tương thích tạimỗithời điểm. 3 ) Cập nhật cây khởi đầu từ lá bên phải trong mỗi trường hợp, sau đó cấutrúc lại cây. 4 ) Quyết định update dựa trên sự phân hoạch và những hàm tiêu chuẩnphân loại. 2.5.3 Thuật toán SOMBước 1 : Khởi tạoChọn giá trị ngẫu nhiên cho những véc-tơ khối lượng bắt đầu wBước 2 : Lấy mẫuLấy một mẫu giảng dạy véc-tơ x từ tập huấn luyện. Bước 3 : Ghép mẫuTìm nơ-ron I ( x ) tốt nhất có véc-tơ trọng số gần nhất với giá trị của véc-tơđầu vào, ví dụ giá trị nhỏ nhất ( ) ( w ) j i jid x x   Bước 4 : Cập nhậtCập nhật thành phần trọng số, ( ) ) w ( ) ( ) ( wji j I x i jit T t x    với, ( ) ( ) j I xT tlà Gauss lân cận và ( ) tlà tỷ suất học. Bước 5 : Lặp lạiLặp lại bước 2 cho đến khi giải thuật tối ưu hoặc đạt đến số lần lặp xácđịnh N cho trước. 142.6 Các thuật toán phân cụm có dữ liệu ràng buộc2. 6.1 Thuật toán K-PrototypeInput : Tập dữ liệu khởi đầu X và số cụm k. Output : k đối tượng người tiêu dùng mẫu sao cho hàm tiêu chuẩn đạt giá trị tối thiểu. Bước 1 : Khởi tạo k đối tượng người dùng mẫu khởi đầu cho X, mỗi đối tượng người tiêu dùng mẫuđóng vai trò là tâm đại diện thay mặt của mỗi cụm. Bước 2 : Phân phối mỗi đối tượng người dùng trong X cho mỗi cụm sao cho chúnggần nhất với đối tượng người dùng mẫu trong cụm, đồng thời update lại đốitượng mẫu cho mỗi cụm. Bước 3 : Sau khi toàn bộ những đối tượng người tiêu dùng đã được phân phối hết cho cáccụm, kiểm tra lại độ tựa như của những đối tượng người dùng trong mỗi cụm với cácđối tượng mẫu, nếu có một đối tượng người tiêu dùng mẫu tựa như nhất với nó màkhác với đối tượng người tiêu dùng mẫu của cụm hiện thời thì vận động và di chuyển đối tượngđang xét này sang cụm tương ứng với đối tượng người dùng mẫu mà nó gần nhấtvà đồng thời update những đối tượng người dùng mẫu cho hai cụm này. Bước 4 : Lặp bước 3 cho đến khi không có đối tượng người dùng nào đổi khác saukhi đã kiểm tra hàng loạt những đối tượng người tiêu dùng. 2.6.2 Thuật toán COP-KMeansInput : – Tập những đối tượng người tiêu dùng dữ liệu – Số lượng cụm : K – Tập ràng buộc must-link và cannot-linkOutput : K phân hoạch tách rời sao cho hàm mục tiêu được tối ưu. Bước 1. Khởi tạo những cụm : những tâm khởi đầu được chọn ngẫu nhiên saocho không vi phạm ràng buộc đã cho. 15B ước 2. Lặp cho tới khi hội tụBước 2.1 Gán cụm : gán mỗi đối tượng người tiêu dùng dữ liệu vào trong cụm gầnnhất sao cho không vi phạm ràng buộcBước 2.2 Ước lượng tâm : update lại tâm là trung bình của tất cảđối tượng nằm trong cụm của tâm đó. Bước 2.3 t = t + 1K ết luận chươngChương 2 tìm hiểu và khám phá về 1 số ít thuật toán nổi bật trong phân cụmdữ liệu. Mỗi một thuật toán có độ đúng chuẩn riêng và năng lực thực hiệntrên từng size dữ liệu là khác nhau. Điều này còn tùy thuộc vào cáchtổ chức dữ liệu ở bộ nhớ chính, bộ nhớ ngoài, … của những thuật toán. Khaiphá dữ liệu sẽ hiệu suất cao hơn khi bước tiền giải quyết và xử lý, lựa chọn thuộc tính, môhình được xử lý tốt. Sau đây là tổng hợp những đặc tính của những chiêu thức và những thuậttoán PCDL nhằm mục đích làm địa thế căn cứ cho việc lựa chọn chiêu thức khi phát triểncác ứng dụng khác. Tùy vào từng ứng dụng và địa thế căn cứ vào những đặc tính củathuật toán ta hoàn toàn có thể tìm được những thuật toán tương thích để vận dụng cho bài toánthực tế. 16CH ƯƠNG 3. ỨNG DỤNG THUẬT TOÁN PHÂN CỤMK-MEANS TRONG PHÂN TÍCH, ĐÁNH GIÁ KẾT QUẢĐIỂM CỦA HỌC SINH. 3.1 Đặt vấn đềCuối mỗi học kì, mỗi năm học dựa trên hiệu quả điểm trung bình ( ĐTB ) của học viên những thầy, cô giáo, những nhà quản trị giáo dục đều muốncó được những thông tin tổng hợp về tình hình học tập của trường, của lớp. Những cách thống kê thường thấy như : – Tính ĐTB theo bộ môn của từng giáo viên, từng lớp, từng khốihoặc toàn trường … – Đếm số lượng ĐTB trong ngưỡng nào đó. Ví dụ, số học viên đạtĐTB dưới 5.0, số học viên đạt ĐTB trên 8.0 … Những cách thống kê đó chưa thể nhìn nhận đúng chuẩn tác dụng họctập của học viên và từ đó những nhà trường chưa có được những những biện phápgiáo dục tương thích nhất. Vì vậy, tôi có ý tưởng sáng tạo vận dụng kỹ thuật phân cụmtrong tìm hiểu và khám phá dữ liệu để nghiên cứu và phân tích, nhìn nhận dữ liệu điểm của học viên. 3.2 Giải quyết vấn đề3. 2.1 Xác định bài toánDữ liệu vào ( Input ) : Dữ liệu được tích lũy từ ĐTB, điểm tổng kếtcuối học kì, cuối năm học của học viên. Dữ liệu ra ( Output ) : Các cụm học viên được phân nhóm theo kếtquả ĐTB của một hay một số ít bộ môn, hoặc phân cụm theo ĐTB học kỳ, ĐTB cả năm. 17D ựa vào những hiệu quả phân cụm người quản lí sẽ có những địnhhướng cho việc dạy và học của giáo viên và học viên, nhìn nhận được nănglực học tập hiện tại của những nhóm học viên dựa trên CSDL đưa vào. 3.2.2 Lựa chọn thuật toánTrong những thuật toán phân cụm dữ liệu đã tìm hiểu và khám phá ở Chương 2 thìthuật toán k-means có vận tốc tương đối nhanh, thích hợp với dữ liệu số khikhông có thành phần nhiễu. Dữ liệu điểm của học viên trong trường phổ thônghiện nay phân phối tốt nhu yếu của thuật toán k-means ( dữ liệu số, điểm sốtrong khoảng chừng từ 0-10, không có phẫn tử nhiễu ). Vì vậy, tôi đã chọn thuậttoán k-means để vận dụng cho bài toán này. 3.2.3 Chương trình ứng dụngCác tính năng chính của chương trình : – Nhập và xem dữ liệu : Dữ liệu ĐTB trên những tệp Excel được nhập ( Import ) và được tàng trữ trên SQL-Server để tiện sử dụng. Sau khi nhập dữliệu người sử dụng hoàn toàn có thể xem lại dữ liệu theo từng năm học và từng khốilớp. – Phân cụm dữ liệu theo ĐTB cả năm hoặc phân cụm theo ĐTBmột hoặc nhiều môn học : Chương trình được cho phép chọn năm học, khối lớpcần nghiên cứu và phân tích, số cụm muốn nghiên cứu và phân tích, những môn học được nghiên cứu và phân tích … trongphần Tùy chọn phân cụm. Phần hiển thị tác dụng phân cụm đưa ra thông tincác cụm : tên cụm, số thành phần, tỷ suất, biểu đồ của những cụm và thông tin chi tiếtcụm ( tên học viên trong cụm, những dữ liệu điểm tương ứng của từng học viên, thống kê số lượng theo từng lớp ) … những hiệu quả phân cụm hoàn toàn có thể xuất ra tệpExcel để tiện sử dụng cho nhiều việc làm khác. 18H ình 3.2 Giao diện nhập và xem dữ liệu3. 3 Kết quả thử nghiệmTrên trong thực tiễn, tác dụng học tập của học viên được nhìn nhận dựa trênhọc lực và hạnh kiểm. Trong luận văn này chỉ nghiên cứu và phân tích những dữ liệu về ĐTBcủa học viên ( nhìn nhận về học lực ). Có 5 mức xếp loại học lực của học viên : Giỏi, Khá, Trung bình, Yếu, Kém. Vì vậy, trong quy trình thử nghiệm tôichọn số cụm để nghiên cứu và phân tích từ 3 đến 5 cụm và hoàn toàn có thể nghiên cứu và phân tích theo ĐTB cuốimỗi học kì hoặc ĐTB cuối năm học. 193.3.1 Phân cụm theo ĐTB cả nămHình 3.3 Phân cụm dữ liệu theo điểm trung bình cả nămVí dụ, từ hiệu quả phân cụm với dữ liệu khối 12 năm 2012 có thểđưa ra một vài nhìn nhận và nhận xét như sau : – Kết quả học tập của học sinh khối 12 không có em nào học lựcyếu ( 100 % học viên đủ điều kiện kèm theo dự thi tốt nghiệp ). Số học sinh học có họclực trung bình là 237 học viên ( chiếm tỷ suất 38.85 % ), số học viên có học lựckhá giỏi là 373 em ( chiếm tỷ suất 61.15 % ). 20 – Ban giám hiệu nhà trường cần rút kinh nghiệm tay nghề với công tác làm việc chủnhiệm và việc dạy-học với 1 số ít lớp như 12A12 ( có 25 em xếp loại trungbình, 15 em khá giỏi ), lớp 12A1 có sự phân cấp quá rõ ràng giữa 2 loại họcsinh khá giỏi và yếu kém, cần có giải pháp hay kế hoạch phụ đạo những họcsinh yếu kém. – So sánh với tác dụng phân cụm trên dữ liệu điểm của học kì 1 vàkết quả phân cụm học viên năm học trước ( năm 2011 ) cho thấy sự ổn địnhvà văn minh trong việc học tập của học viên. 3.3.2 Phân cụm theo ĐTB môn họcVới tính năng Phân cụm theo ĐTB những môn học, ta hoàn toàn có thể chọnmột hoặc một vài môn học để nghiên cứu và phân tích. Dựa trên hiệu quả phân cụm khi sử dụng tính năng Phân cụm theoĐTB môn người sử dụng hoàn toàn có thể thực thi những nhu yếu như : – Chọn đội tuyển học viên giỏi những bộ môn : chọn một môn học đểphân cụm và lấy list học viên trong cụm có ĐTB cao nhất ( những họcsinh khá giỏi ). – Chọn list học viên cần học phụ đạo : lấy list trongcụm có ĐTB thấp nhất ( những học viên có học lực yếu, kém và trung bình ). – Định hướng khối thi Đại học cho học viên : phân cụm những môn thitheo khối thi và chọn ra list học viên trong những cụm có tổng ĐTB caonhất. – Đánh giá việc giảng dạy, học tập của giáo viên và học viên. Có kếhoạch điều chuyển học viên giữa những lớp để những em có môi trường học tậptốt nhất. 21H ình 3.4 Phân cụm dữ liệu theo điểm trung bình môn học3. 3.3 Phân cụm dữ liệu điểm trên ứng dụng WEKA vàSPSSPhân cụm dữ liệu điểm trên ứng dụng WEKA : – Các học viên có học lực khá tập trung chuyên sâu ở cụm 0 và cụm 3 – Các học viên có học lực trung bình tập trung chuyên sâu ở những cụm 1, cụm 2 và cụm 422S ố học viên có học lực trung bình chiếm tỷ suất tương đối cao ( khoảng chừng 60 % ), từ đó cho thấy Nhà trường cần có những giải pháp thúc đẩyviệc dạy và học để đạt tác dụng cao hơn nữa. Phần mềm WEKA ngoài việc đưa ra trọng tâm những cụm, thống kêsố lượng và tỷ suất thành phần trong từng cụm còn cung ứng công cụ đưa ra hìnhảnh trực quan của những cụm dữ liệu. – Phân cụm dữ liệu điểm trên ứng dụng SPSS : – Số học sinh có học lực khá khoảng chừng gần 600 em và tập trung chuyên sâu ởcụm 3, cụm 5 ( khoảng chừng 35 % ). Kết quả phân cụm trên SPSS cũng tươngđương với hiệu quả phân cụm trên WEKA. + Đánh giá hiệu quả thử nghiệm : Các chương trình như WEKA, SPSS thường chỉ đưa ra trọng tâmcác cụm và thống kê số thành phần và tỷ suất trong từng cụm. Kết quả đó chưa hỗtrợ tốt cho việc nghiên cứu và phân tích và nhìn nhận hiệu quả học tập của học viên. Vớichương trình ứng dụng tôi kiến thiết xây dựng phần nào đã tương hỗ tốt hơn khi đưa rađược thông tin những cụm, đồ thị tương ứng và list học viên tương ứngtrong từng cụm. Kết luận chươngViệc phân cụm những học viên chính là việc nhóm những học viên cókhả năng học tốt hay học yếu ở cùng 1 số ít môn học vào một cụm. Nóicách khác, phân cụm học viên là quy trình nhóm những học viên có sự tươngđồng về điểm số vào một cụm. Các học viên ở những cụm khác nhau thì có đặctính điểm số khác nhau. Từ những hiệu quả phân cụm, những nhà quản lí, những giáo viên có thểđưa ra những kế hoạch giảng dạy để tu dưỡng học viên khá giỏi, phụ đạo họcsinh yếu kém và điều phối phân công giảng dạy phải chăng. 23K ẾT LUẬNLuận văn nghiên cứu và điều tra, tổng hợp những nét đặc trưng nhất trong lĩnhvực Khai phá dữ liệu nói chung và giải pháp Phân cụm dữ liệu nóiriêng. Luận văn đã nghiên cứu và điều tra, tìm hiểu và khám phá và trình diễn được 1 số ít kỹ thuậtvà thuật toán phân cụm dữ liệu nổi bật, dựa trên những chiêu thức đã có, thiết lập thử nghiệm thuật toán k-means trong chương trình phân cụm họcsinh theo tác dụng điểm trung bình môn học và điểm trung bình cuối kì, cuốinăm học nhằm mục đích tương hỗ nghiên cứu và phân tích, nhìn nhận tác dụng học tập của học viên đachiều hơn, phong phú hơn và giúp Ban giám hiệu Nhà trường, những nhà quản lýgiáo dục có thêm cơ sở để nhìn nhận đúng đắn nhất, đúng chuẩn nhất về tìnhhình học tập của học viên, hoạt động giải trí giảng dạy của giáo viên từ đó đề rađịnh hướng, hoạch định cho nhà trường trong việc nâng cao chất lượng giáodục. Với những gì mà luận văn đã triển khai và đạt được, hướng pháttriển sau này của luận văn như sau : Về triết lý : liên tục nghiên cứu và điều tra những chiêu thức, những cách tiếpcận mới trong nghành nghề dịch vụ Khai phá dữ liệu như KPDL thời hạn thực, khai phádựa trên tìm kiếm … và những giải pháp Phân cụm dữ liệu như : phân cụmmờ, phân cụm thống kê, phân cụm dựa trên đồ thị, phân cụm khoảng trống … tìm kiếm, so sánh và lựa chọn thuật toán tối ưu nhất để xử lý bài toánđã đưa ra. Về thực tiễn : sẽ tăng trưởng thành bài toán với dữ liệu lớn hơn, quantâm đến nhiều lựa chọn hơn như phân cụm dựa trên : đạo đức ( hạnh kiểm ) của học viên, vùng miền địa phương học viên cư trú, thực trạng mái ấm gia đình củahọc sinh, … và yếu tố nhập dữ liệu từ nhiều hệ quản trị CSDL khác nhau .

5/5 - (1 vote)
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments