TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
Giới thiệu về khám phá tri thức
Trong khi công nghệ điện tử truyền thống tập trung vào điện tử và sóng điện tử, thì hiện nay, dữ liệu, thông tin và tri thức đang trở thành trọng tâm của nghiên cứu và ứng dụng trong lĩnh vực phát hiện tri thức và khai phá dữ liệu.
Dữ liệu thường được hiểu là một chuỗi bit, số, ký hiệu, hoặc các đối tượng mang ý nghĩa khi gửi cho chương trình dưới một dạng cụ thể Chúng ta sử dụng bit để đo lường thông tin, coi đó là dữ liệu đã được tinh giản, loại bỏ các yếu tố thừa, nhằm thể hiện một cách cơ bản nhất về nội dung dữ liệu.
Tri thức được xem như là thông tin tích hợp, bao gồm các sự kiện và mối quan hệ giữa chúng Những mối quan hệ này có thể được hiểu, phát hiện hoặc học hỏi Nói cách khác, tri thức là dữ liệu có mức độ trừu tượng và tổ chức cao.
Phát hiện tri thức trong cơ sở dữ liệu là quá trình nhận diện các mẫu và mô hình với các đặc điểm như hợp lệ, mới mẻ, hữu ích và dễ hiểu Khai thác dữ liệu là giai đoạn trong quy trình phát hiện tri thức, sử dụng các thuật toán chuyên dụng để tìm ra các mẫu hoặc mô hình trong dữ liệu, tuân theo các tiêu chí về hiệu quả tính toán Mục tiêu của cả hai quá trình này là phát hiện các mẫu và mô hình ẩn giấu trong khối lượng lớn dữ liệu.
Quy trình phát hiện tri thức:
Hình 1 1: Quy trình phát hiện tri thức
Bước đầu tiên trong quá trình khai thác dữ liệu là tìm hiểu lĩnh vực ứng dụng và xác định bài toán cụ thể Giai đoạn 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 thác 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à xử lý dữ liệu thô, hay còn gọi là tiền xử lý dữ liệu Mục tiêu của bước này là loại bỏ nhiễu, xử lý thiếu dữ liệu, biến đổi và rút gọn dữ liệu khi cần thiết Đây thường là giai đoạn tốn nhiều thời gian nhất trong toàn bộ quy trình.
Bước thứ ba: là khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc các mô hình ẩn dưới các dữ liệu
Bước thứ tư: là hiểu tri thức đã tìm đƣợc, đặc biệt là làm sáng tỏ các mô
Khai phá dữ liệu và các khái niệm liên quan
Khai phá dữ liệu là một quy trình phân tích nhằm khám phá một lượng lớn dữ liệu để phát hiện các mẫu và mối quan hệ hệ thống giữa các biến Quy trình này bao gồm ba giai đoạn chính: thăm dò dữ liệu, xây dựng mô hình hoặc định nghĩa mẫu, và hợp thức hóa, kiểm chứng kết quả.
1.2.1 Khái niệm khai phá dữ liệu
Khai phá dữ liệu (Data mining) đã phát triển mạnh mẽ và được ứng dụng rộng rãi trong nhiều lĩnh vực, dẫn đến sự xuất hiện của nhiều khái niệm khác nhau Trong bài viết này, tôi xin đưa ra một định nghĩa ngắn gọn về khai phá dữ liệu.
Khai phá dữ liệu là quá trình khám phá các tri thức mới và các tri thức có ích ở dạng tiềm năng trong nguồn dữ liệu đã có
1.2.2 Các phương pháp khai phá dữ liệu
Khai phá dữ liệu có hai mục tiêu chính là dự đoán và mô tả Để đạt được những mục tiêu này, người ta thường áp dụng các phương pháp khác nhau trong quá trình khai thác dữ liệu.
Mô hình ràng buộc (Dependency modeling)
Biểu diễn mô hình (Model Evaluation)
Phân tích sự phát triển và độ lệch (Evolution and deviation analyst)
Luận kết hợp (Associantion rules )
Phương pháp tìm kiếm (Search Method)
1.2.3 Các lĩnh vực ứng dụng trong thực tiễn
Phân tích dữ liệu và hỗ trợ ra quyết định
Phân lớp văn bản, tóm tắt văn bản, phân lớp các trang Web và phân cụm ảnh màu
Chuẩn đoán triệu chứng, phương pháp trong điều trị y học
Tìm kiếm, đối sánh các hệ Gene và thông tin di truyền trong sinh học
Phân tích tình hình tài chính, thị trường, dự báo giá cổ phiếu trong tài chính, thị trường và chứng khoán
1.2.4 Các hướng tiếp cận cơ bản và kỹ thuật áp dụng trong khai phá dữ liệu
Các kỹ thuật khai phá dữ liệu thường được chia thành 2 nhóm chính:
Kỹ thuật khai phá dữ liệu là quá trình mô tả các đặc tính chung của dữ liệu trong cơ sở dữ liệu hiện có Các kỹ thuật này bao gồm phân cụm (Clustering), tổng hợp (Summarization), trực quan hóa (Visualization), phân tích sự phát triển và độ lệch (Evolution and Deviation Analysis), cùng với luận kết hợp (Association Rules) Những phương pháp này giúp hiểu rõ hơn về dữ liệu và phát hiện các mẫu quan trọng.
Kỹ thuật khai phá dữ liệu dự đoán có vai trò quan trọng trong việc đưa ra những dự đoán và suy diễn dựa trên dữ liệu hiện tại Các phương pháp chính trong lĩnh vực này bao gồm phân lớp, giúp phân loại và tổ chức thông tin một cách hiệu quả.
Sau đây em xin được giới thiệu 3 phương pháp thông dụng nhất là: phân cụm dữ liệu, phân lớp dữ liệu và khai phá luận kết hợp
Phân lớp dữ liệu nhằm mục tiêu dự đoán nhãn lớp cho các mẫu dữ liệu Quá trình này thường bao gồm hai bước chính: xây dựng mô hình và áp dụng mô hình để thực hiện phân lớp dữ liệu.
Bước đầu tiên trong quá trình xây dựng mô hình là phân tích các mẫu dữ liệu có sẵn, với mỗi mẫu tương ứng với một lớp được xác định bởi thuộc tính lớp Những mẫu dữ liệu này được gọi là tập dữ liệu huấn luyện (Training dataset), và các nhãn lớp cần phải được xác định trước khi mô hình được xây dựng Phương pháp này được biết đến như là học có thầy (Supervised learning), khác với phân cụm dữ liệu, tức là học không có thầy (Unsupervised learning).
Bước 2: Sử dụng mô hình để phân lớp dữ liệu Đầu tiên, cần tính toán độ chính xác của mô hình Nếu độ chính xác đạt yêu cầu, mô hình sẽ được áp dụng để dự đoán nhãn lớp cho các mẫu dữ liệu trong tương lai.
Phân cụm dữ liệu nhằm mục đích nhóm các đối tượng tương tự trong tập dữ liệu thành các cụm, đảm bảo rằng các đối tượng trong cùng một cụm có sự tương đồng cao, trong khi các cụm khác nhau lại không tương đồng Quá trình này không cho phép dự đoán trước kết quả của các cụm, do đó thường cần sự đánh giá của chuyên gia trong lĩnh vực liên quan Ngoài ra, phân cụm dữ liệu còn đóng vai trò là bước tiền xử lý quan trọng cho các thuật toán khai phá dữ liệu khác.
Khai phá luận kết hợp nhằm mục tiêu phát hiện và chỉ ra các mối liên hệ giữa các giá trị dữ liệu trong cơ sở dữ liệu Kết quả đầu ra của thuật toán khai phá dữ liệu là tập hợp các luận kết hợp đã được tìm ra.
CHƯƠNG 2: PHÂN CỤM DỮ LIỆU VÀ CÁC TIẾP CẬN
Khái niệm chung
Khai phá dữ liệu (Datamining) là quá trình trích xuất thông tin giá trị tiềm ẩn từ các tập dữ liệu lớn lưu trữ trong cơ sở dữ liệu và kho dữ liệu.
Phân cụm dữ liệu là một kỹ thuật quan trọng trong Data Mining, giúp phát hiện các cụm và mẫu dữ liệu tự nhiên ẩn chứa trong tập dữ liệu lớn Kỹ thuật này cung cấp thông tin và tri thức hữu ích, hỗ trợ quá trình ra quyết định hiệu quả.
Phân cụm dữ liệu là quá trình chia nhỏ một tập dữ liệu lớn thành các nhóm cụm, trong đó các phần tử trong cùng một cụm có sự tương đồng cao với nhau.
(Similar) với nhau và các phần tử trong các cụm khác nhau sẽ “phi tương tự”
(Dissimilar) với nhau Số các cụm dữ liệu đƣợc phân ở đây có thể đƣợc xác định trước theo kinh nghiệm hoặc có thể được tự động xác định.
Các kiểu dữ liệu và độ đo tương tự
Cho một một cơ sở dữ liệu D chứa n đối tƣợng trong không gian k chiều trong đó x, y, z là các đối tƣợng thuộc D: x = (x 1 , x2, …, xk); y = (y1, y2,
…, y k ); z = (z1, z2, …, zk), trong đó xi, yi, zi với i = 1 , k là các đặc trƣng hoặc các thuộc tính tương ứng của các đối tượng x, y, z a) Phân loại theo kích thước miền
Thuộc tính liên tục (Continnuous Attribute): nếu miền giá trị của nó là vô hạn không đếm đƣợc
Thuộc tính rời rạc (DiscretteAttribute): nếu miền giá trị của nó là tập hữu hạn, đếm đƣợc
Các thuộc tính nhị phân là một dạng đặc biệt của thuộc tính rời rạc, trong đó miền giá trị chỉ có hai phần tử, thường được biểu diễn dưới dạng Yes/No hoặc False/True Phân loại thuộc tính nhị phân có thể dựa theo hệ đo.
Giả sử chúng ta có hai đối tượng x và y cùng với các thuộc tính xi và yi tương ứng với thuộc tính thứ i của chúng Chúng ta sẽ sử dụng các lớp kiểu dữ liệu như sau:
Thuộc tính định danh (Nominal Scale) là dạng thuộc tính khái quát hóa của 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 này, nếu x và y là hai đối tượng thuộc tính, chúng chỉ có thể được xác định là x khác y (x # y) hoặc x bằng y (x = y).
Thuộc tính có thứ tự (Ordinal Scale) là loại thuộc tính định danh có tính thứ tự nhưng không thể định lượng Trong trường hợp 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 bằng cách so sánh: 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 (Interval Scale) cho phép chúng ta 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 Nếu xi lớn hơn yi, chúng ta có thể nói rằng khoảng cách giữa x và y là xi – yi, tương ứng với thuộc tính thứ i.
Tỉ lệ (Ratio Scale) là thuộc tính được xác định tương đối so với một điểm mốc, chẳng hạn như chiều cao hoặc cân nặng, trong đó điểm 0 đóng vai trò là mốc khởi đầu.
Trong các thuộc tính dữ liệu, 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 (Categorical), trong khi thuộc tính khoảng và thuộc tính tỉ lệ được phân loại là thuộc tính số (Numeric).
2.2.2 Độ đo tương tự và phi tương tự Để phân cụm, người ta phải đ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 mức độ giống nhau giữa các cặp đối tượng Các hàm này thường được sử dụng để tính toán độ tương tự (Similar) hoặc độ phi tương tự (Dissimilar) giữa các đối tượng dữ liệu.
Tất cả các độ đo được xác định trong không gian metric, nơi mà khoảng cách giữa các cặp phần tử được quy định theo các tính chất của khoảng cách hình học Một tập X, bao gồm các đối tượng dữ liệu từ cơ sở dữ liệu D, được coi là không gian metric nếu đáp ứng các tiêu chí cụ thể liên quan đến khoảng cách giữa các phần tử.
Với mỗi cặp phần tử x, y thuộc X đều có xác định, theo một quy tắc nào đó, một số thực δ(x, y), đƣợc gọi là khoảng cách giữa x và y
Quy tắc nói trên thoả mãn hệ tính chất sau: (i) δ(x, y) > 0 nếu x ≠ y ;
(ii) δ(x, y)=0 nếu x =y; (iii) δ(x, y) = δ(y, x) với mọi x, y; (iv) δ(x, y) ≤ δ(x, z)+δ(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
Sau khi chuẩn hóa, độ đo phi tương tự của hai đối tượng dữ liệu x, y đƣợc xác định bằng các matrix khoảng cách nhƣ sau:
( trong đó q là số tự nhiên dương
, đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q =2
, đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q =1
Khoảng cách cực đại: d(x, y) = Max n i 1 x i y i , đây là trường hợp đặc biệt của khoảng cách Minskowski trong trường hợp q
Trong thuộc tính nhị phân, ta có các đại lượng sau: α đại diện cho tổng số thuộc tính có giá trị 1 trong x và y; β là tổng số thuộc tính có giá trị 1 trong x và 0 trong y; γ là tổng số thuộc tính có giá trị 0 trong x và 1 trong y; δ là tổng số thuộc tính có giá trị 0 trong cả x và y Tổng các thuộc tính này được ký hiệu là τ, với τ = α + β + γ + δ.
Các phép đo độ tương đồng đối với 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) = , ở đây cả hai đối tƣợng x và y có vai trò nhƣ nhau, nghĩa là chúng đối xứng và có cùng trọng số
Hệ số Jacard: d(x, y) = , (bỏ qua số các đối sánh giữa 0-0)
Công thức tính này áp dụng khi trọng số của các thuộc tính có giá trị 1 vượt trội hơn so với các thuộc tính có giá trị 0, dẫn đến sự không đối xứng trong các thuộc tính nhị phân.
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) p m p
Trong đó m là số thuộc tính đối sánh tương ứng trùng nhau và p là tổng số các thuộc tính
Thuộc tính có thứ tự:
Giả sử i là thuộc tính thứ tự có M i giá trị (Mi kích thước miền giá trị ):
Các trạng thái Mi được sắp xếp theo thứ tự từ 1 đến Mi Chúng ta có thể thay thế mỗi giá trị của thuộc tính bằng giá trị tương ứng ri trong khoảng từ 1 đến Mi.
Mỗi thuộc tính có thứ tự và các miền giá trị khác nhau, do đó, chúng ta cần chuyển đổi chúng về cùng một miền giá trị [0, 1] thông qua các phép biến đổi tương ứng cho từng thuộc tính.
Sử dụng công thức tính độ phi tương tự cho các thuộc tính khoảng dựa trên các giá trị Z i (i) cũng đồng nghĩa với việc tính độ phi tương tự cho các thuộc tính có thứ tự.
Có nhiều cách khác nhau để tính độ tương tự giữa các thuộc tính tỉ lệ
Một trong những số đó là sử dụng công thức tính logarit cho mỗi thuộc tính
Để tối ưu hóa dữ liệu, có thể loại bỏ đơn vị đo của các thuộc tính bằng cách chuẩn hóa hoặc gán trọng số cho từng thuộc tính dựa trên giá trị trung bình và độ lệch chuẩn Mỗi thuộc tính dữ liệu sẽ được gán trọng số tương ứng w_i (1 ≤ i ≤ k), và độ tương đồng giữa các dữ liệu được xác định theo công thức d(x, y) = √(Σ(w_i * (x_i - y_i)²)).
Các kỹ thuật tiếp cận trong phân cụm dữ liệu
Kỹ thuật phân cụm đa dạng với nhiều cách tiếp cận và ứng dụng thực tiễn, nhằm đạt được hai mục tiêu chính: chất lượng các cụm khám phá và tốc độ thực hiện thuật toán Hiện tại, các kỹ thuật phân cụm được phân loại theo những phương pháp chính.
2.3.1 Phương pháp phân cụm phân hoạch
Phương pháp phân cụm phân hoạch chia một tập dữ liệu n phần tử thành k nhóm, trong đó mỗi phần tử chỉ thuộc một nhóm và mỗi nhóm có ít nhất một phần tử Do độ phức tạp cao khi tìm kiếm nghiệm tối ưu toàn cục cho vấn đề phân cụm dữ liệu lớn (PCDL), người ta thường tìm giải pháp tối ưu cục bộ bằng cách sử dụng hàm tiêu chuẩn để đánh giá chất lượng cụm và hướng dẫn quá trình tìm kiếm Thông thường, quá trình này bắt đầu với một phân hoạch ngẫu nhiên hoặc theo heuristic và được tinh chỉnh liên tục cho đến khi đạt được phân hoạch mong muốn Các thuật toán phân cụm phân hoạch cải thiện tiêu chuẩn bằng cách tính toán độ tương tự giữa các đối tượng dữ liệu và lựa chọn giá trị tối ưu từ dãy sắp xếp để giảm thiểu hàm tiêu chuẩn Ý tưởng chính của các thuật toán này là áp dụng chiến lược ăn tham (Greedy) trong việc tìm kiếm nghiệm Một số thuật toán điển hình như K-means, PAM, CLARA, và CLARANS sẽ được trình bày chi tiết trong chương sau.
2.3.2 Phương pháp phân cụm phân cấp
Phương pháp này tạo ra một phân cấp dựa trên các đối tượng dữ liệu đang được xem xét, sắp xếp một tập dữ liệu thành cấu trúc dạng cây Cấu trúc cây phân cấp này được xây dựng thông qua kỹ thuật đệ quy, với hai cách tiếp cận phổ biến trong kỹ thuật này.
Hòa nhập nhóm, hay còn gọi là tiếp cận Bottom-Up, là phương pháp bắt đầu bằng việc khởi tạo các đối tượng tương ứng với các cụm riêng biệt Sau đó, các đối tượng được nhóm lại dựa trên độ đo tương tự, chẳng hạn như khoảng cách giữa hai trung tâm của hai nhóm Quá trình này tiếp tục cho đến khi tất cả các nhóm được hòa nhập thành một nhóm duy nhất, đạt mức cao nhất của cây phân cấp, hoặc cho đến khi các điều kiện kết thúc được thỏa mãn Phương pháp này áp dụng chiến lược ăn tham trong quá trình phân cụm.
Phân chia nhóm, hay còn gọi là tiếp cận Top-Down, bắt đầu với tất cả các đối tượng được xếp trong một cụm duy nhất Qua từng vòng lặp, các cụm lớn được tách nhỏ hơn dựa trên giá trị của một phép đo độ tương tự cho đến khi mỗi đối tượng trở thành một cụm riêng lẻ, hoặc khi điều kiện dừng được thỏa mãn Phương pháp này áp dụng chiến lược chia để trị trong quá trình phân cụm.
Một số thuật toán phân cụm phân cấp điển hình nhƣ CURE, BIRCH,
…sẽ được trình bày chi tiết ở trong chương sau
Trong thực tế, nhiều trường hợp kết hợp cả hai phương pháp phân cụm phân hoạch và phân cụm phân cấp, cho phép cải thiện kết quả thu được từ phương pháp phân cấp thông qua bước phân cụm phân hoạch Hai phương pháp này là những kỹ thuật cổ điển trong phân tích dữ liệu, và hiện nay, đã có nhiều thuật toán cải tiến dựa trên chúng được áp dụng rộng rãi trong khai phá dữ liệu.
2.3.3 Phương pháp phân cụm dựa trên mật độ
Phương pháp phân cụm dựa trên mật độ xác định các đối tượng theo hàm mật độ, cho phép phát triển thêm dữ liệu mới miễn là số đối tượng lân cận vượt qua ngưỡng nhất định Kỹ thuật này có khả năng phát hiện các cụm dữ liệu với hình thù bất kỳ và khắc phục hiệu quả các phân tử ngoại lai hoặc giá trị nhiễu Tuy nhiên, việc xác định các tham số mật độ của thuật toán gặp nhiều khó khăn, trong khi chúng lại ảnh hưởng lớn đến kết quả phân cụm dữ liệu.
Một số thuật toán PCDL dựa trên mật độ điển hình nhƣ DBSCAN, OPTICS, sẽ được trình bày chi tiết trong chương tiếp theo
2.3.4 Phương pháp phân cụm dựa trên lưới
Phương pháp phân cụm dựa trên lưới là giải pháp hiệu quả cho việc phân cụm dữ liệu nhiều chiều, đặc biệt trong các lớp dữ liệu không gian Phương pháp này sử dụng cấu trúc dữ liệu lưới để tổ chức dữ liệu thành các ô (cell), giúp thực hiện các thao tác PCDL với các đối tượng trong từng ô mà không di chuyển chúng Thay vì dựa vào khoảng cách giữa các đối tượng, các cụm được xác định bởi một tham số cố định Ưu điểm nổi bật của phương pháp này là thời gian xử lý nhanh chóng và tính độc lập với số lượng đối tượng trong tập dữ liệu ban đầu, mà phụ thuộc vào số lượng ô trong mỗi chiều của không gian lưới.
Hình 2 1: Mô hình cấu trúc dữ liệu lưới
Một số thuật toán PCDL dựa trên cấu trúc lưới điển hình STING,
2.3.5 Phương pháp phân cụm dựa trên mô hình
Phương pháp này nhằm tìm kiếm các phép xấp xỉ tối ưu cho các tham số mô hình, đảm bảo sự khớp tốt nhất với dữ liệu Nó có thể áp dụng chiến lược phân cụm phân hoạch hoặc phân cụm phân cấp, tùy thuộc vào cấu trúc hoặc mô hình giả định về tập dữ liệu, đồng thời điều chỉnh các mô hình này để nhận diện các phân hoạch hiệu quả.
Phương pháp PCDL là một kỹ thuật dựa trên mô hình nhằm khớp dữ liệu với mô hình toán học, với giả định rằng dữ liệu được tạo ra từ hỗn hợp phân phối xác suất cơ bản Các thuật toán phân cụm dựa trên mô hình chủ yếu có hai tiếp cận: mô hình thống kê và mạng Nơron Phương pháp này tương tự như phương pháp dựa trên mật độ, vì nó phát triển các cụm riêng biệt để cải thiện các mô hình đã được xác định trước, nhưng không luôn bắt đầu với số cụm cố định và không sử dụng cách tiếp cận này một cách cứng nhắc.
Mức 1 (mức cao nhất) có thể chỉ chứa 1 cell
Cell mức i-1 có thể tương ứng với 4 cell mức i
2.3.6 Phương pháp phân cụm có dữ liệu ràng buộc
Sự phát triển của PCDL không gian trên CSDL lớn đã mang lại nhiều công cụ hữu ích cho phân tích thông tin địa lý Tuy nhiên, hầu hết các thuật toán hiện có lại thiếu khả năng giúp người dùng xác định các ràng buộc thực tế cần được tuân thủ trong quá trình phân cụm.
PCDL tạo ra không gian hiệu quả hơn, tuy nhiên cần thực hiện thêm các nghiên cứu để trang bị cho người dùng khả năng kết hợp các ràng buộc trong thuật toán phân cụm.
Hiện nay, các phương pháp phân cụm đang được phát triển và ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau, dẫn đến sự hình thành của một số nhánh nghiên cứu mới dựa trên các phương pháp này.
Phân cụm thống kê là một nhánh nghiên cứu dựa trên các khái niệm phân tích thống kê, sử dụng các độ đo tương tự để phân loại các đối tượng Tuy nhiên, phương pháp này chỉ áp dụng cho dữ liệu có thuộc tính số.
Kỹ thuật phân cụm khái niệm được phát triển để áp dụng cho dữ liệu hạng mục, nhằm phân nhóm các đối tượng dựa trên các khái niệm mà chúng xử lý.
Các ứng dụng phân cụm dữ liệu
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 pha 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 là nơi 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ợ việc khai thác dữ liệu hiệu quả từ nguồn thông tin phong phú.
MỘT SỐ THUẬT TOÁN CƠ BẢN TRONG PHÂN CỤM DỮ LIỆU
Các thuật toán phân cụm phân hoạch
Thuật toán K-means, được MacQueen giới thiệu vào năm 1967, là một phương pháp phân hoạch trong thống kê, dựa trên việc đo khoảng cách giữa các đối tượng dữ liệu trong cụm Nó xác định khoảng cách đến giá trị trung bình của các dữ liệu trong cụm, được coi là trung tâm của cụm Thuật toán bắt đầu bằng cách khởi tạo một tập hợp các trung tâm cụm ban đầu, sau đó lặp lại các bước gán mỗi đối tượng vào cụm gần nhất và tính toán lại trung tâm của mỗi cụm dựa trên các gán mới Quá trình này tiếp tục cho đến khi các trung tâm cụm hội tụ.
Mục đích của thuật toán K-means là sinh k cụm dữ liệu {C1, C2, …, Ck} từ một tập dữ liệu chứa n đối tƣợng trong không gian d chiều Xi = { xi1 , xi2 ,
…, x id }, i = 1 n, sao cho hàm tiêu chuẩn: k i
2 đạt giá trị tối thiểu, trong đó m i là trọng tâm của cụm Ci, D là khoảng cách giữa hai đối tƣợng
Thuật toán K-means bao gồm các bước sau:
Input: Số cụm k và các trọng tâm cụm m j k j 1
Output: Các cụm C i (i = 1 , k ) và hàm tiêu chuẩn E đạt giá trị tối thiểu
1 ban đầu trong không gian R d (d là số chiều của dữ liệu) Việc lựa chọn này có thể là ngẫu nhiên hoặc theo kinh nghiệm
Bước 2: Tính toán khoảng cách cho từng điểm X_i (1 ≤ i ≤ n) đến các trọng tâm m_j (j = 1, k) Sau đó, xác định trọng tâm gần nhất cho mỗi điểm.
Bước 3: Cập nhật trọng tâm cho mỗi j = 1, k bằng cách tính trung bình cộng các vectơ đối tượng dữ liệu Điều kiện dừng sẽ được áp dụng sau khi hoàn thành quá trình này.
Lặp lại các bước 2 và 3 cho đến khi các trọng tâm của cụm không thay đổi
Độ phức tạp của thuật toán được xác định là O((3nkd) T flop), trong đó n là số lượng đối tượng dữ liệu đầu vào, k là số cụm dữ liệu, d là số chiều, và T flop là thời gian thực hiện một phép toán cơ bản như nhân hoặc chia.
K-means là một phương pháp phân tích cụm đơn giản, phù hợp cho các tập dữ liệu lớn Tuy nhiên, phương pháp này chỉ hiệu quả với dữ liệu số và thường phát hiện các cụm có hình dạng cầu Ngoài ra, K-means cũng rất nhạy cảm với nhiễu và các điểm dữ liệu ngoại lai.
Thuật toán K-Medoids có khả năng giảm thiểu ảnh hưởng của nhiễu bằng cách chọn đối tượng gần tâm cụm nhất làm đại diện cho cụm (medoid) Quy trình thực hiện thuật toán K-Medoids bao gồm các bước cụ thể để xác định và tối ưu hóa các medoid trong tập dữ liệu.
Bước 1: Chọn K đối tượng bất kỳ trong N đối tượng ban đầu làm các medoid ban đầu
Bước 2: Lặp cho tới khi hội tụ
Gán mỗi đối tƣợng còn lại vào cụm có medoid gần nhất với nó
Thay thế medoid hiện tại bằng một đối tượng không phải medoid có thể cải thiện chất lượng phân cụm Chất lượng này được đánh giá thông qua hàm chi phí, sử dụng hàm tính độ phi tương tự giữa đối tượng và medoid của cụm chứa đối tượng đó.
K-medoid tỏ ra hiệu quả hơn K-means trong trường hợp dữ liệu có nhiễu hoặc đối tƣợng ngoại lai (Outlier) Nhƣng so với K-means thì K-
Medoid có độ phức tập tính toán cao hơn Cả hai thuật toán trên đều có nhƣợc điểm chung là số lượng cụm k được cung cấp bởi người dùng
Ngoài thuật toán K-means và K-Medoid, phân cụm phân hoạch còn bao gồm một số thuật toán khác nhƣ: thuật toán PAM, thuật toán CLARA, …
Thuật toán phân cụm phân cấp
Thuật toán CURE khắc phục hiệu quả vấn đề phân cụm với các phần tử ngoại lai, điều mà hầu hết các thuật toán khác không làm được Nó định nghĩa một số điểm đại diện cố định, được chọn để mô tả các cụm trong không gian dữ liệu Các điểm này được tạo ra bằng cách lựa chọn các đối tượng nằm rải rác và sau đó di chuyển chúng về trung tâm cụm thông qua nhân tố co cụm Quá trình này được lặp lại, cho phép đo tỉ lệ gia tăng của cụm Tại mỗi bước, hai cụm có các điểm đại diện gần nhau sẽ được hòa nhập, giúp cải thiện độ chính xác của phân cụm.
Thuật toán CURE cho phép khám phá các cụm có hình dạng không phải hình cầu bằng cách đại diện nhiều điểm cho mỗi cụm Việc co lại các cụm giúp giảm thiểu tác động của các phần tử ngoại lai, cho phép thuật toán xử lý hiệu quả trong trường hợp có phần tử ngoại lai và các hình dạng cũng như kích thước khác nhau Hơn nữa, CURE còn tỉ lệ tốt với cơ sở dữ liệu lớn mà không làm giảm chất lượng phân cụm.
CURE sử dụng mẫu ngẫu nhiên để xử lý các cơ sở dữ liệu lớn, phân cụm từng phần dữ liệu và sau đó thực hiện phân cụm lần thứ hai để tạo ra các cụm con mong muốn Tuy nhiên, mẫu ngẫu nhiên không luôn đảm bảo mô tả đầy đủ cho toàn bộ tập dữ liệu.
Thuật toán CURE được thực hiện qua các bước cơ bản với độ phức tạp tính toán O(n² log(n)) Đây là một thuật toán tin cậy trong việc khám phá các cụm có hình thù bất kỳ, đặc biệt hiệu quả với dữ liệu có phần tử ngoại lai và trên các tập dữ liệu hai chiều Tuy nhiên, CURE rất nhạy cảm với các tham số như số lượng đối tượng đại diện và tỷ lệ co của các phần tử đại diện.
Chọn một mẫu ngẫu nhiên S từ tập dữ liệu ban đầu
Phân hoạch mẫu S thành p nhóm dữ liệu có kích thước bằng nhau là một phương pháp quan trọng, trong đó mỗi nhóm sẽ có kích thước n’/p, với n’ là kích thước tổng thể của mẫu.
Phân cụm các điểm của mỗi nhóm: thực hiện PCDL cho các nhóm cho đến khi mỗi nhóm đƣợc phân thành n’/pq cụm (với q>1)
Loại bỏ các phần tử ngoại lai là bước đầu tiên trong quá trình hình thành cụm, nhằm giảm số lượng cụm xuống một phần so với ban đầu Sau đó, nếu các phần tử ngoại lai được lấy mẫu trong quá trình khởi tạo mẫu dữ liệu, thuật toán sẽ tự động loại bỏ các nhóm nhỏ.
Phân cụm không gian là quá trình mà các đối tượng trong cụm di chuyển về phía trung tâm của cụm, nhằm thay thế bằng các đối tượng gần hơn với trung tâm Đồng thời, việc đánh dấu dữ liệu với các nhãn tương ứng là cần thiết để xác định rõ ràng các cụm này.
Ngoài thuật toán CURE ra, phân cụm phân cấp còn bao gồm một số thuật toán khác nhƣ: thuật toán BIRCH, thuật toán AGNES, thuật toán
DIANA, thuật toán ROCK, thuật toán CHANMELEON
Thuật toán COP-Kmeans là một thuật toán phân cụm dữ liệu nửa giám sát, với phương pháp tiếp cận dựa trên tìm kiếm Trong thuật toán COP-
Kmeans (Wagstaff đề xuất năm 2001), các thông tin bổ trợ đƣợc cung cấp dưới dạng một tập các ràng buộc must-link và cannot-link
Must-link: hai đối tƣợng dữ liệu phải cùng nằm trong một cụm
Cannot-link: hai đối tƣợng dữ liệu phải khác cụm với nhau
Các rằng buộc này đƣợc áp dụng vào trong suốt quá trình phân cụm
Nhằm điều hướng quá trình phân cụm để đạt được kết quả phân cụm theo ý muốn Thuật toán COP-Kmeans đƣợc thực hiện nhƣ sau:
- Tập các đối tƣợn dữ liệu X = {x 1 ,…,x n }, x1 R d
- Tập ràng buộc must-link và cannot-link
- K phân hoạch tách rời: X h K h 1 của X sao cho hàm mục tiêu đƣợc tối ƣu
1 Khởi tạo các cụm: các tâm ban đầu đƣợc chọn ngẫu nhiên sao cho không vi phạm ràng buộc đã cho
2 Lặp cho tới khi hội tụ
- Gán cụm: gán mỗi đối tƣợng dữ liệu vào trong cụm gần nhất sao cho không vi phạm ràng buộc
- Ƣớc lƣợng tâm: cập nhật lại tâm là trung bình của tất cả đối tƣợng nằm trong cụm của tâm đó
CHƯƠNG 4: ỨNG DỤNG THUẬT TOÁN K-MEANS CHO
Tổng quan về phân vùng ảnh
Phân vùng ảnh là bước quan trọng trong xử lý ảnh, giúp phân tích hình ảnh thành các thành phần có đặc tính tương đồng Giai đoạn này sử dụng các tiêu chuẩn như mức xám, màu sắc hoặc độ nhám để xác định các vùng liên thông trong ảnh.
Kỹ thuật phân vùng có thể được chia thành nhiều loại, trong đó phân vùng theo miền đồng nhất sử dụng các miền liên thông, trong khi phân vùng biên tập trung vào các đường biên Bên cạnh đó, còn tồn tại các kỹ thuật khác như phân vùng dựa vào biên độ và phân vùng theo kết cấu (Texture Segmentation).
Phân tích ảnh nhằm mục đích cung cấp một mô tả tổng quát về các thành phần cấu thành ảnh thô Do lượng thông tin trong ảnh rất lớn, trong khi hầu hết các ứng dụng chỉ cần một số thông tin đặc trưng cụ thể, nên cần thiết phải thực hiện quá trình giảm thiểu thông tin khổng lồ này.
Quá trình này bao gồm việc phân vùng ảnh và trích xuất các đặc tính chính, với các kỹ thuật áp dụng sẽ được trình bày ở phần sau.
4.1.1 Phân vùng ảnh theo ngƣỡng biên độ Đặc tính đơn giản nhất và có hữu ích của ảnh đó là biên độ của các tính chất vật lý của ảnh nhƣ: độ phản xạ, độ truyền sáng, màu sắc hoặc đáp ứng đa phổ Thí dụ, trong ảnh X-quang, biên độ mức xám biểu diễn đặc tính bão hòa của các phần hấp thụ của cơ thể làm cho ta có khả năng phân biệt xương với các phần mềm, tế bào lành với các tế bào bị nhiễm bệnh, v v
Kỹ thuật phân ngưỡng theo biên độ đóng vai trò quan trọng trong việc xử lý ảnh nhị phân Quy trình thường được thực hiện qua các bước cơ bản sau:
Xem xét lược đồ xám của ảnh giúp xác định các đỉnh và khe Nếu ảnh có hình dạng rắn lưỡng (nhiều đỉnh và nhiều khe), các khe này có thể được sử dụng để lựa chọn ngưỡng.
Chọn ngưỡng t sao cho một phần xác định trước của tổng số mẫu thấp hơn t, và điều chỉnh ngưỡng dựa trên việc phân tích lược đồ xám của các điểm lân cận.
Chọn ngưỡng phù hợp để xem xét lược đồ xám của các điểm đạt tiêu chuẩn lựa chọn Ví dụ, đối với hình ảnh có độ tương phản thấp, lược đồ của những điểm có biên độ Laplace g(m, n) lớn hơn giá trị t định trước sẽ được xác định.
5% đến 10% số điểm ảnh với gradient lớn nhất sẽ coi nhƣ biên) sẽ cho phép xác định các đặc tính ảnh lƣỡng cực tốt hơn ảnh gốc
Khi làm việc với mô hình phân lớp xác suất, việc xác định ngưỡng là cần thiết để tối thiểu hóa xác suất sai số hoặc các đặc tính khác theo quy tắc Bayes.
4.1.2 Phân vùng ảnh theo miền đồng nhất
Kỹ thuật phân vùng ảnh thành các miền đồng nhất dựa vào các tính chất quan trọng như mức xám, màu sắc, kết cấu sợi và chuyển động Việc lựa chọn các tính chất này sẽ xác định tiêu chuẩn phân vùng, trong đó tính đồng nhất của miền ảnh là yếu tố quyết định hiệu quả của quá trình phân vùng.
Trong ứng dụng ảnh hàng không, phân vùng theo màu giúp phân biệt các loại thảm thực vật như cánh đồng xanh, rừng xanh thẫm, đường xá màu xám và mái nhà đỏ Đối với ảnh chuyển động, quá trình trừ hai ảnh chụp tại hai thời điểm khác nhau cho phép xác định các phần không thay đổi với giá trị không, trong khi các phần thay đổi sẽ nhận giá trị dương hoặc âm tương ứng với sự thay đổi hoặc dịch chuyển.
Các phương pháp thực hiện đó là:
Phương pháp tách cây tứ phân
Phương pháp này kiểm tra tính hợp lệ của tiêu chuẩn trên toàn bộ miền của ảnh Nếu tiêu chuẩn được thỏa mãn, quá trình phân đoạn sẽ hoàn tất Ngược lại, miền đang xét sẽ được chia thành bốn miền nhỏ hơn, và phương pháp sẽ được áp dụng đệ quy cho từng miền nhỏ cho đến khi tất cả các miền đều đáp ứng tiêu chuẩn.
Phương pháp cục bộ hay phân vùng bởi hợp là kỹ thuật phân đoạn ảnh dựa trên việc xem xét các miền nhỏ nhất và hợp chúng lại thành các miền đồng nhất lớn hơn nếu đáp ứng tiêu chuẩn nhất định Quá trình này tiếp tục cho đến khi không còn khả năng hợp các miền nữa, và số miền còn lại sẽ cho kết quả phân đoạn cuối cùng Bước khởi đầu của phương pháp này là điểm ảnh, và nguyên lý quan trọng nhất là việc hợp hai vùng dựa trên các tiêu chí nhất định.
Hai vùng phải đáp ứng tiêu chuẩn, thí dụ nhƣ cùng màu hoặc cùng mức xám
Chúng phải kế cận nhau
Hai phương pháp vừa đề cập có một số nhược điểm Phương pháp tách sẽ hình thành một cấu trúc phân cấp và thiết lập mối quan hệ giữa các vùng.
Tuy nhiên nó thực hiện việc chia quá chi tiết
Thuật toán K-means cho phân đoạn ảnh
Việc gom nhóm các đối tượng mang tính tri giác của con người trong lĩnh vực thị giác máy tính, đặc biệt là xử lý ảnh, đã được nghiên cứu sâu rộng Phân đoạn ảnh có ứng dụng mạnh mẽ trong phân tích và hiểu ảnh tự động, nhưng vẫn là một bài toán khó mà các nhà khoa học chưa giải quyết triệt để Câu hỏi đặt ra là làm thế nào để chia một ảnh thành các tập con và những phương pháp khả thi nào có thể áp dụng để đạt được điều này.
Trong 30 năm qua, nhiều thuật toán đã được phát triển để giải quyết bài toán phân đoạn ảnh, chủ yếu dựa vào hai thuộc tính chính của điểm ảnh: sự khác biệt (dissimilarity) và sự tương đồng (similarity) Các phương pháp dựa trên sự tương đồng được gọi là phương pháp miền (region-based methods), trong khi các phương pháp dựa trên sự khác biệt được gọi là phương pháp biên (boundary-based methods) Bài báo cáo này sẽ trình bày thuật toán K-means như một giải pháp cho vấn đề phân đoạn ảnh.
Số cụm (k) muốn phân đoạn
Output: Ảnh được phân thành k đoạn có màu sắc tương đồng nhau
4.2.2 Các bước thực hiện chính trong thuật toán
Thuật toán sẽ xác định số lượng cụm mong muốn và trọng tâm của các cụm, từ đó tính toán khoảng cách giữa các điểm và các trọng tâm cụm Các điểm sẽ được gán vào cụm có khoảng cách nhỏ nhất đến trọng tâm của nó, sau đó cập nhật lại trọng tâm cụm Kết quả cuối cùng đạt được khi trọng tâm của các cụm không còn thay đổi.
Lưu đồ tổng quát của thuật toán:
4.2.2.1 Tìm kiếm Top X color Đầu tiên ta so sánh số màu thực tế có trong ảnh và số cụm màu, nếu số màu thực tế nhỏ hơn số cụm màu thì ta nhận số cụm màu chính là số màu thực tế Tạo danh sách chứa các loại màu, sau đó sắp xếp chúng theo thứ tự giảm dần Lấy X phần tử đầu tiên của danh sách
Tìm Top X color gán làm trọng tâm
2 Đƣa các điểm về các cụm Cập nhật lại tâm các cụm
Hình 4 2: Tìm kiếm Top X color
_topColours[i] = Color.FromArgb (summaryList[i].Value.Colour.R, summaryList[i].Value.Colour.G, summaryList[i].Value.Colour.B); i ++; int i = 0; int numColours; colours.Count; Đọc ảnh colours.Count
List summaryList = new List; summaryList.AddRange(colours); summaryList.Sort;
Trọng tâm khởi tạo cụm
4.2.2.2 Tính khoảng cách và phân cụm
Thuật toán Euclide được sử dụng để tính khoảng cách màu giữa các điểm và các tâm cụm Dựa vào khoảng cách này, các điểm sẽ được phân loại vào cụm mà chúng có khoảng cách nhỏ nhất tới tâm cụm.
Allocation.Contai nsKey(list[0].Key)
_currentCluster float d= (float)Math.Sqrt((double)Math.Pow ((c.Value.CentroidR -pd.Ch1), 2)+ double) Math.Pow((c.Value.CentroidG-pd.Ch2),2)+
(double)Math.Pow((c.Value CentroidB- pd.Ch3),2)); distances Add(c Key, new Distance(d)); c ++ ;
List list = new List; list AddRange(distances) ; list Sort ;
((List)_pixelDataClust erAllocation[list[0].Key]).Add(pd);
List clrList = new List; clrList add(pd);
_pixelDataClusterAllocation Add(list[0] Key, clrList);
4.2.2.3 Tính lại trọng tâm cụm
Hình 4 4: Tính trọng tâm mới
_currentCluster List clrList=(List)
_pixelDataClusterAllocation[cluster.Key]; float cR=0, cG=0, cB=0;
To update the cluster's centroid values, calculate the new centroid for each color channel by averaging the existing centroid with the new color values (cR, cG, cB) and dividing by the total count of colors plus one Increment the cluster counter after updating the centroid values.
< clrList cR += clr.Ch1; cG += clr.Ch2; cB += clr.Ch3;
_clusterColours.Add(clr.Name, Color.FromArgb((int)cluster.Value
CentroidR,(int)cluster.Value.CentroidG, (int)cluster.Value.CentroidB));
4.2.2.4 Kiểm tra hội tụ Để kiểm tra tính hội tụ của dữ liệu chúng ta kiểm tra trọng tâm hiện tại vừa tính được với trọng tâm trước đó của cụm
Hình 4 5: Kiểm tra hội tụ
Trọng tâm mới bool match = true ;
Chương trình được lập trình với ngôn ngữ C#, cài đặt và chạy thử nghiệm trên môi trường hệ điều hành Windows XP
Giao diện khởi động Đƣa dữ liệu vào
Quá trình xử lý dữ liệu