Đo lường sự giống nhau và không giống nhau của dữ liệu là kỹ thuật thường sử dụng trong trực quan hóa dữ liệu.
Các bài viết liên quan:
Trong các ứng dụng khai thác dữ liệu, chẳng hạn như phân nhóm, phân tích ngoại lệ và phân loại láng giềng gần nhất, chúng ta cần các cách để đánh giá các đối tượng giống nhau hay không giống nhau so với nhau. Ví dụ: một cửa hàng có thể muốn tìm kiếm các nhóm đối tượng khách hàng, dẫn đến các nhóm khách hàng có đặc điểm giống nhau (ví dụ: thu nhập tương tự, khu vực cư trú và độ tuổi). Những thông tin đó sau đó có thể được sử dụng để tiếp thị. Cụm là một tập hợp các đối tượng dữ liệu sao cho các đối tượng trong một cụm tương tự với nhau và khác với các đối tượng trong các cụm khác. Phân tích ngoại lệ cũng sử dụng các kỹ thuật dựa trên phân nhóm để xác định các ngoại lệ tiềm ẩn là các đối tượng rất khác biệt với những đối tượng khác. Kiến thức về sự tương đồng của đối tượng cũng có thể được sử dụng trong các lược đồ phân loại láng giềng gần nhất trong đó một đối tượng nhất định (ví dụ, một bệnh nhân) được gán nhãn lớp (liên quan đến, chẳng hạn như chẩn đoán) dựa trên sự tương tự của nó đối với các đối tượng khác trong mô hình.
Sử dụng một đám mây thẻ để trực quan hóa các thẻ trang Web phổ biến.
Xem thêm Đối tượng dữ liệu và loại thuộc tính trong Data mining
Ma trận dữ liệu so với Ma trận khác biệt
Trong phần này, chúng ta nói về các đối tượng được mô tả bởi nhiều thuộc tính. Do đó, chúng ta cần một sự thay đổi trong ký hiệu. Giả sử rằng chúng ta có n đối tượng (ví dụ: người, vật phẩm hoặc khóa học) được mô tả bằng thuộc tính p (còn được gọi là phép đo hoặc tính năng, chẳng hạn như tuổi, chiều cao, cân nặng hoặc giới tính). Các đối tượng là x1 = (x11, x12, …, x1p ), x2 = (x21, x22, …, x2p ), … trong đó xij là giá trị cho đối tượng xi của thuộc tính thứ j. Để ngắn gọn, chúng ta sau đây gọi đối tượng xi là đối tượng i. Các đối tượng có thể là các bộ dữ liệu trong cơ sở dữ liệu quan hệ và cũng được gọi là mẫu dữ liệu hoặc vectơ đặc trưng.
Các thuật toán phân cụm dựa trên bộ nhớ chính và thuật toán lân cận gần nhất thường hoạt động trên một trong hai cấu trúc dữ liệu sau:
- Ma trận dữ liệu (hoặc cấu trúc theo đối tượng theo thuộc tính): Cấu trúc này lưu trữ n đối tượng dữ liệu dưới dạng bảng quan hệ hoặc ma trận n-x-p (n đối tượng × p thuộc tính):
Mỗi hàng tương ứng với một đối tượng. Là một phần của ký hiệu của chúng tôi, chúng tôi có thể sử dụng f để lập chỉ mục thông qua các thuộc tính p.
- Ma trận khác biệt (hoặc cấu trúc từng đối tượng): Cấu trúc này lưu trữ một tập hợp các điểm gần nhau có sẵn cho tất cả các cặp n đối tượng. Nó thường được biểu diễn bằng một bảng n-by-n:
trong đó d(i, j) là sự khác biệt đo được hoặc “sự khác biệt” giữa các đối tượng i và j. Nói chung, d(i, j) là một số không âm gần bằng 0 khi các đối tượng i và j rất giống nhau hoặc “gần” nhau, và càng lớn thì chúng càng khác nhau. Lưu ý rằng d(i, i) = 0; nghĩa là, sự khác biệt giữa một đối tượng và chính nó là 0.
Ma trận dữ liệu được tạo thành từ hai thực thể hoặc “sự vật”, cụ thể là hàng (đối tượng) và cột (đối với thuộc tính). Do đó, ma trận dữ liệu thường được gọi là ma trận hai chế độ. Ma trận khác biệt chứa một loại thực thể (khác biệt) và do đó được gọi là ma trận một chế độ. Nhiều thuật toán phân cụm và hàng xóm gần nhất hoạt động trên một ma trận khác biệt. Dữ liệu ở dạng ma trận dữ liệu có thể được chuyển đổi thành ma trận khác biệt trước khi áp dụng các thuật toán như vậy.
Các biện pháp lân cận cho các thuộc tính danh nghĩa
Một thuộc tính danh nghĩa có thể có hai hoặc nhiều trạng thái. Ví dụ: màu bản đồ là một thuộc tính danh nghĩa có thể có năm trạng thái: đỏ, vàng, lục, hồng và lam.
Gọi số trạng thái của thuộc tính danh nghĩa là M. Các trạng thái có thể được biểu thị bằng chữ cái, ký hiệu hoặc một tập hợp các số nguyên, chẳng hạn như 1, 2, …, M. Lưu ý rằng các số nguyên như vậy chỉ được sử dụng để xử lý dữ liệu và không đại diện cho bất kỳ thứ tự cụ thể nào.
“Sự khác biệt được tính như thế nào giữa các đối tượng được mô tả bằng các thuộc tính danh nghĩa?” Sự khác biệt giữa hai đối tượng i và j có thể được tính dựa trên tỷ lệ không khớp:
Trong đó m là số lượng đối sánh (tức là số thuộc tính mà i và j ở cùng trạng thái) và p là tổng số thuộc tính mô tả các đối tượng. Trọng lượng có thể được chỉ định để tăng hiệu ứng của m hoặc chỉ định trọng số lớn hơn cho các trận đấu ở các thuộc tính có số lượng trạng thái lớn hơn.
Sự gần gũi giữa các đối tượng được mô tả bởi các thuộc tính danh nghĩa có thể được tính toán bằng cách sử dụng một lược đồ mã hóa thay thế. Các thuộc tính danh nghĩa có thể được mã hóa bằng cách sử dụng các thuộc tính nhị phân không đối xứng bằng cách tạo một thuộc tính nhị phân mới cho mỗi trạng thái M. Đối với một đối tượng có giá trị trạng thái nhất định, thuộc tính nhị phân đại diện cho trạng thái đó được đặt thành 1, trong khi các thuộc tính nhị phân còn lại được đặt thành 0. Ví dụ: để mã hóa màu bản đồ thuộc tính danh nghĩa, một thuộc tính nhị phân có thể được tạo cho mỗi năm màu được liệt kê trước đó. Đối với một đối tượng có màu vàng, thuộc tính màu vàng được đặt thành 1, trong khi bốn thuộc tính còn lại được đặt thành 0. Các số đo lân cận cho dạng mã hóa này có thể được tính bằng cách sử dụng các phương pháp được thảo luận trong tiểu mục tiếp theo.
Các biện pháp lân cận cho các thuộc tính nhị phân
Chúng ta hãy xem xét các phép đo mức độ khác nhau và độ giống nhau cho các đối tượng được mô tả bằng thuộc tính nhị phân đối xứng hoặc không đối xứng.
Nhớ lại rằng một thuộc tính nhị phân chỉ có một trong hai trạng thái: 0 và 1, trong đó 0 có nghĩa là thuộc tính không có và 1 có nghĩa là nó có mặt. Ví dụ, với thuộc tính người hút thuốc mô tả một bệnh nhân, 1 cho biết rằng bệnh nhân hút thuốc, trong khi 0 chỉ ra rằng bệnh nhân không hút thuốc. Xử lý các thuộc tính nhị phân như thể chúng là số có thể gây hiểu lầm. Do đó, các phương pháp dành riêng cho dữ liệu nhị phân là cần thiết để tính toán không giống nhau.
Sự khác biệt của dữ liệu số: Khoảng cách Minkowski
Trong phần này, chúng tôi mô tả các phép đo khoảng cách thường được sử dụng để tính toán sự không giống nhau của các đối tượng được mô tả bằng các thuộc tính số. Các thước đo này bao gồm khoảng cách Euclidean, Manhattan và Minkowski.
Trong một số trường hợp, dữ liệu được chuẩn hóa trước khi áp dụng tính toán khoảng cách. Điều này liên quan đến việc chuyển đổi dữ liệu để nằm trong một phạm vi nhỏ hơn hoặc phổ biến, chẳng hạn như [−1,1] hoặc [0.0, 1.0]. Ví dụ, hãy xem xét một thuộc tính chiều cao, có thể được đo bằng mét hoặc inch. Nói chung, việc thể hiện một thuộc tính bằng các đơn vị nhỏ hơn sẽ dẫn đến phạm vi lớn hơn cho thuộc tính đó và do đó có xu hướng mang lại cho các thuộc tính đó hiệu ứng hoặc “trọng lượng” lớn hơn. Việc chuẩn hóa dữ liệu cố gắng cung cấp cho tất cả các thuộc tính một trọng số như nhau. Nó có thể hữu ích hoặc không trong một ứng dụng cụ thể. Các phương pháp chuẩn hóa dữ liệu được thảo luận chi tiết trong Chương 3 về tiền xử lý dữ liệu.
Thước đo khoảng cách phổ biến nhất là khoảng cách Euclide (tức là đường thẳng hoặc “đường quạ bay”). Cho i = (xi1, xi2, …, xip) và j = (xj1, xj2, …, xjp) là hai đối tượng được mô tả bởi p thuộc tính số. Khoảng cách Euclid giữa các đối tượng i và j được xác định là:
Một thước đo nổi tiếng khác là khoảng cách Manhattan (hoặc khối thành phố), được đặt tên như vậy bởi vì nó là khoảng cách tính bằng khối giữa hai điểm bất kỳ trong một thành phố (chẳng hạn như 2 dãy phố xuống và 3 dãy phố trên tổng số 5 khối). Nó được định nghĩa là:
Cả khoảng cách Euclide và Manhattan đều thỏa mãn các tính chất toán học sau:
Không âm: d(i, j) ≥ 0: Khoảng cách là một số không âm.
Nhận dạng của các điều không thể xác định: d(i, i) = 0: Khoảng cách của một đối tượng đến chính nó là 0.
Tính đối xứng: d(i, j) = d(j, i): Khoảng cách là một hàm đối xứng.
Bất đẳng thức tam giác: d(i, j) ≤ d(i, k) + d(k, j): Đi thẳng từ đối tượng i đến đối tượng j trong không gian không hơn là đi đường vòng qua bất kỳ đối tượng nào khác k.
Một thước đo thỏa mãn những điều kiện này được gọi là thước đo. Xin lưu ý rằng thuộc tính không tiêu cực được ngụ ý bởi ba thuộc tính còn lại.
Các biện pháp lân cận cho các thuộc tính thông thường
Các giá trị của một thuộc tính thứ tự có thứ tự hoặc thứ hạng có ý nghĩa về chúng, nhưng độ lớn giữa các giá trị liên tiếp là không xác định. Một ví dụ bao gồm chuỗi nhỏ, trung bình, lớn cho thuộc tính kích thước. Các thuộc tính thứ tự cũng có thể nhận được từ việc tùy ý hóa các thuộc tính số bằng cách tách phạm vi giá trị thành một số loại hữu hạn. Các danh mục này được sắp xếp thành các cấp bậc. Nghĩa là, phạm vi của một thuộc tính số có thể được ánh xạ tới một thuộc tính thứ tự f có các trạng thái Mf. Ví dụ: phạm vi của nhiệt độ thuộc tính được chia tỷ lệ theo khoảng (tính bằng độ C) có thể được tổ chức thành các trạng thái sau: −30 đến −10, −10 đến 10, 10 đến 30, đại diện cho các loại nhiệt độ lạnh, nhiệt độ trung bình và ấm nhiệt độ tương ứng. Gọi M đại diện cho số trạng thái có thể có mà một thuộc tính thứ tự có thể có. Các trạng thái có thứ tự này xác định xếp hạng 1, …, Mf.
“Các thuộc tính thứ tự được xử lý như thế nào?” Việc xử lý các thuộc tính thứ tự khá giống với cách xử lý các thuộc tính số khi tính toán sự không giống nhau giữa các đối tượng. Giả sử rằng f là một thuộc tính từ một tập các thuộc tính thứ tự mô tả n đối tượng. Việc tính toán sự khác biệt đối với f bao gồm các bước sau:
- Giá trị của f đối với đối tượng thứ i là xif, và f có các trạng thái có thứ tự Mf, đại diện cho thứ hạng 1, …, Mf. Thay mỗi xif bằng thứ hạng tương ứng của nó, rif €{f1, …, Mf}.
- Vì mỗi thuộc tính thứ tự có thể có một số trạng thái khác nhau, nên thường cần ánh xạ phạm vi của từng thuộc tính lên [0.0, 1.0] để mỗi thuộc tính có trọng số bằng nhau. Chúng tôi thực hiện chuẩn hóa dữ liệu như vậy bằng cách thay thế rif hạng của đối tượng thứ i trong thuộc tính thứ f bằng:
- Sự khác biệt sau đó có thể được tính bằng cách sử dụng bất kỳ thước đo khoảng cách nào được mô tả trong Phần 2.4.4 cho các thuộc tính số, sử dụng zif để biểu thị giá trị f cho đối tượng thứ i.
Sự không giống nhau cho các thuộc tính của các loại hỗn hợp
Các phần từ trước đã thảo luận về cách tính toán sự không giống nhau giữa các đối tượng được mô tả bởi các thuộc tính cùng loại, trong đó các loại này có thể là danh nghĩa, nhị phân đối xứng, nhị phân không đối xứng, số hoặc thứ tự. Tuy nhiên, trong nhiều cơ sở dữ liệu thực, các đối tượng được mô tả bằng hỗn hợp các kiểu thuộc tính. Nói chung, một cơ sở dữ liệu có thể chứa tất cả các kiểu thuộc tính này.
“Vì vậy, làm cách nào chúng ta có thể tính toán sự không giống nhau giữa các đối tượng thuộc các loại thuộc tính hỗn hợp?” Một cách tiếp cận là nhóm từng loại thuộc tính lại với nhau, thực hiện phân tích khai thác dữ liệu riêng biệt (ví dụ: phân cụm) cho từng loại. Điều này là khả thi nếu những phân tích này cho kết quả tương thích. Tuy nhiên, trong các ứng dụng thực, không chắc rằng một phân tích riêng biệt cho mỗi loại thuộc tính sẽ tạo ra kết quả tương thích.
Một cách tiếp cận thích hợp hơn là xử lý tất cả các loại thuộc tính với nhau, thực hiện một phân tích duy nhất. Một kỹ thuật như vậy kết hợp các thuộc tính khác nhau thành một ma trận khác biệt duy nhất, đưa tất cả các thuộc tính có ý nghĩa vào một thang đo chung của khoảng [0,0, 1,0].
Giả sử rằng tập dữ liệu chứa p thuộc tính kiểu hỗn hợp. Sự khác biệt d.i, j / giữa các đối tượng i và j được định nghĩa là:
Độ đo tương tự Cosine
Một tài liệu có thể được đại diện bởi hàng nghìn thuộc tính, mỗi thuộc tính ghi lại tần suất xuất hiện của một từ cụ thể (chẳng hạn như từ khóa) hoặc cụm từ trong tài liệu. Do đó, mỗi tài liệu là một đối tượng được đại diện bởi cái được gọi là vectơ tần số hạn.
Các vectơ tần số kỳ hạn thường rất dài và thưa thớt (tức là chúng có nhiều giá trị 0). Các ứng dụng sử dụng các cấu trúc như vậy bao gồm truy xuất thông tin, phân cụm tài liệu văn bản, phân loại sinh học và lập bản đồ đặc điểm gen. Các thước đo khoảng cách truyền thống mà chúng ta đã nghiên cứu trong chương này không hoạt động tốt đối với dữ liệu số thưa thớt như vậy. Ví dụ: hai vectơ tần số số hạng có thể có nhiều giá trị 0 chung, có nghĩa là các tài liệu tương ứng không có nhiều từ, nhưng điều này không làm cho chúng tương tự nhau. Chúng ta cần một thước đo sẽ tập trung vào những từ mà hai tài liệu có điểm chung và tần suất xuất hiện của những từ đó. Nói cách khác, chúng ta cần một thước đo cho dữ liệu số bỏ qua các kết quả không khớp.
Độ tương tự cosine là thước đo độ tương tự có thể được sử dụng để so sánh các tài liệu hoặc nói cách khác, đưa ra xếp hạng các tài liệu liên quan đến một vectơ các từ truy vấn nhất định. Gọi x và y là hai vectơ để so sánh. Sử dụng số đo cosin như một hàm tương tự,
