Đề tài nghiên cứu khoa học cấp trường: Nghiên cứu ứng dụng thuật toán K-Means trong hỗ trợ phân loại và gợi ý sinh viên lựa chọn chuyên ngành học tập

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 (7.47 MB, 74 trang )

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

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC MỞ HÀ NỘI

BAO CÁO TONG KET

DE TÀI NGHIÊN CỨU KHOA HỌC VÀ CÔNG NGHỆ CAP TRUONG

NGHIÊN CUU UNG DUNG THUẬT TOÁN K-MEANS TRONG HO TRỢ PHAN LOẠI VA GỢI Ý SINH VIÊN LỰA CHỌN CHUYEN NGÀNH HỌC TẬP

Mã số: MHN2021-02.03

Chủ nghiệm đề tài: ThS Nguyễn Thị Tâm

Ha Nội, 06/2023

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

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC MỞ HÀ NỘI

BAO CÁO TONG KET

DE TAI NGHIEN CUU KHOA HQC VA CONG NGHE CAP TRUONG

NGHIÊN CUU UNG DỤNG THUẬT TOÁN K-MEANS TRONG HO TRỢ PHAN LOẠI VÀ GỢI Ý SINH VIÊN LỰA CHỌN CHUYÊN NGÀNH HỌC TẬP

Mã số: MHN2021-02.03

PTK Phụ trách Khoa CNTT Chủ nghiệm đề tài

Hà Nội, 06/2023

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

DANH SÁCH THÀNH VIÊN THAM GIA NGHIÊN CỨU ĐÈ TÀI TT Họ và tên Đơn vị công tác Nội dung tham gia

1 | Nguyễn Thị Tâm Khoa CNTT Chủ nghiệm đề tài

2 | Nguyễn Thị Quỳnh Như | Khoa CNTT Thu thập và xử lý dữ liệu dau vào đê phân cụm

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

PHAN MỞ DAU

1.1. Tinh cấp thiết của đề tai 1.2. Tơng quan tình hình nghiên cứu 1.3. Mục tiêu dé tài

1.4. Phương pháp nghiên cứu.1.5. Nội dung nghiên cứu....1.6. Phạm vi nghiên cứu:. 17. Y nghĩa nghiên cứu... PHAN NOI DUNG.... 1.5... Ứng dụng của phân cụm đữ liệu... 1.6. _ Thuật toán phân cụm K - Means...

Chương 2 Ứng dụng kĩ thuật phân cụm hỗ trợ sinh viên lựa chọn chuyên ngành... 2.1 Tiền xử lý dữ liệu...

2.2 Ứng dụng thuật toán K-means trong phân cụm chuyên ngành 2.3 Kết quả triển khai

KET LUẬN.

DANH MỤC TÀI LIỆU THAM KHẢO...

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

KDDKnowleadge Discovery in Database - phát hiện tri thức

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

DANH MỤC HÌNH ANH

Hình 1: Diém mơn Cơ Sở Lập Trình

Hình 2: Điểm mơn Cơ Sở Dữ Lit . Hình 3: Diém mơn Kỹ Thuật Lập Trình Hướng Đồi Tượng Hình 4: Diém mơn Thiết Kết Web.

Hình 5: Điển mơn Mạng Máy Tính. Hình 6: Điểm mơn Quản Tri Man; Hình 7: Diém mơn Lập Trình Web

Hình 8: Tập hợp dữ liệu điểm các mơn cơ sở can xét. Hình 9: Đăng nhập với quyền của giảng và Hình 10: Giảng viên nhập điểm mơn cho sinh viên.Hình 11: Admin đăng nhập tài khoản.

Hinh 12:Cửa số thực hiện phân cum di

Hình 13: Bảng điểm sinh viên qua bước tiền xử lý dit liệu... Hình 14: Cửa số lọc điểm sinh viên đủ điều kiện xét chuyên ngành. Hình 15: Bảng chọn chuyên ngành cần phân cụm và khởi tạo cụm ban đầu Hình 16: Kết quả phân cụm chuyên ngành Công Nghệ Phan Mém . Hình 17: Kết quả phân cụm chuyên ngành Cơng nghệ Da Phương TiệHình 18: Kết quả phân cụm chun ngành Mạng & KTMT... Hình 19: Phân tích dit liệu sau phân cụm Cơng Nghệ Phần M¿ Hình 20: Đăng nhập với quyên sinh viên

Hình 21: Gợi ý chuyên ngành phù hợp cho sinh viên khi đăng nhập Hình 22:: Sinh viên 'Pat' nhưng có dau điểm dưới 5.

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

THÔNG TIN KÉT QUẢ NGHIÊN CỨU

Tên đề tài: Nghiên cứu ứng dụng thuật toán K-means trong hỗ trợ phân loại và gợi ý sinh viên lựa chọn chuyên ngành học tập

Mã số: MHN2021-02.03

Chủ nhiệm đề tài: Nguyễn Thị Tâm. Tel:0947897634. - Email: Cơ quan chủ trì đề tài: Trường ĐH Mở Hà Nội.

Cơ quan và cá nhân phối hợp thực hiệt

- Khoa Công nghệ thông tin, Trường Dai học Mở Hà Nội. - ThS Nguyễn Thị Quỳnh Như, Khoa CNTT, Trường ĐH Mở HN. Thời gian thực hiện: 01/2021 - 06/2022

Mục tiêu đề tài:

Mục tiêu của đề tài "Nghiên cứu ứng dụng thuật toán K-Means trong hỗ trợ phân loại va gợi ý sinh viên lựa chọn chuyên ngành học taj

- Tìm hiểu về phân cụm dữ liệu, các phương pháp phân cum dữ liệu ~ Nghiên cứu thuật toán K-means phân cụm dữ liệu

- Xây dựng ứng dụng giúp phân loại sinh viên dựa trên điểm học tập một số môn cơ sở nhằm đưa ra các giải pháp tư vấn, định hướng giúp sinh viên lựa chọn chuyên ngành phù hợp.

Nội dung chính

~ Nghiên cứu về phân cụm dữ liệu, các phương pháp phân cum dit liệu, quy trình thực hiện phân cụm dữ liệu. Các lĩnh vực ứng dụng đang được triển khai dựa trên phân cụm dit liệu.

- Nghiên cứu thuật toán K-means triển khai phân cụm dữ liệu dựa trên điểm số học tập của sinh viên.

