Notion of DistanceDistance MeasuresEuclidean distanceEuclidean Distance between VectorsDefinition of a MetricMetric PropertiesScale changes can affect nearest neighbor classifiers based on Euclidean distanceStandardizing the Datawhen variables are not commensurateWeighted Euclidean DistanceDistance between VariablesSample Covariance between variablesX and YRelationship between Covariance Matrix and Data MatrixCorrelation CoefficientGeneralizing Euclidean DistanceMinkowski MetricVector Space Representation of DocumentsCosine Distance between Document VectorsEuclidean vs Cosine DistanceBinary-Valued Feature VectorsDistance Measures for Binary DataTanimoto MetricSimilarity/DissimilarityMeasures for Binary VectorsWeighted Dissimilarity Measures for Binary Vectorsk-nn digit recognition accuracyk-nn Reduction RulesTri-Edge Inequality (TEI)Tri Edge Inequality in 3-d Binary SpaceTEI Property with Binary Vector Dissimilarity MeasuresTest for TEISummary of Binary Vector measuresTangent DistanceEffect of Translation on Euclidean DistanceTransformationsTransformation that depends on one parameter a (rotation angle)Learning from a limited set of samplesTangent VectorTransformation that depends on one parameter a (angle of rotation)Tangent VectorAlgorithm for computing tangent vectorsTangent Vectorfor 2-D imagesTangent VectorTV1(rotation)Euclidean Distance, Tangent Distance, Manifold DistanceTangent Distance: from test point x to prototype x’Minimizing value a for Tangent DistanceNotion of DistanceMetric DistanceBinary Vector DistancesTangent DistanceSrihari: CSE 555 1Distance Measures• Many pattern recognition/data mining techniques are based on similarity measures between objects• e.g., nearest-neighbor classification, • cluster analysis, • multi-dimensional scaling• s(i,j): similarity, d(i,j): dissimilarity• Possible transformations: d(i,j)= 1 – s(i,j) or d(i,j)=sqrt(2*(1-s(i,j))• Proximity is a general term to indicate similarity and dissimilarity• Distance is used to indicate dissimilaritySrihari: CSE 555 2Euclidean distanceNearest neighbor classifier relies on a distance function between patternsThe Euclidean formula for distance in d dimensions isNotion of a metric is far more generalabx3d = 3x2x1Euclidean Distance between Vectors()2/112),(⎟⎟⎠⎞⎜⎜⎝⎛−=∑=pkkkEyxyxd• Euclidean distance assumes variables are commensurate• E.g., each variable a measure of length• If one were weight and other was length there is no obvious choice of units• Altering units would change which variables are importantxx1y1x2y2ySrihari: CSE 555 3Srihari: CSE 555 4Definition of a Metric• Notion of a metric is more general than Euclidean distance• Properties of a metricFor all vectors a, b and cx3abd = 3cx2Euclidean distance is a metricx1Srihari: CSE 555 5Metric PropertiesA metric is a dissimilarity (distance)measure that satisfies the following properties:ij1. d(i,j) > 0 Positivity2. d(i,j) = d(j,i) Commutativity3. d(i,j) < d(i,k) + d(k,j) Triangle InequalityikjSrihari: CSE 555 6Scale changescan affect nearest neighbor classifiers based on Euclidean distanceOriginal space Scaled space with α = 1/3Point x is closest to black Point x is closest to RedRescaling the data to equalize ranges is equivalent to changing the metric in the original spaceSrihari: CSE 555 7Standardizing the Datawhen variables are not commensurate• Divide each variable by its standard deviation• Standard deviation for the kthvariable iswhereUpdated value that removes the effect of scale: 2112))((1⎟⎠⎞⎜⎝⎛−=∑=ikkkixnµσ)(11ixnnikk∑==µkkkxxσ='Srihari: CSE 555 8Weighted Euclidean Distance• If we know relative importance of variables2112))()(((),(⎟⎟⎠⎞⎜⎜⎝⎛−=∑=pkkkkWEjxixwjidSrihari: CSE 555 9Distance between Variables• Similarities between cups• Suppose we measure cup-height 100 times and diameter only once• height will dominate although 99 of the height measurements are not contributing anything• They are very highly correlated• To eliminate redundancy we need a data-driven method• approach is to not only to standardize data in each direction but also to use covariance between variablesSrihari: CSE 555 10Sample Covariance between variablesX and YSamplemeans⎟⎠⎞⎜⎝⎛−⎟⎠⎞⎜⎝⎛−=∑=_1_)()(1),( yiyxixnYXCovni• It is a scalar value that measures how X and Y vary together• Obtained by multiplying for each sample its mean-centered value of x with mean-centered value of y and then adding over all samples•Large positive value if large values of X tend to be associated with large values of Y and small values of X with small values of Y•Large negative value if large values of X tend to be associated with small values of Y• With p variables can construct a p x p matrix of covariances. Such a covariance matrix is symmetric.Srihari: CSE 555 11Relationship between Covariance Matrix and Data Matrix• Let X = n x p data matrix• Rows of X are the data vectors x(i)• Definition of covariance:• If values of X are mean-centered (i.e., value of each variable is relative to the sample mean of that variable) then V=XTX is the p x p covariance matrix⎟⎠⎞⎜⎝⎛−⎟⎠⎞⎜⎝⎛−=∑=_1_)()(1),( yiyxixnjiCovknkkSrihari: CSE 555 12Correlation CoefficientValue of Covariance is dependent upon ranges of X and YDependency is removed by dividing values of X by their standard deviation and values of Y by their standard deviationyxniyiyxixYXσσρ∑=−−−=1_))()()((),(With p variables, can form a p x p correlation matrixSrihari: CSE 555 13Correlation Matrix(Housing related variablesacross city suburbs)Reference for -1, 0,+1Variables 3 and 4 are highly negatively correlated with Variable 2Variable 5 is positively correlated withVariable 11Variables 8 and 9 are highly correlatedSrihari: CSE 555 14Generalizing Euclidean DistanceMinkowski or Lλmetric• λ = 2 gives the Euclidean metric• λ = 1 gives the Manhattan or City-block metric• λ = infinity yields()λλ11)()(⎟⎟⎠⎞⎜⎜⎝⎛−∑=pkkkjxix∑=−pkkkjxix1|)()(||)()(|max jxixkkk−Srihari: CSE 555 15• The Lknorm•L1norm is the Manhattan (city block) distance•L2norm is the Euclidean distanceMinkowski MetricEach colored surfaceconsists of pointsof distance 1.0 from the originUsing different values for kin the Minkowski metric(k is in red)OriginManhattanStreetsSrihari: CSE 555 16Vector Space Representation of DocumentsDocument-Term Matrixt1