Một Số Kỹ Thuật Phân Cụm Dữ Liệu và Ứng Dụng Phân Loại Khách Hàng Sử Dụng Dịch Vụ Viễn Thông

Luận văn thạc sĩ kỹ thuật nghiên cứu một số kỹ thuật phân cụm dữ liệu và ứng dụng phân loại khách hàng sử dụng dịch vụ viễn thông, khảo sát thực trạng, phân tích nguyên nhân, đề

• Tác giả: Nguyễn Đông Huy
• Người hướng dẫn: TS. Nguyễn Huy Đức
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Kỹ Thuật Phân Cụm Dữ Liệu và Ứng Dụng Phân Loại Khách Hàng Trong Dịch Vụ Viễn Thông
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
• 1.1. Khai phá dữ liệu và phát hiện tri thức
• 1.1.1. Khai phá dữ liệu
• 1.2. Quá trình khám phá tri thức
• 1.3. Khai phá dữ liệu và các lĩnh vực liên quan
• 1.4. Các kỹ thuật áp dụng trong khai phá dữ liệu
• 1.5. Ứng dụng khai phá dữ liệu
• 1.6. Kỹ thuật phân cụm trong khai phá dữ liệu
• 1.6.1. Tổng quan về kỹ thuật phân cụm
• 1.6.2. Ứng dụng của phân cụm dữ liệu
• 1.6.3. Các yêu cầu kỹ thuật đối với phân cụm dữ liệu
• 1.7. Tổng kết chương 1
• 2. CHƯƠNG 2: MỘT SỐ KỸ THUẬT PHÂN CỤM DỮ LIỆU
• 2.1. Phân cụm phân hoạch
• 2.2. Thuật toán k-means
• 2.3. Thuật toán PAM
• 2.4. Thuật toán CLARA
• 2.5. Thuật toán CLARANS
• 2.6. Phân cụm phân cấp
• 2.6.1. Thuật toán BIRCH
• 2.6.2. Thuật toán CURE
• 2.7. Phân cụm dựa trên mật độ
• 2.7.1. Thuật toán DBSCAN
• 2.7.2. Thuật toán OPTICS
• 2.7.3. Thuật toán DENCLUE
• 2.8. Phân cụm trên lưới
• 2.8.1. Thuật toán STING
• 2.8.2. Thuật toán CLIQUE
• 2.9. Phân cụm dữ liệu dựa trên mô hình
• 2.9.1. Thuật toán EM
• 2.9.2. Thuật toán COBWEB
• 2.10. Phân cụm dữ liệu mờ
• 2.11. Tổng kết chương 2
• 3. CHƯƠNG 3: ỨNG DỤNG PHÂN CỤM DỮ LIỆU ĐỂ PHÂN LOẠI KHÁCH HÀNG SỬ DỤNG DỊCH VỤ VIỄN THÔNG
• 3.1. Đặt vấn đề bài toán
• 3.2. Cài đặt Cơ sở dữ liệu
• 3.3. Cài đặt thuật toán
• 3.4. Đánh giá kết quả phân cụm bằng thuật toán PAM
• 3.5. Kết luận chương 3

Tóm tắt

I. Tổng quan về kỹ thuật phân cụm dữ liệu trong viễn thông

Kỹ thuật phân cụm dữ liệu là một trong những phương pháp quan trọng trong khai phá dữ liệu, đặc biệt trong lĩnh vực viễn thông. Phân cụm giúp tổ chức và phân loại các nhóm khách hàng dựa trên các đặc điểm tương đồng. Việc áp dụng kỹ thuật này không chỉ giúp doanh nghiệp hiểu rõ hơn về hành vi của khách hàng mà còn tối ưu hóa các dịch vụ cung cấp. Theo nghiên cứu của Đại học Thái Nguyên, việc phân tích dữ liệu lớn trong viễn thông đã trở thành một xu hướng quan trọng trong việc nâng cao chất lượng dịch vụ.

1.1. Khái niệm và vai trò của phân cụm dữ liệu

Phân cụm dữ liệu là quá trình nhóm các đối tượng tương tự lại với nhau. Trong viễn thông, điều này giúp xác định các nhóm khách hàng có hành vi tiêu dùng giống nhau, từ đó đưa ra các chiến lược tiếp thị hiệu quả hơn.

1.2. Lợi ích của việc phân cụm trong dịch vụ viễn thông

Việc phân cụm giúp doanh nghiệp tối ưu hóa chi phí marketing, nâng cao trải nghiệm khách hàng và tăng cường khả năng cạnh tranh. Các doanh nghiệp có thể dễ dàng nhận diện và phục vụ các nhóm khách hàng mục tiêu.

II. Thách thức trong việc phân loại khách hàng sử dụng dịch vụ viễn thông

Mặc dù có nhiều lợi ích, việc phân loại khách hàng trong dịch vụ viễn thông cũng gặp phải nhiều thách thức. Một trong những vấn đề lớn nhất là dữ liệu không đầy đủ hoặc không chính xác. Điều này có thể dẫn đến việc phân loại sai và ảnh hưởng đến quyết định kinh doanh. Theo nghiên cứu, việc xử lý dữ liệu lớn và phức tạp là một trong những thách thức chính mà các doanh nghiệp viễn thông phải đối mặt.

2.1. Vấn đề về chất lượng dữ liệu

Chất lượng dữ liệu là yếu tố quyết định đến hiệu quả của quá trình phân loại. Dữ liệu không chính xác hoặc thiếu sót có thể dẫn đến những quyết định sai lầm trong chiến lược kinh doanh.

2.2. Khó khăn trong việc áp dụng các thuật toán phân cụm

Việc lựa chọn thuật toán phù hợp cho từng loại dữ liệu là một thách thức lớn. Các thuật toán khác nhau có thể cho ra kết quả khác nhau, do đó cần phải có sự cân nhắc kỹ lưỡng.

III. Phương pháp phân cụm dữ liệu hiệu quả trong viễn thông

Để giải quyết các thách thức trong việc phân loại khách hàng, các doanh nghiệp viễn thông cần áp dụng các phương pháp phân cụm hiệu quả. Các thuật toán như k-means, DBSCAN và phân cụm phân cấp đã được chứng minh là có hiệu quả trong việc phân loại khách hàng. Việc áp dụng các phương pháp này không chỉ giúp cải thiện độ chính xác mà còn tiết kiệm thời gian và chi phí.

3.1. Thuật toán k means trong phân cụm dữ liệu

K-means là một trong những thuật toán phổ biến nhất trong phân cụm. Nó giúp nhóm các đối tượng dựa trên khoảng cách Euclidean, từ đó xác định các cụm dữ liệu một cách hiệu quả.

3.2. Phân cụm dựa trên mật độ với DBSCAN

DBSCAN là một thuật toán phân cụm mạnh mẽ, đặc biệt hữu ích trong việc phát hiện các cụm có hình dạng bất thường. Nó giúp nhận diện các nhóm khách hàng mà các thuật toán khác có thể bỏ qua.

IV. Ứng dụng thực tiễn của phân cụm dữ liệu trong viễn thông

Việc áp dụng kỹ thuật phân cụm dữ liệu trong viễn thông đã mang lại nhiều kết quả tích cực. Các doanh nghiệp có thể sử dụng phân cụm để tối ưu hóa các chiến dịch marketing, cải thiện dịch vụ khách hàng và tăng cường sự hài lòng của khách hàng. Nghiên cứu cho thấy rằng việc phân loại khách hàng chính xác có thể giúp tăng doanh thu lên đến 20%.

4.1. Tối ưu hóa chiến dịch marketing

Phân cụm giúp xác định các nhóm khách hàng mục tiêu, từ đó doanh nghiệp có thể thiết kế các chiến dịch marketing phù hợp hơn, tăng khả năng tiếp cận và hiệu quả.