- Thu thập và xử lý dữ liệu điểm đầu vào các môn học làm cơ sở cho phân cụm dữ liệu - Xây dựng hệ thống hỗ trợ phân cụm sinh viên theo chuyên ngành từ đó đưa ra gợi ¥ lựa chọn chun ngành cho sinh viên theo học.

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

Kết quả đạt được: 1. Kết quả nghiên cứu

- Đã nghiên cứu tong quan về phân cụm dữ liệu.

- Đã nghiên cứu về các phương pháp phân cụm dữ liệu bao gồm phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ. phân cụm dựa trên lưới, ưu nhược điểm của từng phương pháp.

~ Nghiên cứu và ứng dụng phân cụm dữ liệu với thuật toán K-means để sử dụng trong hệ thống hỗ trợ phân loại và gợi ý lựa chọn chuyên ngành cho sinh viên. Với cách thức phân cụm dữ liệu nay mỗi sinh viên sẽ có khả năng được xếp vao các chuyên ngành theo dữ liệu điểm đầu vào được cung cấp.

- Triển khai xây dựng ứng dụng thử nghiệm hỗ trợ phân cụm sinh viên và gợi ý lựa chọn chuyên ngành học tập.

2. San phẩm

- Sản phẩm khoa học: 01 bài báo nằm trong danh mục được tính điểm bởi Hội đồng chức danh Giáo sư Nhà nước.

Nguyễn Thị Tâm, Nguyễn Thị Quỳnh Như, Nguyễn Thị Thúy Lan, "Ứng dựng kĩ thuật phân cụm dữ liệu hỗ trợ sinh viên lựa chọn chuyên ngành", Tạp chí Thiết bị giáo dục, số tháng 6/2023.

- Sản phẩm ứng dụng: 01 phần mềm hỗ trợ phân loại sinh viên và gợi ý lựa chọn chuyên ngành dựa trên điểm học tập.

- San phẩm đào tạo:

* 01 đề tải nghiên cứu khoa học sinh viên, đề tài "Ứng dụng kĩ thuật phân cụm dữ liệu hỗ trợ sinh viên lựa chọn chuyên ngành" do nhóm sinh viên gồm Nguyễn Mạnh Hùng, Nguyễn Văn Tiến, Trần Quỳnh Trang, Nguyễn Thị Dịu thực hiện và đạt giải Ba cấp Trường.

* 01 đồ án tốt nghiệp đại học, đề tài "Nghiên cứu bài toán phân cụm dữ liệu và ứng dụng trong phân cụm dữ liệu khách hàng" do sinh viên Phạm Đình Ngọc thực hiện. Đề tài đã bảo vệ tháng 4/2023.

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

8 PHAN MO DAU 1.1. Tinh cấp thiết của dé tài

Hiện nay tại Khoa Công nghệ thông tin Trường Đại học Mở Hà Nội, sinh viên sẽlựa chọn chuyên ngành học khi tích lũy đủ 100/140 tín chỉ. Việc chọn một ngành học phù hợp dé theo đuôi va phát triển là một quyết định quan trọng của mỗi sinh viên. Bên cạnh những sinh viên đã xác định được con đường mình muốn đi thì cịn rất nhiều sinh viên chưa xác định được mình giỏi trong mảng nào và nên theo chuyên ngành gì. Mà hệ lụy của việc chọn sai ngành thì vơ cùng lớn, nó tác động lớn tới trường học, xã hội và nhất là chính bản thân sinh viên.

Tuy nhiên hiện nay chưa có giải pháp gì hỗ trợ giúp sinh viên cũng như giảng viên

là cố vấn học tập có thể biết được sinh viên nên theo chuyên ngành gì sẽ phù hợp với năng lực của bản thân. Vì thế đến thời điểm lựa chọn chuyên ngành sinh viên và cố vấn học tập thường lúng túng, sinh viên có thể chọn theo phong trào, theo bạn bè cho vui, theo xu hướng hay theo sự quyết định của gia đình,...

Vi vậy, dé tài này thực hiện nghiên cứu và ứng dụng kĩ thuật phân cụm dữ liệu dé xây dựng giải pháp giúp sinh viên có thể đưa ra sự lựa chọn đúng đắn cho mình, cố vấn học tập cũng có cơ sở dé đưa ra lời khuyên cho sinh viên khi thực hiện tư vấn.

1.2. Tổng quan tình hình nghiên cứu

Trên thế giới, khai phá dữ liệu sử dụng kĩ thuật phân cụm đã được áp dụng trong nhiều lĩnh vực như ngân hàng, bán lẻ, nông nghiệp, y tế, ... [1] và cũng có khá nhiều các nghiên cứu về việc triển khai kĩ thuật phân cụm dữ liệu trong lĩnh vực giáo dục. Trong nghiên cứu [2] nhóm tác giả sử dụng thuật toán phân cụm K-Means kết hợp cùng cây quyết định dé dự đoán điểm trung bình có thể đạt được của sinh viên và dựa vào đó giáo viên có thé có những tư van cần thiết dé cai thiện kết quả học tập của sinh viên, giảm tỉ lệ bỏ học.

Khai phá dữ liệu với kĩ thuật phân cụm dữ liệu là một trong những kĩ thuật nhậnđược nhiêu sự quan tâm của các nhà nghiên cứu và doanh nghiệp.

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

Trong nghiên cứu [3] nhóm tác giả phân nhóm khách hàng dựa trên các đặc điểm hành vi tiêu dùng, thói quen mua sắm, mức chỉ tiêu từ đó xác định các phân khúc khách hang dé có chiến lược quảng cáo, tiếp thị và chăm sóc khách hàng hiệu quả.

Với báo cáo [4] tác giả đã thực nghiệm phân cụm sinh viên để tư vấn định hướng lựa chọn ngành nghề phù hợp cho sinh viên của các khoa trường Đại học Kiến trúc Hà Nội, tác giả đã có đánh giá so sánh với sở thích, nguyện vọng của sinh viên nhưng tỉ lệ

chính xác đạt được cịn thấp.

1.3. Mục tiêu đề tài

Xây dựng một hệ thống thử nghiệm hỗ trợ phân cụm sinh viên theo chuyên ngành dựa trên kết quả học tập được tích lũy. Hệ thống sẽ giúp cho sinh viên và giảng viên có thêm căn cứ dé đưa ra tư van, lựa chọn chuyên ngành phù hợp nhất.

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

