��Cardamom Planters’ Association College�(Re-accredited with ‘B’ Grade by NAAC)�Pankajam Nagar, Bodinayakanur – 625513���Department of CS & IT��PROXIMITY MEASURES�

S.ROHINI ME.,

ASSISTANT PROFESSOR

DEPARTMENT OF CS & IT

C.P.A COLLEGE

Proximity measures

• Whenever classification is carried out, it is done according to some similarity of the test pattern to the training patterns.

​

• For clustering also, patterns which are similar to each other are to be put into the same cluster while patterns which are dissimilar are to be put into different clusters.

​

• To determine this similarity/dissimilarity, proximity measures are used.

​

• Some of the proximity measures are metrics while some are not.

​

​

• The distance between two patterns is used as a proximity measure. If this distance is smaller, then the two patterns are more similar.

​

• For the distance measure to be metric, the following properties should hold
• Positive reflexivity d(x,x)=0
• Symmetry d(x,y) = d(y,x)
• Triangular inequality d(x,y) ≤ d(x,z) + d(z,y)

​

Types of proximity measures

• Distance measures
• Weighted distance measures
• Non metric similarity functions
• Edit distance
• Mutual neighbourhood distance
• Conceptual cohesiveness
• Kernel functions

​

Distance measures

Weighted distance measures

Non metric similarity function

• Similarity functions which do not obey either the triangular inequality or symmetry come under this category.

​

• Usually these similarity functions are useful for images or string data. They are robust to outliers or to extremely noisy data.

​

• The squared Euclidean distance is itself an example of a non-metric, but it gives the same ranking as the Euclidean distance which is a metric

​

• One non-metric similarity function is the k-median distance between two vectors.

Edit distance

• It measures the distance between two strings.

​

• It is also called the Levenshtein distance.

​

• The edit distance between two strings s1 and s2 is defined as the minimum number of point mutations required to change s1 to s2.

​

• A point mutation involves any one of the following operations.
• Changing a letter
• Inserting a letter
• Deleting a letter

​

​

Mutual neighbourhood distance

Conceptual cohesiveness

Kernel functions

• The kernel function can be used to characterize the distance between two patterns x and y.
• Polynomial kernel - The similarity between x and y can be represented using the polynomial kernel function

​

• Radial basis function kernel

​