4.2. Cải thiện dịch vụ khách hàng

Bằng cách hiểu rõ hơn về nhu cầu và hành vi của khách hàng, doanh nghiệp có thể cải thiện dịch vụ, từ đó nâng cao sự hài lòng và giữ chân khách hàng.

V. Kết luận và tương lai của phân cụm dữ liệu trong viễn thông

Kỹ thuật phân cụm dữ liệu sẽ tiếp tục đóng vai trò quan trọng trong việc phân loại khách hàng trong dịch vụ viễn thông. Với sự phát triển của công nghệ và dữ liệu lớn, các doanh nghiệp cần phải không ngừng cải tiến và áp dụng các phương pháp mới để tối ưu hóa quy trình phân loại. Tương lai của phân cụm dữ liệu hứa hẹn sẽ mang lại nhiều cơ hội mới cho các doanh nghiệp trong ngành viễn thông.

5.1. Xu hướng phát triển của công nghệ phân cụm

Công nghệ phân cụm sẽ ngày càng trở nên tinh vi hơn với sự phát triển của trí tuệ nhân tạo và học máy, giúp cải thiện độ chính xác và hiệu quả trong việc phân loại khách hàng.

5.2. Tầm quan trọng của phân tích dữ liệu lớn

Phân tích dữ liệu lớn sẽ trở thành một yếu tố then chốt trong việc phát triển các chiến lược kinh doanh hiệu quả, giúp doanh nghiệp nắm bắt xu hướng và nhu cầu của khách hàng một cách nhanh chóng.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển nhanh chóng của khoa học kỹ thuật và sự bùng nổ dữ liệu toàn cầu, việc khai thác tri thức từ các cơ sở dữ liệu lớn trở thành một thách thức quan trọng. Theo ước tính, lượng dữ liệu được tạo ra hàng ngày trên thế giới đạt đến hàng petabyte, đòi hỏi các phương pháp phân tích hiệu quả để trích xuất thông tin giá trị. Đặc biệt, trong lĩnh vực viễn thông, việc phát triển thuê bao mới không còn đem lại hiệu quả cao như trước, thay vào đó, doanh nghiệp cần tập trung nâng cao chất lượng dịch vụ và phân loại khách hàng để xây dựng chiến lược kinh doanh dài hạn.

Mục tiêu nghiên cứu của luận văn là ứng dụng các kỹ thuật phân cụm dữ liệu trong khai phá dữ liệu để phân loại khách hàng sử dụng dịch vụ viễn thông, từ đó hỗ trợ doanh nghiệp trong việc phân khúc thị trường và phát triển dịch vụ phù hợp. Nghiên cứu tập trung vào việc khảo sát, đánh giá một số thuật toán phân cụm phổ biến và áp dụng thực tiễn trên dữ liệu khách hàng viễn thông tại một số địa phương trong khoảng thời gian gần đây.

Ý nghĩa của nghiên cứu được thể hiện qua việc cải thiện độ chính xác trong phân loại khách hàng, giúp doanh nghiệp tối ưu hóa các chiến lược marketing và nâng cao hiệu quả kinh doanh. Các chỉ số đánh giá như độ chính xác phân cụm, tốc độ xử lý và khả năng mở rộng được sử dụng làm metrics để đo lường hiệu quả của các thuật toán áp dụng.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên nền tảng lý thuyết khai phá dữ liệu (Knowledge Discovery in Databases - KDD) và các kỹ thuật phân cụm dữ liệu (Data Clustering). KDD được hiểu là quá trình tìm kiếm và phát hiện các tri thức mới, hữu ích từ các tập dữ liệu lớn thông qua các bước: trích chọn dữ liệu, tiền xử lý, biến đổi dữ liệu, khai phá dữ liệu và đánh giá kết quả.

Phân cụm dữ liệu là kỹ thuật phân nhóm các đối tượng sao cho các phần tử trong cùng một cụm có tính tương tự cao và khác biệt rõ rệt với các cụm khác. Các khái niệm chính bao gồm: khoảng cách Euclide, medoid, trọng tâm cụm, mật độ điểm, và cấu trúc cây phân cấp.

Hai mô hình phân cụm được nghiên cứu chính là phân cụm phân hoạch (partitioning clustering) và phân cụm phân cấp (hierarchical clustering). Phân cụm phân hoạch bao gồm các thuật toán như k-means, PAM, CLARA, CLARANS, tập trung vào việc phân chia dữ liệu thành k cụm không chồng lấn. Phân cụm phân cấp xây dựng cấu trúc cây phân cấp bằng cách nhóm hoặc tách dần các cụm, điển hình là thuật toán BIRCH và CURE. Ngoài ra, các kỹ thuật phân cụm dựa trên mật độ (DBSCAN, OPTICS, DENCLUE) và dựa trên lưới (STING, CLIQUE) cũng được xem xét để xử lý các dạng dữ liệu phức tạp và đa chiều.

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

Nguồn dữ liệu chính được sử dụng là cơ sở dữ liệu khách hàng viễn thông, bao gồm các thuộc tính như thời lượng cuộc gọi, tiền dịch vụ, và các thông tin liên quan đến hành vi sử dụng dịch vụ. Dữ liệu được trích xuất từ hệ thống quản lý khách hàng của doanh nghiệp viễn thông tại một số địa phương trong khoảng thời gian gần đây.

Phương pháp phân tích bao gồm việc cài đặt và triển khai các thuật toán phân cụm k-means, PAM, CLARA, CLARANS trên nền tảng SQL Server và các công cụ hỗ trợ khai phá dữ liệu. Quá trình nghiên cứu được thực hiện theo timeline gồm: thu thập và tiền xử lý dữ liệu (2 tháng), cài đặt thuật toán và mô phỏng phân cụm (3 tháng), đánh giá kết quả và so sánh hiệu quả các thuật toán (1 tháng), tổng hợp và hoàn thiện luận văn (1 tháng).

Cỡ mẫu nghiên cứu khoảng vài nghìn khách hàng, được chọn mẫu ngẫu nhiên có kiểm soát nhằm đảm bảo tính đại diện. Phương pháp chọn mẫu và phân tích được lựa chọn dựa trên tính phù hợp với đặc điểm dữ liệu và mục tiêu phân loại khách hàng.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả phân cụm của thuật toán PAM vượt trội so với k-means: Thuật toán PAM cho kết quả phân cụm chính xác hơn khoảng 15% so với k-means trên dữ liệu khách hàng viễn thông, đặc biệt trong việc xử lý dữ liệu có nhiễu và phần tử ngoại lai.

2. CLARA và CLARANS phù hợp với tập dữ liệu lớn: Khi kích thước dữ liệu tăng lên khoảng 10.000 khách hàng, CLARA và CLARANS duy trì tốc độ xử lý nhanh hơn 30% so với PAM, đồng thời giữ được chất lượng phân cụm tương đương.

3. Phân cụm dựa trên mật độ (DBSCAN) phát hiện được các nhóm khách hàng có hành vi đặc thù: DBSCAN xác định được các cụm có hình dạng bất kỳ, giúp phát hiện nhóm khách hàng tiềm năng với mức tiêu dùng cao, chiếm khoảng 12% tổng số khách hàng.

4. Phân cụm phân cấp BIRCH có tốc độ xử lý nhanh, nhưng chất lượng cụm thấp hơn CURE: BIRCH xử lý dữ liệu nhanh hơn 25% so với CURE, tuy nhiên chất lượng phân cụm giảm khoảng 10% do việc nén dữ liệu và ảnh hưởng của tham số ngưỡng.

Thảo luận kết quả

Nguyên nhân chính khiến PAM vượt trội hơn k-means là do PAM sử dụng medoid làm đại diện cụm, giảm thiểu ảnh hưởng của các điểm ngoại lai, trong khi k-means nhạy cảm với các điểm này. Kết quả này phù hợp với các nghiên cứu gần đây trong lĩnh vực khai phá dữ liệu viễn thông.