o Nghiên cứu lý thuyết về phân cụm dữ liệu, các phương pháp phân cum dữ liệu.

o Nguyên cứu thuật toán phân cụm K-Means và áp dụng giải quyết yêu cầu bài toán.

o Tiến hành thực nghiệm trên dữ liệu mẫu. o Phân tích đánh giá kết quả đạt được. 1.5. Nội dung nghiên cứu

o Nghiên cứu về phân cụm đữ liệu, các phương pháp phân cụm dữ liệu, quy trình thực hiện phân cụm dữ liệu. Các lĩnh vực ứng dụng đang được triển khai dựa trên phân cụm dữ liệu.

o Nghiên cứu thuật toán K-means triển khai phân cụm dữ liệu dựa trên điểm số học tập của sinh viên.

o Thu thập và xử lý dit liệu điểm đầu vào các môn học làm cơ sở cho phân cụm đữ liệu

o_ Xây dựng hệ thống hỗ trợ phân cụm sinh viên theo chuyên ngành từ đó dua ra gợi ý lựa chọn chuyên ngành cho sinh viên theo học.

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

1.6. Pham vi nghiên cứu:

Triển khai thử nghiệm với dữ liệu điểm sinh viên thuộc Khoa Công nghệ thông tin Đại học Mở Hà Nội với 3 chuyên ngành

o_ Công nghệ phầm mềm o Công nghệ đa phương tiệno Mạng và kĩ thuật máy tính. 1.7. Ý nghĩa nghiên cứu

Giúp cho sinh viên và giảng viên có thêm căn cứ đê đưa ra những lựa chọn chuyên ngành phù hợp nhất.

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

PHAN NOI DUNG Chương 1 Co sở lý thuyết 1.1. Phát hiện tri thức và khai phá dữ liệu

Phát hiện tri thức trong các cơ sở dit liệu là một qui trình nhận biết các mẫu hoặc các mơ hình trong dữ liệu với các tính năng: phù hợp, có tính mới, có ý nghĩa và có thể hiểu được. Cịn khai thác dữ liệu là một bước trong qui trình phát hiện tri thức gồm có các thuật tốn khai thác dữ liệu chun biệt với các qui định về hiệu quả tính tốn chấp nhận

được để tìm ra các mẫu hoặc các mơ hình trong dữ liệu.

- Quy trình phát hiện tri thức bao gồm:

Chon lọc dit liệu: Đây là giai đoạn tập hợp các dữ liệu được khai thác từ một cơ sở dữ liệu, một kho dữ liệu, thậm chí từ các nguồn ứng dụng khác nhau vào một cơ sở dữ liệu riêng.

Tiền xử lý dữ liệu: Hầu hết các CSDL đều ít nhiều mang tính khơng nhất qn. Vì vậy khi gom dữ liệu rất có thé mắc một số lỗi như dữ liệu không day đủ, chặt chẽ và không logic (bị trùng lặp, giá trị bị sai lệch, ...) nên cần xử lý đữ liệu.

Chuyển đổi dữ liệu: dữ liệu sẽ được chuyển đổi về dang thuận tiện để tiến hành các thuật toán khai phá dữ liệu.

Khai phá dữ liệu: là sử dụng các kỹ thuật nhằm phát hiện ra các tri thức tiềm an trong dữ liệu. Một số kỹ thuật được sử dụng đó là: phân lớp, gom cụm, luật kết hop, ...

Đánh giá kết quả mẫu: Đây là giai đoạn cuối cùng trong tiến trình phát hiện tri thức. Trong giai đoạn này, các mẫu dữ liệu được chiết xuất bởi các phần mềm khai phá dữ liệu.

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

Hình 1: Quy trình phát hiện tri thức

Khai phá dữ liệu là một tập hợp các kỹ thuật được sử dụng để tự động khai thác và tìm ra các mối quan hệ lẫn nhau của dữ liệu trong một tập hợp dữ liệu khổng lồ và phức tạp, đồng thời cũng tìm ra các mẫu tiềm an trong tập dữ liệu đó.

Khai phá dữ liệu là một bước trong bảy bước của quá trình KDD (Knowleadge Discovery in Database) và KDD được xem như 7 quá trình khác nhau theo thứ tự sau:

* Lam sạch dữ liệu: Loại bỏ nhiễu và các dữ liệu khơng cần thiết.

* Tích hợp dữ liệu: quá trình hợp nhất dữ liệu thành những kho dữ liệu sau khi đã làm sạch và tiền xử.

® Trích chon dữ liệrich chọn dit liệu từ những kho dữ liệu và sau đó chuyền đổi về dang thích hợp cho quá trình khai thác tri thức. Quá trình này bao gồm cả việc xử lý với dữ liệu nhiễu, dữ liệu không đầy đủ v.v. * Chuyển đổi dit Các dữ liệu được chuyên đổi sang các dạng phù hợp

cho quá trình xử lý.

* Khai phá dữ liệu: Là một trong các bước quan trọng nhất, trong đó sử dụng những phương pháp thông minh để chắt lọc ra những mẫu dữ liệu.

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

* _ Ước lượng mẫu: Quá trình đánh giá các kết quả tìm được thơng qua các độ đo nào đó.

* Biểu diễn tri: Quá trình nay sử dụng các kỹ thuật để biểu diễn và thể hiện trực quan cho người dùng.

1.2. Phân cụm là gì?

Phân cụm dữ liệu (Data Clustering) hay phân cụm, cũng có thê gọi là phân tích

cụm, phân tích phân đoạn, phân tích phân loại, là q trình nhóm một tập các đối tượng

cụ thê hay trừu tượng thành lớp các đối tượng tương tự. Một cụm là một tập hợp các đối tượng dữ liệu mà các phần tử của nó tương tự nhau cùng trong một cụm và phi tương tự với các đối tượng trong các cụm khác.

Thuật toán phân cụm phụ thuộc vào từng tập dữ liệu và mục dich sử dụng kết quả. Phân tích cụm khơng phải là một nhiệm vụ tự động, mà là một quá trình lặp đi lặp lại dé khám phá kiến thức hoặc tối ưu hóa đa mục tiêu tương tác liên quan đến thử nghiệm và thất bại. Thông thường cần phải sửa đôi các tham số tiền xử lý dữ liệu và mơ hình cho đến khi kết quả đạt được các thuộc tính mong muốn.

