Luận Văn Thạc Sĩ Về Phân Cụm Dữ Liệu Dựa Trên Mật Độ và Ứng Dụng

Luận văn thạc sĩ nghiên cứu hay phân cụm dữ liệu dựa trên mật độ và ứng dụng, khảo sát thực trạng, phân tích nguyên nhân, đề xuất giải pháp cải thiện thực tiễn.

• Tác giả: Vũ Ngọc Thanh
• Người hướng dẫn: Ts. Nguyễn Huy Đức
• Trường học: Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Phân Cụm Dữ Liệu Dựa Trên Mật Độ và Ứng Dụng
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CÁM ƠN
• 1. CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM DỮ LIỆU
• 1.1. Tổng quan về khai phá dữ liệu
• 1.1.1. Khái niệm
• 1.1.2. Tiến trình khai phá dữ liệu
• 1.1.3. Các mô hình khai phá dữ liệu
• 1.1.4. Các hướng tiếp cận và kỹ thuật sử dụng trong khai phá dữ liệu
• 1.1.5. Các dạng dữ liệu có thể khai phá
• 1.1.6. Các ứng dụng của khai phá dữ liệu
• 1.2. Tổng quan về phân cụm dữ liệu
• 1.2.1. Khái niệm
• 1.2.2. Ví dụ về phân cụm dữ liệu
• 1.2.3. Các mục tiêu của phân cụm dữ liệu
• 2. CHƯƠNG 2: PHÂN CỤM DỮ LIỆU DỰA TRÊN MẬT ĐỘ
• 2.1. Thuật toán DBSCAN
• 2.2. Thuật toán DBRS
• 2.3. Thuật toán OPTICS
• 2.4. Thuật toán DENCLUDE
• 3. CHƯƠNG 3: XÂY DỰNG CHƯƠNG TRÌNH THỰC NGHIỆM
• 3.1. Ý tưởng bài toán
• 3.2. Nguồn dữ liệu đầu vào
• 3.3. Phương pháp giải quyết bài toán
• 3.4. Kết quả thực nghiệm
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Phân Cụm Dữ Liệu Dựa Trên Mật Độ

Phân cụm dữ liệu dựa trên mật độ là một kỹ thuật quan trọng trong khai phá dữ liệu. Kỹ thuật này giúp xác định các cụm dữ liệu tự nhiên trong một tập dữ liệu lớn. Phân cụm không chỉ đơn thuần là nhóm các đối tượng mà còn giúp phát hiện các mẫu và xu hướng trong dữ liệu. Việc áp dụng phương pháp này mang lại nhiều lợi ích cho các lĩnh vực như kinh tế, y tế và nghiên cứu khoa học.

1.1. Khái Niệm Về Phân Cụm Dữ Liệu

Phân cụm dữ liệu là quá trình tổ chức các đối tượng thành từng nhóm mà các đối tượng trong mỗi nhóm đều tương tự nhau. Kỹ thuật này giúp đơn giản hóa dữ liệu và làm nổi bật các đặc điểm quan trọng.

1.2. Lịch Sử Phát Triển Của Phân Cụm Dữ Liệu

Phân cụm dữ liệu đã phát triển từ những năm 1960 và trở thành một phần quan trọng trong khai phá dữ liệu. Các thuật toán như K-means và DBSCAN đã được phát triển để cải thiện hiệu quả phân cụm.

II. Vấn Đề và Thách Thức Trong Phân Cụm Dữ Liệu

Mặc dù phân cụm dữ liệu mang lại nhiều lợi ích, nhưng cũng tồn tại nhiều thách thức. Các vấn đề như xác định số lượng cụm, lựa chọn thuật toán phù hợp và xử lý dữ liệu không đồng nhất là những khó khăn thường gặp. Việc hiểu rõ các thách thức này là cần thiết để áp dụng hiệu quả các phương pháp phân cụm.

2.1. Xác Định Số Lượng Cụm

Một trong những thách thức lớn nhất là xác định số lượng cụm cần thiết cho phân tích. Việc này thường phụ thuộc vào bản chất của dữ liệu và mục tiêu phân tích.

2.2. Chọn Thuật Toán Phù Hợp

Có nhiều thuật toán phân cụm khác nhau, mỗi thuật toán có ưu và nhược điểm riêng. Việc lựa chọn thuật toán phù hợp với loại dữ liệu và mục tiêu phân tích là rất quan trọng.

III. Phương Pháp Phân Cụm Dữ Liệu Dựa Trên Mật Độ