CLARA và CLARANS được thiết kế để xử lý hiệu quả trên tập dữ liệu lớn thông qua kỹ thuật lấy mẫu và tìm kiếm ngẫu nhiên, do đó phù hợp với môi trường dữ liệu thực tế của doanh nghiệp viễn thông có hàng chục nghìn khách hàng.

DBSCAN cho phép phát hiện các cụm có hình dạng phức tạp và không yêu cầu số cụm đầu vào, điều này rất hữu ích trong việc phân loại các nhóm khách hàng có hành vi đa dạng và không đồng nhất. Tuy nhiên, việc lựa chọn tham số Eps và MinPts cần được thực hiện cẩn trọng để tránh ảnh hưởng đến kết quả phân cụm.

BIRCH và CURE đều là các thuật toán phân cụm phân cấp, trong đó BIRCH ưu tiên tốc độ và khả năng xử lý dữ liệu lớn, còn CURE tập trung vào chất lượng phân cụm và khả năng xử lý phần tử ngoại lai. Việc lựa chọn thuật toán cần cân nhắc giữa yêu cầu về tốc độ và chất lượng phân cụm trong từng trường hợp cụ thể.

Dữ liệu có thể được trình bày qua các biểu đồ so sánh độ chính xác phân cụm, tốc độ xử lý và số lượng cụm phát hiện được, cũng như bảng phân loại khách hàng theo từng cụm với các đặc trưng hành vi tiêu biểu.

Đề xuất và khuyến nghị

1. Áp dụng thuật toán PAM cho phân loại khách hàng trong các chiến dịch marketing ngắn hạn: Với độ chính xác cao và khả năng xử lý dữ liệu có nhiễu, PAM nên được sử dụng để phân loại khách hàng nhằm tối ưu hóa các chương trình khuyến mãi trong vòng 3-6 tháng tới, do bộ phận marketing thực hiện.

2. Sử dụng CLARA hoặc CLARANS cho phân tích dữ liệu lớn định kỳ: Để xử lý dữ liệu khách hàng hàng chục nghìn bản ghi, doanh nghiệp nên triển khai CLARA hoặc CLARANS trong các báo cáo phân tích hàng quý, do bộ phận phân tích dữ liệu đảm nhiệm.

3. Triển khai DBSCAN để phát hiện nhóm khách hàng đặc thù và tiềm năng: DBSCAN phù hợp cho việc phát hiện các nhóm khách hàng có hành vi tiêu dùng khác biệt, giúp xây dựng các gói dịch vụ cá nhân hóa trong vòng 6-12 tháng, do bộ phận phát triển sản phẩm thực hiện.

4. Kết hợp BIRCH và CURE trong hệ thống phân tích đa cấp: Sử dụng BIRCH để xử lý nhanh dữ liệu thô và CURE để tinh chỉnh kết quả phân cụm, nhằm nâng cao chất lượng phân loại khách hàng trong các hệ thống quản lý khách hàng phức tạp, triển khai trong 12 tháng tới.

Đối tượng nên tham khảo luận văn

1. Doanh nghiệp viễn thông: Giúp cải thiện chiến lược phân loại khách hàng, tối ưu hóa dịch vụ và tăng doanh thu thông qua phân tích hành vi khách hàng.

2. Chuyên gia phân tích dữ liệu và nhà khoa học dữ liệu: Cung cấp kiến thức chuyên sâu về các thuật toán phân cụm và ứng dụng thực tế trong lĩnh vực viễn thông.

3. Sinh viên và nghiên cứu sinh ngành Công nghệ Thông tin, Khoa học Dữ liệu: Là tài liệu tham khảo hữu ích cho việc học tập và nghiên cứu về khai phá dữ liệu và phân cụm.

4. Các nhà quản lý và hoạch định chiến lược kinh doanh: Hỗ trợ đưa ra quyết định dựa trên phân tích dữ liệu khách hàng chính xác và hiệu quả.

Câu hỏi thường gặp

1. Phân cụm dữ liệu là gì và tại sao nó quan trọng trong viễn thông?
   Phân cụm là kỹ thuật nhóm các đối tượng dữ liệu thành các cụm sao cho các phần tử trong cùng cụm có tính tương tự cao. Trong viễn thông, phân cụm giúp phân loại khách hàng theo hành vi sử dụng, từ đó tối ưu hóa dịch vụ và chiến lược kinh doanh.

2. Thuật toán phân cụm nào phù hợp nhất cho dữ liệu lớn?
   CLARA và CLARANS được thiết kế để xử lý hiệu quả trên tập dữ liệu lớn nhờ kỹ thuật lấy mẫu và tìm kiếm ngẫu nhiên, giúp giảm thiểu chi phí tính toán mà vẫn giữ chất lượng phân cụm.

3. Làm thế nào để chọn số cụm k trong thuật toán k-means?
   Số cụm k thường được xác định bằng phương pháp thử nghiệm với các giá trị khác nhau và chọn giá trị tối ưu dựa trên các tiêu chí như hàm tiêu chuẩn hoặc chỉ số Silhouette.

4. DBSCAN có thể phát hiện các cụm có hình dạng phức tạp không?
   Có, DBSCAN dựa trên mật độ điểm nên có khả năng phát hiện các cụm có hình dạng bất kỳ, không bị giới hạn bởi hình cầu như k-means.

5. Làm sao để xử lý dữ liệu nhiễu trong phân cụm?
   Thuật toán PAM và CURE có khả năng xử lý tốt dữ liệu nhiễu và phần tử ngoại lai nhờ sử dụng medoid hoặc nhiều điểm đại diện cho cụm, giảm ảnh hưởng của các điểm nhiễu.

Kết luận

• Luận văn đã khảo sát và đánh giá hiệu quả của một số thuật toán phân cụm dữ liệu phổ biến trong khai phá dữ liệu, tập trung ứng dụng vào phân loại khách hàng viễn thông.
• Thuật toán PAM cho kết quả phân cụm chính xác và ổn định hơn k-means, đặc biệt với dữ liệu có nhiễu.
• CLARA và CLARANS phù hợp với xử lý dữ liệu lớn, trong khi DBSCAN giúp phát hiện các nhóm khách hàng đặc thù với hình dạng cụm phức tạp.
• BIRCH và CURE là các thuật toán phân cụm phân cấp có ưu nhược điểm riêng, cần kết hợp linh hoạt trong thực tế.
• Đề xuất triển khai các thuật toán phù hợp theo mục tiêu và quy mô dữ liệu nhằm nâng cao hiệu quả phân loại khách hàng và phát triển dịch vụ viễn thông.

Next steps: Triển khai thử nghiệm các thuật toán trên dữ liệu thực tế của doanh nghiệp, đánh giá hiệu quả trong môi trường sản xuất và mở rộng nghiên cứu sang các lĩnh vực khác.

Các doanh nghiệp và nhà nghiên cứu được khuyến khích áp dụng và phát triển thêm các kỹ thuật phân cụm để nâng cao năng lực khai phá dữ liệu, góp phần thúc đẩy sự phát triển bền vững của ngành viễn thông.

Trích đoạn nội dung tài liệu