Phân tích cụm là một tác vụ chính của khai phá dữ liệu, và là một kỹ thuật phổ biến trong thống kê phân tích dữ liệu, được dùng trong nhiều lĩnh vực, bao gồm nhận dạng mẫu, phân tích ảnh, truy hồi thông tin, tin sinh học, nén dữ liệu, đồ họa máy tính và

học máy.

Hình 2: Phan cụm dữ liệu

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

143.Các bước thực hiện phân cụm.

Trước khi bắt đầu phân cụm, ta cần phải làm sạch và tiền xử lý dữ liệu dé đảm bảo tính đúng đắn của kết quả phân cụm. Bước này bao gồm loại bỏ các giá trị thiếu, xử lý giá trị ngoại lai và chuẩn hóa dữ liệu đây gọi là giai đoạn tiền xử lý dữ liệu. Tiếp theo đó chọn phương pháp phù hợp để phân cụm dữ liệu. Điều này phụ thuộc vào tính chất của dữ liệu và mục tiêu của bài toán.

Xác định số lượng cụm: Số lượng cụm phù hợp cũng phụ thuộc vào tính chất của dữ liệu và mục tiêu của bài tốn. Có thể sử dụng nhiều phương pháp khác nhau để xác định số lượng cụm, ví dụ như phương pháp Elbow hoặc phương pháp Silhouette.

Thực hiện phân cụm: Sau khi xác định số lượng cụm, sử dụng phương pháp phân cụm để phân loại các điểm dữ liệu vào các cụm. Việc này có thể được thực hiện bằng các thuật toán như K-means, DBSCAN, Hierarchical Clustering. ..

Đánh giá và tỉnh chỉnh: Sau khi phân cụm, đánh giá kết quả đề đảm bảo tính chính xác và đáng tin cậy của kết quả. Nếu kết quả không phù hợp, hãy tỉnh chỉnh các tham số và phương pháp phân cụm để đạt được kết quả tốt hơn.

Sử dụng kết quả: Cuối cùng, sử dụng kết quả phân cụm đề giải quyết bài tốn, ví dụ như phân tích các đặc tính và xu hướng của từng cụm hoặc phân loại các điểm dữ liệu mới vào các cụm đã được xác định.

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

ó——}*|_ Xác định số lượng cụm

Thực hiện phân cụm

anh giá va tinh chỉnh kết quả sau phân cụm

Hình 3: Quy trình hoạt động phân cụm dữ liệu

Giai đoạn tiền xử lý dữ liệu là một bước quan trọng trong phân cụm dữ liệu, đảm bảo tính chính xác và đáng tin cậy của kết quả phân cụm. Các bước của tiền xử lý dữ liệu bao gồm:

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

- Xử lý giá trị thiếu: Dữ liệu thiếu có thể làm giảm tính chính xác của kết quả phân cụm.

- _ Xử lý giá trị ngoại lai: Giá trị ngoại lai có thé ảnh hưởng đáng ké đến kết quả phân cụm. Ta có thé sử dụng các phương pháp như cắt tia (trimming) hoặc chuyên đồi giá trị (transformation) dé xử lý giá trị ngoại lai.

- Chuẩn hóa dit liệu: Chuẩn hóa dữ liệu giúp đưa các đặc trưng có thang đo khác nhau về cùng một thang do dé đảm bảo tính chính xác của kết quả phân cụm. Có nhiều phương pháp chuẩn hóa dữ liệu, chang hạn như chuẩn hóa min-max, chuẩn hóa z-score, hoặc chuẩn hóa tỷ lệ.

Giảm chiều dữ liệu: Nếu dữ liệu có số chiều cao, việc giảm chiều dữ liệu có thể giúp giảm độ phức tạp tính tốn và cải thiện hiệu suất phân cụm

Lựa chọn đặc trưng: Nếu dữ liệu có nhiều đặc trưng, có thể xem xét lựa chọn đặc trưng đê giảm độ phức tạp tính tốn và cải thiện hiệu suất phân cụm.

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

1.4. Một số phương pháp phân cụm.

Một số phương pháp phân cụm điền hình: Phân cụm phân hoạch, phân cụm phân cấp, phân cụm dựa trên mật độ, phân cụm dựa trên lưới, phân cụm dựa trên mơ hình, phân cụm có ràng buộc, ...

1.4.1 Phân cụm phân hoạch

Phương pháp này xây dựng các vùng của dữ liệu, trong đó mỗi vùng đại diện cho

một cụm và số lượng vùng dữ liệu không lớn hơn số lượng điểm dữ liệu. Nói cách khác, phương pháp phân hoạch thực hiện phân vùng trên tập dữ liệu. Mỗi một vùng sẽ có ít nhất một điểm dữ liệu, mỗi điểm dữ liệu phải thuộc về chính xác một vùng dit liệu.

Phương pháp này được phát triển vào những năm 1950 và 1960, một trong những, thuật toán đầu tiên được áp dụng vào phương pháp này thuật tốn Lloyd (1957), cịn được gọi là thuật toán K-means được đề xuất bởi Stuart P. Lloyd vào năm 1957.

Thuật toán K-mean.

- Trong thuật toán K-mean, mỗi cụm sẽ được đại diện bằng tâm của cụm. Trong đó trọng tâm của cụm là một vector, giá trị của mỗi phần tử trong cụm là trung bình cộng của các thành phần tương ứng của các đối tượng vector dữ liệu trong cụm đang xét. Tham số đầu vào của thuật toán là số cụm k. Đầu ra là các trọng tâm của các cụm. Độ đo khoảng cách D giữa các đối tượng (thường dùng khoảng cách Euelide), vì đây là mơ hình khoảng cách dễ để lấy đạo hàm và xác định các cực trị tối thiểu. Hàm tiêu chuẩn và độ đo khoảng cách có thể được xác định cụ thể hơn tuỳ vào ứng dụng hoặc quan điểm của người dùng.

- Đầu vào của thuật toán: số K cụm và cơ sở dữ liệu. - _ Thuật tốn sẽ bao. gồm 4 bước chính:

o Bước 1: Phân hoạch đối tượng thay k tập con/ cụm khác rỗng.

o_ Bước 2: Tìm các điểm dữ liệu làm tâm(trung bình các đối tượng của cụm)

cho từng cụm trong từng cụm hiện hành.

o Bước 3: Gan từng đối tượng vào cụm có tâm gần nhất, cập nhật lại tâm

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

o Bước 4: Quay về bước 2, cham dứt khi khơng cịn phép gan mới. Ưu điểm:

o Đơn giản và dễ hiểu: Phương pháp phân hoạch là một trong những phương pháp đơn giản nhất để phân loại dữ liệu.

o_ Hiệu quả với dữ liệu lớn: Phương pháp phân hoạch hoạt động tốt với các tập dữ liệu lớn và phức tạp.

Nhược điểm:

o Yêu cầu số lượng cụm được xác định trước: Trước khi thực hiện phân hoạch, số lượng cụm phải được xác định trước đó.

o Nhạy cảm với giá trị khởi tạo ban đầu: Kết quả phân hoạch sẽ khác nhau nếu chúng ta khởi tạo các giá trị trung tâm ban đầu khác nhau.

chứa nhiễu.

1.4.2 Phân cụm phân cấp

Phương pháp phân cụm phân cấp (hierarchical clustering) là một phương pháp phân cụm dữ liệu dựa trên việc xây dựng một cây phân cấp các cụm để biểu diễn sự tương đồng giữa các điểm dữ liệu. Phương pháp này chia dữ liệu thành từng cụm nhỏ và thực hiện các phép gộp cụm dựa trên một tiêu chi tong đồng để tạo ra các cụm lớn hơn.

Cây phân cụm có thể xây dựng bằng một trong 2 phương pháp sau: Phương pháp Bottom up:

o Bắt đầu mỗi đối tượng khởi tạo tương ứng với các cụm riêng biệt.Nhóm các đối tượng theo một độ đo tương tự (như khoảng cách giữa hai trung tâm của hai nhóm).

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

o_ Thực hiện cho đến khi tất cả các nhóm được hịa nhập vào một nhóm(mức cao nhất của cây phân cấp), hoặc đến khi thỏa mãn điều kiện kết thúc. Phương pháp Top down:

o Bất đầu tất cả các đối tượng được xếp trong cùng một cụm

o Mỗi vòng lặp thành công, một cụm được tách thành các cụm nhỏ hơn theo giá trị của một phép đo độ tương tự.

o_ Đến khi mỗi đối tượng là một cụm, hoặc điều kiện dừng thỏa mãn. Phương pháp phân cụm dữ liệu này có một số thuật tốn điền hình như: CURE [5], BIRCH [6] ...

Thuat toán BIRCH.

- BIRCH (Balanced Iterative Reducing and Clustering Using Hierarchies) là một thuật toán sử dụng chiến lược phân cụm trên xuống (top down) với ý tưởng khơng lưu tồn bộ các đối tượng dữ liệu của các cụm trong bộ nhớ mà chỉ lưu lại đặc trưng của cụm (số lượng trong cụm, tổng các giá trị thuộc tính của các đối tượng trong cụm, tơng. bình phương của các giá trị thuộc tính của các đối tượng trong cụm) được lưu lại trong một cây gọi là cây CF (CF-tree).

- Cây CF là cây cân bằng. Cây CF chứa các nút trong và nút lá. Một cây CF được đặc trưng bởi hai tham số:

o Yếu tố nhánh (Branching Factor -B): xác định số tối đa các nút con của mỗi

nút trong.

o Ngưỡng (Threshold -T): Khoảng cách tối đa giữa bat kỳ một cặp đối tượng trong nút lá của cây, khoảng cách này cịn gọi là đường kính của các cụm conđược lưu tại các nút lá.

- Input của thuật toán: CSDL gồm n đối tượng, ngưỡng T, k. - Output của thuật toán: k cụm dữ liệu.

~_ Thuật toán sẽ bao gồm 4 bước chính:

o Bước 1: Duyệt tat 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

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

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 hồ 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 đọ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 dé gan nhãn cho các dit liệu khởi tạo và loại bỏ các đối tượng ngoại lai.

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

Bất a

Tao một nút lá

(lưu lại số lượng cụm, giá trị của đối tượng,..)

Tìm đối tượng gộp vào nút lá #——————————————

Xét xem đối tượng có hợp với nút lá khơng

CóGop đối tượng vào nút lá

Cập nhật lại cây, cập nhật lại nút lá

Đã phân cụm (các đối tượng đã gộpvào các nút lá tương ứng)

Hình 5: Sơ đồ hoạt động của thuật tốn BIRCH

Khơng

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

Ưu điểm:

o Dễ sử dung và triển khai: Phương pháp phân cụm dữ liệu phân cấp là phương pháp đơn giản và dễ sử dụng, không cần phải thiết lập số lượng cụm trước.

o Phân tích được cấu trúc cụm: Phương pháp này giúp phân tích được cầu trúc cụm dữ liệu từ những cụm con nhỏ đến cụm lớn hơn, giúp hiểu rõ hơn về dữ liệu.

Nhược điểm:

o Không hiệu quả với dit liệu có kích thước lớn do độ phức tạp tính tốn vàkhó thực hiện.

o Cần lựa chọn kỹ thuật phù hợp: Việc lựa chọn kỹ thuật phân cụm phù hợp với dữ liệu là rất quan trọng, do đó cần phải đánh giá kỹ các kỹ thuật dé lựa chọn kỹ thuật tốt nhất cho bài tốn cụ thê.

o Khơng thé sửa đổi sau khi hoàn thành: Khi sử dụng phương pháp phân cụm

phân cấp, các cụm được tạo ra không thê được sửa đổi.

1.4.3 Phân cụm dựa trên mật độ

Phương pháp phân cụm dựa vào mật độ sinh ra dé giải quyết bài toán mà phương pháp phân vùng và phân cấp (hai phương pháp tìm các cụm hình cầu) chưa giải quyết được giúp tìm các cụm có hình dạng tuỳ ý, có thê mơ hình hóa các cụm như các vùng dày đặc trong không gian dữ liệu, được tách rời bởi các vùng thưa, có thể khám phá ra các cụm có hình dạng khơng phải là hình cầu.

Phương pháp này sẽ nhóm các đối tượng theo hàm mật độ xác định. Mật độ được định nghĩa như là số các đối tượng lân cận của một đối tượng dữ liệu theo một ngưỡng

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

nào đó. Khi một dữ liệu đã xác định thì nó tiếp tục được phát triển thêm các đối tượng dữ

liệu mới miễn là số các lân cận của chúng lớn hơn một ngưỡng đã xác định.

Phương pháp này được đề xuất bởi Ester, Kriegel, Sander vào năm 1996 và thuật tốn điển hình của nó là DBSCAN (Density-Based Spatial Clustering of Applications with Noise) [7], sau này phát triển thêm các thuật toán như OPTICS [8, 7], DENCLUE.. Thuat tốn DBSCAN