Các phương pháp phân cụm dựa trên mật độ như DBSCAN và OPTICS đã được phát triển để giải quyết các vấn đề trong phân cụm dữ liệu. Những phương pháp này giú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ố lượng cụm phải xác định trước.

3.1. Thuật Toán DBSCAN

DBSCAN là một thuật toán phân cụm dựa trên mật độ, giúp phát hiện các cụm có hình dạng bất kỳ. Thuật toán này hoạt động bằng cách xác định các điểm có mật độ cao và nhóm chúng lại với nhau.

3.2. Thuật Toán OPTICS

OPTICS mở rộng DBSCAN bằng cách tạo ra một thứ tự phân cụm cho các điểm dữ liệu. Điều này cho phép phân tích các cụm có mật độ khác nhau mà không cần xác định số lượng cụm trước.

IV. Ứng Dụng Thực Tiễn Của Phân Cụm Dữ Liệu Dựa Trên Mật Độ

Phân cụm dữ liệu dựa trên mật độ đã được áp dụng rộng rãi trong nhiều lĩnh vực như y tế, tài chính và marketing. Việc phân tích dữ liệu giúp các tổ chức đưa ra quyết định chính xác hơn và tối ưu hóa quy trình làm việc.

4.1. Ứng Dụng Trong Y Tế

Trong y tế, phân cụm dữ liệu giúp phân tích các mẫu bệnh tật và xác định các nhóm bệnh nhân có đặc điểm tương tự, từ đó cải thiện chất lượng điều trị.

4.2. Ứng Dụng Trong Marketing

Trong marketing, phân cụm giúp xác định các nhóm khách hàng tiềm năng, từ đó tối ưu hóa chiến lược tiếp thị và tăng cường hiệu quả bán hàng.

V. Kết Luận và Tương Lai Của Phân Cụm Dữ Liệu Dựa Trên Mật Độ

Phân cụm dữ liệu dựa trên mật độ là một công cụ mạnh mẽ trong khai phá dữ liệu. Tương lai của phương pháp này hứa hẹn sẽ tiếp tục phát triển với sự ra đời của các thuật toán mới và cải tiến trong công nghệ xử lý dữ liệu lớn.

5.1. Xu Hướng Nghiên Cứu Tương Lai

Nghiên cứu trong lĩnh vực phân cụm dữ liệu sẽ tiếp tục tập trung vào việc cải thiện độ chính xác và hiệu suất của các thuật toán hiện có.

5.2. Tích Hợp Với Công Nghệ Mới

Việc tích hợp phân cụm dữ liệu với các công nghệ mới như trí tuệ nhân tạo và học máy sẽ mở ra nhiều cơ hội mới cho phân tích dữ liệu.

Nội dung chính

Tổng quan nghiên cứu

Sự phát triển mạnh mẽ của công nghệ thông tin đã thúc đẩy sự hình thành của hàng triệu cơ sở dữ liệu với dung lượng khổng lồ từ hàng chục gigabyte đến hàng trăm terabyte trong các lĩnh vực kinh tế, y tế, viễn thám và xã hội. Trong thực tế, khoảng 80% nguồn dữ liệu thu thập được là dữ liệu không gán nhãn hoặc sở hữu cấu trúc không gian phi tuyến tính phức tạp. Tình trạng bùng nổ thông tin này đặt ra yêu cầu cấp thiết về việc phát triển các công cụ tự động hóa nhằm chuyển đổi dữ liệu thô thành tri thức hữu ích phục vụ hỗ trợ ra quyết định. Phân cụm dữ liệu, một kỹ thuật học không giám sát then chốt trong tiến trình khám phá tri thức từ cơ sở dữ liệu, đóng vai trò phân tách dữ liệu thành các nhóm tự nhiên đồng nhất. Tuy nhiên, các kỹ thuật phân hoạch truyền thống bộc lộ hạn chế lớn khi không thể xử lý hiệu quả các cụm có hình dạng bất kỳ và dễ bị sai lệch bởi dữ liệu nhiễu.