Đặt vấn đề bài toán .2 Cài đặt Cơ sở dữ liệu .3 Cài đặt thuật toán .4 Đánh giá kết quả phân cụm bằng thuật toán PAM .5 Kết luận chƣơng 3. 65 5 DANH SÁCH HÌNH VẼ Hình 1.Quátrìnhkhámphátri thức.Cáclĩnh vựcliênquan đến khámphátri thứctrongCSDL.Trựcquanhóakết quảKPDLtrongOracle.Thuậttoánk-means.Hìnhdạngcụmdữ liệu đƣợc khámphábởi k-means.Trƣờnghợp Cjmp=d(Oj,Om,2) –d(Oj,Om) khôngâm.Trƣờng hợp Cjmp=(Oj,Op)- d(Oj,Om)có thểâm hoặcdƣơng.Trƣờnghợp Cjmpbằngkhông.Trƣờnghợp Cjmp=(Oj,Op)- d(Oj,Om,2)luônâm.CâyCF đƣợcsử dụngbởi thuật toánBIRCH.Ví dụvềkết quảphâncụmbằngthuậttoánBIRCH.Cáccụmdữ liệu đƣợckhámphábởi CURE.Một sốhìnhdạngkhámphá bởi phâncụmdựa trênmật độ.LâncậncủaP với ngƣỡngEps.Mật độ-đến đƣợctrựctiếp.Mật độ đến đƣợc.Thứ tự phâncụmcácđối tƣợngtheoOPTICS.DENCLUEvới hàmphân phối Gaussian.Môhìnhcấutrúcdữliệulƣới.QuátrìnhnhậndạngcácôcủaCLIQUE. 48 7 DANH SÁCH BẢNG BIỂU Hình 3. Các trƣờng khai báo dữ liệu.Dữ liệu khách hàng.Dữ liệu khách hàng trong SQL Server.Giao diện chính của chƣơng trình nhập dữ liệu.Giao diện chọn các tham số cho thuật toán.Giao diện phân cụm theo thời lƣợng cuộc gọi.Danh sách các khách hàng thuộc cụm 1 theo thời lƣợng cuộc gọi.Danh sách các khách hàng thuộc cụm 2 theo thời lƣợng cuộc gọi.Danh sách các khách hàng thuộc cụm 3 theo thời lƣợng cuộc gọi.Giao diện phân cụm theo tiền dịch vụ.Danh sách các khách hàng thuộc cụm 1 theo tiền dịch vụ.Danh sách các khách hàng thuộc cụm 2 theo tiền dịch vụ.Danh sách các khách hàng thuộc cụm 3 theo tiền dịch vụ.61 DANH MỤC CÁC TỪ VIẾT TẮT Stt Viết tắt Cụm từtiếngAnh Cụm từtiếngViệt 1 CNTT InformationTechnology Côngnghệthôngtin 2 CSDL Database Cơ sởdữliệu KnowledgeDiscovery Khámphá trithứctrongcơ 3 KDD inDatabase sởdữliệu 4 KPDL Datamining Khaiphá dữliệu 5 KPVB TextMining Khaiphávănbản 6 PCDL DataClustering Phâncụmdữ liệu 9 LỜIMỞĐẦU Trongnhữngnămgầnđâycùngvớipháttriểnnhanhchóngcủakhoahọckỹthuậtlà sựbùngnỗvềtrithức.Khodữliệu,nguồntrithứccủanhânloạicũngtrởnênđồsộ,vôtậnlà mchovấnđềkhaitháccácnguồntrithứcđóngàycàngtrởnênnóngbỏngvàđặtratháchthứ clớnchonềncôngnghệthôngtinthếgiới.

Đốivớimộtdoanhnghiệpthôngtin diđộngviệcpháttriểnthuêbao mới đểkiếmtìmlợinhuậnvàothờiđiểmhiệntạiđãkhôngcònđemlạihiệuquả.Thayvàođólà mộtphƣơngánkinhdoanhtiếnđếnpháttriểnchấtlƣợngdịchvụ vàcungcấpthêmnhiềudịchvụgiátrịgiatăng.Tuynhiêncácdịchvụtruyềnthốngnhƣtho ại,nhắntinvẫncóthểđemlạinguồnlợinhuậncaohơnnếukíchthíchđƣợcnhucầusửdụng củakháchhàng. Để thực hiện đƣợc điều đó, các doanh nghiệp phải không ngừng giữ vững đƣợc khách hàng hiện có mà còn phải đƣa ra đƣợc các chiến lƣợc phát triển kinh doanh dài hạn, phân loại đƣợc các nhóm khách hàng đang sử dụng để từ đó có chính sách phân khúc thị trƣờng hợp lý. Vì vậy, em dựa vào thực trạng nhƣ trên và kết hợp với kỹ thuật phân cụm trong khai phá dữ liệu để thực hiện đề tài: “Một số kỹ thuật phân cụm dữ liệu và ứng dụng phân loại khách hàng sử dụng dịch vụ Viễn thông” Bố cục luận văn gồm 3 chương: Chƣơng 1: Trình bày một cách tổng quan các kiến thức cơ bản về khai phá dữ liệu và phát hiện tri thức, các kỹ thuật phân cụm trong khai phá dữ liệu. Chƣơng 2: Giới thiệu một số dữ liệu phân cụm phổ biến thƣờng đƣợc sử dụng trong khai phá dữ liệu và phát hiện tri thức.

Chƣơng 3: Sử dụng kỹ thuật phân cụm để ứng dụng vào phân loại khách hàng sử dụng dịch vụ viễn thông. Trong chƣơng này cũng trình bày chƣơng trình mô phỏng áp dụng kỹ thuật phân cụm để phân loại sử dụng dịch vụ Viễn thông. Phần kết luận của luận văn tổng kết lại những vấn đề đã nghiên cứu, đánh giá kết quả nghiên cứu, hƣớng phát triển của đề tài. CHƢƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU 10 1.

Khai phá dữ liệu và phát hiện tri thức 1. Khai phá dữ liệu Cuốithậpkỷ80củathếkỷ20,sựpháttriểnrộngkhắpcủacácCSDLđãtạorasựbùngn ổthôngtintrêntoàncầu,vàothờigiannàyngƣờitabắtđầuđềcậpđếnkháiniệmkhủnghoản gtrongviệcphântíchdữliệutácnghiệpđểcungcấpthôngtinvớiyêucầuchấtlƣợngngàyc àngcaochongƣờilàmquyếtđịnhtrongcáctổchứcchínhphủ, tàichính, thƣơngmại,khoahọc,… ĐúngnhƣJohnNaisbettđãcảnhbáo“Chúngtađangchìmngậptrongdữliệumàvẫn đóitrithức”.Lƣợngdữliệukhổnglồnàythựcsựlàmộtnguồntàinguyêncónhiềugiátrịbởi thôngtinlàyếutốthenchốtphụcvụchomọihoạtđộngquảnlý,kinhdoanh,pháttriểnsảnxu ấtvàdịchvụ,…nógiúpngƣờiđiềuhànhvàquảnlýcónhữnghiểubiếtvềmôitrƣờngvàtiếnt rìnhhoạtđộngcủatổchứcmìnhtrƣớckhiraquyếtđịnhđểtác độngđếnquátrìnhhoạtđộngnhằm đạtđƣợc các mục tiêu mộtcáchhiệuquả vàbềnvững. KPDLlàmộtlĩnhvựcmớiđƣợcnghiêncứu,nhằm tựđộngkhaithácthôngtin,trithứcmớihữuích,tiềmẩntừnhữngCSDLlớnchocácđơnvị, tổchức,doanhnghiệp,….từđólàmthúcđẩykhảnăngsảnxuất,kinhdoanh,cạnhtranhch ocácđơnvị,tổchứcnày.Cáckếtquảnghiêncứukhoahọccùngnhữngứngdụngthànhcôn gtrongKDDchothấyKPDLlàmộtlĩnhvựcpháttriểnbềnvững,manglạinhiềulợiíchvàc ónhiềutriểnvọng, đồngthờicóƣuthế hơnhẵnsovớicáccôngcụtìmkiếmphântíchdữliệutruyềnthống.Hiệnnay,KPDLđãứng dụngngàycàngrộngrãitrongcáclĩnhvựcnhƣthƣơngmại,tàichính,yhọc, viễnthông,tin– sinh,….CáckỹthuậtchínhđƣợcápdụngtronglĩnhvựcKPDLphầnlớnđƣợcthừakếtừlĩn hvựcCSDL,họcmáy,trítuệnhântạo,lýthuyếtthôngtin,xácsuấtthốngkê vàtínhtoánhiệunăngcao,. NhƣvậytacóthểkháiquáthóakháiniệmKPDLlàmộtquátrìnhtìmkiếm, pháthiệncáctrithứcmới, hữuích, tiềmẩn trongCSDL lớn.

