Similarity and Dissimilarity Measures and k-Nearest Neighbours
Similarity is a numerical measure of how alike two data objects are; dissimilarity is a numerical measure of how different they are. k-nearest neighbours classifies a new record by the closest training records.
Similarity is higher when objects are more alike and usually falls in the range 0 to 1. Dissimilarity is lower when objects are more alike; the minimum is usually 0 and the upper limit varies. Proximity refers to either. The most common dissimilarity for numeric data is the Euclidean distance: d(x, y) = square root of the sum of (xi - yi) squared. The Manhattan distance sums the absolute differences, and the Minkowski distance generalizes both with a parameter r. Cosine similarity compares document vectors by the angle between them.
k-nearest neighbours (k-NN) is a simple classifier: to classify a new record, find the k closest training records using a distance measure and give it the majority class of those neighbours. k is the number of nearby neighbours used. A k that is too small is sensitive to noise; a k that is too large includes points from other classes. Because distances drive the method, attributes should be normalized first.
Euclidean distance can be misleading in high dimensions, which is one reason dimensionality reduction is used.
Key points
- Similarity: higher = more alike, usually 0 to 1.
- Dissimilarity: lower = more alike, minimum usually 0.
- Euclidean = sqrt of summed squares; Manhattan = summed absolute differences.
- k-NN votes among the k nearest training records.
- Normalize attributes before using distances.
Worked example
Points (1, 2) and (4, 6): Euclidean distance = sqrt(9 + 16) = 5. Manhattan distance = 3 + 4 = 7.
Common questions
What does k mean in k-nearest neighbours?
The number of nearest training records consulted to classify a new record.
Which is a dissimilarity measure?
Distance measures such as Euclidean distance. Smaller distance means more alike.
Practice questions on this topic
Try these, then open the app to check your answers with explanations.
- Which is the number of nearby neighbours to be used to classify the new record?
- A. k (the number of nearest neighbors)
- B. Validation data
- C. Euclidean Distance
- D. All the above
- Which of these terms can mean a numerical measure of how alike two data objects are?
- A. Similarity
- B. Dissimilarity
- C. Proximity
- D. A, and C are true
- A numerical measure of how different two data objects are is:
- A. Similarity measure
- B. Dissimilarity measure
- C. Proximity
- D. B, C are true
Related topics
- What is Data Mining? Tasks: Classification, Clustering, Regression, Association Rules
- The KDD Process: Knowledge Discovery in Databases Steps
- Types of Attributes: Nominal, Ordinal, Interval and Ratio
- Data Cleaning: Noise, Outliers, Missing Values and Inconsistent Data
- Binning: Equal-Width vs Equal-Frequency (Equal-Depth) with Examples
- Data Normalization: Min-Max, Z-Score and Decimal Scaling with Examples
- All topics: Data Mining
BASMAGLY is an independent student project, not an official Delta University site. Check lectures and your instructor for the final word.