Đề tài Tìm hiểu và xây dựng thuật toán K-Means và KNN

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
**************************
BÁO CÁO BÀI TẬP LỚN
KHO DỮ LIỆU VÀ KHAI PHÁ DỮ LIỆU
Đề tài: Tìm hiểu và xây dựng thuật toán K-means
và KNN
Giảng viên hướng dẫn: (Cô) Nguyễn Quỳnh Chi
Nhóm thực hiện: Nhóm 10
Thành viên:
Bùi Trung Hiếu B17DCCN224
Trần Minh Tân B17DCCN552
Bùi Văn Đông B17DCCN132
Nguyễn Như Tuấn B17DCCN659
Vương Đình Hiếu B17DCCN247
1
Phân công công việc:
Thành viên Công việc
Bùi Trung Hiếu Tìm hiểu code và dataset
Trần Minh Tân Tìm hiểu và xây dựng code, tài liệu
Bùi Văn Đông Tìm hiểu code xây dựng tài liệu
Nguyễn Như Tuấn Xây dựng tài liệu
Vương Đình Hiếu Xây dựng tài liệu
2
Giới thiệu
Data mining là lĩnh vực đóng vai trò quan trọng trong việc phân tích và quản lý
dữ liệu. Dựa vào đó chúng ta có thể đưa ra những dự đoán cho kế hoạch tương
lai. Trong thời buổi công nghệ ngày càng phát triển như hiện nay, việc áp dụng
khoa học công nghệ thông tin vào quá trình xử lý và phân tích dữ liệu là vô
cùng cần thiết. Data mining chính là một trong số đó. Sau đây chúng ta sẽ cùng
nhau tìm hiểu về Data mining.
3
Contents
I. Data mining 3
1. Khái niệm 3
2. Các kỹ thuật quan trọng 3
a. Kỹ thuật phân tích phân loại (Classification Analysis) 3
b. Kỹ thuật Association Rule Learning: 4
c. Kỹ thuật phát hiện bất thường (Anomaly or Outlier Detection) 4
d. Kỹ thuật phân tích theo cụm (Clustering Analysis) 4
e. Kỹ thuật dự báo (prediction) 4
f. Kỹ thuật Sequential Patterns: 5
g. Kỹ thuật Decision Trees 5
II. K-Mean 6
1. Khái niệm: 6
2. Ý tưởng của thuật toán k-means 7
3. Một số lưu ý: 7
a. Lựa chọn số cụm: 7
b. Khởi tạo K vị trí ban đầu: 7
c. Về vấn đề tính dừng (hội tụ) 7
III. KNN (K-Nearest Neighbors) 9
1. Giới thiệu: 9
2. Khái niệm: 9
3. Thuật toán: 10
4. Ứng dụng: 10
4
I. Data mining
Data Mining là một trong những thuật ngữ mới xuất hiện đầu thế kỷ 21, nó
là hệ quả của sự bùng nổ Internet đạt tới đỉnh điểm. Theo một công bố của
Intel vào tháng 9 năm 2013 cứ 11 giây trôi qua chúng ta có thêm 1 Petabybe
dữ liệu, nó tương đương với một video chất lượng HD dài 13 năm. Và để
khai phá, trích xuất nó Data Mining ra đời, dưới đây là khái niệm Data
Mining là gì?
1. Khái niệm
Data mining – khai phá dữ liệu là quá trình phân loại, sắp xếp các tập hợp dữ
liệu lớn để xác định các mẫu và thiết lập các mối liên hệ nhằm giải quyết các
vấn đề nhờ phân tích dữ liệu. Các MCU khai phá dữ liệu cho phép các doanh
nghiệp có thể dự đoán được xu hướng tương lai.
Quá trình khai phá dữ liệu là một quá trình phức tạp bao gồm kho dữ liệu
chuyên sâu cũng như các công nghệ tính toán. Hơn nữa, Data Mining không
chỉ giới hạn trong việc trích xuất dữ liệu mà còn được sử dụng để chuyển
đổi, làm sạch, tích hợp dữ liệu và phân tích mẫu.
Có nhiều tham số quan trọng khác nhau trong Data Mining, chẳng hạn như
quy tắc kết hợp, phân loại, phân cụm và dự báo. Một số tính năng chính của
Data Mining:
● Dự đoán các mẫu dựa trên xu hướng trong dữ liệu.
● Tính toán dự đoán kết quả
● Tạo thông tin phản hồi để phân tích
● Tập trung vào cơ sở dữ liệu lớn hơn.
● Phân cụm dữ liệu trực quan
2. Các kỹ thuật quan trọng
Về cơ bản, Data Mining hay khai phá dữ liệu là việc xử lý, nhận biết các xu
hướng từ các thông tin dữ liệu để có thể đưa ra quyết định hoặc đánh giá.
Thông thường, các bạn sẽ thấy có 6 kỹ thuật cốt lõi, được sử dụng nhiều
trong việc khai phá dữ liệu:
a. Kỹ thuật phân tích phân loại (Classification Analysis)
Kỹ thuật khai phá dữ liệu đầu tiên là kỹ thuật phân tích phân loại. Đây
là kỹ thuật cho phép phân loại một đối tượng vào một hoặc một số lớp
cho trước. 
Chúng ta thường sử dụng kỹ thuật khai thác dữ liệu này để lấy các
thông tin quan trọng từ dữ liệu và siêu dữ liệu. Vì vậy, trong phân tích
5
phân loại, chúng ta cần áp dụng các thuật toán khác nhau tùy thuộc
vào mục tiêu sử dụng.
b. Kỹ thuật Association Rule Learning:
Kỹ thuật Association Rule Learning trong khai phá dữ liệu được sử
dụng để xác định mối quan hệ giữa các biến khác nhau trong cơ sở
dữ liệu. Ngoài ra, nó còn được sử dụng để “giải nén” các mẫu ẩn
trong dữ liệu. Association Rule rất hữu ích để kiểm tra, dự đoán hành
vi và thường được áp dụng trong ngành bán lẻ.
c. Kỹ thuật phát hiện bất thường (Anomaly or Outlier Detection)
Về cơ bản, kỹ thuật khai phá dữ liệu (Data Mining) này dùng để nhấn
mạnh vào việc quan sát các mục dữ liệu trong bộ dữ liệu để tìm ra các tập
dữ liệu không khớp với mẫu dự kiến. Bất thường ở đây có thể đề cập đến
độ lệch, sự khác thường, các nhiễu và ngoại lệ. 
Sự bất thường được xem là khá quan trọng vì nó có thể cung cấp một số
thông tin cần thiết. Nó có thể là một dữ liệu khác biệt so với mức trung
bình chung trong một tập dữ liệu. Điều này chỉ ra rằng một cái gì đó khác
thường đã xảy ra và các nhà phân tích dữ liệu cần chú ý.
d. Kỹ thuật phân tích theo cụm (Clustering Analysis)
“Cụm” có nghĩa là một nhóm các đối tượng dữ liệu. Các đối tượng tương
tự nhau thì sẽ nằm trong một cụm. Kết quả là các đối tượng tương tự
nhau trong cùng một nhóm. 
Về cơ bản, kỹ thuật khai phá dữ liệu này thường được ứng dụng để tạo hồ
sơ khách hàng. Hoặc trong lĩnh vực Marketing, đây được xem là việc
chia phân khúc khách hàng.
e. Kỹ thuật dự báo (prediction)
6
Trong khai phá dữ liệu, kỹ thuật dự báo được ứng dụng ở một số trường
hợp đặc biệt. Nó được sử dụng để khám phá mối quan hệ giữa các biến
độc lập và phụ thuộc.
f. Kỹ thuật Sequential Patterns:
Đây là một kỹ thuật quan trọng trong khai phá dữ liệu. Kỹ thuật này giúp
tìm cách khám phá các mẫu tương tự.
g. Kỹ thuật Decision Trees
Decision Trees là một thuật ngữ rất quan trọng trong khai phá dữ liệu. Nó
đóng một vai trò quan trọng trong quá trình khai phá dữ liệu bởi vì mô
hình này rất dễ hiểu cho người dùng.
Trong kỹ thuật Decision Trees, gốc cây là một câu hỏi đơn giản có nhiều
câu trả lời. Ngoài ra, mỗi câu hỏi dẫn đến bộ câu hỏi khác. Và nó sẽ giúp
chúng ta xác định dữ liệu. Vì vậy, chúng ta có thể đưa ra quyết định cuối
cùng nhờ vào kỹ thuật này.
7
II. K-Mean
1. Khái niệm:
K-means là một thuật toán phân cụm đơn giản thuộc loại học không giám sát(tức là
dữ liệu không có nhãn) và được sử dụng để giải quyết bài toán phân cụm. Ý tưởng
của thuật toán phân cụm k-means là phân chia 1 bộ dữ liệu thành các cụm khác
nhau. Trong đó số lượng cụm được cho trước là k. Công việc phân cụm được xác
lập dựa trên nguyên lý: Các điểm dữ liệu trong cùng 1 cụm thì phải có cùng 1 số
tính chất nhất định. Tức là giữa các điểm trong cùng 1 cụm phải có sự liên quan lẫn
nhau. Đối với máy tính thì các điểm trong 1 cụm đó sẽ là các điểm dữ liệu gần
nhau.
Thuật toán phân cụm k-means là một phương pháp được sử dụng trong phân tích
tính chất cụm của dữ liệu. Nó đặc biệt được sử dụng nhiều trong khai phá dữ liệu
và thống kê. Nó phân vùng dữ liệu thành k cụm khác nhau. Giải thuật này giúp
chúng ta xác định được dữ liệu của chúng ta nó thực sử thuộc về nhóm nào.
8
2. Ý tưởng của thuật toán k-means
3. Một số lưu ý:
a. Lựa chọn số cụm:
Chỉ việc lựa chọn số cụm k đã có thể tách thành 1 bài toán riêng.
Không có 1 con số k nào là hợp lý cho tất cả các bài toán. Bạn có thể
đọc hiểu tập dữ liệu của mình để xác định xem trong đó có thể có bao
nhiêu cụm? Nhưng không phải lúc nào bạn cũng có thể làm thế. Cách
làm duy nhất là bạn hãy thử với từng giá trị k=1,2,3,4,5, để xem kết
quả phân cụm thay đổi như thế nào. Một số nghiên cứu cho thấy việc
thay đổi k sẽ có hiệu quả nhưng sẽ dừng lại ở 1 con số nào đó. Như
vậy bạn hoàn toàn có thể thử xem dữ liệu của mình tốt với giá trị k
nào đó.
b. Khởi tạo K vị trí ban đầu:
Bằng cách nào đó, hãy có gắng khởi tạo k tâm cụm này phân bố đồng
đều trên không gian của bộ dữ liệu. Điều đó có thể làm khi bạn có thể
xác định được không gian và tính chất của dữ liệu. Nhưng ít nhất, các
tâm cụm mà bạn khởi tạo cũng đừng quá gần nhau, cũng đừng trùng
nhau.
Còn 1 cách cuối cùng là bạn sẽ chạy thuật toán nhiều lần để lấy kết
quả tốt nhất trong các lần chạy đó. Với điều kiện là bạn khởi tạo tâm
của k cụm ngẫu nhiên.
c. Về vấn đề tính dừng (hội tụ)
Đối với những trường hợp dữ liệu phức tạp, thuật toán k-means sẽ rất
lâu hoặc không bao giờ hội tụ. Tức là sẽ không bao giờ xác định được
tâm cụm cố định để kết thúc bài toán. Hoặc là phải chạy qua rất nhiều
bước lặp. Trong những trường hợp như vậy, thay vì phải tìm được k
tâm cụm cố định thì ta sẽ dừng bài toán khi sự thay đổi ở một con số
9
chấp nhận được. Tức là giữa hai lần cập nhật tâm cụm thì chênh lệch
vị trí giữa tâm cũ và mới nhỏ hơn một số delta cho phép nào đó.
4. Cài đặt
a. Khởi tạo dữ liệu
Khởi tạo dữ liệu dựa trên số lượng cụm nhập vào (k). Mỗi cụm
random ra 500 điểm trên tọa độ không gian Oxy. Thêm tất cả các cụm
vào tập dữ liệu tổng.
10
Khởi tạo tâm cụm (ramdom)
b. Lặp cho tới khi phân cụm hoàn thành
11
Kết quả sau khi chạy xong.
12
III. KNN (K-Nearest Neighbors)
1. Giới thiệu:
K-Nearest Neighbors algorithm (K-NN) được sử dụng rất phổ biến trong lĩnh
vực Data Mining. K-NN là phương pháp để phân lớp các đối tượng dựa vào
khoảng cách gần nhất giữa đối tượng cần xếp lớp (Query point) và tất cả các đối
tượng trong Training Data. Một đối tượng được phân lớp dựa vào K láng giềng
của nó. K là số nguyên dương được xác định trước khi thực hiện thuật toán.
Người ta thường dùng khoảng cách Euclidean để tính khoảng cách giữa các đối
tượng.
2. Khái niệm:
Thuật toán KNN là một trong những phương pháp học có giám sát “Supervised
Learning” tức dựa trên biến mục tiêu đã được xác định trước đó, thuật toán sẽ
xem xét dữ liệu đã chứa biến mục tiêu (đã phân loại) để “học” và tìm ra những
biến d có thể tác động đến biến mục tiêu.
KNN dựa trên giả định là những thứ tương tự hay có tính chất gần giống nhau
sẽ nằm ở vị trí gần nhau, với giả định như vậy, KNN được xây dựng trên các
công thức toán học phục vụ để tính khoảng cách giữa 2 điểm dữ liệu (gọi là
Data points) để xem xét mức độ giống nhau của chúng.
KNN còn gọi là “Lazy learning method” vì tính đơn giản của nó, có nghĩa là
quá trình training không quá phức tạp để hoàn thiênhj mô hình (tất cả các dữ
liệu đào tạo có thể được sử dụng để kiểm tra mô hình KNN). Điều này làm cho
việc xây dựng mô hình nhanh hơn nhưng giai đoạn thử nghiệm chậm hơn và tốn
13
kém hơn về mặt thời gian và bộ nhớ lưu trữ, đặc biệt khi bộ dữ liệu lớn và phức
tạp với nhiều biến khác nhau. Trong trường hợp xấu nhất, KNN cần thêm thời
gian để quét tất cả các điểm dữ liệu và việc này sẽ cần nhiều không gian bộ nhớ
hơn để lưu trữ dữ liệu. Ngoài ra KNN không cần dựa trên các tham số khác
nhau để tiến hành phân loại dữ liệu, không đưa ra bất kỳ kết luận cụ thể nào
giữa biến đầu vào và biến mục tiêu, mà chỉ dựa trên khoảng cách giữa data
point cần phân loại với data point đã phân loại trước đó. Đây là một đặc điểm
cực kỳ hữu ích vì hầu hết dữ liệu trong thế giới thực tại không thực sự tuân theo
bất kỳ giả định lý thuyết nào ví dụ như phân phối chuẩn trong thống kê.
3. Thuật toán:
a) Xác định giá trị tham số K (số láng giềng gần nhất)
b) Tính khoảng cách giữa đối tượng cần phân lớp (Query Point) với tất
cả các đối tượng trong training data (thường sử dụng khoảng các
Euclidean)
c) Sắp xếp khoảng cách theo thứ tự tăng dần và xác định K láng giềng
gần nhất với Query Point
d) Lấy tất cả các lớp của K láng giềng gần nhất đã xác định
e) Dựa vào phần lớn lớp của láng giềng gần nhất để xác định lớp cho
Query Point
4. Ứng dụng:
Trong y tế
Trong lĩnh vực ngân hàng
Trong giáo dục
Trong thương mại điện tử
Trong kinh tế
5. Cài đặt
a. Load dữ liệu từ file excel
14
Lấy 100 bản ghi đầu làm tập tranning
Lấy các bản ghi còn lại làm tập testing
b. Lặp qua từng bản ghi testing, dự đoán nhãn
15
Tìm k hàng xóm gần nhất với bản ghi thử
Lấy nhãn đa số trong tập k hang xóm
Gán nhãn cho bản ghi thử
16
Sau khi lặp qua tất cả bản ghi thử, tính toán tỉ lệ dự đoán chính xác.
17