DBSCAN là một thuật tốn có thé tim ra các cụm với hình thù bat kỳ. Thuật tốn tìm các đối tượng mà có số đối tượng láng giéng lớn hơn một ngưỡng tối thiểu. Tìm tat cả các đối tượng mà các láng giềng của nó thuộc về lớp các đối tượng đã xác định. Một cụm được xác định bằng một tập tất cả các đối tượng liên thông mật độ với các lang giềng của nó.

~_ Thuật tốn u cầu các tham số đầu vào (Eps và MinPts) và đưa ra các định nghĩa quy tắc áp dụng trong lưu đồ của thuật toán.

- Thuật toán gồm 5 bước:

o Bước 1: Khởi tạo điểm p tuỳ ý và lấy tat cả các điểm đến được mật độ từ p với Eps, MinPts.

o Bước 2: Nếu p khơng phải là nhân (có thé là biên, nhiễu, hoặc số lân cận của p ít hơn Minpts) thì DBSCAN sẽ đi thăm điểm tiếp theo.

o Bước 3: Ngược lại (p là nhân) thì một cụm được hình thành và chứa tất cả các đối tượng trong lân cận của p. Sau đó, lân cận của những điểm nay sẽ được khảo sát dé xem liệu nó có được thêm tiếp vào cụm này hay không. o Bước 4: Nếu cum không thể mở rộng thêm được nữa, thuật toán chọn ngẫu

nhiên một đối tượng p khác chưa xét và lặp lại quá trình trên.

o Bước 5: Lap cho đến khi mọi đối tượng đều được gom cụm hay được đánh dấu là ngoại lai/nhiễu. Với một CSDL có n mẫu tin, cần phải truy vấn vùng nlân

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

Bắt đầu

" dg

Lấy tắt cả những điểm liên quan đến điểm p dựa.

trên (Eps, MinPts)

Chỉ số lân cận của P < MinPts

Moi đối tượng đã được gom cụm hay

= đánh dầu ngoại lai chưa?

Kếtthúc — ¬›

Hình 6: Sơ đồ hoạt động của thuật toán DBSCAN

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

Ưu điểm:

o Kha năng phát hiện được các cụm có hình dang và kích thước khơng đều, các cụm có dạng khơng phải hình cầu, khơng u cầu sự giám sát hay giả định trước về số cụm.

o Khả năng xử lý và phân cụm dữ liệu có nhiễu và bất thường.

o Khả năng tìm được các cụm có mật độ dữ liệu thấp giữa các cụm khác có mật độ cao.

Nhược điểm:

o Khơng thể phân cụm các cụm có mật độ dữ liệu khác nhau.

o Phải định nghĩa và sử dụng các thông số như thể hiện mật độ và bán kính cụm cho từng bài tốn riêng biệt, địi hỏi sự hiểu biết chuyên môn. 1.4.4 Phân cụm dựa trên lưới

Kỹ thuật phân cụm dựa trên lưới 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 dé 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. Mục tiêu của phương pháp nay là lượng hóa dữ liệu thành các 6 tao thành cấu trúc dữ liệu lưới. Sau đó, các thao tác phân cụm chỉ cần làm việc với các đối tượng trong từng ở trên lưới chứ không phải các đối tượng dữ liệu. Cách tiếp cận dựa trên lưới này không di chuyền các đối tượng trong các 6 mà xây dung nhiều mức phân cấp của nhóm các đối tượng trong một ô. Phương pháp này gần giống với phương pháp phân cụm phân cấp nhưng chúng không trộn các ô, đồng thời giải quyết khắc phục yêu cầu đối với dữ liệu nhiều chiều mà phương pháp phân phân cụm dựa trên mật độ không giải quyết được.

Một số thuật toán phân cụm dữ liệu dựa trên cấu trúc lưới điển hình như: STING

(Statistical Information Grid) [9], WAVECluster [10], CLIQUE (CLustering In QUEst)[1D]

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

Một cell của mức thứ (-1) ứng vớibốn cell của mức thứ ¡

chỉ có một cell

Tầng thứ (-1)

Tầng thứ i

Hình 7: Mơ hình cấu trúc dữ liệu dang lưới 'Thuật toán STING

Thuật toán STING là kỹ thuật phân cụm đa phân giải dựa trên lưới, trong đó ving khơng gian dữ liệu được phân rã thành số hữu hạn các ô chữ nhật, điều này có nghĩa là các ô lưới được hình thành từ các ơ lưới con đê thực hiện phân cụm. Cónhiêu mức của các ơ chữ nhật tương ứng với các mức khác nhau của phân giải trong cấu trúc lưới, và các ơ này hình thành cấu trúc phân cấp: mỗi ô ở mức cao

được phân hoạch thành số các ô nhỏ ở mức thấp hơn tiếp theo trong cấu trúc phân

Bước 2: Với mỗi tầng, tính tốn khoảng tin cậy (hoặc ước lượng khoảng) của xác suất mà ô này liêu quan đến truy vấn.

Bước 3: Từ khoảng tin cậy của tính tốn trên, gán nhãn cho là có liên quanhoặc khơng liên quan.

Bước 4: Nếu lớp này là lớp dưới cùng, chuyển sang bước 6 khơng thì chuyển sang bước 5.

Bước 5: Duyệt xuống đướ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 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.

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

o Bước 7: Truy lục dữ liệu vào các ô liên quan để thực hiện và 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.

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

Hình 8: Sơ dé hoạt động thuật tốn STING L— ]Duyêt cây phân cấp xuống một múc|

Ưu điểm:

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

o Thuận tiện và nhanh chóng trong việc xử lý dữ liệu lớn, đặc biệt là trong cácbài toán phân cụm dữ liệu trong thời gian thực

o Cho phép áp dụng cho các loại dữ liệu khác nhau, kể cả các dữ liệu có kích thước lớn.

Nhược điểm:

o Phuong pháp này dễ dẫn đến vấn đề trùng lặp phân cụm, tức là một đối

tượng có thê được gán vào nhiều phân cụm khác nhau.

o_ Kích thước 6 lưới phải được chon sao cho đảm bảo tính chất của phân phối dữ liệu, do đó, nêu kích thước ơ lưới khơng được chọn đúng, có thé dẫn đến việc phân cụm sai hoặc khơng chính xác.

