Data Mining and Knowledge Discovery Handbook, 2 Edition part 10. Knowledge Discovery demonstrates intelligent computing at its best, and is the most desirable and interesting end-product of Information Technology. To be able to discover and to extract knowledge from data is a task that many researchers and practitioners are endeavoring to accomplish. There is a lot of hidden knowledge waiting to be discovered – this is the challenge created by today’s abundance of data. Data Mining and Knowledge Discovery Handbook, 2nd Edition organizes the most current concepts, theories, standards, methodologies, trends, challenges and applications of data mining (DM) and knowledge discovery. | 70 Christopher . Burges Notice that the elements are squared distances despite the name. Pe can also be used to center both Gram matrices and distance matrices. We can see this as follows. Let C i j be that matrix whose ij th element is C i j . Then Pe xi Xj Pe PeXX Pe PeX PeX x -n xj - P . In addition using this result Pe x - -Xj 2 Pe Pe xi 2eiej xj 2eiej - 2x Xj Pe -2Pex XjPe -2 x - xj - . For the following theorem the earliest form of which is due to Schoenberg Schoenberg 1935 we first note that for any A e Mm and letting Q mee PeAPe 1 - Q A 1 - Q ij Aij - ARj - AC Aj where AC AQ is the matrix A with each column replaced by the column mean Ar QA is A with each row replaced by the row mean and ARC QAQ is A with every element replaced by the mean of all the elements. Theorem Consider the class of symmetric matrices A e Sn such that A j 0 and Ai 0 Vi j. Then A -PeAPe is positive semidefinite if and only if A is a distance matrix with embedding space Rd for some d . Given that A is a distance matrix the minimal embedding dimension d is the rank of A and the embedding vectors are any set of Gram vectors of A scaled by a factor of . Proof Assume that A e Sm Aij 0 and Aii 0 Vi and that A is positive semidefinite. Since A is positive semidefinite it is also a Gram matrix that is there exist vectors x e Rm i 1 m such that A j x xj. Introduce y - x . Then from Eq. A - -P P6 - - A I AR I AC ARC A. Aij -P AP ij xi x j -Aij Aij Aij - Aij so that 2 v-v 2 x--x- 2 AR AC_ARC AR AC _ARC 2 yi yj xi xj Aii Aii Aii Ajj Ajj Ajj -2 -Aij ARj ACj - ARC 2Aij using An 0 ARj ARj ACj AC and from the symmetry of A AR AC . Thus A is a distance matrix with embedding vectors yi. Now consider a matrix A e Sn that is a distance matrix so that Aij yi - yj 2 for some yi e Rd for some d and let Y be the matrix whose rows are the yi. Then since each row and column of Pe sums to zero we have A - PeAPe 2 PeY PeY hence A is positive semidefinite. Finally given a distance .