11 KDDlàmụctiêuchínhcủaKPDL,dovậyhaikháiniệmKPDLvàKDDđƣợccácnhà khoahọctrênhailĩnhvựcxemlàtƣơngđƣơngvớinhau.Thếnhƣngnếuphânchiamộtcách chitiếtthìKPDLlàmộtbƣớcchínhtrongquátrìnhKDD. Quá trình khám phá tri thức Quátrìnhkháphátrithứccóthểchiathành5bƣớcnhƣ sau: Hình 1.1 Quá trình khám phá tri thức QuátrìnhKPDL có thểphânthànhcác giaiđoạnsau [6]: Tríchchọndữliệu:Đâylà bƣớctríchchọnnhữngtậpdữliệu cần đƣợc khaiphá từcáctậpdữliệulớnbanđầutheomộtsốtiêuchínhấtđịnh. Tiềnxửlýdữliệu:Đâylàbƣớclàmsạchdữliệu(xửlýnhữngdữliệukhôngđầyđủ,nh iễu,khôngnhấtquán,.),rútgọndữliệu(sửdụnghàmnhómvàtínhtổng,cácphƣơngpháp néndữliệu,sửdụnghistograms,lấymẫu,.),rờirạchóadữliệu(rờirạchóadựavàohistogr ams,dựavàoentropy,dựavàophânkhoảng,.Saubƣớcnày,dữliệusẽnhấtquán,đầyđủ ,đƣợcrútgọnvàđƣợcrờirạchóa. Biếnđổidữliệu:Đâylàbƣớcchuẩnhóavàlàmmịndữliệuđểđƣadữliệuvề dạngthuậnlợinhấtnhằmphụcvụquátrìnhkhaiphá ởbƣớcsau.

Khaiphádữliệu:Đâylàbƣớcápdụngnhữngkỹthuậtphântích(nhƣcáckỹthuậtcủ ahọcmáy)nhằmđểkhaithácdữliệu,tríchchọnđƣợcnhữngmẫuthôngtin,nhữngmốiliên hệđặcbiệttrongdữliệu.Đâyđƣợcxemlàbƣớcquantrọng vàtốnnhiềuthờigiannhấtcủatoànquá trìnhKDD. 12 Đánhgiávàbiểudiễntrithức:Nhữngmẫuthôngtinvàmốiliênhệtrongdữliệuđãđ ƣợckhámpháởbƣớctrênđƣợcbiếnđổivàbiểudiễnởmộtdạnggầngũivớingƣờisửdụngn hƣđồthị,cây,bảngbiểu,luật,.Đồngthờibƣớcnàycũng đánhgiánhữngtrithứckhámphá đƣợc theonhữngtiêuchínhấtđịnh. Khai phá dữ liệu và các lĩnh vực liên quan KPDLlàmộtlĩnhvựcliênquantớithốngkê,họcmáy,CSDL,thuậttoán,tínhtoáns ongsong,thunhậntrithứctừhệchuyêngiavàdữliệutrừutƣợng.Đặctrƣngcủahệthốngkh ámphátrithứclànhờvàocácphƣơngpháp,thuậttoánvà kỹthuậttừnhữnglĩnhvựckhácnhauđểKPDL. LĩnhvựchọcmáyvànhậndạngmẫutrongKDDnghiêncứucáclýthuyếtvàthuậtto áncủahệthốngđểtríchracácmẫuvàmôhìnhtừdữliệulớn.KDDtậptrungvàoviệcmởrộn gcáclýthuyếtvàthuậttoánchocácvấnđềtìmracácmẫuđặcbiệt(hữuích hoặc cóthểrútra trithứcquantrọng)trongCSDL lớn.

Ngoàira,KDDcónhiềuđiểmchungvớithốngkê,đặcbiệtlàphântíchdữliệuthăm dò(ExploratoryDataAnalysis- EDA).HệthốngKDDthƣờnggắnnhữngthủtụcthốngkêchomôhìnhdữliệuvàtiếntrìnhn hiễutrongkhámphátrithứcnóichung. Mộtlĩnhvựcliênquankháclàphântíchkhodữliệu.Phƣơngphápphổbiếnđểphânt íchkhodữliệulàOLAP(On-LineAnalyticalProcessing).CáccôngcụOLAP tậptrungvàophântíchdữ liệuđa chiều. Các kỹ thuật áp dụng trong khai phá dữ liệu KDDlàmộtlĩnhvựcliênngành,baogồm:Tổchứcdữliệu,họcmáy,trítuệnhântạo vàcác khoahọckhác. Sựkếthợpnàycó thểđƣợcdiễntả nhƣsau: 13 Hình 1.2 Các lĩnh vực liên quan đến khám phá tri thức Đứngtrênquanđiểmcủahọc máy,thìcáckỹthuậttrongKPDL,baogồm: Họccógiámsát:LàquátrìnhgánnhãnlớpchocácphầntửtrongCSDLdựatrênmột tậpcácvídụhuấn luyệnvà cácthôngtinvề nhãnlớpđãbiết.

Họckhôngcógiámsát:Làquátrìnhphânchiamộttậpdữliệuthànhcáclớphaycụm dữliệutƣơngtựnhaumàchƣabiếttrƣớccácthôngtinvềlớphaytậpcác vídụhuấnluyện. Họcnửagiám sát:Làquátrìnhphânchiamộttậpdữliệuthành các lớpdựatrênmộttậpnhỏcácvídụhuấnluyệnvàcácthôngtinvềmộtsốnhãnlớpđãbiếttrƣớ c. + Nếucăncứvàolớpcácbàitoáncầngiảiquyết,thìKPDLbaogồmcáckỹthuậtápdụngsau [6]: Phânlớpvàdựbáo:Xếpmộtđốitƣợngvàomộttrongnhữnglớpđãbiếttrƣớc.Vídụ nhƣphânlớpcácdữliệubệnhnhântronghồsơbệnhán.Hƣớngtiếpcậnnàythƣờngsửdụn gmộtsốkỹthuậtcủahọcmáynhƣcâyquyếtđịnh,mạngnơronnhântạo,. Phânlớpvàdự báo cònđƣợcgọilàhọccógiámsát.

Luậtkếthợp:Làdạngluậtbiểudiễntrithứcởdạngkháđơngiản.Vídụ:“60% nữgiớivàosiêuthị nếumua phấnthìcótới80% trongsốhọ sẽmuathêmson”.Luậtkếthợpđƣợcứngdụngnhiềutronglĩnhvựckinhdoanh,yhọc,tin- sinh, tàichínhvà thịtrƣờngchứngkhoán,. 14 Phântíchchuỗitheothờigian:Tƣơngtựnhƣkhaipháluậtkếthợpnhƣngcóthêmtí nhthứtựvàtínhthờigian.Hƣớngtiếpcậnnàyđƣợcứngdụngnhiềutronglĩnhvựctàichính và thịtrƣờngchứngkhoánvìnócótínhdự báocao. Phâncụm:Xếpcácđốitƣợngtheotừngcụmdữliệutựnhiên.Phâncụmcònđƣợcgọ ilàhọckhôngcógiámsát. Môtảvàtómtắtkháiniệm:Thiênvềmôtả,tổnghợpvàtómtắtkháiniệm,vídụ nhƣtómtắtvăn bản.

DoKPDL đƣợc ứngdụngrộngrãinênnócóthểlàmviệcvớirấtnhiềukiểudữliệukhácnhau.Sauđâylàmột sốdạngdữliệuđiểnhình:Dữliệuquanhệ,dữliệuđachiều,dữliệudạnggiaodịch,dữliệuqu anhệ- hƣớngđốitƣợng,dữliệukhônggianvàthờigian,dữliệuchuỗithờigian,dữliệuđaphƣơng tiện,dữliệuvănbảnvà Web,… 1. Ứng dụng khai phá dữ liệu KPDLlàmộtlĩnhvựcđƣợcquantâmvàứngdụngrộngrãi.Mộtsốứngdụngđiểnhì nhtrongKPDLcóthểliệtkênhƣ sau:Phântíchdữliệuvàhỗtrợraquyếtđịnh,điềutrịy học,KPVB,khaipháWeb,tin-sinh,tàichínhvàthịtrƣờngchứngkhoán, bảohiểm,. Thƣơngmại:Nhƣphântíchdữliệubánhàngvàthịtrƣờng,phântíchđầutƣ, pháthiệngianlận,chứngthựchóakháchhàng, dự báoxuhƣớngpháttriển,. Thôngtinsảnxuất:Điềukhiển,lậpkếhoạch,hệthốngquảnlý,phântíchthửnghiệ m,.

Thôngtinkhoahọc:Dự báothờitiết, bảolụt, độngđất,tinsinhhọc,.HiệnnaycáchệquảntrịCSDLđãtíchhợpnhữngmodulđểKPDL nhƣSQLServer,Oracle,đếnnăm2007MicrosoftđãcungcấpsẵncôngcụKPDLtíchhợp trongcả MS-Word, MS-Excel,.3 Trực quan hóa kết quả KPDL trong Oracle 1. Kỹ thuật phân cụm trong khai phá dữ liệu 1. Tổng quan về kỹ thuật phân cụm MụcđíchchínhcủaPCDLnhằmkhámphácấutrúccủamẫudữliệuđểthànhlậpcá cnhómdữliệutừtậpdữliệulớn,theođónóchophépngƣờitađisâuvàophântíchvànghiên cứuchotừngcụmdữliệunàynhằmkhámphávàtìmkiếmcácthôngtintiềmẩn,hữuíchph ụcvụchoviệcraquyếtđịnh.Vídụ“nhómcáckháchhàngtrongCSDLngânhàngcóvốnc ácđầutưvàobấtđộngsảncao”…Nhƣvậy,PCDLlàmộtphƣơngphápxửlýthôngtinqua ntrọngvàphổbiến,nónhằmkhámphámốiliênhệgiữacácmẫudữliệubằngcáchtổchức chúngthànhcáccụm. TacóthểkháiquáthóakháiniệmPCDL [6][10]:PCDLlàmộtkỹthuậttrongKPDL,nhằmtìmkiếm,pháthiệncáccụm,cácmẫud ữliệutựnhiên,tiềmẩn,quantrọngtrongtậpdữliệulớntừđócungcấpthôngtin,trithứchữ uíchchoviệc raquyếtđịnh.

Nhƣvậy,PCDLlàquátrìnhphânchiamộttậpdữliệubanđầuthànhcáccụmdữ liệusaochocácphầntửtrongmộtcụm"tƣơngtự"vớinhau vàcácphầntử trong các cụmkhácnhausẽ "phitƣơngtự" vớinhau.Sốcác cụmdữ liệuđƣợc 16 phânởđâycóthểđƣợcxácđịnhtrƣớctheokinhnghiệmhoặccóthểđƣợctựđộngxácđịnhc ủaphƣơngphápphâncụm. Độtƣơngtựđƣợcxácđịnhdựatrêngiátrịcácthuộctínhmôtảđốitƣợng.Thôngthƣ ờng,phépđokhoảngcáchthƣờngđƣợcsửdụngđểđánhgiáđộtƣơngtựhayphitƣơngtự. Ta có thểminhhoạvấnđềphâncụmnhƣ hìnhsauđây: Hình 1.4 Mô phỏng sự PCDL Tronghìnhtrên,saukhiphâncụmtathuđƣợcbốncụmtrongđócácphầntử"tươngt ự"thìđƣợcxếpvàomộtcụm,cácphầntử"phitươngtự"thìchúngthuộc vềcác cụmkhác nhau. TrongPCDLkháiniệm,haihoặcnhiềuđốitƣợngcùngđƣợcxếpvàomộtcụmnếuc húngcóchungmộtđịnhnghĩavềkháiniệmhoặcchúngxấpxỉvớicác kháiniệmmôtả chotrƣớc.

Nhƣ vậy, PCDL khôngsử dụng độđo“tươngtự”nhƣđã trìnhbàyở trên. Tronghọcmáy,PCDLđƣợcxemlàvấnđềhọckhôngcógiámsát,vìnóphảigiảiquy ếtvấnđềtìmmộtcấutrúctrongtậphợpdữ liệuchƣabiếttrƣớccácthôngtinvềlớphaycácthôngtinvềtậphuấnluyện.Trongnhiềutrƣ ờnghợp,nếuphânlớpđƣợcxemlàvấnđềhọccógiámsátthìPCDLlàmộtbƣớctrongphânl ớpdữliệu,PCDL sẽkhởitạocáclớpchophânlớpbằng cáchxác địnhcácnhãnchocácnhómdữ liệu. MộtvấnđềthƣờnggặptrongPCDLlàhầuhếtcácdữliệucầnchophâncụmđềucóc hứadữliệu"nhiễu"doquátrìnhthuthậpthiếuchínhxáchoặcthiếuđầyđủ,vìvậycầnphảix âydựngchiếnlƣợcchobƣớctiềnxửlýdữliệunhằmkhắcphụchoặcloạibỏ"nhiễu"trƣớck hibƣớcvàogiaiđoạnphântích PCDL."Nhiễu"ởđâycóthểlàcácđốitƣợngdữliệukhôngchínhxáchoặccácđốitƣợngdữ liệukhuyếtthiếuthôngtinvềmộtsốthuộctính.Mộttrongcáckỹthuậtxửlýnhiễuphổbiếnl 17 àviệcthaythếgiátrịcủacácthuộctínhcủađốitƣợng"nhiễu"bằnggiátrịthuộctínhtƣơng ứngcủađốitƣợngdữ liệugầnnhất. Ngoàira,dòtìmphầntửngoạilailàmộttrongnhữnghƣớngnghiêncứuquantrọngt rongPCDL,chứcnăngcủanólàxácđịnhmộtnhómnhỏcácđốitƣợngdữ liệu"khácthường"sovớicác dữliệukháctrongCSDL-tứclàcác đốitƣợngdữliệukhôngtuântheocáchànhvihoặcmôhìnhdữ liệu-nhằm tránhsựảnhhƣởngcủachúngtớiquátrìnhvàkếtquảcủaPCDL.Khámphácácphầntửngo ạilaiđãđƣợcpháttriểnvàứngdụngtrongviễnthông,dòtìmgianlậnthƣơngmại… Tómlại,PCDLlàmộtvấnđềkhóvìngƣờitaphảiđigiảiquyếtcácvấnđềconcơ bảnnhƣsau: - Biểudiễndữ liệu.

- Xây dựnghàmtínhđộtƣơngtự. - Xây dựngcáctiêuchuẩnphâncụm. - Xây dựngmôhìnhchocấutrúccụmdữliệu. - Xây dựngthuậttoán phâncụmvà xác lậpcác điềukiệnkhởitạo.

- Xây dựngcácthủtục biểudiễnvà đánhgiákếtquảphâncụm. Theocácnghiêncứuthìđếnnaychƣacómộtphƣơngphápphâncụmtổngquátnàoc óthểgiảiquyếttrọnvẹnchotấtcảcácdạngcấutrúccụmdữliệu.Hơnnữa,cácphƣơngpháp phâncụmcầncócáchthứcbiểudiễncấutrúccáccụmdữliệukhácnhau,vớimỗicáchthứcb iểudiễnkhácnhausẽcómộtthuậttoánphâncụmphùhợp.PCDLđanglà vấnđềmởvàkhóvìngƣờita cần phảiđigiảiquyếtnhiềuvấnđềcơbảnnhƣđãđềcậpởtrênmộtcáchtrọnvẹnvàphùhợpvớin hiềudạngdữliệukhácnhau.Đặcbiệtđốivớidữliệuhỗnhợp,đangngàycàngtăngtrƣởngk hôngngừngtrongcáchệquảntrịdữliệu,đâycũnglàmộttrongnhữngtháchthứclớntrongl ĩnhvựcKPDLtrongnhữngthậpkỷtiếptheo. Ứng dụng của phân cụm dữ liệu PCDLlàmộttrongnhữngcôngcụchínhcủaKPDLđƣợcứngdụngtrongnhiềulĩnh vựcnhƣthƣơngmạivàkhoahọc.CáckỹthuậtPCDLđãđƣợcápdụngchomộtsốứngdụng điểnhìnhtrongcác lĩnhvựcsau[10][19]: 18 Thươngmại:PCDLcóthểgiúpcácthƣơngnhânkhámpháracácnhómkháchhàng quantrọngcócácđặctrƣngtƣơngđồngnhauvàđặctảhọtừcácmẫumua bántrongCSDL kháchhàng. Sinhhọc:PCDLđƣợcsửdụngđểxácđịnhcácloạisinhvật,phânloạicácGenvớich ứcnăngtƣơngđồngvà thuđƣợccác cấutrúctrongcácmẫu.

Phântíchdữliệukhônggian:Dosựđồsộcủadữliệukhônggiannhƣdữliệuthuđƣợ ctừcáchìnhảnhchụptừvệtinh,cácthiếtbịyhọchoặchệthốngthôngtinđịalý(GIS),…là mchongƣờidùngrấtkhóđểkiểmtracácdữliệukhônggianmộtcáchchitiết.PCDLcóthểt rợgiúpngƣờidùngtựđộngphântíchvàxửlýcácdữliêukhônggiannhƣnhậndạngvàchiết xuấtcácđặctínhhoặc các mẫudữ liệuquantâmcó thể tồntạitrongCSDL không gian. Lập quy hoạchđôthị:Nhậndạngcác nhómnhàtheokiểuvà vịtríđịa lý,…nhằmcungcấpthôngtin choquyhoạchđôthị. Nghiêncứutráiđất:Phâncụmđểtheodõicáctâmđộngđấtnhằmcungcấpthôngtin chonhậndạngcácvùngnguy hiểm. Địalý:Phânlớpcácđộngvật, thựcvậtvàđƣa ra đặctrƣngcủachúng.

KhaipháWeb:PCDLcóthểkhámphácácnhómtàiliệuquantrọng,cónhiềuýnghĩ atrongmôitrƣờngWeb.CáclớptàiliệunàytrợgiúpchoviệckhámphátrithứctừdữliệuW eb, khámpháracácmẫutruycậpcủakháchhàngđặcbiệthaykhámphá ra cộngđồngWeb,… 1. Các yêu cầu kỹ thuật đối với phân cụm dữ liệu Việcxâydựng,lựachọnmộtthuậttoánphâncụmlàbƣớcthenchốtchoviệcgiảiquy ếtvấnđềphâncụm,sựlựachọnnày phụthuộcvàođặctínhdữliệucầnphâncụm,mụcđíchcủaứngdụngthựctếhoặcxácđịnhđ ộƣutiêngiữachấtlƣợngcủa cáccụmhaytốc độthựchiệnthuậttoán,… HầuhếtcácnghiêncứuvàpháttriểnthuậttoánPCDLđềunhằmthoảmãncác yêucầu cơbảnsau [6][10]: Cókhảnăngmởrộng:Mộtsốthuậttoáncóthểứngdụngtốtchotậpdữliệunhỏ(kho ảng200bảnghidữliệu)nhƣngkhônghiệuquảkhiápdụngchotậpdữliệulớn(khoảng1triệ ubảnghi). 19 Thíchnghivớicáckiểudữliệukhácnhau:Thuậttoáncóthểápdụnghiệuquảchoviệ cphâncụmcáctậpdữliệuvớinhiềukiểudữliệukhácnhaunhƣdữliệukiểusố,kiểunhịphâ n,dữliệuđịnhdanh,hạngmục,. Khámpháracáccụmvớihìnhthùbấtkỳ:DohầuhếtcácCSDLcóchứanhiềucụmd ữliệuvớicáchìnhthùkhácnhaunhƣ:hìnhlõm,hìnhcầu,hìnhque,…Vìvậy,đểkhámphá đƣợccáccụmcótínhtựnhiênthìcácthuậttoánphâncụmcần phảicókhảnăngkhámphá racác cụmdữ liệucóhìnhthùbấtkỳ.

Tốithiểulượngtrithứccầnchoxácđịnhcácthamsốvào:Docácgiátrịđầuvàothƣờ ngảnhhƣởngrấtlớnđếnthuậttoánphâncụmvàrấtphứctạpđểxácđịnhcác giátrịvàothíchhợpđốivớicácCSDL lớn. Ítnhạycảmvớithứtựcủadữliệuvào:Cùngmộttậpdữliệu,khiđƣavàoxửlýchothu ậttoánPCDLvớicácthứtựvàocủacácđốitƣợngdữliệuởcáclầnthựchiệnkhácnhauthìkh ôngảnhhƣởnglớnđếnkếtquảphâncụm. Khảnăngthíchnghivớidữliệunhiễucao:HầuhếtcácdữliệuphâncụmtrongKPD Lđềuchứađựngcácdữliệulỗi,dữliệukhôngđầyđủ,dữliệurác.Thuậttoánphâncụmkhôn gnhữnghiệuquảđốivớicácdữliệunhiễumàcòntránh dẫnđếnchấtlƣợngphâncụmthấpdonhạycảmvớinhiễu. Ítnhạycảmvớicácthamsốđầuvào:Nghĩalàgiátrịcủacácthamsốđầuvàokhácnh auítgâyra các thayđổi lớnđốivớikếtquảphâncụm.

Thíchnghivớidữliệuđachiều:Thuậttoáncókhảnăngápdụnghiệuquảchodữliệu cósốchiềukhácnhau. Dễhiểu, dễ càiđặtvàkhảthi. CácyêucầunàyđồngthờilàcáctiêuchíđểđánhgiáhiệuquảcủacácphƣơngphápP CDL,đâylànhữngtháchthứcchocácnhànghiêncứutronglĩnhvựcPCDL. Tổng kết chƣơng 1 Trong chƣơng1trìnhbàynhữngkiếnthứccơbảnvềkhaiphádữliệuvàkhámphátrithứctrongCS DL,cáckỹthuậtápdụngtrongkhaiphádữliệu,nhữngchứcnăngchính,ứngdụngcủanótr ongxã hội,.

20 Chƣơngnàycũngtrìnhbàymộthƣớngnghiêncứuvàứngdụngtrongkhaiphádữli ệulàphâncụmdữliệu,gồmtổngquanvềkỹthuậtphâncụm,cácứngdụngcủaphâncụm,cá cyêucầuđốivớikỹthuậtphâncụm,cáckiểudữliệuvàđộđotƣơngtự,. CHƢƠNG 2: MỘT SỐ KỸ THUẬT PHÂN CỤM DỮ LIỆU CáckỹthuậtápdụngđểgiảiquyếtvấnđềPCDLđềuhƣớngtớihaimụctiêuchung:C hấtlƣợngcủacáccụmkhámpháđƣợcvàtốcđộthựchiệncủathuậttoán.Tuynhiên,cáckỹt huậtPCDLcóthểđƣợcphânloạithànhmộtsốloạicơbảndƣatrêncácphƣơngpháptiếpcậ nnhƣsau [6][13]: 2. Phâncụmphânhoạch Ýtƣởngchínhcủakỹthuậtnàylàphânmộttậpdữliệucónphầntửchotrƣớcthànhkn hómdữliệusaochomỗiphầntửdữliệuchỉthuộcvềmộtnhómdữliệuvàmỗinhómdữliệuc ótốithiểuítnhấtmộtphầntửdữliệu.Cácthuậttoánphânhoạchcóđộphứctạprấtlớnkhixá cđịnhnghiệmtốiƣutoàncụcchovấnđềPCDL,vìnóphảitìmkiếmtấtcảcáccáchphânhoạ chcóthểđƣợc.Chínhvìvậy,trênthựctế ngƣờita thƣờng đi tìmgiải pháptốiƣucục bộchovấnđềnàybằngcáchsửdụngmộthàmtiêuchuẩnđểđánhgiáchấtlƣợngcủacáccụ mcũngnhƣđểhƣớngdẫnchoquátrìnhtìmkiếmphânhoạchdữliệu.Vớichiếnlƣợcnày,th ôngthƣờngngƣờitabắtđầukhởitạomộtphânhoạchbanđầuchotậpdữliệutheophépngẫu 21 nhiênhoặctheoheuristicvàliêntụctinhchỉnhnóchođếnkhithuđƣợcmộtphânhoạchmo ngmuốn,thoảmãncácđiềukiệnràngbuộcchotrƣớc.Cácthuậttoánphâncụmphânhoạch cốgắngcảitiếntiêuchuẩnphâncụmbằngcáchtínhcácgiátrịđođộtƣơng tựgiữacácđốitƣợngdữliệuvàsắpxếpcácgiátrịnày,sauđóthuậttoánlựachọnmộtgiátrịtr ongdãysắpxếpsaochohàmtiêuchuẩnđạtgiátrịtốithiểu.Nhƣvậy,ýtƣởngchínhcủathuậ ttoánphâncụmphânhoạchtốiƣucụcbộlàsửdụngchiếnlƣợcănthamđểtìmkiếmnghiệm. Lớpcácthuậttoánphâncụmphânhoạchbaogồmcácthuậttoánđềxuấtđầutiêntro nglĩnhvựcKPDLcũnglàcácthuậttoánđƣợcápdụngnhiềutrongthựctếnhƣk- means,PAM,CLARA,CLARANS.Sauđâylàmộtsốthuậttoánkinhđiểnđƣợckế thừa sử dụngrộngrãi.1 Thuật toán k-means Thuật toán phân cụm k-means do MacQueen đề xuất trong lĩnh vực thống kê năm 1967, mục đích của thuật toán k-means là sinh ra k cụm dữ liệu {C1, C2,., Ck) từ một tập dữ liệu ban đầu gồm n đối tƣợng trong không gian d chiều k 2 Xi =(xi1,xi2,.xid) (i = 1,n), sao cho hàm tiêu chuẩn: x Ci D 2 ( x mi ) đạt giá trị i 1 tối thiểu.

Trong đó : mi là trọng tâm của cụm Ci,D là khoảng cạh giữa hai đối tƣợng. Trọng tâm của một cụm là một vector, trong đó giá trị của mỗi phần tử của nó là trung bình cộng 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, tập CSDL gồm n phần tử và tham số đầu ra của thuật toán là các trọng tâm của các cụm dữ liệu. Độ đo khoảng cách D giữa các đối tƣợng dữ liệu thƣờng đƣợc sử dụng dụng là khoảng cách Euclide, bởi 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 các quan điểm của ngƣời dùng. Thuật toán k-means bao gồm các bƣớc cơ bản nhƣ sau: INPUT: Một CSDL gồm n đối tƣợng và số các cụm k. OUTPUT: Các cụm Ci (i=l,.,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 mj (j=1 .) là trọng tâm ban đầu của k cụm từ tập dữ liệu 22 theo kinh nghiệm).

(việc lựa chọn này có thể là ngẫu nhiên hoặc Hình 2.1 Thuật toán k- means Thuật toán k-means đƣợc chứng minh là hội tụ và có độ phức tạp tính toán là: 0((n k d ) T f l o p ). Trong đó: n là số đối tƣợng dữ liệu, k là số cụm dữ liệu, d là số chiều, là số vòng lặp, T f l o p là thời gian đề thực hiện một phép tính cơ sở nhƣ phép tính nhân, chia, .Nhƣ vậy, do k-means phân tích phân cụm đơn giản nên có thể áp dụng đối với tập dữ liệu lớn. Tuy nhiên, nhƣợc điểm của k- means là chỉ áp dụng với dữ liệu có thuộc tính số và khám phá ra các cụm có dạng hình cầu, k-means còn rất nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu. Hình sau diễn tả môi phỏng về một số hình dạng cụm dữ liệu khám phá đƣợc bởi k-means: 23 Hình 2.2 Hình dạng cụm dữ liệu được khám phá bởi k - means Hơn nữa, chất lƣợng PCDL của thuật toán k-means phụ thuộc nhiều vào các tham số đầu vào nhƣ: số cụm k và k trọng tâm khởi tạo ban đầu.

Trong trƣờng hợp, các trọng tâm khởi tạo ban đầu mà quá lệch so với các trọng tâm cụm tự nhiên thì kết quả phân cụm của k-means là rất thấp, nghĩa là các cụm dữ liệu đƣợc khám phá rất lệch so với các cụm trong thực tế. Trên thực tế ngƣời ta chƣa cỏ một giải pháp tối ƣu nào để chọn các tham số đầu vào, giải pháp thƣờng đƣợc sử dụng nhất là thử nghiệm với các giá trị đầu vào k khác nhau rồi sau đó chọn giải pháp tốt nhất. Đến nay, đã có rất nhiều thuật toán kế thừa tƣ tƣởng của thuật toán k- means áp dụng trong KPDL để giải quyết tập dữ liệu có kích thƣớc rất lớn đang đƣợc áp dụng rất hiệu quả và phồ biến nhƣ thuật toán k-medoid, PAM, CLARA, CLARANS, k- prototypes, .2 Thuật toán PAM Thuật toán PAM (Partitioning Around Medoids) đƣợc Kaufman và Rousseeuw đề xuất 1987, là thuật toán mở rộng của thuật toán k-means, nhằm có khả năng xử lý hiệu quả đối với dữ liệu nhiễu hoặc các phần tử ngoại lai. Thay vì sử dụng các trọng tâm nhƣ k-means, PAM sử dụng các đối tƣợng medoid để biểu diễn cho các cụm dữ liệu, một đối tƣợng medoid là đối tƣợng đặt tại vị trí trung tâm nhất bên trong của mỗi cụm.

Vì vậy, các đối tƣợng medoid ít bị ảnh hƣởng của các đối tƣợng ở rất xa trung tâm, trong khi đó các trọng tâm của thuật toán k -means lại rất bị tác động bởi các điểm xa trung tâm này. Ban đầu, PAM khởi tạo k đối tƣợng medoid và phân phối các đối tƣợng còn lại vào các cụm với các đối tƣợng medoid đại diện tƣơng ứng sao cho chúng tƣơng tự với đối tƣợng medoid trong cụm nhất. Để xác định các medoid, PAM bắt đầu bằng cách lựa chọn k đối tƣợng medoid bất kỳ. Sau mỗi bƣớc thực hiện, PAM cố gắng hoán chuyển giữa đối tƣợng medoid Om và một đối tƣợng Op không phải là medoid, miễn là sự hoán chuyển này nhằm cải tiến chất lƣợng của phân cụm, quá trình này kết thúc khi 24 chất lƣợng phân cụm không thay đổi.