Luận văn thạc sĩ chuyên ngành Khoa học máy tính với đề tài nghiên cứu về phân cụm dữ liệu dựa trên mật độ và ứng dụng do học viên Vũ Ngọc Thanh thực hiện, dưới sự hướng dẫn khoa học của Tiến sĩ Nguyễn Huy Đức, được bảo vệ thành công năm 2016 tại Trường Đại học Công nghệ Thông tin và Truyền thông thuộc Đại học Thái Nguyên. Mục tiêu nghiên cứu tập trung làm rõ cơ sở lý thuyết khai phá dữ liệu, đánh giá chuyên sâu các giải thuật phân cụm mật độ tiêu biểu gồm DBSCAN, DBRS, OPTICS, DENCLUE, đồng thời xây dựng chương trình thực nghiệm với thuật toán DBSCAN. Luận văn khẳng định ý nghĩa thực tiễn khi nâng cao hiệu suất xử lý dữ liệu không gian, giảm độ phức tạp tính toán trung bình xuống mức tối ưu và cải thiện tốc độ xử lý nhanh hơn từ 250 đến 1.900 lần so với giải thuật phân hoạch truyền thống trên các tập dữ liệu thử nghiệm quy mô lớn.

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 vận dụng toàn diện tiến trình khám phá tri thức từ cơ sở dữ liệu chuẩn mực gồm 5 giai đoạn liên hoàn: trích chọn dữ liệu, tiền xử lý (làm sạch dữ liệu thiếu và lọc ngoại lai), chuyển đổi dữ liệu về không gian tính toán phù hợp, khai phá dữ liệu bằng thuật toán phân cụm, và đánh giá, biểu diễn tri thức. Cơ sở toán học của nghiên cứu dựa trên lý thuyết không gian metric với các độ đo khoảng cách như khoảng cách Minkowski, khoảng cách Euclidean bậc 2, khoảng cách Manhattan bậc 1 và hệ số tương đồng Jaccard dành cho dữ liệu nhị phân.

Hệ thống lý thuyết phân cụm dựa trên mật độ được thiết lập chặt chẽ thông qua các khái niệm nền tảng:

• Bán kính lân cận Epsilon (Eps): Vùng không gian bao quanh một điểm dữ liệu xác định.
• Số điểm lân cận tối thiểu (MinPts): Ngưỡng số lượng phần tử tối thiểu cần có trong vùng bán kính Eps để hình thành vùng mật độ cao.
• Điểm nòng cốt (Core point): Điểm có số lượng phần tử lân cận lớn hơn hoặc bằng MinPts.
• Điểm biên (Border point): Điểm thuộc vùng lân cận của điểm nòng cốt nhưng bản thân không đạt ngưỡng MinPts.
• Điểm nhiễu (Noise point): Điểm cô lập không thuộc lân cận của bất kỳ điểm nòng cốt nào.
• Mật độ đạt được trực tiếp và mật độ liên thông: Cơ chế kết nối các chuỗi điểm nòng cốt để mở rộng cụm có hình dạng tùy ý.

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

Nghiên cứu kết hợp phương pháp phân tích lý thuyết giải thuật với thực nghiệm mô phỏng định lượng trên máy tính. Dữ liệu đầu vào bao gồm các tập dữ liệu không gian 2 chiều mô phỏng và cơ sở dữ liệu thực nghiệm có quy mô từ 500 đến hơn 100.000 điểm dữ liệu. Phương pháp chọn mẫu ngẫu nhiên phân tầng kết hợp lấy mẫu ngẫu nhiên có kiểm soát được áp dụng nhằm kiểm tra tính ổn định của giải thuật dưới các tỷ lệ nhiễu thực tế từ 5% đến 20%.

Lý do lựa chọn thuật toán DBSCAN làm trọng tâm phân tích thực nghiệm là nhờ khả năng kết hợp xuất sắc với các cấu trúc chỉ mục không gian như cây tứ phân, cây R-tree và cây R*-tree. Nhờ cấu trúc này, chi phí truy vấn lân cận giảm mạnh từ bậc tuyến tính xuống bậc logarit, đưa độ phức tạp thời gian trung bình của toàn bộ tiến trình phân cụm n phần tử về mức tối ưu. Về phương pháp xác định tham số, tác giả ứng dụng Heuristic đồ thị khoảng cách k-dist đã sắp xếp với hệ số k cố định bằng 4 cho dữ liệu không gian 2 chiều, giúp định vị chính xác điểm ngưỡng phân tách giữa mật độ cụm và nhiễu ngoại vi. Toàn bộ timeline nghiên cứu được tiến hành trong 12 tháng từ tháng 09/2015 đến tháng 09/2016, phân bổ qua các giai đoạn tổng quan tài liệu, thiết kế mô hình, lập trình thử nghiệm và đo lường đối sánh.

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

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

Quá trình nghiên cứu và thử nghiệm thực tế đã mang lại 4 phát hiện khoa học mang tính đột phá:

• Tối ưu hóa vượt bậc về thời gian thực thi: Thuật toán DBSCAN đạt độ phức tạp thời gian trung bình dạng gần tuyến tính O(n log n) khi ứng dụng chỉ mục không gian. Thực nghiệm đối sánh với thuật toán CLARANS trên cùng tập dữ liệu cho thấy DBSCAN hoàn thành tác vụ nhanh hơn từ 250 đến 1.900 lần, và khoảng cách hiệu năng này tiếp tục nới rộng khi kích thước cơ sở dữ liệu tăng từ 1.000 lên 100.000 đối tượng.
• Nhận diện chính xác cụm có hình dạng bất kỳ: DBSCAN đạt tỷ lệ nhận diện chính xác 100% đối với các cấu trúc cụm phi lồi, cụm hình chữ nhật, dạng dải uốn lượn hoặc các cụm lồng nhau phức tạp. Trong khi đó, các thuật toán phân hoạch như K-Means chỉ đạt độ chính xác dưới 60% do xu hướng mặc định ép các cụm về dạng hình cầu đồng kích thước.
• Khả năng lọc nhiễu tự động vượt trội: Giải thuật loại bỏ thành công trên 95% các phần tử ngoại lai ra khỏi cấu trúc cụm chính, gán nhãn chúng vào tập hợp nhiễu riêng biệt mà không làm biến dạng ranh giới phân cụm.
• Tính độc lập với thứ tự dữ liệu đầu vào: Dựa trên hai bổ đề toán học về điểm hạt nhân, kết quả phân cụm của DBSCAN hoàn toàn nhất quán và không bị phụ thuộc vào thứ tự duyệt các bản ghi trong cơ sở dữ liệu, ngoại trừ tỷ lệ sai biệt không đáng kể dưới 1% đối với các điểm biên nằm giữa hai cụm tiếp giáp.

Thảo luận kết quả

Hiệu năng ấn tượng của giải thuật bắt nguồn từ nguyên lý phát triển cụm dựa trên tính liên thông mật độ thay vì tính toán khoảng cách hình học tới một tâm cụm cố định. Trong thực tế, dữ liệu thực nghiệm có thể được trình bày trực quan thông qua đồ thị phân tán 2 chiều (scatter plot), trong đó mỗi cụm được thể hiện bằng một màu sắc riêng biệt và các điểm nhiễu được biểu diễn bằng màu độc lập. Biểu đồ đường cong 4-dist thể hiện rõ nét điểm gãy khúc, cung cấp bằng chứng trực quan giúp người vận hành xác định giá trị bán kính Eps tối ưu mà không cần trải qua hàng chục lần thử nghiệm mò mẫm.

Ngoài ra, luận văn làm rõ những cải tiến của thuật toán DBRS so với DBSCAN. DBRS kết hợp kỹ thuật lấy mẫu ngẫu nhiên và tích hợp thuộc tính phi không gian với ngưỡng độ tinh khiết MinPur, giúp phân cụm hiệu quả trên các tập dữ liệu có mật độ phân bố chênh lệch lớn và quy mô hàng trăm nghìn mẫu. Kết quả so sánh giữa 4 giải thuật DBSCAN, DBRS, K-Means và CLARANS có thể được hệ thống hóa qua bảng tổng hợp định lượng, minh chứng rằng hướng tiếp cận mật độ là giải pháp toàn diện cho các bài toán phân tích không gian phức tạp trong thực tế.

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

Nhằm tối ưu hóa hiệu quả ứng dụng của phương pháp phân cụm mật độ trong kỷ nguyên dữ liệu lớn, luận văn đề xuất 4 nhóm giải pháp cụ thể:

• Tích hợp mô hình phân cụm đa mật độ thích ứng: Các nhóm nghiên cứu tại các viện công nghệ và trường đại học cần phát triển giải thuật lai ghép giữa DBSCAN và mô hình phân cấp OPTICS hoặc DENCLUE. Giải pháp này hướng tới mục tiêu giảm tỷ lệ phân cụm sai sót xuống dưới 5% trên các cơ sở dữ liệu có độ lệch mật độ giữa các vùng vượt quá 50%, với lộ trình nghiên cứu hoàn thiện trong 12 tháng.
• Tự động hóa tiến trình xác định tham số đầu vào: Các kỹ sư khoa học dữ liệu cần xây dựng mô-đun tự động nhận diện điểm uốn trên đồ thị khoảng cách k-dist bằng các thuật toán tối ưu hóa thông minh hoặc giải thuật học tăng cường. Giải pháp này giúp cắt giảm 80% thời gian can thiệp thủ công của chuyên viên phân tích, dự kiến triển khai thử nghiệm trong 6 tháng.
• Triển khai phân tán giải thuật trên nền tảng dữ liệu lớn: Doanh nghiệp công nghệ và các trung tâm tính toán hiệu năng cao cần tái cấu trúc thuật toán DBSCAN trên nền tảng tính toán song song như Apache Spark hoặc Hadoop. Mục tiêu đặt ra là xử lý mượt mà các tập dữ liệu không gian quy mô trên 10 triệu bản ghi với thời gian phản hồi dưới 30 giây, hoàn thành trong vòng 12 đến 18 tháng.
• Chuẩn hóa quy trình tiền xử lý dữ liệu đa thuộc tính: Đơn vị quản trị hệ thống thông tin cần thiết lập quy chuẩn làm sạch dữ liệu, chuẩn hóa thuộc tính về thang đo đoạn [0, 1] và khai thác thuộc tính ghép theo mô hình DBRS nhằm nâng cao độ chính xác phân loại khách hàng và đối tượng không gian lên trên 90%, áp dụng định kỳ 3 tháng một lần.

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

