TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU
Giới thiệu về khám phá tri thức
Các điện từ và sóng điện từ là nền tảng của công nghệ điện từ truyền thống, trong khi dữ liệu, thông tin và tri thức hiện đang trở thành trọng tâm trong nghiên cứu và ứng dụng phát hiện tri thức cũng như khai phá dữ liệu.
Dữ liệu thường được hiểu là một chuỗi bit, số liệu và ký hiệu, hoặc các đối tượng mang ý nghĩa khi được gửi đến chương trình dưới 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 và lọc bỏ thừa, nhằm đặc trưng hóa cơ bản cho dữ liệu Tri thức có thể được xem như là thông tin tích hợp, bao gồm các thông tin và mối quan hệ có thể 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 với mức độ trừu tượng và tổ chức cao hơn.
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 tiêu chí như hợp lệ, mới mẻ, hữu ích và dễ hiểu Khai phá dữ liệu là một bước quan trọng trong quy trình này, sử dụng các thuật toán chuyên biệt để phát hiện các mẫu trong dữ liệu theo các tiêu chuẩn về hiệu quả tính toán Mục tiêu chính của cả hai quy trình là tìm ra những mẫu và mô hình tiềm ẩn trong các cơ sở dữ liệu, giúp giải mã những thông tin quý giá bị ẩn giấu trong khối lượng dữ liệu lớn.
Quy trình khám phá tri thức như sau:
Hình 1: Quy trình phát hiện tri thức
Bước đầu tiên trong quy 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 những 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ư bản chất của dữ liệu.
Bước 2 trong quy trình khám phá 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ý các vấn đề về thiếu dữ liệu, biến đổi và rút gọn dữ liệu cần thiết Thời gian dành cho bước này thường chiếm phần lớn trong toàn bộ quy trình.
- Bước 3: 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 4: Nắm vững tri thức đã thu thập, đặc biệt là làm rõ các mô tả và dự đoán Các bước trước đó có thể được thực hiện nhiều lần, và kết quả thu được có thể được tính trung bình từ tất cả các lần thực hiện.
Hình thành và định nghĩa bài toán
Thu thập và tiền xử lý dữ liệu
Khai thác 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
Khai phá dữ liệu và các khái niệm liên quan
Khai phá dữ liệu là quy trình phân tích nhằm khám phá khối 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 các giai đoạn cơ bản: thăm dò, xây dựng mô hình hoặc định nghĩa mẫu, hợp thức hóa và kiểm chứng kết quả.
1.2.1 Khái niệm khai phá dữ liệu
Trong hơn một thập kỷ qua, lượng thông tin lưu trữ trên các thiết bị điện tử đã tăng lên với tốc độ bùng nổ Điều này đặt ra câu hỏi về khả năng khai thác giá trị từ "núi" dữ liệu khổng lồ này, dẫn đến sự ra đời của khái niệm "khai phá dữ liệu".
Khai phá dữ liệu là quá trình phát hiện tri thức từ cơ sở dữ liệu, giúp rút ra những thông tin tiềm ẩn nhằm hỗ trợ dự báo trong kinh doanh và sản xuất Phương pháp này không chỉ tăng cường hiệu quả mà còn giảm thiểu chi phí thời gian so với các phương pháp truyền thống trước đây.
Khai phá dữ liệu là quá trình hỗ trợ ra quyết định bằng cách khám phá các mẫu thông tin hữu ích, chưa được biết đến và bất ngờ trong cơ sở dữ liệu lớn.
Khai phá dữ liệu là một bước chính quan trọng và mang tính quyết định trong quá trình KDD
1.2.2 Các bước trong quá trình khai phá dữ liệu
Quá trình khai phá dữ liệu gồm các bước như sau:
Hình 2: Các bước trong khai phá dữ liệu
- Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết
- Xác định các dữ liệu liên quan dùng để xây dựng giải pháp giải quyết nhiệm vụ bài toán
- Thu thập các dữ liệu có liên quan và xử lý chúng thành dạng sao cho giải thuật khai phá dữ liệu có thể hiểu được
Chọn thuật toán khai phá dữ liệu phù hợp để tìm ra các mẫu có ý nghĩa mới mẻ, được đánh giá dựa trên sự thay đổi trong dữ liệu hoặc tri thức liên quan Độ mới của mẫu thường được đo bằng hàm logic hoặc hàm đo độ mới, độ bất ngờ Bên cạnh đó, các mẫu cần có tiềm năng sử dụng, dẫn đến những hành động hữu ích, được đánh giá qua hàm lợi ích, như trong trường hợp dữ liệu khoản vay, nơi hàm lợi ích giúp tăng lợi nhuận từ các khoản vay.
Thu thập và tiền xử lý dữ liệu
Xác định dữ liệu liên quan
Dữ liệu trực tiếp Mẫu vay Mẫu khai thác được phải có giá trị đối với các dữ liệu mới với độ chính xác nào đó
1.2.3 Các thành phần trong khai phá dữ liệu
Giải thuật khai phá dữ liệu bao gồm 3 thành phần chính như sau: biểu diễn mô hình, kiểm định mô hình và phương pháp tìm kiếm
Mô hình cần được biểu diễn bằng một ngôn ngữ có khả năng khai thác, vì nếu mô tả bị hạn chế, việc học và tạo ra mẫu sẽ gặp khó khăn Mặc dù mô tả mô hình phong phú có thể giúp tăng cường hiểu biết, nhưng nó cũng làm tăng nguy cơ học quá mức, dẫn đến khả năng dự đoán dữ liệu chưa biết giảm sút Hơn nữa, việc tìm kiếm và giải thích mô hình trong trường hợp này sẽ trở nên phức tạp hơn.
Kiểm định mô hình là quá trình đánh giá khả năng của một mẫu trong việc đáp ứng các tiêu chuẩn của quá trình phát hiện tri thức Để thực hiện việc này, cần kiểm tra dữ liệu, đặc biệt trong các nhiệm vụ dự đoán, ngoài việc kiểm tra dữ liệu, độ chính xác của dự đoán cũng phải được xem xét Đánh giá độ chính xác này thường dựa trên phương pháp đánh giá chéo.
- Tìm kiếm mô hình: Bao gồm tìm kiếm theo số và tìm kiếm theo mô hình
Quá trình tối ưu hóa mô hình bao gồm hai bước chính: tìm kiếm theo số và tìm kiếm mô hình Trong tìm kiếm theo số, thuật toán sẽ xác định các tham số để cải thiện các tiêu chí đánh giá mô hình dựa trên dữ liệu quan sát và mô hình đã định Tiếp theo, tìm kiếm mô hình diễn ra như một vòng lặp, trong đó mô hình được điều chỉnh để tạo ra một tập hợp các mô hình khác nhau Mỗi mô hình mới sẽ sử dụng phương pháp tìm kiếm tham số để đánh giá chất lượng của nó Để vượt qua thách thức về kích thước không gian mô hình, các phương pháp tìm kiếm mô hình thường áp dụng các kỹ thuật tìm kiếm heuristic.
1.2.4 Các hướng tiếp cận và kỹ thuật áp dụng trong khai phá dữ liệu
Khai phá dữ liệu là một lĩnh vực đa dạng với nhiều hướng nghiên cứu và bài toán khác nhau Các phương pháp tiếp cận chính trong khai phá dữ liệu bao gồm phân tích, mô hình hóa và dự đoán, giúp khám phá và tận dụng thông tin từ tập dữ liệu lớn.
Phân lớp và dự đoán trong học có giám sát là quá trình xây dựng mô hình nhằm phân loại các đối tượng thành những lớp khác nhau Mục tiêu của phân lớp dữ liệu là dự đoán giá trị bị thiếu ở một số thuộc tính hoặc dự đoán giá trị của dữ liệu trong tương lai.
Phân cụm dữ liệu là một kỹ thuật khai phá dữ liệu tương tự như phân lớp, nhưng khác biệt ở chỗ đây là quá trình học không giám sát Quá trình này nhằm nhóm các đối tượng vào các lớp tương ứng, sao cho các đối tượng trong cùng một nhóm có sự tương đồng cao, trong khi khác biệt với các đối tượng thuộc nhóm khác.
Luật kết hợp là quá trình phát hiện các tập giá trị thuộc tính xuất hiện thường xuyên trong dữ liệu Từ những tập giá trị phổ biến này, chúng ta có thể xây dựng các luật kết hợp giữa các thuộc tính trong các đối tượng dữ liệu.
Khai phá chuỗi theo thời gian là quá trình phân tích nhằm tìm ra các mẫu trong tập dữ liệu rời rạc, nơi chuỗi được hình thành từ các giá trị rời rạc Phân tích chuỗi theo thời gian và khai phá luật kết hợp có nhiều điểm tương đồng, nhưng phân tích chuỗi theo thời gian còn bao gồm yếu tố thứ tự và thời gian, giúp phát hiện các mối quan hệ và xu hướng trong dữ liệu.
Phân tích ngoại lệ là một hình thức phân cụm, tập trung vào những trường hợp đặc biệt khác biệt so với các trường hợp thông thường Nó không chỉ giúp phát hiện lỗi trong dữ liệu mà còn làm nổi bật những điểm thú vị nhất trong tập dữ liệu đó.
Hồi quy là phương pháp dự báo dựa trên dữ liệu hiện có thông qua việc áp dụng các công thức Kỹ thuật hồi quy và tuyến tính sẽ giúp học ra một hàm từ bộ dữ liệu, từ đó sử dụng hàm này để đưa ra dự đoán cho dữ liệu mới.
1.2.5 Ứng dụng của khai phá dữ liệu
Phân cụm dữ liệu
Phân cụm dữ liệu là một trong những hướng nghiên cứu trọng tâm củalĩnh vực khai phá dữ liệu (Data Mining) và lĩnh vực khám phá tri thức
2.1.1 Định nghĩa về phân cụm dữ liệu
Mục đích của phân cụm là tổ chức các đối tượng thành những nhóm có sự tương đồng cao trong cùng một cụm, trong khi đó, độ bất tương đồng giữa các cụm lại lớn Điều này giúp cung cấp thông tin và tri thức hữu ích cho quá trình ra quyết định.
Phân cụm dữ liệu là quá trình chia nhỏ một tập dữ liệu ban đầu thành các nhóm, trong đó các phần tử trong cùng một nhóm có sự tương đồng cao, trong khi các phần tử thuộc các nhóm khác lại có sự khác biệt rõ rệt Số lượng các cụm dữ liệu có thể được xác định trước dựa trên kinh nghiệm hoặc được tự động xác định thông qua các phương pháp phân cụm.
Sau khi xác định các đặc tính của dữ liệu, việc tìm cách đo khoảng cách giữa các đối tượng trở nên cần thiết Các hàm đo sự giống nhau giữa các cặp đối tượng dữ liệu thường được sử dụng để tính độ tương tự hoặc độ phi tương tự Giá trị của hàm tính độ tương tự càng cao thì sự giống nhau giữa các đối tượng càng lớn, trong khi đó, hàm tính độ phi tương tự có mối quan hệ tỉ lệ nghịch với độ tương tự.
Trong quá trình phân cụm dữ liệu, nhiễu là vấn đề lớn nhất do thông tin thu thập không chính xác hoặc không đầy đủ Do đó, việc khử nhiễu là cần thiết để đảm bảo chất lượng phân tích dữ liệu.
Các bước chính trong quá trình phân cụm dữ liệu:
- Xây dụng hàm tính độ tương tự
- Xây dựng các tiêu chuẩn phân cụm
- Xây dụng mô hình cho cấu trúc cụm dữ liệu
- Xây dựng thuật toán phân cụm và các xác lập các điều kiện khởi tạo
- Xây dựng các thủ tục biểu diễn và đánh giá kết quả phân cụm
Phân cụm dữ liệu là một bài toán quan trọng trong lĩnh vực học máy không giám sát, được áp dụng phổ biến để khai thác thông tin từ dữ liệu.
2.1.2 Một số ví dụ về phân cụm dữ liệu
Phân cụm dữ liệu có thể được ứng dụng trong nhiều lĩnh vực của cuộc sống ví dụ như:
Trong lĩnh vực thương mại, việc xác định nhóm khách hàng quan trọng với những đặc điểm tương đồng là rất cần thiết Điều này có thể được thực hiện thông qua việc phân tích các bản ghi mua bán trong cơ sở dữ liệu khách hàng để tìm ra những đặc trưng chung của họ.
Phân cụm dữ liệu là một phương pháp phân tích quan trọng trong biểu diễn dữ liệu gene, thường được sử dụng để tổ chức và phân tích thông tin gen Dữ liệu gene được thu thập từ DNA microarray, một thiết bị chứa các đoạn DNA được sắp xếp thành các hàng siêu nhỏ trên bề mặt thủy tinh hoặc nhựa Tập hợp dữ liệu này có thể được trình bày dưới dạng ma trận giá trị thực, giúp dễ dàng hơn trong việc phân tích và trực quan hóa thông tin gen.
Dữ liệu biểu diễn gene sẽ được phân cụm theo hai phương pháp chính Phương pháp đầu tiên là nhóm các mẫu gene tương đồng, chẳng hạn như gom các dòng của ma trận D Phương pháp thứ hai là nhóm các mẫu khác biệt dựa trên các hồ sơ tương ứng, ví dụ như gom các cột của ma trận D.
Phân cụm dữ liệu trong lĩnh vực sức khỏe tâm lý đóng vai trò quan trọng trong việc thúc đẩy và duy trì sức khỏe, cải thiện hệ thống chăm sóc sức khỏe, cũng như công tác phòng chống bệnh tật và hỗ trợ người khuyết tật Công cụ này giúp xác định các nhóm dân cư có thể hưởng lợi từ các dịch vụ y tế cụ thể, từ đó tối ưu hóa hiệu quả của các chiến dịch quảng cáo sức khỏe Đồng thời, phân cụm dữ liệu cũng hỗ trợ việc nhận diện các nhóm có nguy cơ cao do tình trạng sức khỏe và điều kiện kinh tế, nhằm phát triển các giải pháp hỗ trợ phù hợp.
Phân cụm dữ liệu trong nghiên cứu thị trường là một phương pháp quan trọng để phân đoạn và xác định mục tiêu thị trường Bằng cách chia thị trường thành các cụm có ý nghĩa, như phân loại nam giới từ 21 đến 30 tuổi và nam giới trên 51 tuổi, chúng ta có thể nhận diện xu hướng tiêu dùng khác nhau Ví dụ, nam giới trên 51 tuổi thường ít có xu hướng mua sắm các sản phẩm mới, điều này giúp các doanh nghiệp định hình chiến lược marketing hiệu quả hơn.
Phân đoạn ảnh là quá trình phân tích mức xám hoặc màu sắc của hình ảnh thành các vùng đồng nhất Trong hoạt động này, phân cụm dữ liệu thường được áp dụng để phát hiện biên của các đối tượng trong ảnh.
Phân cụm dữ liệu là một vấn đề quan trọng và được quan tâm rộng rãi, mặc dù chưa có định nghĩa đồng bộ Về cơ bản, phân cụm dữ liệu liên quan đến việc nhóm các điểm dữ liệu lại với nhau dựa trên sự tương đồng, trong khi các điểm dữ liệu khác nhau sẽ được phân tách do sự không đồng dạng Vấn đề này có ứng dụng rộng rãi trong nhiều lĩnh vực như khai phá văn bản, biểu diễn gene, phân loại khách hàng và xử lý ảnh.
Một số kiểu dữ liệu trong phân cụm
Trong phân cụm dữ liệu, các đối tượng thường được mô tả qua các đặc tính hay thuộc tính, đóng vai trò quan trọng trong việc giải quyết vấn đề phân cụm Việc lựa chọn và phân loại các thuộc tính này có ảnh hưởng lớn đến kết quả phân cụm, giúp nhận diện sự khác biệt giữa các phần tử dữ liệu Các thuật toán phân cụm thường áp dụng một trong hai cấu trúc dữ liệu để tối ưu hóa quá trình phân tích.
1 Ma trận dữ liệu: Là mảng n hàng, p cột trong đó p là số thuộc tính của đối tượng, các phần tử trong mỗi hàng chỉ giá trịthuộc tính tương ứng của đối tượng đó Mảng được cho như sau:
2 Ma trận phi tương tự: Là ma trận n hàng, n cột, phần tử d(i,j) chứa khoảng cách hay độ khác biệt giữa đối tượng i,j; d(i,j) là một số không âm trong đó nếu d(i,j) xấp xỉ bằng 0 thì đối tượng i và j khá gần nhau, nếu d(i,j) càng lớn thì 2 đối tượng i và j khá khác nhau Do đó d(i,j)=d(j,i)=0 nên ta biểu diễn ma trận này như sau:
Phần lớn các thuật toán phân cụm dữ liệu sử dụng cấu trúc phi tương tự
Để tiến hành phân cụm dữ liệu, nếu dữ liệu được tổ chức dưới dạng ma trận, cần phải chuyển đổi nó sang dạng ma trận phi tương tự trước.
Có 2 đặc trưng để phân loại: kích thước miền và hệ đo Cho một cơ sở dữ liệu D chứa n đối tượng trong không gian k chiều; x, y, z là các đối tượng thuộc
D, với x=(x 1 , x 2 , x k ); y=(y 1 , y 2 , y k ); z=(z 1 , z 2 , z k ); trong đó x i, y i, z i 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 Như vậy nó sẽ có các kiểu dữ liệu sau:
2.2.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ó miền giá trị vô hạn không đếm được, cho phép tồn tại vô số giá trị giữa hai điểm Ví dụ về các thuộc tính này bao gồm màu sắc, cường độ, nhiệt độ và âm thanh.
Thuộc tính rời rạc có miền giá trị là tập vô hạn đếm được, ví dụ 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, hay on/off.
2.2.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 của thuộc tính nhị phân, với miền giá trị là 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, 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à thuộc tính định danh nhưng có thêm tính thứ tự nhưng chúng không được định lượng Nếu x và y là
2 thuộc tính thứ tự thì có thể xác định là x=y, xy, x>y, x y i, thì khoảng cách giữa x và y được tính 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 có ảnh hưởng lớn đến chất lượng phân cụm, vì đơn vị đo càng nhỏ thì khoảng cách xác định càng lớn, dẫn đến kết quả phân cụm bị ảnh hưởng nhiều hơn Để giảm thiểu sự phụ thuộc vào đơn vị đo, dữ liệu cần được chuẩn hóa, nhằm 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 ưu tiên Một phương pháp phổ biến để chuẩn hóa là biến đổi các thuộc tính về dạng không có đơn vị đo.
+ Tính độ lệnh trung bình:
Trong đó x 1f x nf là các 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:
+ Độ đo được chuẩn hóa:
- Thuộc tính nhị phân: Là thuộc tính có 2 giá trị là 0 và 1
- Thuộc 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 đã được trình bày, thuộc tính định danh và thuộc tính thứ tự được gọi chung 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 phân loại là thuộc tính số.
Phép đo độ tương tự và khoảng cách đối với các kiểu dữ liệu
2.3.1 Khái niệm tương tự và phi tương tự
Khi xác định các đặc tính của dữ liệu, cần tìm cách đo "khoảng cách" giữa các đối tượng, tức là phép đo sự tương tự giữa chúng Các hàm này thường dùng để tính độ tương tự (Similar) hoặc độ phi tương tự (Dissimilar) giữa các đối tượng dữ liệu Giá trị của hàm tương tự càng cao thì sự giống nhau giữa các đối tượng càng lớn, trong khi 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, thường được đo bằng khoảng cách giữa các đối tượng, và phụ thuộc vào kiểu thuộc tính đang phân tích Ví dụ, đối với thuộc tính hạng mục (Categorical), không sử dụng độ đo khoảng cách mà áp dụng một hướng hình học của dữ liệu.
Tất cả các độ đo được xác định trong không gian metric, trong đó thuật ngữ "độ đo" đề cập đến hàm tính độ tương tự hoặc độ phi tương tự Một không gian metric là tập hợp cho phép xác định khoảng cách giữa các cặp phần tử, tuân theo các tính chất của khoảng cách hình học Do đó, tập X bao gồm các đối tượng dữ liệu trong cơ sở dữ liệu D, mà mỗi phần tử có thể là bất kỳ đối tượng nào.
- 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 d(x, y), được gọi là khoảng cách giữa x và y
- Quy tắc trên thoả mãn hệ tính chất sau: i d( x,y) > 0 nếu x≠ y; 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 d(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
Thuộc tính khoảng : Sau khi chuẩn hoá, độ đo phi tương tự của hai đối tượng dữ liệu x, y được xác định bằng các metric khoảng cách như sau:
, ( ) n q q i i i d x y x y , với q là 1 số nguyên dương
, ( ) n i i i d x y x y , ( Trường hợp đặc biệt của Minskowski trong trường hợp q=2)
, n i i i d x y x y , ( 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 , M ax i n 1 x i y i , ( Đây là trường hợp của khoảng cách Minskowski trong trường hợp q )
Thuộc tính nhị phân: Trước hết chúng ta có xây dựng bản tham số sau: y:1 y:0 x:1 Α β α+β x:0 Γ δ γ+δ α+γ β+δ τ
Trong đó: τ=α+β+γ+δ, các đối tượng x, y mà tất cả các thuộc tính của nó đều là nhị phân biểu thị bằng 0 và 1 Bảng trên cho ta các thông tin sau:
- α là tổng số các thuộc tính có giá trị là 1 trong cả 2 đối tượng x,y
- β là tổng số các giá trị thuộc tính có giá trị là 1 trong x và 0 trong y
- γ là tổng số các giá trị thuộc tính có giá trị 0 trong x và 1 trong y
- δ là tổng số các giá trị thuộc tính có giá trị 0 trong x và y
Các phép đo độ tương tự đố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ả 2 đối tượng x và y có vai trò như nhau, nghĩa là chúng đối xứng và có trọng số
- Hệ số Jacard: d x y, , tham số này bỏ qua số các đối sánh giữa
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 trong dữ liệu vượt trội 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.
Độ đo phi tương tự giữa hai đối tượng x và y được xác định bằng công thức p m d x y p, trong đó m đại diện cho số lượng thuộc tính đối sánh tương ứng trùng nhau và p là tổng số thuộc tính.
Phép đo độ phi tương tự giữa các đối tượng dữ liệu với thuộc tính có thứ tự được thực hiện bằng cách sắp xếp các trạng thái của thuộc tính thứ tự M i trong miền giá trị [1… M i ] Mỗi giá trị của thuộc tính được thay thế bằng giá trị tương ứng r i, với i từ 1 đến M Do mỗi thuộc tính thứ tự có miền giá trị khác nhau, chúng ta cần chuyển đổi về miền giá trị [0,1] thông qua các phép biến đổi thích hợp cho từng thuộc tính.
Để tính độ phi tương tự của thuộc tính khoảng cách đối với các giá trị z_i (j), ta áp dụng công thức với M, trong đó i = 1…M Độ phi tương tự này phản ánh chính xác sự tương đồng của thuộc tính có giá trị.
Để tính độ tương tự giữa các thuộc tính tỉ lệ, có nhiều phương pháp khác nhau Một trong những cách hiệu quả là sử dụng công thức logarit cho mỗi thuộc tính x_i, cụ thể là q_i = log(x_i) Trong trường hợp này, q_i sẽ được xem như thuộc tính khoảng Phép biến đổi logarit này rất phù hợp khi giá trị của thuộc tính là số mũ.
Khi tính toán độ đo tương tự dữ liệu, người ta thường chỉ xem xét một phần các thuộc tính đặc trưng hoặc gán trọng số cho tất cả các thuộc tính dữ liệu Để cải thiện độ chính xác, đôi khi các đơn vị đo của các thuộc tính được loại bỏ thông qua việc chuẩn hoá hoặc gán trọng số cho mỗi thuộc tính dựa trên giá trị trung bình và độ lệch chuẩn Những trọng số này có thể được áp dụng trong các độ đo khoảng cách, trong đó độ tương tự dữ liệu được xác định dựa trên các trọng số tương ứng với từng thuộc tính.
Người dùng có khả năng chuyển đổi giữa các mô hình dữ liệu khác nhau, chẳng hạn như dữ liệu kiểu hạng mục có thể được chuyển đổi thành dữ liệu nhị phân và ngược lại Tuy nhiên, phương pháp này có thể tốn kém về mặt chi phí tính toán, vì vậy cần cân nhắc kỹ lưỡng trước khi áp dụng.
Tùy thuộc vào từng trường hợp dữ liệu cụ thể, các mô hình tính độ tương tự sẽ được sử dụng khác nhau Việc xác định độ tương tự dữ liệu một cách chính xác và khách quan là rất quan trọng, góp phần vào việc xây dựng thuật toán PCDL hiệu quả, đồng thời đảm bảo chất lượng và tối ưu chi phí tính toán.
Các hướng tiếp cận của bài toán phân cụm dữ liệu
Các phương pháp phân cụm được phân loại thành nhiều nhóm khác nhau, bao gồm phương pháp phân hoạch, phân cấp, dựa trên mật độ, dựa trên lưới, mô hình và ràng buộc.
2.4.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 là kỹ thuật dùng để chia một tập dữ liệu gồm n phần tử trong cơ sở dữ liệu D thành K nhóm dữ liệu Mỗi cụm phải chứa ít nhất một đối tượng và mỗi đối tượng chỉ thuộc về một cụm duy nhất Giá trị K là số lượng cụm đã được xác định trước.
Các thuật toán phân hoạch dữ liệu đối mặt với độ phức tạp cao trong việc xác định nghiệm tối ưu toàn cục cho vấn đề phân công dữ liệu lớn (PCDL), vì chúng cần khám phá tất cả các khả năng phân hoạch có thể.
Một số thuật toán phân cụm phân hoạch điển hình như: K - MEANS, PAM, CLARA, CLARANS
2.4.2 Phương pháp phân cụm phân cấp
Phân cụm dữ liệu phân cấp tổ chức một tập dữ liệu thành cấu trúc cây thông qua kỹ thuật đệ quy Có hai phương pháp chính để xây dựng cây phân cấp: phương pháp trên xuống (Top-down) và phương pháp dưới lên (Bottom-up) Các phương pháp này tập trung vào việc tạo ra phân cấp cụm mà không cần xác định số lượng cụm ban đầu, vì số cụm sẽ được quyết định bởi khoảng cách giữa các cụm hoặc điều kiện dừng Tiêu chuẩn để gom cụm thường dựa vào ma trận khoảng cách Cấu trúc phân cấp này thường được thể hiện dưới dạng đồ thị cây, trong đó lá cây đại diện cho các đối tượng riêng lẻ và các nút bên trong biểu thị cho các cụm.
Quá trình gộp bắt đầu bằng cách xuất phát từ mỗi đối tượng và tạo thành một cụm chứa nó Nếu hai cụm gần nhau, chúng sẽ được gộp lại thành một cụm duy nhất Quá trình này tiếp tục lặp lại cho đến khi chỉ còn lại một cụm duy nhất, đại diện cho toàn bộ không gian.
Để tách cụm, bắt đầu từ toàn bộ không gian dữ liệu và chọn cụm có độ phân biệt cao nhất để thực hiện tách đôi Áp dụng các phương pháp phân hoạch cho cụm đã chọn và lặp lại quá trình này cho đến khi mỗi đối tượng được phân vào một cụm riêng biệt hoặc đạt được điều kiện dừng.
Bước Bước Bước Bước Bước
Bước Bước Bước Bước Bước
Hình 3: Hai phương pháp tiếp cận phân cấp
Các khoảng cách giữa các cụm thường dùng là: a b c d e a b d e c d e a b c d e
Khoảng cách nhỏ nhất, hay còn gọi là khoảng cách liên kết đơn, là phương pháp hiệu quả để phát hiện các cụm có dạng chuỗi thay vì dạng khối Định nghĩa khoảng cách này được thể hiện qua công thức d(Ci, Cj) = min x Ci, y Cj {d(x,y)}, cho phép xác định khoảng cách gần nhất giữa các điểm trong hai cụm.
Khoảng cách lớn nhất, hay còn 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 này được xác định bởi d(Ci, Cj) = max x∈Ci, y∈Cj {d(x,y)}.
- Khoảng cách trung bình: d(C i ,C j ) = avg x Cj, 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 sử dụng để 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 giúp tăng tốc độ tính toán nhờ vào việc chỉ tập trung vào trọng tâm, từ đó giảm thiểu khối lượng tính toán cần thiết.
Một số thuật toán phân cụm phân cấp điển hình như: CURE, BIRCH,…
2.4.3 Phương pháp phân cụm dựa trên mật độ
Phương pháp này phân nhóm các đối tượng dựa trên hàm mật độ xác định, với mật độ được hiểu là số lượng đối tượng lân cận của một đối tượng dữ liệu theo ngưỡng cụ thể Khi một cụm dữ liệu đã được xác định, nó có thể mở rộng thêm các đối tượng dữ liệu mới, miễn là số lượng lân cận của các đối tượng này vượt qua ngưỡng đã được thiết lập trước.
Các kí hiệu và khái niệm:
1 p, q, o là các điểm dữ liệu bất kỳ (các đối tượng)
2 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
Min Pts là số nguyên dương được xác định trước, đóng vai trò là ngưỡng tối thiểu để xác định một điểm là trù mật Khi đề cập đến một điểm là hạt nhân, chúng ta hiểu rằng nó liên quan đến một bán kính cụ thể và một ngưỡng trù mật nhất định.
4 p được gọi là điểm biên nếu nó không phải là điểm nhân
5 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 thuộc lân cận của p
6 p n được gọi là đi tới được theo mật độ từ p1 nếu tồn tại một dãy các điểm pi (i = 2, …n) sao cho pi liên thông mật độ trực tiếp từ pi+1
7 p và q được gọi là có kết nối theo mật độ nều tồn tại điểm o sao cho cả p và q đều liên thông mật độ từ o
Hình 4 mô tả điểm hạt nhân p với bán kính Eps 1cm và ngưỡng trù mật min Pts là 3 Khoảng cách được sử dụng là khoảng cách Euclide trong không gian hình học hai chiều, trong đó q là một điểm liên thông mật độ trực tiếp từ p.
Hình 5: q là một điểm liên thông mật độ từ p min Pts = 3
Các thuật toán dựa trên mật độ cho rằng một cụm bao gồm một tập hợp tối đại các điểm có sự kết nối mật độ, trong đó p và q là hai điểm thể hiện mối liên hệ này.
Thuật toán DBSCAN có các bước sau:
1 Chọn một điểm p bất kỳ thuộc không gian dữ liệu D
2 Tìm tập P gồm tất cả các điểm liên thông mật độ từ p với ngưỡng bán kính Eps và ngưỡng mật độ Pts
3 Nếu p là một điểm hạt nhân thì a P chính là một cụm cần tìm b D = D \ P (loại P ra khỏi D)
4 Quay lại bước 1 cho đến khi tất cả các điểm trong D đều đã được xét
5 Các điểm đã xét nhưng không thuộc cụm nào thì chính là các mẫu cá biệt Ưu điểm của DBSCAN là tìm được các cụm từ có hình dạng bất kỳ do nhiễu hoặc mẫu khác biệt gây ra
Khuyết điểm của thuật toán DBSCAN là việc lựa chọn các ngưỡng EPs và min Pts gặp khó khăn, dẫn đến kết quả gom cụm không hiệu quả khi mật độ trong các cụm tự nhiên có sự chênh lệch lớn Thêm vào đó, DBSCAN không phù hợp cho việc phân cấp cụm, mà chỉ đáp ứng nhu cầu phân hoạch đơn giản.
Một số thuật toán phân cụm dữ liệu
2.5.1 Các thuật toán phân cụm phân hoạch
Thuật toán k-means, được đề xuất bởi MacQueen trong lĩnh vực thống kê vào năm 1967, là một phương pháp phân hoạch dựa trên độ đo khoảng cách giữa các đối tượng trong cụm Thuật toán này xác định khoảng cách tới giá trị trung bình của dữ liệu trong cụm, được coi là trung tâm của cụm Để bắt đầu, cần khởi tạo một tập trung tâm các 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 từng cụm dựa trên gán mới Quá trình lặp này sẽ dừng lại khi các trung tâm cụm hội tụ Mục tiêu của k-means là tạo ra k cụm {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, , xid).
1 i n), sao cho hàm tiêu chuẩn: 2
K-means là một phương pháp phân tích cụm đơn giản, giúp xác định các cụm trong dữ liệu lớn, với trọng tâm của mỗi cụm được ký hiệu là m i và khoảng cách giữa các đối tượng là D Tuy nhiên, phương pháp này chỉ phù hợp với dữ liệu có thuộc tính số và thường chỉ phát hiện các cụm có hình dạng cầu Một nhược điểm lớn của K-means là sự nhạy cảm với nhiễu và các phần tử ngoại lai trong dữ liệu, điều này có thể ảnh hưởng đến độ chính xác của kết quả phân tích.
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 Quy trình thực hiện thuật toán này bao gồm các bước cụ thể để xác định và tối ưu hóa các tâm cụm.
+ Chọn k đối tượng bất kỳ trong n đối tượng ban đầu làm các medoids ban đầu
Lặp lại quá trình cho đến khi đạt được sự hội tụ bằng cách gán mỗi đối tượng vào cụm có medoid gần nhất Sau đó, thay thế medoid hiện tại bằng một đối tượng không phải là medoid nhằm cải thiện chất lượng của phân cụm.
K-medoids hiệu quả hơn k-means khi xử lý dữ liệu có nhiễu hoặc đối tượng ngoại lai, nhưng độ phức tạp tính toán của k-medoids cao hơn Cả hai thuật toán đều yêu cầu người dùng xác định số lượng k cụm ngay từ đầu, điều này là một nhược điểm chung.
Ngoài ra còn có các thuật toán phân cụm phân hoạch khác: PAM, CLARA
2.5.2 Thuật toán phân cụm phân cấp
Thuật toán phân cụm phân cấp khắc phục nhược điểm của các thuật toán phân cụm truyền thống, vốn chỉ hiệu quả với các cụm có hình dạng cầu và kích thước tương đồng, đồng thời không xử lý tốt các đối tượng ngoại lai Thuật toán CURE giải quyết vấn đề này bằng cách định nghĩa một số điểm đại diện cố định, phân bổ rải rác trong không gian dữ liệu để mô tả các cụm Các điểm này được tạo ra bằng cách chọn các đối tượng nằm rải rác trong cụm và sau đó điều chỉnh chúng về trung tâm cụm thông qua nhân tố co cụm Quá trình này lặp lại, cho phép đo tỷ lệ gia tăng của cụm, và tại mỗi bước, hai cụm có cặp điểm đại diện gần nhau sẽ được hợp nhất.
Thuật toán CURE cho phép khám phá các cụm không hình cầu nhờ vào việc sử dụng nhiều hơn một điểm đại diện 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 các trường hợp có sự hiện diện của chúng Điều này cũng giúp CURE hoạt động tốt với các hình dạng và kích thước khác nhau, đồng thời duy trì hiệu suất cao khi làm việc với cơ sở dữ liệu lớn mà không làm giảm chất lượng phân cụm.
Thuật toán CURE xử lý dữ liệu lớn bằng cách sử dụng mẫu ngẫu nhiên và phân hoạch Đầu tiên, một mẫu được xác định ngẫu nhiên trước khi thực hiện phân hoạch, sau đó tiến hành phân cụm trên mỗi phân hoạch Mỗi phân hoạch sẽ được phân cụm thành các phần riêng biệt, và các cụm thu được sẽ được phân cụm lần thứ hai để tạo ra các cụm con mong muốn Tuy nhiên, việc sử dụng mẫu ngẫu nhiên không nhất thiết phản ánh toàn bộ đặc điểm của dữ liệu.
Thuật toán được thực hiện qua các bước cơ bản sau:
- Chọn ngẫu nhiên S từ tập ban đầu
- Phân hoạch S thành các nhóm dữ liệu có kích thước bằng nhau
- Phân cụm các điểm của mỗi nhóm
Để loại bỏ các phần tử ngoại lai, đầu tiên các cụm được hình thành và sau đó giảm xuống một phần so với các cụm ban đầu Trong quá trình pha khởi tạo dữ liệu mẫu, nếu các phần tử ngoại lai được lấy mẫu, thuật toán sẽ tự động loại bỏ các nhóm nhỏ.
Phân cụm các cụm không gian là quá trình mà các đối tượng đại diện cho các cụm di chuyển về hướng trung tâm của cụm, qua đó chúng được thay thế bằng các đối tượng gần trung tâm hơn.
Thuật toán CURE, với độ phức tạp O(n² log(n)), đáng tin cậy trong việc phát hiện các cụm có hình dạng bất kỳ, đặc biệt hiệu quả với dữ liệu có phần tử ngoại lai và trong các tập dữ liệu hai chiều Tuy nhiên, nó cũng 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ử này.
Ngoài ra còn có một số thuật toán phân cụm phân cấp 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 COP-Kmeans, được đề xuất bởi Wagstaff vào năm 2001, là một phương pháp phân cụm dữ liệu nửa giám sát dựa trên lưới và tìm kiếm Thuật toán này sử dụng các ràng buộc bổ trợ dưới dạng tập hợp các liên kết "must-link" và "cannot-link" để cải thiện độ chính xác trong phân cụm dữ liệu.
- 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 nằm khác cụm với nhau
Các ràng buộc được áp dụng trong suốt quá trình phân cụm nhằm điều hướng để đạt được kết quả mong muốn Thuật toán COP – Kmeans được thực hiện theo quy trình cụ thể để tối ưu hóa kết quả phân cụm.
- Input: Tập các đối tượng dữ liệu X = {X 1 , ,X n } với X 1 R d , số lượng cụm
K, tập ràng buộc must – link và cannot – link
Để đạt giá trị tối ưu cho hàm mục tiêu, cần thực hiện phân hoạch tách rời Bước đầu tiên là khởi tạo các cụm, với các tâm ban đầu được chọn ngẫu nhiên, đảm bảo không vi phạm các ràng buộc đã được xác định Quá trình này sẽ tiếp tục lặp lại cho đến khi đạt được sự 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ả các đối tượng nằm trong cụm của tâm đó o t t+1
Tổng quan về phân vùng ảnh
Phân đoạn ảnh là một thao tác quan trọng trong xử lý ảnh, giúp chia ảnh thành các vùng đồng nhất và xác định biên giới giữa chúng Các vùng này thường tương ứng với các đối tượng thực trong ảnh, đóng vai trò then chốt trong các ứng dụng như thị giác máy tính và nhận dạng đối tượng Ban đầu, phương pháp phân đoạn chủ yếu áp dụng cho ảnh mức xám do hạn chế về công nghệ, nhưng hiện nay, ảnh màu đã trở thành tiêu chuẩn nhờ vào khả năng lưu trữ và biểu diễn thông tin vượt trội Do đó, các kỹ thuật phân đoạn mới đã được phát triển để xử lý ảnh màu, dựa trên các thuật toán phân đoạn ảnh mức xám trước đó.
Phân vùng có thể được thực hiện dựa trên các vùng liên thông, được gọi là phân vùng theo miền đồng nhất, hoặc dựa vào biên, được gọi là kỹ thuật phân vùng biên Bên cạnh đó, còn có các kỹ thuật khác như phân vùng dựa vào biên độ và phân vùng dựa vào kết cấu.
Phân tích ảnh nhằm tạo ra các mô tả tổng hợp về các thành phần khác nhau trong ả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, nên cần thiết phải thực hiện quá trình giảm thiểu thông tin này.
Các hướng tiếp cận phân đoạn ảnh
Phân đoạn ảnh là quá trình chia ảnh thành các vùng không trùng lặp, mỗi vùng bao gồm một nhóm pixel liên thông và đồng nhất theo tiêu chí cụ thể, như màu sắc, mức xám, kết cấu hoặc độ sâu của các layer Để đảm bảo chất lượng phân đoạn, việc xác định rõ mục tiêu của quá trình là rất quan trọng Các phương pháp phân đoạn ảnh có thể được phân loại thành ba nhóm chính, tùy thuộc vào cách tiếp cận và tiêu chí phân đoạn.
- Các kỹ thuật phân đoạn ảnh dựa trên không gian đặc trưng
- Các kỹ thuật dựa trên không gian ảnh
- Các kỹ thuật dựa trên các mô hình vật lý
3.2.1 Các phương pháp dựa trên không gian đặc trưng
Nếu coi màu sắc bề mặt của các đối tượng trong ảnh là thuộc tính bất biến và ánh xạ vào một không gian màu, mỗi đối tượng sẽ được nhìn nhận như một cụm điểm trong không gian đó, với mức độ phân tán của các điểm phụ thuộc vào sự khác biệt về màu sắc Thay vào đó, chúng ta có thể xây dựng một histogram dựa trên các đặc trưng màu như Hue, trong đó các đối tượng thường xuất hiện như các giá trị đỉnh Do đó, việc phân vùng các đối tượng trong ảnh tương ứng với việc xác định các cụm trong không gian màu hoặc các vùng cực trị trong histogram.
Các phương pháp tiếp cận phân đoạn hình ảnh chỉ hoạt động trên các không gian màu xác định, như phương pháp của Park áp dụng cho không gian màu RGB, trong khi phương pháp của Weeks và Hague sử dụng không gian màu HIS Dựa trên không gian đặc trưng, có nhiều phương pháp phân đoạn khác nhau, bao gồm phân nhóm đối tượng không giám sát, phân lớp trung bình-k thích nghi và phương pháp lấy ngưỡng histogram.
3.2.2 Các phương pháp dựa trên không gian ảnh
Hầu hết các phương pháp được đề cập hoạt động dựa trên các không gian đặc trưng của ảnh, chủ yếu là màu sắc, dẫn đến các vùng ảnh kết quả đồng nhất theo các đặc trưng đã chọn Tuy nhiên, không có đảm bảo rằng các vùng này thể hiện sự cô đọng về nội dung theo ý nghĩa không gian ảnh, điều này rất quan trọng sau tính thuần nhất của các vùng ảnh Các phương pháp gom cụm và xác định ngưỡng histogram thường bỏ qua thông tin về vị trí của các pixel trong ảnh.
Trong các nghiên cứu khoa học về phân vùng ảnh mức xám, nhiều kỹ thuật đã được phát triển nhằm đáp ứng đồng thời hai tiêu chí quan trọng: tính đồng nhất trong không gian đặc trưng của ảnh và tính cô đọng của nội dung ảnh Các thuật giải này được phân loại thành nhiều nhóm khác nhau, tùy thuộc vào các kỹ thuật mà chúng áp dụng.
- Các thuật giải áp dụng kỹ thuật chia và trộn vùng
- Các thuật giải áp dụng kỹ thuật tăng trưởng vùng
- Các thuật giải áp dụng lý thuyết đồ thị
- Các giải thuật áp dụng mạng neural
- Các giải thuật dựa trên cạnh
3.2.3 Các phương pháp dựa trên mô hình vật lý
Các giải thuật phân vùng ảnh hiện tại đều có khả năng phát sinh lỗi phân vùng trong những trường hợp cụ thể, đặc biệt khi các đối tượng trong ảnh màu bị ảnh hưởng bởi vùng sáng hoặc bóng mờ, dẫn đến sự thay đổi đột ngột của màu sắc Kết quả là, các thuật toán này thường tạo ra kết quả phân vùng không mong muốn so với cảm nhận của mắt thường Để khắc phục vấn đề này, các phương pháp phân vùng ảnh đã áp dụng mô hình tương tác vật lý giữa bề mặt đối tượng và ánh sáng Các công cụ toán học sử dụng trong các phương pháp này tương tự như những phương pháp trước đó, nhưng điểm khác biệt chính là việc áp dụng các mô hình vật lý để minh họa các thuộc tính phản chiếu ánh sáng trên bề mặt màu sắc của các đối tượng.
Cột mốc quan trọng trong phân vùng ảnh màu dựa trên mô hình vật lý được Shafer giới thiệu, với mô hình phản xạ lưỡng sắc cho các vật chất điện môi không đồng nhất Klinker đã phát triển một thuật toán dựa trên mô hình này, đưa ra giả thuyết quang học liên quan đến màu sắc, bóng sáng và bóng mờ của các đối tượng, nhằm phù hợp với hình dạng của các cụm Tuy nhiên, hạn chế lớn nhất của thuật toán là chỉ áp dụng cho vật chất điện môi không đồng nhất Hai ông Tsang đã ứng dụng mô hình phản xạ lưỡng sắc trong không gian HSV để xác định các đường biên trong ảnh màu.
Healey đề xuất một mô hình phản xạ đơn sắc cho các vật chất kim loại
Các phương pháp được trình bày trong phần này chỉ áp dụng cho hai loại vật chất: kim loại và điện môi không đồng nhất Maxwell và Shafer đã đề xuất một thuật toán tổng quát và phức tạp hơn để giải quyết vấn đề này.
Tóm lại, một cái nhìn tổng quan về các phưong pháp phân đoạn ảnh như sau:
Mỗi phương pháp đều có những ưu nhược điểm nhất định:
Phương pháp phân vùng Ưu điểm Khuyết điểm
Clustering Phân loại không cần giám sát
Tồn tại các phương pháp heuristic và hữu hạn
Không quan tâm đến các thông tin trong không gian ảnh
Có vấn đề trong việc xác định số lượng các cụm ban đầu
Khó khăn trong việc điều chỉnh các cụm sao cho phù hợp với các vùng trong ảnh
Adaptive Clustering Sở hữu tính liên tục trong không gian ảnh và tính thích nghi cục bộ đối với các vùng ảnh
Sử dụng các ràng buộc về không gian ảnh
Cực đại hoá một xác suất hậu điều kiện có thể bị sai do các cực trị địa phương
Phương pháp phân vùng Ưu điểm Khuyết điểm
Histogram thresholding Không cần biết trước bất kỳ thông tin nào từ ảnh
Các giải thuật nhanh và dễ dàng cài đặt
Bỏ qua các thông tin về không gian ảnh
Lấy ngưỡng trong các histogram đa chiều là
Feature-based Spatial-based Physics-based
Split and merge Region growing Edge based Neural network based Graph theoretical một quá trình phức tạp
Ảnh hưởng dễ dàng bởi nhiễu xuất hiện trong ảnh
Spit and Merge Sử dụng các thông tin về không gian ảnh là chính
Cho kết quả tốt với các ảnh chứa nhiều vùng màu đồng nhất
Định nghĩa mức độ đồng nhất về màu sắc có thể phức tạp và khó khăn
Quadtree có thể gây ra các kết quả không như mong muốn
Region growing Các vùng ảnh đồng nhất và liên thông
Có một số thuật giải có tốc độ thực thi khá nhanh
Tốn kém chi phí sử dụng bộ nhớ và tính toán
Gặp khó khăn trong việc thu thập tập các điểm mầm và xác định các điều kiện đồng nhất đầy đủ
Chịu ảnh hưởng bởi các đặc tính tự nhiên của kỹ thuật này
Graph theories Thể hiện tốt không gian ảnh bằng đồ thị.
Một số thuật toán có tốc độ thực hiện nhanh
Một vài thuật giải mất khá nhiều thời gian thực hiện
Các đặc trưng cục bộ đôi khi được sử dụng nhiều hơn các đặc trưng toàn cục
Neural networks Mức độ song song hoá cao và có tốc độ thực thi nhanh
Khả năng chống chịu tốt trước các thay đổi xấu
Một công cụ hữu hiệu cho các ứng dụng nhận dạng và xử lý ảnh y khoa
Màu sắc có thể làm tăng độ phức tạp của mạng
Quá trình học cần phải biết trước số lượng các phân lớp/cụm
Edge-based Là phương pháp được hỗ trợ mạnh bởi các toán tử dò biên
Có hiệu năng tốt với các ứng dụng dò biên đối tượng theo đường cong
Khó khăn trong việc định nghĩa một hàm gradient cho các ảnh màu
Nhiễu hoặc các ảnh có độ tương phản kém ảnh hưởng xấu đến kết quả phân vùng
Phương pháp phân vùng Ưu điểm Khuyết điểm
Khẳng định tính chắc chắn đối với các vùng bóng sáng/tối, và vùng bóng chuyển tiếp (diffuse hoặc shade)
Phân vùng các đối tượng dựa vào thành phần vật liệu cấu tạo
Bị giới hạn vào một số lượng nhất định các loại vật chất hình thành nên đối tượng
Khó khăn trong việc xác định vùng bóng sáng và bóng chuyển tiếp trong các ảnh thực
Một vài giải thuật đòi hỏi các thông tin về hình dạng đối tượng (không luôn luôn đáp ứng được)
Chi phí tính toán cho bài toán truy vấn ảnh theo nội dung là khá cao, đặc biệt trong bước tiền xử lý phân đoạn, nơi cần chú ý đến thông tin toàn cục và cục bộ, đồng thời đảm bảo tính liên tục trong không gian ảnh Bài viết sẽ tập trung vào các thuật toán phân đoạn, bao gồm phương pháp phân đoạn yếu của B.G Prasad áp dụng trong hệ thống truy vấn ảnh của ông, phương pháp phân đoạn trung bình-k thích nghi, và phương pháp phân đoạn theo ngưỡng cục bộ thích nghi.
Một số phương pháp phân đoạn cụ thể
3.3.1 Phương pháp phân đoạn yếu của B.G Prasad Đây là phương pháp do B.G Prasad đề xuất và được áp dụng tronh hệ thống truy vấn ảnh theo chỉ mục màu sắc hình dạng và vị trí của tác giả Phương pháp này sử dụng sự lượng tử hóa màu trong không gian màu RGB, sử dụng 25 màu phân biệt (bằng giác quan) để phân đoạn ảnh dựa trên những màu trội Vì 25 màu là đủ để phân biệt rõ tất cả các vùng màu trong cơ sở dữ liệu hình ảnh mà tác giả chọn
Việc lựa chọn số lượng màu trong không gian màu giảm là sự cân nhắc giữa khả năng thể hiện và tốc độ cho từng ứng dụng cụ thể Sử dụng chỉ mục màu hiệu quả, việc giảm số lượng màu không chỉ phù hợp mà còn giúp giảm thiểu tính toán Dưới đây là bảng gồm 25 màu được chọn từ bảng màu RGB chuẩn.
Ví dụ phân đoạn ảnh
Hình 8: ví dụ phân đoạn ảnh bằng phương pháp phân đoạn yếu
Không gian màu RGB được phân chia thành các không gian con gọi là phân loại màu, và để tính toán độ tương đồng giữa hai vùng màu, chúng ta sử dụng khoảng cách Euclidean chuẩn.
Phương pháp này dựa vào việc xác định các biên, trong đó màu sắc của một pixel có thể được mô tả thông qua loại màu trong vùng màu giảm tương ứng Quy trình phân đoạn và xử lý chọn vùng trội được minh họa bằng sơ đồ dưới đây.
Sơ đồ xử lý chọn vùng và phân đoạn
Thủ tục này phân đoạn ảnh thành các vùng bằng cách ánh xạ toàn bộ pixel của ảnh lên các màu tương ứng trong không gian màu đã được giảm Mỗi pixel màu trên ảnh gốc sẽ được tìm kiếm màu gần nhất trong 25 màu đã định nghĩa trước và lưu lại làm màu trong ảnh mới Để xác định màu kết quả, chúng ta sử dụng khoảng cách Euclidean.
Gọi p r, p g, p b là cường độ màu của pixel cho ba thành phần đỏ, xanh lá và xanh dương; trong khi C iR, C iG, C iB là các giá trị màu tương ứng.
Gán màu gần nhất cho mỗi pixel
Sắp xếp bảng tần xuất (Histogram) theo thứ tự giảm
Lặp lại cho mỗi giá trị màu trong bảng tần xuất
Tìm màu xuất hiện đầu tiên iseed = img_array i jseed = img_array j
Gọi hàm Mark_Region(img_array, col, iseed, jseed, region)
Gọi hàm Fix_Boundary(img_array, col, region)
Tính diện tích (vùng hình chữ nhật) Diện tích = ((reg x1 - reg x2) * (reg y1 - reg y2))
Lưu region trong mảng Region
No nó trong bảng màu Để tính khoảng cách màu C d , ta sử dụng khoảng cách Euclidean như sau:
Sau khi có ảnh mới với màu sắc đã giảm thiểu, người dùng sẽ đánh dấu các vùng chọn trên ảnh Mỗi vùng được chọn sẽ được vẽ một đường biên hình chữ nhật, và diện tích của hình chữ nhật này sẽ được sử dụng để xác định diện tích vùng màu trội được chuẩn hóa Tất cả thông tin về số lượng vùng hiện có, màu sắc và diện tích được lưu trữ trong metafile để xử lý sau này Những thông tin này sẽ hỗ trợ trong việc xây dựng cây chỉ mục ảnh cho các máy tìm kiếm.
Giải thích sơ đồ (các bước) phân đoạn và dò đường biên:
(1) Đọc ảnh và tạo một mảng ảnh chứa các thành phần màu RGB của mỗi pixel trong ảnh
(2) Với mỗi pixel trong ảnh, thực hiện:
(a) Tìm màu gần với màu của pixel trong ảnh gốc bằng cách sử dụng công thức tính C d (với i=1,2,…,25)
C d r iR g iG b iB với p r , p g , p b : 3 thành phần màu RGB của ảnh gốc
C iR, C iG và C iB là ba thành phần màu tại vị trí i trong bảng 25 màu Khi tính toán giá trị C d min, chúng ta sẽ xác định được vị trí i, từ đó tìm ra màu gần nhất cần thiết.
(b) Gán màu tìm được này cho pixel đang xét (ứng với C d min)
(3) Tạo bảng tần xuất cho mỗi màu được gán (tạo histogram cho ảnh)
(4) Sắp xếp bảng tần xuất theo thứ tự giảm (để xác định những vùng màu trội)
(5) Lặp lại từ bước 6 đến 10 cho đến khi tìm được 3 vùng màu trội hoặc đến cuối bảng tần xuất
(6) Tiếp tục quét điểm ảnh theo thứ tự, dừng lại ở pixel đầu tiên có cùng giá trị màu trong bảng tần xuất được sắp xếp
(7) Gán vị trí pixel tìm được đó vào hai biến iseed, jseed tương ứng theo chiều ngang và chiều dọc của ảnh
(8) Đánh dấu toàn bộ vùng (region) bằng cách sử dụng vùng lân cận 8 connected của pixel đó
(9) Lấy tọa độ đường biên (x,y) của vùng được đánh dấu R và vẽ hình chữ nhật biên
(10) Xác định kích thước chuẩn hóa s(R) của hình chữ nhật biên bằng công thức: s(R) = (|x 1 - x 2 |*|y 1 - y 2 |)/N
Với (x 1, y 1) và (x 2, y 2 )là tọa độ của tương ứng của 2 đỉnh đối nhau trong hình chữ nhật biên, N là kích thước của ảnh
Theo thuật toán, để ngăn chặn việc lặp lại các vùng trội, ở bước 6, sau khi chọn pixel đầu tiên phù hợp, chúng ta cần kiểm tra xem pixel này đã nằm trong vùng đã xét trước đó hay chưa; nếu chưa, chúng ta sẽ chọn pixel đó.
3.3.2 Phương pháp phân đoạn dựa trên ngưỡng cục bộ thích nghi
Số ngưỡng cục bộ và giá trị của chúng được xác định thông qua việc kiểm tra thông tin cục bộ, không được chỉ định trước Giải thuật thực hiện các bước tuần tự để đạt được kết quả.
- Áp dụng giải thuật Watershed chia ảnh thành rất nhiều vùng con
- Trộn các vùng và đồng thời phát hiện ngưỡng cục bộ Ngưỡng được tính từ thông tin cục bộ của vùng và các vùng lân cận
Giải thuật này cho kết quả tương đối tin cậy trên nhiều loại ảnh khác nhau
3.3.3 Phân đoạn sơ khởi bằng Watershed
Giải thuật Watershed hoạt động trên ảnh xám, vì vậy bước đầu tiên là chuyển đổi ảnh đầu vào I thành ảnh xám Tiếp theo, áp dụng giải thuật tìm cạnh để tiếp tục xử lý.
Canny sử dụng cường độ gradient, ký hiệu là I G, để phân tích ảnh Ảnh gradient tạo ra có thể được hình dung như một lược đồ địa hình, trong đó các vùng có độ xám cao hơn tương ứng với các vùng trũng, và ngược lại Đánh giá tại mỗi pixel dựa trên giá trị mức xám của pixel đó.
Giải thuật định nghĩa hai thuật ngữ quan trọng là vũng chứa nước (catchment basin) và đập ngăn nước (dams) Mỗi vũng chứa nước được xác định dựa trên giá trị M nhỏ nhất, trong đó M là tập hợp các pixel liên thông mà một giọt nước sẽ rơi từ bất kỳ pixel nào trong vũng chứa này cho đến khi đạt được giá trị nhỏ nhất Trong quá trình rơi, giọt nước chỉ đi qua các pixel thuộc về vũng chứa nước đó.
Đập thực chất là các đường phân nước, tập hợp các pixel để phân cách các lưu vực Khi giọt nước rơi từ một bên của đập, nó sẽ đạt giá trị nhỏ nhất của một lưu vực, trong khi giọt nước từ phía bên kia sẽ đạt giá trị nhỏ nhất của lưu vực khác Hình 1 dưới đây minh họa cho các lưu vực và đập.
Catchment basin và dam là hai khái niệm quan trọng trong việc áp dụng giải thuật watershed, phiên bản của Vincent và Soille Giải thuật này mô phỏng quá trình ngâm nước dần dần trên bề mặt địa hình của ảnh, bắt đầu từ vùng thấp nhất cho đến khi mọi pixel đều được ngâm trong nước Quá trình này gồm hai bước: sắp thứ tự các pixel theo cường độ xám và làm ngập nước để xây dựng các catchment basin với nhãn phân biệt Hãy tưởng tượng việc ngâm nước bề mặt địa hình, bắt đầu từ điểm thấp nhất và cho nước dâng dần Khi nước từ các vũng cạnh nhau có thể hòa vào nhau, ta xây dựng đập chắn nước và tiếp tục cho nước dâng lên Quá trình này lặp đi lặp lại cho đến khi toàn bộ bề mặt địa hình được ngâm nước.