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

Nội dung text: Báo cáo Tìm hiểu và xây dựng thuật toán K-Means và KNN

1. HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG BAO CAO BAI 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 Giang 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
2. 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
3. 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
4. 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
5. 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
6. 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
7. 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
8. 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
9. 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
10. 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
11. 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
12. Kết quả sau khi chạy xong. 12
13. 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
14. 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
15. 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
16. 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
17. 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