Công trình nghiên cứu mang lại giá trị tham khảo chuyên sâu và tính ứng dụng cao cho 4 nhóm đối tượng chính:

• Học viên cao học và nghiên cứu sinh ngành Khoa học máy tính, Hệ thống thông tin: Nắm vững nền tảng toán học về không gian metric, quy trình KDD 5 bước và mã giả chi tiết của các giải thuật mật độ; ứng dụng trực tiếp vào việc phát triển đề tài nghiên cứu thạc sĩ và bài báo khoa học về học máy.
• Kỹ sư Khoa học Dữ liệu (Data Scientists) và AI Engineers: Vận dụng cơ chế nhận diện cụm phi tuyến tính và lọc nhiễu của DBSCAN để giải quyết các bài toán phân khúc khách hàng thương mại, phát hiện gian lận thẻ tín dụng hoặc nhận dạng bất thường trong an ninh mạng.
• Chuyên viên phân tích Hệ thống thông tin địa lý (GIS) và Quy hoạch đô thị: Khai thác khả năng phân cụm không gian hình dạng tự do để phân tích mật độ dân cư, khoanh vùng các điểm nóng giao thông, theo dõi tâm chấn động đất và đánh giá các vùng rủi ro thiên tai phục vụ quy hoạch hạ tầng.
• Giảng viên và Nhà nghiên cứu học thuật: Sử dụng cấu trúc luận văn và kết quả thực nghiệm làm tài liệu giảng dạy chuyên đề Khai phá dữ liệu và Học máy không giám sát, cung cấp các ví dụ đối sánh trực quan và bài tập thực hành thuật toán cho sinh viên đại học.

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

Thuật toán DBSCAN có điểm gì khác biệt cốt lõi so với thuật toán K-Means?

DBSCAN phân chia cụm dựa trên mật độ phần tử trong vùng bán kính Eps, tự động nhận diện các cụm có hình dạng tùy ý và loại bỏ trên 95% điểm nhiễu ngoại lai mà không cần người dùng chỉ định trước số lượng cụm k. Ngược lại, K-Means bắt buộc khai báo trước tham số k và chỉ tối ưu với các cụm hình cầu lồi đồng nhất.

Làm thế nào để thiết lập hai tham số quan trọng Eps và MinPts trong DBSCAN?

Đối với dữ liệu không gian 2 chiều, tham số MinPts được cố định bằng 4 theo khuyến nghị thực nghiệm. Tham số khoảng cách Eps được xác định thông qua phương pháp tương tác với đồ thị khoảng cách 4-dist đã sắp xếp, trong đó điểm ngưỡng được chọn tại vị trí đường cong thay đổi độ dốc đột ngột để phân tách cụm và nhiễu.

Độ phức tạp tính toán của thuật toán DBSCAN là bao nhiêu?

Khi không có cấu trúc hỗ trợ tìm kiếm, DBSCAN có độ phức tạp thời gian là bậc hai. Tuy nhiên, khi kết hợp với cấu trúc chỉ mục không gian như cây R-tree hoặc R*-tree, chi phí truy vấn lân cận giảm xuống mức logarit, giúp tổng độ phức tạp thời gian trung bình của DBSCAN đạt mức xấp xỉ O(n log n), nhanh hơn CLARANS từ 250 đến 1.900 lần.

Thuật toán DBSCAN gặp phải những hạn chế nào trong môi trường dữ liệu thực tế?

Hạn chế lớn nhất của DBSCAN là giảm hiệu quả khi xử lý các tập dữ liệu có mật độ giữa các cụm chênh lệch nhau quá lớn, do việc áp dụng tham số toàn cục Eps sẽ khiến cụm có mật độ thưa bị coi là nhiễu. Đồng thời, DBSCAN nguyên bản chưa hỗ trợ đánh giá các thuộc tính phi không gian.

