KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU
Khai phá dữ liệu là gì
Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỷ 80
Khai phá dữ liệu là một quy trình bao gồm nhiều kỹ thuật nhằm phát hiện thông tin giá trị tiềm ẩn trong các kho dữ liệu lớn Quá trình này chủ yếu liên quan đến việc phân tích dữ liệu và áp dụng các phương pháp để tìm kiếm các mẫu hình có tính chính quy trong tập dữ liệu.
Năm 1989, Fayyad, Piatestsky-Shapiro và Smyth đã giới thiệu khái niệm Phát hiện tri thức trong cơ sở dữ liệu (KDD), đề cập đến toàn bộ quá trình khám phá tri thức hữu ích từ các tập dữ liệu lớn Khai phá dữ liệu là một bước quan trọng trong quá trình này, sử dụng các thuật toán đặc biệt để chiết xuất các mẫu hoặc mô hình từ dữ liệu.
Quy trình khai phá dữ liệu
Quy trình phát hiện tri thức thường tuân theo các bước sau:
Bước đầu tiên trong quá trình phân tích dữ liệu là hình thành và xác định bài toán Giai đoạn này bao gồm việc tìm hiểu lĩnh vực ứng dụng để từ đó xác định các nhiệm vụ cần hoàn thành Việc này rất quan trọng vì nó giúp rút ra tri thức hữu ích và lựa chọn các phương pháp khai phá dữ liệu phù hợp với mục đích ứng dụng cũng như đặc điểm của dữ liệu.
Bước thứ hai trong quy trình phát hiện tri thức là thu thập và tiền xử lý dữ liệu, bao gồm việc làm sạch dữ liệu để loại bỏ nhiễu, xử lý thiếu dữ liệu để làm giàu thông tin, biến đổi và rút gọn dữ liệu khi cần thiết Đây là bước tốn nhiều thời gian nhất do dữ liệu thường được lấy từ nhiều nguồn khác nhau và không đồng nhất, dễ gây nhầm lẫn Sau khi hoàn thành, dữ liệu sẽ trở nên nhất quán, đầy đủ, được rút gọn và rời rạc hóa.
Bước thứ ba trong quy trình phát hiện tri thức là khai phá dữ liệu và rút ra các tri thức, nơi mà các mẫu và mô hình ẩn dưới dữ liệu được trích xuất Giai đoạn này rất quan trọng và bao gồm các công đoạn như chức năng, nhiệm vụ và mục đích của việc khai phá dữ liệu, cũng như phương pháp khai phá được sử dụng Thông thường, các bài toán khai phá dữ liệu bao gồm các vấn đề mang tính mô tả, nhằm đưa ra những tính chất chung nhất của dữ liệu, và các bài toán dự báo.
Hình thành và Định nghĩa bài toán
Thu thập và Tiền xử lý dữ liệu
Rút ra các tri thức
Phân tích và kiểm định kết quả
Sử dụng các tri thức phát hiện đƣợc Đồ án tốt nghiệp Trường ĐHDL Hải Phòng
Phạm Văn Đức - Lớp CT1201 4 nhấn mạnh tầm quan trọng của việc phát hiện suy diễn từ dữ liệu hiện có Tùy thuộc vào từng bài toán cụ thể, việc lựa chọn phương pháp khai phá dữ liệu phù hợp là điều cần thiết để đạt được kết quả tối ưu.
Bước thứ tư: Sử dụng các tri thức phát hiện được, đặc biệt là làm sáng tỏ các mô tả và dự đoán
Các bước thực hiện có thể được lặp lại nhiều lần để thu được kết quả trung bình, từ đó ứng dụng vào nhiều lĩnh vực khác nhau Kết quả của quá trình phát hiện tri thức, bao gồm các dự đoán và mô tả, có thể được tích hợp vào hệ thống hỗ trợ ra quyết định, giúp tự động hóa quy trình này.
Tóm lại: KDD là một quá trình kết xuất ra tri thức từ kho dữ liệu mà trong đó khai phá dữ liệu là công đoạn quan trọng nhất.
Các kỹ thuật khai phá dữ liệu
Khai phá dữ liệu là lĩnh vực quan trọng giúp con người sử dụng thông tin hiệu quả Quá trình này liên quan đến việc phát hiện các mẫu thông qua các phương pháp như sử dụng công cụ truy vấn, xây dựng cây quyết định, và phát hiện luật kết hợp Những phương pháp này đã được phát triển và tích hợp vào các hệ thống lai để nâng cao khả năng khai thác dữ liệu Tuy nhiên, khi đối mặt với khối lượng dữ liệu lớn, các phương pháp này gặp phải thách thức về hiệu quả và quy mô.
1.3.1 Phương pháp suy diễn và quy nạp
Cơ sở dữ liệu không chỉ là kho thông tin mà còn cho phép suy diễn các thông tin quan trọng Hai kỹ thuật chính để thực hiện điều này là suy diễn và quy nạp.
Để rút ra thông tin từ cơ sở dữ liệu, ta áp dụng các toán tử liên kết cho các bảng chứa thông tin về nhân viên và phòng ban, từ đó suy ra mối quan hệ giữa nhân viên và trưởng phòng Phương pháp suy diễn dựa trên các sự kiện chính xác giúp tạo ra tri thức mới từ thông tin cũ, thường là các luật suy diễn Ví dụ, từ tập dữ liệu khách hàng vay vốn, ta có thể chiết xuất luật: "Nếu thu nhập của khách hàng lớn hơn t đồng, thì khách hàng có khả năng trả nợ."
Phương pháp quy nạp là một kỹ thuật tìm kiếm và khai thác thông tin từ cơ sở dữ liệu mà không dựa vào tri thức đã biết trước Thay vào đó, nó tự động tìm kiếm, tạo mẫu và sinh ra tri thức mới, cung cấp các thông tin và tri thức cấp cao về các đối tượng trong cơ sở dữ liệu Phương pháp này tập trung vào việc phát hiện các mẫu ẩn trong dữ liệu, giúp nâng cao khả năng phân tích và hiểu biết về thông tin.
Trong khai phá dữ liệu, quy nạp được sử dụng trong cây quyết định và tạo luật
1.3.2 Cây quyết định và luật
Cây quyết định là một phương pháp đơn giản để phân loại dữ liệu thành các lớp khác nhau, trong đó các nút đại diện cho thuộc tính và các cạnh thể hiện giá trị của chúng Các đối tượng được phân loại thông qua các đường đi trên cây, dẫn đến các lá mô tả các lớp khác nhau Hình 1.3 minh họa một ví dụ về kết quả của quá trình khai thác dữ liệu sử dụng cây quyết định trong việc phân tích hồ sơ khách hàng xin vay vốn.
Hình 1.2 Mẫu kết quả với phương pháp cây quyết định
Các luật được phát triển để suy diễn các mẫu dữ liệu có ý nghĩa thống kê, thường có dạng "nếu P thì Q", trong đó P là một mệnh đề đúng với một phần của cơ sở dữ liệu (CSDL).
Mệnh đề Q thể hiện dự đoán, ví dụ như: nếu giá một sản phẩm thấp hơn giá sản phẩm cùng loại 5000 đồng, thì số lượng bán ra sẽ tăng 5% Những quy luật này thường được sử dụng để mô tả tri thức trong hệ chuyên gia và có ưu điểm là dễ hiểu đối với người sử dụng.
Cây quyết định và luật là những công cụ mô tả đơn giản, giúp người dùng dễ dàng hiểu được các mô hình suy diễn Tuy nhiên, chúng có hạn chế trong việc chỉ biểu diễn một số dạng chức năng, dẫn đến độ chính xác của mô hình bị giới hạn Đối với các quy mô lớn, việc đánh giá mô hình thường dựa vào các phương pháp xác suất với độ phức tạp khác nhau Các phương pháp tìm kiếm cũng đóng vai trò quan trọng trong quá trình này.
"Tham lam" là một phương pháp liên quan đến việc tăng cường và rút gọn các luật cũng như cấu trúc cây, chủ yếu nhằm khai thác không gian siêu mũ của các mô hình Cây và luật được ứng dụng chủ yếu trong mô hình hóa dự đoán, phân lớp và hồi quy (Apte & Hong; Fayyad, Djorgovski, & Wei) Ngoài ra, chúng còn có thể được sử dụng để tóm tắt và mô hình hóa các mô tả (Agrawal et al.).
1.3.3 Phân nhóm và phân đoạn
Kỹ thuật phân nhóm và phân đoạn là phương pháp chia dữ liệu thành các nhóm đồng nhất theo tiêu chí nhất định Mối quan hệ giữa các thành viên trong nhóm dựa trên mức độ tương đồng, từ đó tạo ra các quy tắc ràng buộc giữa chúng Một kỹ thuật phân nhóm khác là phát triển các hàm đánh giá thuộc tính của các thành viên.
Thu nhập > t Đồ án tốt nghiệp Trường ĐHDL Hải Phòng
Phạm Văn Đức-Lớp CT1201 6 đề cập đến phương pháp phân hoạch tối ưu (optimal partitioning), trong đó các thành phần được xác định như hàm của các tham số Ví dụ điển hình của phương pháp này là việc phân nhóm khách hàng dựa trên độ giống nhau, cho phép tối ưu hóa các nhóm thuế trong việc thiết lập biểu thuế bảo hiểm.
Mẫu đầu ra của quá trình khai phá dữ liệu sử dụng kỹ thuật này là các tập mẫu chứa dữ liệu có chung tính chất, được phân tách từ cơ sở dữ liệu Khi các mẫu được thiết lập, chúng có thể tái tạo các tập dữ liệu ở dạng dễ hiểu hơn và cung cấp nhóm dữ liệu cho các hoạt động phân tích Việc lấy ra các nhóm này là rất quan trọng đối với cơ sở dữ liệu lớn.
1.3.4 Phương pháp ứng dụng K-láng giềng gần
Sự miêu tả các bản ghi trong tập dữ liệu trong không gian nhiều chiều rất quan trọng cho phân tích dữ liệu Bằng cách sử dụng các miêu tả này, chúng ta có thể xác định nội dung của vùng lân cận, nơi các bản ghi gần nhau được xem là láng giềng Khái niệm này được áp dụng trong khoa học kỹ thuật dưới tên K-láng giềng gần, với K là số lượng láng giềng được tính đến Phương pháp này vừa hiệu quả vừa đơn giản, với ý tưởng cơ bản là "hành động như các láng giềng gần của bạn đã làm".
Kỹ thuật K-láng giềng gần là một phương pháp tìm kiếm đơn giản nhưng có những hạn chế về phạm vi ứng dụng Thuật toán này có độ phức tạp tính toán là bậc hai theo số lượng bản ghi trong tập dữ liệu.
Vấn đề chính liên quan đến thuộc tính của bản ghi là sự tồn tại của nhiều thuộc tính độc lập, tạo thành một điểm trong không gian tìm kiếm có số chiều lớn Trong không gian này, khoảng cách giữa hai điểm bất kỳ thường tương tự nhau, dẫn đến việc kỹ thuật K-láng giềng không cung cấp thông tin hữu ích, vì hầu hết các cặp điểm đều là láng giềng Hơn nữa, phương pháp K-láng giềng thiếu lý thuyết để hiểu cấu trúc dữ liệu, và hạn chế này có thể được khắc phục bằng kỹ thuật cây quyết định.
1.3.5 Các phương pháp dựa trên mẫu
Các ứng dụng của khai phá dữ liệu
Mặc dù khai phá dữ liệu vẫn còn nhiều thách thức cần nghiên cứu, nhưng tiềm năng của nó đã được chứng minh qua sự phát triển của nhiều ứng dụng trong các lĩnh vực khác nhau của cuộc sống.
Trong các lĩnh vực khoa học như quan sát thiên văn, phân tích dữ liệu gene và sinh vật học, việc tìm kiếm và so sánh các hệ gene cùng thông tin di truyền là rất quan trọng Những nghiên cứu này giúp xác định mối liên hệ giữa gene và các bệnh di truyền, từ đó mở ra hướng đi mới trong y học và nghiên cứu sinh học.
Dự báo thời tiết là quá trình mô hình hóa các thay đổi khí hậu và phân tích các hiện tượng như mưa bão, lốc xoáy và sóng thần Mục tiêu của dự báo này là cung cấp những dự đoán chính xác và kịp thời để người dân có thể chủ động ứng phó với các tình huống thời tiết khắc nghiệt.
Bảo hiểm, tài chính và thị trường chứng khoán đóng vai trò quan trọng trong việc phân tích tình hình tài chính và dự báo giá cổ phiếu Việc theo dõi danh mục vốn, giá cả, lãi suất cùng với dữ liệu thẻ tín dụng và phát hiện gian lận giúp nhà đầu tư đưa ra quyết định chính xác hơn trong thị trường chứng khoán.
Điều trị y học và chăm sóc y tế đóng vai trò quan trọng trong việc chuẩn đoán bệnh lưu trong hệ thống quản lý bệnh viện Việc phân tích mối liên hệ giữa các triệu chứng bệnh, chuẩn đoán chính xác và phương pháp điều trị hiệu quả là cần thiết để nâng cao chất lượng chăm sóc sức khỏe.
Một số thách thức đặt ra cho việc khai phá dữ liệu
Khai phá dữ liệu là một kỹ thuật mới với nhiều tiềm năng chưa được khai thác triệt để Mặc dù nghiên cứu và ứng dụng kỹ thuật này gặp nhiều khó khăn, nhưng chúng ta cần tìm ra các giải pháp để hoàn thiện hơn các phương pháp khai phá dữ liệu Một số khó khăn trong quá trình này có thể được liệt kê như sau:
Cho đến nay, cơ sở dữ liệu với hàng triệu bản ghi và kích thước lên đến gigabytes đã trở nên phổ biến, và hiện nay xuất hiện các cơ sở dữ liệu có kích thước lên đến terabytes Để giải quyết vấn đề này, các phương pháp hiện tại bao gồm việc thiết lập ngưỡng cho cơ sở dữ liệu, lấy mẫu, sử dụng các phương pháp xấp xỉ và xử lý song song (Agrawal et al, Holsheimer et al).
Khi dữ liệu có số lượng bản ghi và số trường lớn, kích thước bài toán trở nên phức tạp hơn, dẫn đến việc tăng không gian tìm kiếm mô hình suy diễn Điều này cũng làm gia tăng khả năng xuất hiện các mẫu giả trong quá trình khai thác dữ liệu Để khắc phục vấn đề này, cần giảm kích thước tác động của bài toán và áp dụng tri thức biết trước nhằm xác định các biến không phù hợp.
Dữ liệu động là đặc điểm cơ bản của hầu hết các cơ sở dữ liệu, trong đó nội dung liên tục thay đổi theo thời gian Việc khai thác dữ liệu bị ảnh hưởng bởi thời điểm quan sát, với một số giá trị như cân nặng và chiều cao thay đổi liên tục, trong khi những giá trị khác như nhịp đập của mạch chỉ có giá trị quan sát mới nhất Sự thay đổi nhanh chóng của dữ liệu có thể làm mất giá trị các mẫu khai thác trước đó Các biến trong cơ sở dữ liệu cũng có thể thay đổi, bị xóa hoặc tăng lên theo thời gian Để giải quyết vấn đề này, cần áp dụng các giải pháp tăng trưởng nhằm nâng cấp các mẫu và coi những thay đổi là cơ hội để khai thác, tìm kiếm các mẫu mới bị biến đổi.
Các trường không phù hợp:
Một yếu tố quan trọng là tính không thích hợp của dữ liệu, khi mà các mục dữ liệu không còn phù hợp với mục tiêu hiện tại của việc khai thác Bên cạnh đó, tính ứng dụng của một thuộc tính cũng có thể liên quan đến một tập con cụ thể trong cơ sở dữ liệu.
Các giá trị bị thiếu:
Sự có mặt hay vắng mặt của giá trị các thuộc tính dữ liệu ảnh hưởng lớn đến quá trình khai phá dữ liệu Trong các hệ thống tương tác, việc thiếu dữ liệu quan trọng có thể dẫn đến yêu cầu xác định giá trị của nó Ngoài ra, sự vắng mặt của dữ liệu cũng có thể được xem như một điều kiện, trong đó thuộc tính bị mất được coi là một giá trị trung gian và là giá trị không biết.
Một quan sát không đầy đủ cơ sở dữ liệu có thể dẫn đến việc dữ liệu giá trị bị xem là lỗi Việc phát hiện toàn bộ các thuộc tính cần thiết cho giải thuật khai phá dữ liệu là rất quan trọng để giải quyết vấn đề Nếu các thuộc tính không phân biệt được các tình huống đáng quan tâm, điều đó cho thấy có lỗi trong dữ liệu Ví dụ, trong hệ thống chẩn đoán bệnh sốt rét, nếu các bản ghi bệnh nhân có triệu chứng tương tự nhưng lại có chẩn đoán khác nhau, điều này cho thấy dữ liệu đã bị lỗi Tình trạng này cũng thường xảy ra trong cơ sở dữ liệu kinh doanh, nơi các thuộc tính quan trọng có thể bị thiếu nếu dữ liệu không được chuẩn bị đúng cách Độ nhiễu và không chắc chắn trong dữ liệu cũng phụ thuộc vào kiểu dữ liệu của các giá trị cho phép, bao gồm số thực, số nguyên, chuỗi và giá trị định danh, có thể được sắp xếp theo thứ tự hoặc có cấu trúc ngữ nghĩa.
Một yếu tố quan trọng trong độ không chắc chắn là tính kế thừa và độ chính xác của dữ liệu, liên quan đến độ nhiễu của nó Các mô hình thống kê được xây dựng dựa trên các phép đo và phân tích ưu tiên để xác định tính ngẫu nhiên, từ đó định nghĩa độ mong muốn và độ dung sai của dữ liệu Những mô hình này thường được áp dụng để xác định các thuộc tính một cách chủ quan nhằm đạt được thống kê và đánh giá khả năng chấp nhận của các giá trị thuộc tính Đặc biệt với dữ liệu số, độ chính xác của dữ liệu đóng vai trò quan trọng trong quá trình khai thác.
Mối quan hệ phức tạp giữa các trường:
Các thuộc tính và giá trị có cấu trúc phân cấp cùng với các mối quan hệ giữa chúng đòi hỏi các thuật toán phải có khả năng khai thác hiệu quả thông tin trong cơ sở dữ liệu Kỹ thuật khai phá dữ liệu ban đầu chỉ được phát triển cho các bản ghi, nhưng giờ đây đã mở rộng để đáp ứng nhu cầu phức tạp hơn trong việc diễn tả tri thức về nội dung.
Phạm Văn Đức, sinh viên lớp CT1201, đang nghiên cứu giá trị thuộc tính đơn giản Hiện nay, nhiều người đang nỗ lực phát triển các kỹ thuật để khám phá mối quan hệ giữa các biến này.
Kết luận chương 1
Khai phá dữ liệu là lĩnh vực nghiên cứu đang thu hút sự quan tâm lớn từ các chuyên gia CNTT toàn cầu và được ứng dụng rộng rãi trong nhiều lĩnh vực Tại Việt Nam, mặc dù kỹ thuật này còn mới mẻ, nhưng đang được nghiên cứu và dần áp dụng Trong những năm gần đây, nhiều phương pháp và thuật toán mới đã được công bố, chứng tỏ tiềm năng lớn và lợi ích của khai phá dữ liệu Chương này cung cấp cái nhìn tổng quan về khai phá tri thức và khai phá dữ liệu.
PHÂN CỤM DỮ LIỆU VÀ CÁC GIẢI THUẬT THEO TIẾP CẬN PHÂN HOẠCH
Phân cụm dữ liệu là gì?
Phân cụm dữ liệu (PCDL) là một phương pháp học không giám sát, trong đó các mẫu học chưa được gán nhãn Mục tiêu của PCDL là xác định các mẫu đại diện và nhóm các dữ liệu tương tự lại thành các cụm Các điểm dữ liệu trong cùng một cụm có độ tương tự cao hơn so với các điểm thuộc các cụm khác.
Hình 2.1: Mô phỏng vấn đề PCDL
Trong hình trên, quá trình phân cụm đã tạo ra bốn nhóm khác nhau Các phần tử được xếp vào cùng một cụm khi chúng "gần nhau" hoặc "tương tự" về đặc điểm.
"Xa nhau" và "phi tương tự" là hai cụm từ khác nhau Để làm rõ vấn đề này, chúng ta có thể xem xét các hình ảnh minh họa cụ thể.
Hình 2.2: Dữ liệu nguyên thuỷ Đồ án tốt nghiệp Trường ĐHDL Hải Phòng
Phạm Văn Đức-Lớp CT1201 12
Hình 2.7: Kết quả của quá trình phân cụm
Các hình 2.2, 2.3, 2.4, 2.5, 2.6 ,2.7 là thể hiện quá trình phân cụm từ khi“bắt đầu” cho đến khi “kết thúc”
Các ứng dụng của phân cụm
Phân cụm dữ liệu có rất nhiều ứng dụng trong các lĩnh vực khác nhau:
Thương mại: Giúp các doanh nhân khám phá ra các nhóm khách hàng quan trọng để đưa ra các mục tiêu tiếp thị
Sinh học: Xác định các loài sinh vật, phân loại các Gen với chức năng tương đồng và thu được các cấu trúc trong các mẫu
Lập quy hoạch đô thị: Nhận dạng các nhóm nhà theo kiểu và vị trí địa lý, nhằm cung cấp thông tin cho quy hoặch đô thị
Thư viện : Phân loại các cụm sách có nội dung và ý nghĩa tương đồng nhau để cung cấp cho độc giả
Bảo hiểm: Nhận dạng nhóm tham gia bảo hiểm có chi phí bồi thường cao, nhận dạng gian lận thương mại
Nghiên cứu trái đất: Phân cụm để theo dõi các tâm động đất nhằm cung cấp thông tin cho nhân dạng các vùng nguy hiểm
World Wide Web cung cấp khả năng khám phá các nhóm tài liệu quan trọng, mang lại nhiều ý nghĩa trong môi trường trực tuyến Những lớp tài liệu này hỗ trợ hiệu quả cho việc khai thác dữ liệu từ các nguồn thông tin.
Các yêu cầu đối với thuật toán phân cụm dữ liệu
Hiện tại, chưa có phương pháp phân cụm tổng quát nào có thể giải quyết hoàn toàn tất cả các dạng cấu trúc cơ sở dữ liệu (CSDL) Các phương pháp phân cụm cần phải có cách thức biểu diễn cấu trúc của CSDL, và mỗi cách biểu diễn sẽ tương ứng với thuật toán phân cụm phù hợp Do đó, phân cụm dữ liệu vẫn là một vấn đề khó khăn và mở, yêu cầu giải quyết nhiều vấn đề cơ bản một cách toàn diện, đặc biệt với kho dữ liệu hỗn hợp ngày càng gia tăng Thách thức này trong lĩnh vực khai thác dữ liệu (KPDL) đến từ những ứng dụng tiềm năng của phân cụm, phù hợp với các yêu cầu đặc thù Với đặc điểm của cơ sở dữ liệu lớn, phức tạp và có dữ liệu nhiễu, các thuật toán phân cụm cần đáp ứng nhiều yêu cầu khắt khe.
- Thuật toán phải hiệu quả và thời gian chạy phải là tăng tuyến tính theo kích thước của dữ liệu
Thuật toán cần phải có khả năng xử lý và áp dụng hiệu quả trên các cơ sở dữ liệu phức tạp và nhiều nhiễu, bao gồm cả dữ liệu không gian và phi không gian, dữ liệu số và phi số, kiểu nhị phân, cũng như dữ liệu định danh và hạng mục, đồng thời thích nghi với các kiểu dữ liệu hỗn hợp.
Thuật toán cần phải có khả năng nhận diện các cụm với hình dáng đa dạng, bao gồm cả những cụm có hình dạng lồng nhau, hình lõm, hình cầu và hình que.
Để xác định các tham số đầu vào cho thuật toán phân cụm, cần tối thiểu một lượng tri thức nhất định Các giá trị đầu vào này có ảnh hưởng lớn đến hiệu quả của thuật toán, và việc xác định giá trị phù hợp cho các cơ sở dữ liệu lớn là một nhiệm vụ phức tạp.
Thuật toán cần phải hoạt động hiệu quả với mọi thứ tự của dữ liệu đầu vào, điều này có nghĩa là kết quả đạt được từ thuật toán phải không phụ thuộc vào cách sắp xếp dữ liệu Khi áp dụng cho cùng một tập dữ liệu, thuật toán sẽ cho ra kết quả nhất quán, đảm bảo tính ổn định và đáng tin cậy trong quá trình thực hiện.
Phạm Văn Đức, lớp CT1201, đã thực hiện xử lý thuật toán PCDL với các thứ tự vào của các đối tượng dữ liệu khác nhau trong các lần thực hiện Kết quả cho thấy rằng thứ tự vào không ảnh hưởng lớn đến kết quả phân cụm.
- Thuật toán không đòi hỏi những tri thức về cơ sở dữ liệu từ người dùng
- Thuật toán phải làm việc được với cơ sở dữ liệu chứa nhiều lớp đối tượng dữ liệu phức tạp và có tính chất khác nhau
- Thuật toán phải thích nghi với dữ liệu đa chiều: Thuật toán có khả năng áp dụng hiệu quả cho dữ liệu có số khác chiều nhau
Thuật toán phân cụm cần phải dễ hiểu, dễ cài đặt và khả thi, giúp người sử dụng nhận được những kết quả rõ ràng và dễ giải thích Việc giải thích ý nghĩa và ứng dụng của sự phân cụm là rất quan trọng Do đó, nghiên cứu cách để ứng dụng đạt được mục tiêu sẽ ảnh hưởng lớn đến việc lựa chọn các phương pháp phân cụm.
Các kiểu dữ liệu trong phân cụm
Trong phân cụm, các đối tượng dữ liệu được mô tả bằng các thuộc tính, tương đương với khái niệm "các kiểu dữ liệu" Việc lựa chọn các thuộc tính này có ảnh hưởng lớn đến kết quả phân cụm Phân loại các kiểu thuộc tính là cần thiết để nhận diện sự khác biệt giữa các phần tử dữ liệu trong hầu hết các tập dữ liệu Các thuật toán phân cụm thường dựa vào một trong hai cấu trúc dữ liệu chính để thực hiện quá trình này.
Ma trận dữ liệu (Data matrix) là cấu trúc dạng đối tượng theo biến, bao gồm n hàng và p cột, trong đó p đại diện cho số thuộc tính của mỗi đối tượng Mỗi hàng trong ma trận biểu thị một đối tượng, và các phần tử trong mỗi hàng chứa giá trị thuộc tính tương ứng của đối tượng đó.
Ma trận phi tương tự (Dissimilarity matrix) là một cấu trúc dạng mảng với n hàng và n cột, trong đó mỗi phần tử d(i,j) đại diện cho khoảng cách hoặc độ khác biệt giữa hai đối tượng i và j Giá trị d(i,j) luôn không âm; nếu d(i,j) gần bằng 0, điều đó có nghĩa là hai đối tượng i và j rất "gần" nhau, trong khi giá trị lớn hơn cho thấy sự khác biệt rõ rệt giữa chúng Đặc biệt, ma trận phi tương tự có tính đối xứng, tức là d(i,j) = d(j,i) và d(i,i) = 0.
Với d(i,j) là khoảng cách giữa đối tượng i và đối tượng j
Hầu hết các thuật toán phân cụm đều dựa trên cấu trúc ma trận phi tương tự Vì vậy, để thực hiện phân cụm hiệu quả, dữ liệu cần được tổ chức dưới dạng ma trận phi tương tự trước khi tiến hành.
Có hai đặc trưng để phân loại: kích thước miền và hệ đo
Trong một cơ sở dữ liệu D chứa n đối tượng trong không gian k chiều, các đối tượng x, y, z được biểu diễn dưới dạng x (x1, x2, , xk), y (y1, y2, , yk), và z (z1, z2, , zk) Mỗi thành phần xi, yi, zi (với i = 1, , k) đại diện cho các đặc trưng hoặc thuộc tính tương ứng của các đối tượng này, tạo nên các kiểu dữ liệu đa dạng trong cơ sở dữ liệu.
2.4.1 Kiểu dữ liệu dựa trên kích thước miền
Thuộc tính liên tục có nghĩa là miền giá trị của nó là vô hạn không đếm được, tức là giữa hai giá trị bất kỳ luôn tồn tại vô số giá trị khác Ví dụ về các thuộc tính này bao gồm màu sắc, nhiệt độ và cường độ âm thanh.
Thuộc tính rời rạc là những thuộc tính có miền giá trị là tập hữu hạn và có thể đếm được, như các thuộc tính số Một trường hợp đặc biệt của thuộc tính rời rạc là thuộc tính nhị phân, trong đó miền giá trị chỉ bao gồm hai phân tử, chẳng hạn như Yes/No, True/False, hoặc On/Off.
2.4.2 Kiểu dữ liệu dựa trên hệ đo
Thuộc tính định danh là một dạng thuộc tính khái quát hóa từ thuộc tính nhị phân, với miền giá trị rời rạc, không phân biệt thứ tự và có nhiều hơn hai phần tử Trong trường hợp hai đối tượng thuộc tính x và y, chúng ta chỉ có thể xác định mối quan hệ giữa chúng là x ≠ y hoặc x = y.
Thuộc tính có thứ tự là loại thuộc tính định danh với tính thứ tự nhưng không thể định lượng Trong trường hợp có hai thuộc tính thứ tự x và y, chúng ta có thể xác định mối quan hệ giữa chúng là x khác y, x bằng y, x lớn hơn y hoặc x nhỏ hơn y.
Thuộc tính khoảng cho phép đo lường các giá trị theo cách tuyến tính, giúp xác định vị trí của một thuộc tính so với thuộc tính khác cùng với khoảng cách giữa chúng Cụ thể, nếu x i lớn hơn y i, ta có thể nói rằng khoảng cách giữa x và y là x i - y i tương ứng với thuộc tính thứ i.
Việc lựa chọn đơn vị đo cho các thuộc tính ảnh hưởng đến chất lượng phân cụm, với đơn vị đo càng nhỏ thì khoảng cách xác định càng lớn, từ đó tác động nhiều đến kết quả phân cụm Để giảm thiểu sự phụ thuộc vào đơn vị đo, dữ liệu cần được chuẩn hóa, giúp gán trọng số bằng nhau cho tất cả các thuộc tính Tuy nhiên, người sử dụng có thể điều chỉnh trọng số cho các thuộc tính trong nhiều trường hợp khác nhau.
Phạm Văn Đức, lớp CT1201, cho biết rằng để chuẩn hóa các độ đo, một phương pháp phổ biến là chuyển đổi các thuộc tính sang dạng không có đơn vị đo Đối với các thuộc tính f, quy trình thực hiện sẽ như sau:
- Tính độ lệch trung bình:
Trong đó x 1f ,…,x nf là giá trị thuộc tính f của n phần tử dữ liệu, và m f là giá trị trung bình của f, được cho như sau: m f = (x 1f + x 2f +… + x nf )
- Độ đo được chuẩn hóa:
Thuộc tính nhị phân là thuộc tính có hai giá trị là 0 và 1
Thuộc tính tính tỷ lệ: Là thuộc tính khoảng nhưng được xác định một cách tương đối so với điểm mốc
Trong các thuộc tính trình bày, thuộc tính định danh và thuộc tính có thứ tự được gọi là thuộc tính hạng mục, trong khi thuộc tính khoảng cách và thuộc tính tỷ lệ được xếp vào thuộc tính số Đặc biệt, dữ liệu không gian là loại dữ liệu có thuộc tính số khái quát trong không gian nhiều chiều, mô tả thông tin liên quan đến không gian chứa đựng các đối tượng như hình học, quan hệ metric và quan hệ hướng Dữ liệu không gian có thể tồn tại dưới dạng dữ liệu liên tục hoặc rời rạc.
- Dữ liệu không gian liên tục: Bao chứa một vùng không gian
Dữ liệu không gian rời rạc là các điểm trong không gian nhiều chiều, giúp xác định khoảng cách giữa các đối tượng dữ liệu.
Phép đo độ tương tự và khoảng cách đối với các kiểu dữ liệu
2.5.1 Khái niệm tương tự, phi tương tự
Khi các đặc tính của dữ liệu được xác định, phải tìm cách thích hợp để xác định
Khoảng cách giữa các đối tượng là phép đo tương tự dữ liệu, giúp xác định sự giống nhau giữa các cặp đối tượng Các hàm đo này thường tính toán độ tương tự hoặc độ phi tương tự, trong đó giá trị cao của hàm tương tự cho thấy sự giống nhau lớn hơn, còn hàm phi tương tự tỉ lệ nghịch với hàm tương tự Độ tương tự và phi tương tự có nhiều phương pháp xác định, chủ yếu dựa vào khoảng cách giữa các đối tượng, và phụ thuộc vào loại thuộc tính được phân tích Ví dụ, với thuộc tính hạng mục, không sử dụng độ đo khoảng cách mà áp dụng một hướng hình học cho dữ liệu.
Tất cả các độ đo dưới đây được xác định trong không gian metric, trong đó bất kỳ metric nào cũng là một độ đo, nhưng không phải mọi độ đo đều là metric Thuật ngữ "độ đo" ở đây chỉ hàm tính độ tương tự hoặc độ phi tương tự Một không gian metric là tập hợp có thể xác định "khoảng cách" giữa từng cặp phần tử, với các tính chất giống như khoảng cách hình học Cụ thể, một tập X, trong đó các phần tử có thể là bất kỳ đối tượng nào, được gọi là không gian metric nếu thỏa mãn các điều kiện nhất định.
- Với mỗi cặp phần tử x, y thuộc X đều xác định theo một quy tắc nào đó, một số thực d(x,y) được gọi là khoảng cách giữa x và y
- Quy tắc nói trên thỏa mãn hệ tính chất sau:
(ii) d(x,y) = 0 nếu x= y ; (iii) d(x,y) = d(y,x) với mọi x,y ; (iv) d(x,y) ≤ d(x,z) + d(z,y) ; Hàm δ(x,y) được gọi là một metric của không gian Các phần tử của X được gọi là các điểm của không gian này
Một yếu tố quan trọng trong thuật toán phân cụm là phép đo khoảng cách giữa hai điểm dữ liệu Khi các thành phần của vectơ dữ liệu thuộc cùng một đơn vị, khoảng cách Euclidean có thể được sử dụng để xác định nhóm dữ liệu tương tự Tuy nhiên, cần lưu ý rằng khoảng cách Euclidean không phải lúc nào cũng mang lại kết quả chính xác.
Lưu ý rằng vấn đề không nằm ở đồ thị mà ở công thức toán học được dùng để kết hợp khoảng cách giữa các thành phần đơn trong dữ liệu vectơ Việc sử dụng các công thức khác nhau sẽ dẫn đến những kết quả phân cụm khác nhau.
Các thuật toán phân cụm yêu cầu các phép đo khoảng cách hoặc độ tương tự giữa hai đối tượng Để đảm bảo hiệu quả, cần sử dụng kiến thức miền nhằm xác định phép đo khoảng cách phù hợp cho từng ứng dụng Hiện nay, các phép đo này có sự đa dạng và được điều chỉnh tùy theo từng tình huống cụ thể.
Khoảng cách Euclidean: là khoảng cách Minkowski khi q=2 Khoảng cách Euclidean chính là khoảng cách hình học trong không gian n chiều d(i,j)=
Khoảng cách Manhattan: là khoảng cách Minkowski khi q=1 d(i,j)=
Khoảng cách có trọng là một sự cải tiến của khoảng cách Minkowski, cho phép xem xét ảnh hưởng của từng thuộc tính đến khoảng cách giữa hai đối tượng Trong đó, thuộc tính có trọng số w càng lớn sẽ có ảnh hưởng lớn hơn đến khoảng cách d Việc lựa chọn trọng số phù hợp là rất quan trọng và phụ thuộc vào ứng dụng cũng như mục tiêu cụ thể của từng trường hợp.
Các phép đo được đề cập chủ yếu áp dụng cho các biến liên tục Đối với các biến danh nghĩa, "phép đo khoảng cách" được xác định là 0 khi các trường hợp có cùng giá trị danh nghĩa và 1 khi các trường hợp có giá trị danh nghĩa khác nhau.
Khi xem xét biến định danh p, chúng ta có thể đánh giá độ tương tự giữa các trường hợp thông qua số lượng biến có giá trị giống nhau Điều này giúp xác định mối liên hệ và sự tương đồng trong các dữ liệu.
Phạm Văn Đức - Lớp CT1201 18 có hai lớp nhãn, với một lớp là 1 và lớp còn lại là 0 Bài viết xây dựng và phân tích bảng ngẫu nhiên các sự kiện có thể xảy ra, đồng thời định nghĩa các thuộc tính của đối tượng x và y thông qua các biến nhị phân 0 và 1.
Trong bài viết này, chúng ta sẽ xem xét các thuộc tính của hai đối tượng x và y Cụ thể, a đại diện cho tổng số thuộc tính có giá trị 1 trong cả hai đối tượng, b là tổng số thuộc tính có giá trị 1 trong x và 0 trong y, c là tổng số thuộc tính có giá trị 0 trong x và 1 trong y, và d là tổng số thuộc tính có giá trị 0 trong cả hai đối tượng Cuối cùng, p là tổng số tất cả các thuộc tính của hai đối tượng x và y.
Ta có tổng số các thuộc tính về đối tượng p = a + b + c + d
Các phép đo độ tương tự giữa hai đối tượng trong trường hợp dữ liệu thuộc tính nhị phân được định nghĩa như sau:
Hệ số đối sánh đơn giản: d(x,y)= cả hai đối tượng có vai trò như nhau, nghĩa là chúng đối xứng và có cùng trọng số
Hệ số Jaccard: d(x,y)= tham số này bỏ qua số các đối sánh 0-0
Công thức này áp dụng khi trọng số của các thuộc tính có giá trị 1 trong dữ liệu cao hơn nhiều so với các thuộc tính có giá trị 0, dẫn đến sự không đối xứng trong thuộc tính nhị phân.
2.5.4 Thuộc tính định danh Độ đo phi tương tự giữa hai đối tượng x và y được định nghĩa như sau: d(x,y)= trong đó, m là số thuộc tính đối sánh tương ứng trùng nhau, p là tổng số các thuộc tính
2.5.5 Thuộc tính có thứ tự
Phép đo độ phi tương tự giữa các đối tượng dữ liệu với thuộc tính thứ tự được thực hiện bằng cách xác định thuộc tính thứ tự i có M i giá trị, trong đó M i đại diện cho kích thước miền giá trị.
Các trạng thái M i được sắp thứ tự như sau: [1…M i ], chúng ta có thể thay thế mỗi giá trị của thuộc tính bằng giá trị cùng loại ri, với r i M i
Mỗi thuộc tính có thứ tự và miền giá trị riêng, do đó chúng ta cần chuyển đổi chúng về cùng một miền giá trị từ 0 đến 1 thông qua các phép biến đổi thích hợp cho từng thuộc tính.
Sử dụng công thức tính độ phi tương tự của thuộc tính khoảng cho các giá trị, đây chính là độ phi tương tự của thuộc tính có thứ tự.
2.5.6 Thuộc tính tỉ lệ (Ratio Scale)
Các hướng tiếp cận bài toán phân cụm dữ liệu
Có nhiều phương pháp phân cụm dữ liệu khác nhau, và việc lựa chọn phương pháp phù hợp phụ thuộc vào kiểu dữ liệu, mục tiêu và ứng dụng cụ thể Các phương pháp này có thể được phân loại thành nhiều nhóm khác nhau.
2.6.1 Các phương pháp phân hoạch Đây là các phương pháp tạo phân hoạch cơ sở dữ liệu D có n đối tượng thành k Đồ án tốt nghiệp Trường ĐHDL Hải Phòng
Phạm Văn Đức-Lớp CT1201 20
Mỗi cụm chứa ít nhất một đối tượng
Mỗi đối tượng thuộc về một cụm duy nhất k là số cụm đã được cho trước
Các phương pháp tiếp cận phân hoạch
Tối ưu toàn cục bằng phương pháp vét cạn cho một giá trị k nhất định có thể tạo ra (k n - (k-1) -…- 1) khả năng phân hoạch khác nhau Số lượng này trở nên quá lớn khi n tăng, dẫn đến việc thực hiện trở nên gần như không khả thi.
Heuristic methods for clustering include K-means, introduced by MacQueen in 1967, where each cluster is represented by its centroid, and K-medoids, also known as Partitioning Around Medoids (PAM), developed by Kaufman and Rousseeuw in 1987, where each cluster is represented by an actual object from the cluster Further details on K-means will be provided in the subsequent sections.
2.6.2 Phương pháp phân cấp( Hierachical methods) Đây là các phương pháp tạo phân cấp cụm (hierarchical clustering) chứ không tạo phân hoạch các đối tượng Phương pháp này không cần phải xác định số cụm từ đầu Số cụm sẽ do khoảng cách giữa các cụm hoặc điều kiện dừng quyết định Tiêu chuẩn phân cụm thường được xác định bởi ma trận khoảng cách Phân cấp cụm thường được biểu diễn dưới dạng đồ thị dạng cây các cụm (dendogram) Lá của cây biểu diễn đối tượng riêng lẻ, nút trong biểu diễn các cụm
Các phương pháp tiếp cận để phân cụm phân cấp gồm
Hình 2.9: Hai phương pháp tiếp cận phân cấp Gộp:
B1 Xuất phát mỗi đối tượng và tạo một cụm chứa nó
B2 Nếu hai cụm đủ gần nhau (dưới một ngưỡng nào đấy) sẽ được gộp lại thành một cụm duy nhất
B3 Lặp lại B2 dến khi chỉ còn một cụm duy nhất là toàn bộ không gian
B1 Xuất phát từ một cụm duy nhất là toàn bộ không gian
B2 Lựa chọn cụm có độ phân biệt cao nhất, dựa trên ma trận phân biệt với phần tử lớn nhất hoặc trị trung bình lớn nhất, để thực hiện việc tách đôi Ở bước này, các phương pháp phân hoạch sẽ được áp dụng cho cụm đã được chọn.
B3 Lặp lại B2 đến khi mỗi đối tượng thuộc một cụm hoặc đạt điều kiện dừng
(đủ số cụm cần thiết hoặc khoảng cách giữa các cụm đạt ngưỡng đủ nhỏ)
Các khoảng cách giữa các cụm thường được dùng là:
Khoảng cách nhỏ nhất, hay còn gọi là khoảng cách liên kết đơn (single link) hoặc khoảng cách người láng giềng gần nhất, là một phương pháp hữu ích trong việc phát hiện các cụm có hình dạng chuỗi thay vì hình dạng khối Công thức tính khoảng cách này được thể hiện bằng d(Ci, Cj) = minx Ci, y Cj {d(x,y)}.
Khoảng cách lớn nhất, còn được gọi là khoảng cách liên kết hoàn toàn, là phương pháp lý tưởng để phát hiện các cụm có hình dạng khối thay vì chuỗi Công thức tính khoảng cách giữa hai cụm C_i và C_j được biểu diễn là d(C_i, C_j) = max_{x ∈ C_i, y ∈ C_j} {d(x,y)}.
Khoảng cách trung bình: d(C i ,C j ) = avgx Ci, y Cj {d(x,y)}
Khoảng cách trọng tâm là khoảng cách giữa hai trọng tâm của các cụm được chọn, giúp xác định khoảng cách giữa chúng Phương pháp này hiệu quả trong việc phát hiện các cụm có dạng khối, đồng thời tối ưu hóa tốc độ tính toán nhờ chỉ tập trung vào trọng tâm, từ đó giảm thiểu khối lượng tính toán.
2.6.3 Các phương pháp dựa trên mật độ (Density based Methods)
Các ký hiệu và khái niệm: p, q, o là các điểm dữ liệu bất kỳ (các đối tượng)
Với Eps dương cho trước,tập hợp NEps(p) ={q | d(q,p) ≤Eps } được gọi là lân cận bán kính Eps của p p được gọi là điểm hạt nhân nếu thỏa mãn
Trong bài viết này, min Pts được định nghĩa là một số nguyên dương tối thiểu để xác định một điểm là trù mật Khi nhắc đến một điểm là hạt nhân, điều này có nghĩa là nó liên quan đến một bán kính và ngưỡng trù mật nhất định Điểm p được xem là điểm biên nếu nó không phải là điểm nhân, trong khi q được gọi là đi tới được trực tiếp theo mật độ từ p nếu p là một điểm nhân và q nằm trong lân cận của p Cuối cùng, p n được xem là đi tới được theo mật độ từ p 1 nếu tồn tại một chuỗi các điểm p i.
Trong nghiên cứu về kết nối theo mật độ, hai điểm p và q được xem là có mối liên hệ nếu tồn tại một điểm o mà từ đó cả p và q đều có thể liên thông mật độ Điều này có nghĩa là, với mỗi điểm p_i (i=2,…,n), tồn tại một kết nối mật độ trực tiếp từ p_i đến p_(i+1) Đồ án tốt nghiệp tại Trường ĐHDL Hải Phòng đã tập trung vào việc phân tích và ứng dụng khái niệm này.
Phạm Văn Đức-Lớp CT1201 22
2.6.4 Phân cụm dữ liệu dựa trên lưới Ý tưởng: dùng các cấu trúc dữ liệu dạng lưới với nhiều cấp độ phân giải Những ô lưới có mật độ cao sẽ tạo thành những cụm Phương pháp này rất phù hợp với các phân tích phân cụm ừng dụng trong không gian (phân loại sao, thiên hà, …) Ngoài ra còn có các thuật toán khác như thuật toán STING, WaveCluster, CLIQUE
2.6.5 Phương pháp dựa trên mô hình (Gom cụm khái niệm, mạng neural) Đây là các phương pháp dựa trên sự phù hợp giữa dữ liệu và các mô hình toán học Ý tưởng của các phương pháp này là: Dữ liệu phát sinh từ một sự kết hợp nào đó của các phân phối xác xuất ẩn Có hai phương pháp tiếp cận chính:
Tiếp cận thống kê (phương pháp COBWEB, CLASSIT, AUTOCLASS)
Tiếp cận mạng noron (học cạnh tranh, bản đồ tự cấu trúc SOM).
Các vấn đề có thể gặp phải
- Các kỹ thuật phân cụm hiện tại chỉ giải quyết được một phần các yêu cầu của bài toán
Một thách thức phổ biến trong phân cụm dữ liệu là sự hiện diện của nhiễu, thường do quá trình thu thập dữ liệu không chính xác hoặc không đầy đủ Do đó, việc xây dựng một chiến lược tiền xử lý dữ liệu là cần thiết để khắc phục hoặc loại bỏ nhiễu trước khi tiến hành phân tích cụm.
- Việc phân cụm một dữ liệu với kích thước và số lượng lớn là vấn đề khó khăn bởi vì độ phức tạp thời gian tăng cao
- Khả năng hiệu quả của các phương pháp phân cụm phụ thuộc vào định nghĩa
"khoảng cách" (khi phân cụm dựa trên khoảng cách);
Nếu không có khoảng cách, chúng ta cần phải "định nghĩa" nó, nhưng quá trình này rất phức tạp, đặc biệt trong không gian đa chiều.
Phương pháp phân hoạch (Partion Methods)
Cho k là số cụm sau khi phân hoạch (1≤ k ≤ n, với n là số điểm( đối tượng) trong không gian giữ liệu)
Thuật toán k-means gồm 4 bước:
B1 Chọn ngẫu nhiên k điểm làm trọng tâm ban đầu của k cụm
B2 Gán từng điểm vào cụm gần nhất cho đến khi không còn phép gán nào xảy ra Khi không có phép gán mới, điều này cho thấy các cụm đã ổn định và thuật toán không thể cải thiện độ phân biệt hơn nữa.
B3 Tính lại trọng tâm cho từng cụm
Minh họa thuật toán với k=2
Hình 2.10: Ví dụ về một số hình dạng cụm dữ liệu được khám phá bởi
K-means Ưu điểm của phương pháp gom cụm k-means
Thuật toán có độ phức tạp O(tkn), trong đó t là số lần lặp (thường nhỏ hơn nhiều so với n), k là số cụm cần phân hoạch và n là số điểm trong không gian dữ liệu Nhờ vào khả năng tương đổi nhanh, thuật toán này mang lại hiệu quả cao trong việc xử lý dữ liệu.
- K-means phù hợp với các cụm có dạng hình cầu
Nhược điểm của phương pháp k-mean
Kết quả đầu ra của thuật toán không đảm bảo tối ưu toàn cục, phụ thuộc nhiều vào việc lựa chọn k điểm khởi đầu Vì vậy, cần phải chạy lại thuật toán với nhiều bộ khởi đầu khác nhau để đạt được kết quả tốt hơn Thực tế, có thể áp dụng thuật giải di truyền để tạo ra các bộ khởi đầu hiệu quả.
- Cần phải xác định trước số cụm
- Khó xác định số cụm thực sự mà không gian dữ liệu có Do đó có thể phải thử với các giá trị k khác nhau
- Khó phát hiện các loại cụm có hình dạng phức tạp và nhất là các dạng cụm không lồi
- Không thể xử lý nhiễu và mẫu cá biệt
- Chỉ có thể áp dụng khi tính được trọng tâm
Thuật toán K-Medoids là cải tiến của thuật toán k-means, k-medoids khác k-means ở:
- Chiến lược chọ k trọng tâm đầu tiên
- Phương pháp tính độ phân biệt
- Phương pháp tính trọng tam trong cụm
Thuật toán K-Medoids được thực hiện qua các bước sau:
B1: Chọn ngẫu nhiên k điểm O i ( i=1,…,k) làm trung tâm (medoids) ban đầu của k cụm Đồ án tốt nghiệp Trường ĐHDL Hải Phòng
Phạm Văn Đức-Lớp CT1201 24
B2: Gán ( hoặc gán lại) từng điểm vào cụm có trung tâm gần điểm đang xét nhất B3: Với mỗi điểm trung tâm O i ( i=1,…,k):
B3.1 Lần lượt xét các điểm không là trung tâm (non-medoids) x
B3.2 Tính S là độ lợi khi hoán đổi O i bởi x S được xác định như sau:
S=E x – E Oi với E Oi và E x lần lượt là giá trị hàm mục tiêu trước và sau khi thay O i bởi x k
B3.3 Nếu S là âm thì thay thế O i trong bộ k trung tâm bởi x ( chọn trung tâm mới tốt hơn)
B4 Nếu có ít nhất 1 sự thay đổi trong B3 thì tiếp tục quay lại B2 Ngược lại thì kết thúc thuật toán Ƣu điểm thuật toán K-medoids
K-medoids làm việc được với nhiễu và biệt lệ
Nhƣợc điểm thuật toán K-medoids
K-medoids chỉ hiệu quả khi tập dữ liệu không quá lớn vì có độ phức tạp là O(k(n-k) 2 t) Trong đó: n là số điểm trong không gian dữ liệu, k là số cụm cần phân hoạch, t là số lần lặp ( t khá nhỏ so với n).
Kết luận chương 2
Trong chương 2 chúng ta có 2 vấn đề quan tâm đó là phân cụm dữ liệu và các giải thuật theo tiếp cận phân hoạch
Phân cụm dữ liệu nhằm gom nhóm các dữ liệu tương tự để cung cấp thông tin hữu ích cho việc ra quyết định, là một trong những hướng nghiên cứu chính trong khai phá dữ liệu Các giải thuật phân hoạch có ưu điểm là đơn giản, dễ áp dụng và hiệu quả với cơ sở dữ liệu nhỏ, nhưng chỉ có thể tạo ra các cụm hình dạng lồi Phương pháp này sử dụng tâm cụm để xác định nhóm dữ liệu, do đó không thể xử lý các cụm có hình dạng lõm hoặc lồng nhau Hơn nữa, trong trường hợp cơ sở dữ liệu có nhiễu hoặc các điểm dữ liệu xa tâm, phương pháp phân cụm phân hoạch không hiệu quả vì sẽ làm lệch tâm cụm, dẫn đến việc không tạo ra các cụm chính xác.
CÀI ĐẶT VÀ THỬ NGHIỆM
Môi trường cài đặt
Chương trình được lập trình với ngôn ngữ C# của Visual Studio 2008 Được cài đặt và chạy trên windown XP SP3
Input: Đưa vào một bức ảnh định dạng JPEG
Output: Các nhóm (cụm) điểm ảnh, trong đó các điểm ảnh có cùng màu sẽ được gom vào một nhóm.
Giới thiệu chương trình ứng dụng
3.2.1 Lưu đồ thuật toán sử dụng trong chương trình
Tìm Top X color gán làm trọng tâm
Tính d(x,y) Đưa các điểm về các cụm, cập nhật lại tâm các cụm
No Đồ án tốt nghiệp Trường ĐHDL Hải Phòng
Phạm Văn Đức-Lớp CT1201 26
Tìm Top X color gán làm trung tâm
Tính khoảng cách và phân cụm Đồ án tốt nghiệp Trường ĐHDL Hải Phòng
Phạm Văn Đức-Lớp CT1201 28
Kiểm tra hội tụ Đồ án tốt nghiệp Trường ĐHDL Hải Phòng
Phạm Văn Đức-Lớp CT1201 30
Giao diện khởi động Đƣa dữ liệu vào xử lý
Quá trình xử lý dữ liệu Đồ án tốt nghiệp Trường ĐHDL Hải Phòng
Phạm Văn Đức-Lớp CT1201 32
Quá trình xử lý kết thúc
Chạy Thuật toán K-Means với hệ HSV