Кластерный анализ - как упорядочивающая операция объектов в однородные группы

CLUSTER ANALYSIS Class 2 Class 1 Class 3 OBJECT X1 XnХn SIGNS

2 1. Symmetry. Given two objects x and y; the distance between them satisfies the condition d (x, y) = d (y, x) triangle inequality. Given three objects x, y, z; the distances between them satisfy the condition d (x, y) d (x, z) + d (y, z). 3. Distinctness of non-identical objects. Given two objects x and y: if d (x, z) 0, then x y. 4. Indistinguishability of identical objects. For two identical objects x and x d (x, x) = 0, i.e. the distance between these objects is zero. Let wi is the i-th group (class, cluster) of objects, N i is the number of objects that make up the group wi, vector i is the arithmetic average of objects included in wi

4 1. The distance of the nearest neighbor is the distance between the nearest cluster objects: 2. Distance of the far neighbor distance between the farthest objects of clusters: 3. The distance of the centers of gravity is equal to the distance between the central points of the clusters:

5 4. The generalized (according to Kolmogorov) distance between the classes, or the generalized K-distance, is calculated by the formula

6 DISTANCES OF CLUSTER ANALYSIS 1. Euclidean distance distance (x, y) = {(xi - yi) 2} 1/2 2. Square Euclidean distance distance (x, y) = (xi - yi) 2 3. Distance of urban quarters (Manhattan distance). distance (x, y) = | xi - yi | 4. Chebyshev distance. distance (x, y) = max | xi - yi |

7 5. Powerful distance. distance (x, y) = {| xi - yi | p} 1 / r 6. Percentage of disagreement. distance (x, y) = (Number xiyi) / i Rules for merging or communication Centroid cluster

8 Cluster 1 Cluster 2 Cluster 3

9 - Single connection (nearest neighbor method). - Full communication (the method of the most distant neighbors). - Unweighted pairwise average. - Weighted paired average. - Unweighted centroid method. - Weighted centroid method (median). - Ward method.

10 AGLOMERATIVE METHODS OF CONSTRUCTION OF A TREE OF SOLUTIONS - DENDROGRAMS 1. Construction of a distance matrix (distance measure) 1-1; 1-2; 1-3; 1-4; ; 1-104; 1-105; 2-1; 2-2; 2-3; 2-4; ; 2-104; 2-105; ; ; 103-1; 103-2; ; ; ; 104-1; 104-2; ; ; ; 105-1; 105-2; ; ; Two observations (monoclusters), between which the minimum distance is combined into one cluster 3. Analysis of the remaining monoclusters and the addition of a new object to an existing cluster or the combination of two observations into a cluster

11 signs distance

13 Squared Euclidean distances (cars.sta) PRICE ACCELER BRAKING HANDLING MILAGE PRICE, 0 62.4 43,930,757,7 ACCELER 62,4,048,651,636,8 BRAKING 43,948,6,040,437,4 HANDLING 30,751,640,437,0 MILAGE57,736,837,452,236 Mat distances by featured

14 objects

16 Acura Audi BMW Buick CorvetteChryslerDodge Acura, 09,97,97,716,55,75,8 Audi 9,9,01,45,06,02,53,0 BMW 7,91,4,08,03,42,12,0 Buick7 , 75,08,0,019,42,93,9 Corvette 16,56,03,419,4,09,58,3 Chrysler 5,72,52,12,99,5,0,2 Dodge 5,83,02,03,98, 3.2.0 Distance Matrix

17 Iterative methods The k-means method of McKean 1) select or assign k observations, which will be the primary centers of the clusters; 2) if necessary, intermediate clusters are formed; 3) after assigning all observations to individual clusters, the primary cluster centers are replaced by cluster averages; 4) the previous iteration is repeated until the changes in the coordinates of the cluster centers become minimal.

18 1 step 2 step Assigning an object as a cluster and a centroid Calculation of distances to all objects and association with the nearest object in a cluster 3 step Recalculation of centroids of classes 4 step Calculation of distances from centroids to objects and association with the nearest object into a cluster Step 2-4 repeats iteratively

19 Step N Step N + 1 Final centroids Calculation of distances from centroids to objects Tugging of closest objects, recalculating centroids Repeating steps N and N + 1 to the minimum change in coordinates of the centroids

20 Standard Mean Deviatn.Variance PRICE,,, ACCELER-,,, BRAKING, 099270,484478, HANDLING, 280263,423215, MILAGE-, 876397,655936, Statistics for the classes Standard Mean Deviatn.Variance PRICE -, 434787.386686, ACCELER , 365078,721615, BRAKING-,,, HANDLING-,,, MILAGE, 408985,867383, class 1 class

21 MEDIUM SCHEDULE

22 AFTER REMOVAL OF MINOR OBSERVATIONS

23 Standard Mean Deviatn.Variance PRICE, 195402,622618, ACCELER, 788538,558425, MILAGE-, 480841,648858, Statistics for the classes Standard Mean Deviatn.Variance PRICE 1.119891,, ACCELER-1,59237,595372, MILAGE-, 89508,658416, CLASS 2 CLASS Standard Mean Deviatn.Variance PRICE -, 604276,118952, ACCELER, 006119,541236, MILAGE, 742706,828777,686872