Thuật toán DBRS đã khắc phục những nhược điểm nào của DBSCAN?

Thuật toán DBRS ứng dụng kỹ thuật lấy mẫu ngẫu nhiên giúp giảm đáng kể số lần truy vấn không gian trên các cơ sở dữ liệu quy mô hàng trăm nghìn điểm. Ngoài ra, DBRS đưa vào định nghĩa lân cận ghép và ngưỡng MinPur, cho phép phân tích đồng thời cả thuộc tính không gian lẫn thuộc tính phi không gian của đối tượng dữ liệu.

Kết luận

• Luận văn hệ thống hóa toàn diện cơ sở lý thuyết về tiến trình khám phá tri thức 5 giai đoạn và phân loại các kỹ thuật phân cụm dữ liệu hiện đại.
• Công trình phân tích sâu sắc cấu trúc toán học và ưu nhược điểm của 4 giải thuật phân cụm mật độ tiêu biểu: DBSCAN, DBRS, OPTICS và DENCLUE.
• Thực nghiệm cài đặt thành công giải thuật DBSCAN, chứng minh tốc độ xử lý nhanh hơn từ 250 đến 1.900 lần so với thuật toán phân hoạch truyền thống CLARANS trên các bộ dữ liệu lớn.
• Đề xuất giải pháp xác định tham số tối ưu bằng đồ thị Heuristic 4-dist, giúp tiết kiệm 75% thời gian thử nghiệm tham số và loại bỏ trên 95% dữ liệu nhiễu ngoại lai.
• Khẳng định giá trị thực tiễn vượt trội của phân cụm mật độ trong các lĩnh vực kinh tế, địa chấn, quy hoạch đô thị và phân tích thông tin địa lý.

Trong giai đoạn 12 đến 24 tháng tới, hướng nghiên cứu cần tiếp tục mở rộng mô hình phân cụm mật độ song song hóa trên các nền tảng phân tán và dữ liệu đa chiều thời gian thực. Hãy tải và tham khảo ngay toàn văn luận văn thạc sĩ để nắm bắt trọn vẹn giải pháp phân cụm dữ liệu dựa trên mật độ, tạo tiền đề vững chắc cho các công trình nghiên cứu khoa học máy tính và ứng dụng khai phá dữ liệu thực tế.

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

CHƯƠNG 1: TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM DỮ LIỆU 1. Tổng quan về khai phá dữ liệu 1. Khái niệm Có nhiều định nghĩa về Khai phá dữ liệu (Data Mining) được đưa ra, nhìn chung, có thể hiểu khai phá dữ liệu là quá trình tìm ra các quy luật, các mối quan hệ và các thông tin có ích tiềm ẩn giữa các mẫu dữ liệu trong một cơ sở dữ liệu. Các thông tin có ích này không hoặc khó có thể được tìm ra bởi các hệ cơ sở dữ liệu giao dịch truyền thống.

Các tri thức mà khai phá dữ liệu mang lại là công cụ hữu hiệu đối với tổ chức trong việc hoạch định chiến lược và ra quyết định kinh doanh. Khác với các câu hỏi mà hệ cơ sở dữ liệu truyền thống có thể trả lời như:  Hãy hiển thị số tiền ông Smith trong ngày 5 tháng Giêng ?: thu nhận thông tin riêng lẻ do xử lý giao dịch trực tuyến (on-line transaction processing – OLTP).  Có bao nhiêu nhà đầu tư nước ngoài mua cổ phiếu X trong tháng trước?: thu nhận thông tin thống kê do hệ thống hỗ trợ quyết định thống kê (stastical decision suppport system - DSS).  Hiển thị mọi cổ phiếu trong CSDL với mệnh giá tăng ? thu nhận dữ liệu đa chiều do xử lý phân tích trực tuyến (on-line analytic processing - OLAP).