o Phương pháp này thường không hoạt động tốt với dữ liệu dạng tụ điểm (dense data) hoặc dữ liệu không đồng đều (non-uniform data) vì nó khơng xử lý được vùng dữ liệu có mật độ cao.

1.4.5 Phân cụm dựa trên mơ hình

Phương pháp phân cụm dữ liệu dựa trên mơ hình là một phương pháp trong học máy, lấy ý tưởng phân cụm dữ liệu dựa trên mơ hình xác suất và sử dụng chúng để phân loại các điêm dữ liệu vào các nhóm khác nhau.

Phương pháp này bao gồm các mơ hình phơ biến: phân cụm Gaussian hỗn hợp

(Gaussian mixture clustering), phân cụm Bernoulli hỗn hợp (Bernoulli mixture clustering) và phân cụm Poisson hỗn hợp (Poisson mixture clustering).

Mơ hình Gaussian mixture là một mơ hình hỗn hợp gồm các phân phối Gaussian, được sử dụng để phân cụm các đữ liệu không đồng nhất trong không gian đặc trưng. Mô hình này giả sử rằng mỗi cụm là một phân phối Gaussian với trung bình và ma trận hiệp phương sai khác nhau. Thuật toán Gaussian Mixture Model (GMM) dé phân cụm các điểm dữ liệu vào từng phân phối Gaussian. [12]

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

Thuật toán GMM

GMM giả định rằng các điểm dữ liệu được phân phối theo tổ hợp của nhiều phân

phối Gaussian có trung bình và độ lệch chuẩn khác nhau. Mỗi phân phối Gaussian

trong tổ hợp này đại diện cho một nhóm cụ thể của các điểm dữ liệu.

Sau khi thực hiện thuật toán GMM, ta sẽ có được phân phối của các điểm dữ liệu vào từng phân phối Gaussian. Các điểm dữ liệu có xác suất cao nhất thuộc về phân phối Gaussian nào sẽ được phân vào nhóm tương ứng với phân phối Gaussian đó. Các bước thực hiện của thuật tốn:

° Chuẩn bị dữ liệu: chuẩn bị dữ liệu và chuyển chúng về định dạng mà thuật tốn GMM có thể sử dụng, ví dụ như định dạng ma trận hoặc vector. Xác định số lượng nhóm: Xác định số lượng nhóm mà ta muốn phân chia các điểm dữ liệu.

Khởi tạo các tham số ban đầu: Khởi tạo các trung bình và ma trận hiệp

phương sai cho mỗi phân phối Gaussian.

E-Step: Với mỗi điểm dữ liệu, tính xác suất rằng nó thuộc về mỗi phân phối Gaussian, sử dụng công thức Bayes. M-Step: Dựa trên xác suất đã tính được ở bước E-Step, cập nhật trung bình và hiệp phương sai cho mỗi phân phối Gaussian.

Lap lại các bước 4 và 5 cho đến khi giá trị hàm mục tiêu không thay đôi đáng kể hoặc khi đạt đến sé lần lặp tối đa.

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

cấp nhật tung bình và biếp phương sai

hàm mục êu không thay đỗ lấp đến số lần tối đa

Hình 9: Sơ đồ hoạt động thuật toán GMM Ưu điểm:

o Phân cụm dữ liệu dựa trên mơ hình có khả năng tìm ra các nhóm dữ liệu có tính phân phối đồng nhất hoặc khơng đồng nhất, hình dạng và kích thước khác nhau.

o Các mơ hình phân cụm dữ liệu dựa trên phương pháp này thường có tính giải thích cao, giúp cho người sử dụng có thê hiểu được cách các nhóm được hình thành và tương quan giữa các đặc trưng của dữ liệu.

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

o Các mơ hình phân cụm dữ liệu dựa trên phương pháp này có thể được sử dụng đê xử lý các bài toán phân cụm dữ liệu lớn và phức tạp.

Nhược điểm:

o Phương pháp phân cụm dựa trên mơ hình u cầu sử dụng các mơ hình thống kê hoặc máy học, có thể làm tăng độ phức tạp của quá trình phân cụm.

o Các mơ hình phân cụm dữ liệu dựa trên phương pháp này có thé khơng phù hợp cho các tập dữ liệu có tính động hoặc khơng tn theo các giả định củamơ hình.

1.4.6 Phân cụm dựa trên ràng buộc

Phương pháp phân cụm dựa trên ràng buộc là một kỹ thuật phân cụm dữ liệu, trong đó các ràng buộc được áp dụng để hạn chế hoặc điều chỉnh quá trình phân cụm. Các ràng buộc có thể được xác định bởi người sử dụng hoặc được xác định tự động dựa trên đặc trưng của dữ liệu. Việc áp dụng các ràng buộc có thê giúp tăng tính linh hoạt và khả năng khám phá của phương pháp phân cụm, đồng thời giúp giải quyết các vấn đề thực tế trong

việc phân cụm dữ liệu, chăng hạn như đối với các dữ liệu thưa, khơng cân bằng, hay có

nhiễu.

Có rất nhiều thuật tốn dựa phân cụm dựa trên ràng buộc như: o Constrained K-means clustering

o Constrained spectral clusteringo Constrained hierarchical clusteringo Constrained density-based clusteringo Constrained subspace clustering [13] [14]

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

32Thuat toán Constrained K-means clustering.

- Constrained K-means clustering là một phiên ban của thuật toán K-means clustering, nơi các ràng buộc được áp dụng dé điều chỉnh quá trình phân cụm. Thuật tốn này có thể giải quyết các vấn đề như việc phân cụm dữ liệu thưa, không cân bằng hoặc dữ liệu bị nhiễu.

- Các ràng buộc có thê được áp dụng dưới dạng ràng buộc cứng hoặc ràng buộc

Bước 2: Gán mỗi điểm dữ liệu vào một cụm gần nhất: Tính khoảng cách giữa mỗi điểm dữ và các trung tâm cụm. Gan mỗi điểm dữ liệu vào cụm gần nhất dựa trên khoảng cách tính được.

Bước 3: Tính tốn trung tâm cụm mới. Tính trung bình các điểm dữ liệu trong mỗi cụm để tính tốn trung tâm cụm mới.

Bước 4: Cập nhật ràng buộc áp dụng các ràng buộc cứng và mềm vào các cụm để tạo ra hàm mục tiêu ràng buộc. Sử dụng hàm mục tiêu ràng buộc đê điều chỉnh vị trí của các trung tâm cụm.