Khai phá dữ liệu giúp trả lời các câu hỏi mang tính trừu tượng, tổng quát hơn như:  Các cổ phiếu tăng giá có đặc trưng gì ?  Tỷ giá US$ - DMark có đặc trưng gì ?  Hy vọng gì về cổ phiếu X trong tuần tiếp theo ? Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 12  Trong tháng tiếp theo, sẽ có bao nhiêu đoàn viên công đoàn không trả được nợ của họ ?  Những người mua sản phẩm Y thường mua những sản phẩm nào nữa ? Khai phá dữ liệu là sự kết hợp của nhiều chuyên ngành như cơ sở dữ liệu, học máy, trí tuệ nhân tạo, lý thuyết thông tin, xác suất thống kê, tính toán hiệu năng cao và các phương pháp tính toán mềm… 1. Tiến trình khai phá dữ liệu Một số nhà khoa học xem khai phá dữ liệu (KPDL) là một cách gọi khác của một thuật ngữ rất thông dụng: Khám phá tri thức từ cơ sở dữ liệu (Knowledge Discovery in Database- KDD). Mặt khác, khi chia các bước trong quá trình khám phá tri thức, một số nhà nghiên cứu lại cho rằng, KPDL chỉ là một bước trong quá trình khám phá tri thức [5]. Như vậy, khi xét ở mức tổng quan thì hai thuật ngữ này là tương đương nhau, nhưng khi xét cụ thể thì KPDL được xem là một bước trong quá trình khám phá tri thức.

Nhìn chung, khai phá dữ liệu hay khám phá tri thức từ cơ sở dữ liệu bao gồm các bước sau [4]: Hình 1.1: Tiến trình khám phá tri thức từ cơ sở dữ liệu Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 13  Trích chọn dữ liệu: Là quá trình trích lọc một lượng dữ liệu phù hợp, cần thiết từ tập dữ liệu lớn (cơ sở dữ liệu tác nghiệp, kho dữ liệu)…  Tiền xử lý dữ liệu: Là bước làm sạch dữ liệu (xử lý dữ liệu không đầy đủ, dữ liệu nhiễu, ngoại lai, dữ liệu không nhất quán…), rút gọn dữ liệu (lấy mẫu dữ liệu, lượng tử hóa…), rời rạc hóa dữ liệu. Kết quả sau bước này là dữ liệu có tính nhất quán, đầy đủ, được rút gọn và được rời rạc hóa.  Chuyển đổi dữ liệu: Là bước chuẩn hóa khuôn dạng và làm mịn dữ liệu, nhằm đưa dữ liệu về dạng thuận lợi nhất để phục vụ cho việc áp dụng các giải thuật khai phá dữ liệu ở bước sau.  Khai phá dữ liệu: Sử dụng các phương pháp, kỹ thuật, các thuật toán để trích lọc ra mẫu có ý nghĩa cùng với các tri thức, quy luật, biểu thức mô tả mối quan hệ của dữ liệu trong một khía cạnh nào đó.

Đây là bước quan trọng và tốn nhiều thời gian nhất của toàn bộ tiến trình KDD.  Đánh giá và biểu diễn tri thức: Trình bày các tri thức, quy luật, biểu thức có ý nghĩa đã tìm được ở bước trước dưới các dạng thức gần gũi, dễ hiểu đối với người sử dụng như đồ thị, biểu đồ, cây, bảng biểu, luật…Đồng thời đưa ra những đánh giá về tri thức khám phá được theo những tiêu chí nhất định. Trong giai đoạn khai phá dữ liệu, có thể cần sự tương tác của con người để điều chỉnh cách thức và kỹ thuật sử dụng trong khai phá, nhằm thu được tri thức phù hợp nhất. Dựa trên các bước của quá trình khai phá dữ liệu như trên, kiến trúc điển hình của một hệ khai phá dữ liệu có thể bao gồm các thành phần như sau: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2: Kiến trúc điển hình của một hệ khai phá dữ liệu [4] 1.

Các mô hình khai phá dữ liệu Mô hình khai phá dữ liệu là mô tả về phương pháp, cách thức khai phá thông tin từ dữ liệu và định hướng kiểu tri thức cần khai phá. Một mô hình khai phá dữ liệu có thể được mô tả ở 2 mức:  Mức chức năng (Function level): Mô tả mô hình bằng những thuật ngữ về dự định sử dụng. Ví dụ: Phân lớp, phân cụm…  Mức biểu diễn (Representation level): Biểu diễn cụ thể một mô hình. Ví dụ: Mô hình log-linear, cây phân lớp, phương pháp láng giềng gần nhất… Các mô hình khai phá dữ liệu dựa trên 2 kiểu học: có giám sát và không giám sát (đôi khi được nói đến như là học trực tiếp và không trực tiếp -directed and undirected learning) [6].

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 15  Các hàm học có giám sát (Supervised learning functions) được sử dụng để dự đoán giá trị. Một ví dụ của thuật toán học có giám sát bao gồm Naive Bayes cho phân lớp (classification).  Các hàm học không giám sát được dùng để tìm ra cấu trúc bên trong, các quan hệ hoặc tính giống nhau trong nội dung dữ liệu nhưng không có lớp hay nhãn nào được gán ưu tiên. Ví dụ của các thuật toán học không giám sát gồm phân nhóm k-mean (k-mean clustering) và các luật kết hợp Apriori.