Bước 5: Lap lại các bước 2-4 cho đến khi đạt được điều kiện dừng. Điều kiện dừng có thé là khi khơng có điểm dữ liệu nào chuyển cụm hoặc khi hàm mục tiêu đạt được giá trị tối ưu.

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

bu, anu! _

Lấy tắt cả những điểm liên quan đến điểm p dựa

trên (Eps, MinPts)

Chỉ số lân cận của P < MinPts

Moi đối tượng đã được gom cụm hayđánh dầu ngoại lai chưa?

Kết thúc. >

Hình 10: So đồ hoạt động thuật tốn Constrained K-means clustering

sg

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

- Ưuđiểm:

o_ Giúp tăng tính đồng nhất trong các cụm: Phương pháp này có thể tạo ra các cụm đồng nhất hơn so với phương pháp phân cụm khác.

o Hạn chế ảnh hưởng của nhiễu: Phương pháp này có thé giảm ảnh hưởng của dữ liệu nhiều bằng cách yêu cầu các điểm được phân vào các cụm có. thể thỏa mãn các ràng buộc.

o Cho phép tính tốn thống nhất: Phương pháp này có thể tạo ra các cụm đồng nhất về kích thước và hình dạng, giúp cho việc so sánh giữa các cụm

trở nên dé dàng hơn.

o Cho phép giám sát dễ dàng: Phương pháp này cho phép quản lý dé dang hơn khi các ràng buộc được thiết lập, giúp cho việc kiểm tra và giám sát trở

nên dễ dàng hơn.

- Nhược điểm:

o Khó tính tốn: Phương pháp nay có thể tốn nhiều thời gian và năng lượng để tính tốn vì phải đáp ứng nhiều ràng buộc.

o Rang buộc khó lập trình: Việc lập trình các rang buộc có thể rất phức tạp và khó khăn.

o Khơng đáp ứng được với dữ liệu phân tán: Phương pháp này không phù hợp.với các tập dit liệu phân tán, khi các ràng buộc có thê khơng được đáp ứng đầy đủ.

Trong nghiên cứu này chúng ta chọn phương pháp phân cụm phân hoạch sử dụng thuật toán K - Means nhằm gom cụm các sinh viên theo chuyên ngành phù hợp dựa trên điểm số một số học phần đã tích lũy được trong thời gian học tập.

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

Phân cụm dữ liệu có thê ứng dụng trong nhiều lĩnh vực như:

o Thương mại tìm kiếm nhóm các khách hàng quan trọng dựa vào các thuộc tính đặc trưng tương đồng và những đặc tả của ho trong các bản ghi mua ban của cơ sở dữ liệu.

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

o Sinh học phân loại động, thực vật qua các chức năng gen tương đồng của chúng.

©_ Thư viện phân loại các cụm sách có nội dung và ý nghĩa trong đồng nhau đề cung cấp cho độc giả cũng như đặt hàng với nhà cung cấp

o Bảo hiểm nhận dạng nhóm tham gia bảo hiểm có chỉ phi u cầu bồi thưởng trung bình cao, xác định gian lận trong bảo hiểm thông qua các mẫu cả biệt. o_ Quy hoạch đô thị: nhận dạng các nhóm nhà theo kiểu, vị trí địa lí, giá tri...

nhằm cung cấp thông tin cho quy hoạch đô thị.

o Nghiên cứu địa chan: phân cụm để theo dõi các tâm động đất nhằm cung cấp thông tin cho việc nhận dạng các vùng nguy hiểm

o Tài liệu phân loại, phân nhóm dữ liệu weblog để khám phá các nhóm về các hình thức tiếp cận tương tự trợ giúp cho việc khai phá thông tin từ dữ liệu. 1.6. Thuật tốn phân cụm K - Means

Giới thiệu - "¬

K - means là kỹ thuật rât quan trọng và được sử dụng phô biên trong kỹ thuật phân cụm dữ liệu. Thuật tốn này tìm cách phân cụm các đối tượng đã cho vào k cụm (k là số xác định trước, k nguyên dương) sao cho tổng bình phương khoảng cách giữa các đối tượng đến tâm cụm (centroid) là nhỏ nhất. Về nguyên lý, có n đối tượng, mỗi đối tượng có m thuộc tính, các đối tượng được phân chia thành k cụm dựa trên thuộc tính của đối tượng bằng cách sử dụng thuật toán K-means. Bài tốn này xem mỗi thuộc tính của đối tượng (đối tượng có m thuộc tính) như một tọa độ của không gian m chiều và biểu diễn đối tượng như một điểm trong khơng gian m chiều, đó là:

đị = (Xin Xin» Xixy Xin «ề) — () Trong đó:

a; (i=1, 2, ..., n) là đối tượng thứ i.

xj (I, 2, ..., n, j=, 2, ..., m) là thuộc tính thứ j của đối tượng i.

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

36Khoảng cách Euclid

Phương pháp phân cụm dit liệu thực hiện dựa trên khoảng cách Euclid là khoảng cách nhỏ nhất từ đối tượng đến phần tử trọng tâm của các cụm. Phần tử trọng tâm của

cụm được xác định bằng giá trị trung bình các phan tử trong cụm.

ai = (Xịt, Xp „ Xim); i= 1..n là đối tượng thứ i cần phân cụm. C= (Xj, Xj2, Xịm); j = 1..k là phần tử trọng tâm cụm j

Khoảng cách Euclid từ đối tượng a, đến phan tử trọng tâm nhóm j; c; được tính tốn dựa trên cơng thức:

dy =Trong đó:

Ø¡;: Khoảng cach Euclid thir a; dén Ge Xi: Thuộc tinh thứ s của đối tượng a; x¡¿ Thuộc tính thứ s của phan tử trọng tâm ¢; Phần tử trọng tâm

K phần tử trọng tâm ban đầu được chọn ngẫu nhiên, sau mỗi lần gom các đối tượng vào các cụm, phần tử trọng tâm được tính tốn lại:

cj = {ai, aa, as,.... a} — cụm thứ ¡ ï= 1...k, k là số cum

j ...m, m là số thuộc tính. t là số phần tử hiện có của nhóm thứ i x, thuộc tính thứ j của phan tử s; s = 1...t cụ phần tử thứ j của phan tử trung tâm cụm i;

=15/ @)

Thuật toán K-means. [15]

</div>