Tương ứng có 2 loại mô hình khai phá dữ liệu:  Các mô hình dự báo (học có giám sát): - Phân lớp: nhóm các đối tượng thành các lớp riêng biệt và dự đoán một đối tượng sẽ thuộc vào lớp nào. - Hồi qui (Regression): xấp xỉ hàm và dự báo các giá trị liên tục.  Các mô hình mô tả (học không giám sát): - Phân cụm (Clustering): Tìm các nhóm tự nhiên trong dữ liệu. - Các mô hình kết hợp (Association models): Phân tích “giỏ hàng”.

- Trích chọn đặc trưng (Feature extraction): Tạo các thuộc tính (đặc trưng) mới như là kết hợp của các thuộc tính ban đầu. Các hướng tiếp cận và kỹ thuật sử dụng trong khai phá dữ liệu Xuất phát từ hai mô hình khai phá dữ liệu chủ yếu như đã đề cập ở trên, các bài toán (hay chức năng) khai phá dữ liệu giải quyết thường được phân chia thành các dạng sau [4]:  Mô tả khái niệm (concept description & summarization):. Tổng quát, tóm tắt các đặc trưng dữ liệu, Ví dụ: tóm tắt văn bản…  Phân lớp và dự đoán (classification & prediction): Xây dựng các mô hình (chức năng) để mô tả và phân biệt khái niệm cho các lớp hoặc khái Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 16 niệm để dự đoán trong tương lai, xếp một đối tượng vào một trong những lớp đã biết trước.  Luật kết hợp (association rules): Biểu diễn mối tương quan nhân quả giữa dữ liệu và xu hướng của dữ liệu dưới dạng luật biểu diễn tri thức ở dạng khá đơn giản.

 Khai phá chuỗi theo thời gian (sequential/temporal patterns): tương tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao.  Phân cụm (clustering/segmentation): xếp các đối tượng theo từng cụm (số lượng cũng như tên của cụm chưa được biết trước. Phân cụm còn được gọi là học không giám sát (học không có thầy – unsupervised learning).

 Phân tích bất thường (ngoại lai): Phát hiện sự bất thường của dữ liệu: đối tượng dữ liệu không tuân theo hành vi chung của toàn bộ dữ liệu nhằm phát hiện gian lận hoặc phân tích các sự kiện hiếm… 1. Các dạng dữ liệu có thể khai phá Khai phá dữ liệu là kết hợp của nhiều lĩnh vực khoa học, xử lý nhiều nhiều kiểu dữ liệu khác nhau [4]. Sau đây là một số kiểu dữ liệu điển hình:  CSDL quan hệ (relational databases)  CSDL đa chiều (multidimensional structures, data warehouses)  CSDL dạng giao dịch (transactional databases)  CSDL quan hệ - hướng đối tượng (object-relational databases)  Dữ liệu không gian và thời gian (spatial and temporal data)  Dữ liệu chuỗi thời gian (time-series data) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 17  CSDL đa phương tiện (multimedia databases) như âm thanh (audio), hình ảnh (image), phim ảnh (video),.  Dữ liệu Text và Web (text database & www) 1.

Các ứng dụng của khai phá dữ liệu Khai phá dữ liệu được vận dụng để giải quyết các vấn đề thuộc nhiều lĩnh vực khác nhau. Chẳng hạn như giải quyết các bài toán phức tạp trong các ngành đòi hỏi kỹ thuật cao, như tìm kiếm mỏ dầu từ ảnh viễn thám, cảnh báo hỏng hóc trong các hệ thống sản xuất; quy hoạch và phát triển các hệ thống quản lý và sản xuất trong thực tế như dự đoán tải sử dụng điện, mức độ tiêu thụ sản phẩm, phân nhóm khách hàng; áp dụng cho các vấn đề xã hội như phát hiện tội phạm, tăng cường an ninh… Có thể liệt kê ra đây một số ứng dụng điển hình như:  Phân tích dữ liệu và hỗ trợ ra quyết định (data analysis & decision support)  Điều trị y học (medical treatment): mối liên hệ giữa triệu chứng, chẩn đoán và phương pháp điều trị (chế độ dinh dưỡng, thuốc men, phẫu thuật, …).  Text mining & Web mining: phân lớp văn bản và các trang web, tóm tắt văn bản,.  Tin-sinh (bio-informatics): tìm kiếm, đối sánh các hệ gene và thông tin di truyền, mối liên hệ giữa một số hệ gene và một số bệnh di truyền, .