案例教案组会dicks report

1、Three kinds of Cluster Analysis MethodsSupervisor: Tingjun HouReporter: Qian ZhangCluster analysis, which can also be called unsupervised classification, is used to group a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to e

2、ach other than to those in other groups (clusters).Different kinds of Cluster:Cluster analysis, which can also be called unsupervised classification, is used to group a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each

3、other than to those in other groups (clusters).Different kinds of Cluster:Cluster analysis, which can also be called unsupervised classification, is used to group a set of objects in such a way that objects in the same group (called a cluster) are more similar (in some sense or another) to each othe

4、r than to those in other groups (clusters).Different kinds of Cluster:K-means clusteringK-means clustering aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean, serving as a prototype of the cluster.Algorithm:Distance between centrio

5、ds and pointsk initial centroidsClusterRecalculate centriodsCentriods changeOutput centriodsYNK-means clustering+A,B,C,D=kmeans(data,n); (Matlab)K-means clusteringTime cost: O(num*k*m)Space cost: O(k+m)num : number of the iterations, usually bounded.k: number of the clusterm: number of pointsTime co

6、st O(m)Space cost O(m) Advantage: simple and fast, centroids will be returned.Disadvantage: results depend on the initial centroids, and outliers will influence the clustering. Note: If this method is used, it needs to be done for several time to get the best result.Hierarchical ClusteringHierarchic

7、al clustering is a method of cluster analysis which seeks to build a hierarchy of clusters. Strategies for hierarchical clustering generally fall into two types: agglomerative and divisive hierarchical clustering.Algorithm:Distance matrixMerge the nearest two points as a clusterAll points be assigne

8、dOutput resultNYAgglomerative: This is a bottom up approach: each observation starts in its own cluster, and pairs of clusters are merged as one moves up the hierarchy.Agglomerative Hierarchical Clusteringtree=rand(5,6); (Matlab)dist=pdist(tree)10.2077420.1947640.3111020.9797480.5948960.11741820.301

9、2460.2259220.923380.438870.2622120.29667630.4709230.1707080.4302070.1111190.6028430.31877840.2304880.2276640.1848160.2580650.7112160.42416750.8443090.4356990.9048810.408720.2217470.50785812345100.9055160.9376330.8037421.19732920.90551600.7063970.8950050.62161930.9376330.70639700.407080.83934740.8037

10、420.8950050.4070801.09901251.1973290.6216190.8393471.0990120Agglomerative Hierarchical Clustering340.40708250.621619670.706397180.803742link=linkage(dist)dendrogram(link)Agglomerative Hierarchical Clustering0.2077420.1947640.3111020.9797480.5948960.1174180.3012460.2259220.923380.438870.2622120.29667

11、60.4709230.1707080.4302070.1111190.6028430.3187780.2304880.2276640.1848160.2580650.7112160.4241670.8443090.4356990.9048810.408720.2217470.50785812345100.9055160.9376330.8037421.19732920.90551600.7063970.8950050.62161930.9376330.70639700.407080.83934740.8037420.8950050.4070801.09901251.1973290.621619

12、0.8393471.0990120Agglomerative Hierarchical Clustering0.2077420.1947640.3111020.9797480.5948960.1174180.3012460.2259220.923380.438870.2622120.2966760.4709230.1707080.4302070.1111190.6028430.3187780.2304880.2276640.1848160.2580650.7112160.4241670.8443090.4356990.9048810.408720.2217470.50785812345100.

13、9055160.9376330.8037421.19732920.90551600.7063970.8950050.62161930.9376330.70639700.407080.83934740.8037420.8950050.4070801.09901251.1973290.6216190.8393471.0990120Agglomerative Hierarchical Clustering0.2077420.1947640.3111020.9797480.5948960.1174180.3012460.2259220.923380.438870.2622120.2966760.470

14、9230.1707080.4302070.1111190.6028430.3187780.2304880.2276640.1848160.2580650.7112160.4241670.8443090.4356990.9048810.408720.2217470.5078581265100.9055160.8037421.19732920.90551600.7063970.62161960.8037420.70639700.83934751.1973290.6216190.83934706Agglomerative Hierarchical Clustering0.2077420.194764

15、0.3111020.9797480.5948960.1174180.3012460.2259220.923380.438870.2622120.2966760.4709230.1707080.4302070.1111190.6028430.3187780.2304880.2276640.1848160.2580650.7112160.4241670.8443090.4356990.9048810.408720.2217470.5078581265100.9055160.8037421.19732920.90551600.7063970.62161960.8037420.70639700.839

16、34751.1973290.6216190.83934706Agglomerative Hierarchical Clustering0.2077420.1947640.3111020.9797480.5948960.1174180.3012460.2259220.923380.438870.2622120.2966760.4709230.1707080.4302070.1111190.6028430.3187780.2304880.2276640.1848160.2580650.7112160.4241670.8443090.4356990.9048810.408720.2217470.50

17、7858167100.9055160.80374260.90551600.70639770.9376330.706397067Agglomerative Hierarchical Clustering0.2077420.1947640.3111020.9797480.5948960.1174180.3012460.2259220.923380.438870.2622120.2966760.4709230.1707080.4302070.1111190.6028430.3187780.2304880.2276640.1848160.2580650.7112160.4241670.8443090.

18、4356990.9048810.408720.2217470.507858167100.9055160.80374260.90551600.70639770.9376330.706397067Agglomerative Hierarchical Clustering0.2077420.1947640.3111020.9797480.5948960.1174180.3012460.2259220.923380.438870.2622120.2966760.4709230.1707080.4302070.1111190.6028430.3187780.2304880.2276640.1848160

19、.2580650.7112160.4241670.8443090.4356990.9048810.408720.2217470.50785818100.80374280.8037420678Divisive: This is a top down approach: all observations start in one cluster, and splits are performed recursively as one moves down the hierarchy.Divisive Hierarchical ClusteringAlgorithm: It has many met

20、hods, here Minimum Spanning Tree Clustering will introduced. Distance matrixGenerete MSTRemain one clusterOutput resultNYCut longest edgeDivisive Hierarchical Clustering12345100.9055160.9376330.8037421.19732920.90551600.7063970.8950050.62161930.9376330.70639700.407080.83934740.8037420.8950050.407080

21、1.09901251.1973290.6216190.8393471.0990120Distance matrix123450.9060.7060.9380.8041.1971.0990.4070.8390.6210.895Divisive Hierarchical Clustering123450.9060.7060.9380.8041.1971.0990.4070.8390.6210.895Divisive Hierarchical Clustering123450.9060.7060.9380.8041.1971.0990.4070.8390.6210.895Divisive Hiera

22、rchical Clustering123450.9060.7060.9380.8041.1971.0990.4070.8390.6210.895Divisive Hierarchical Clustering123450.9060.7060.9380.8041.1971.0990.4070.8390.6210.895Divisive Hierarchical Clustering123450.9060.7060.9380.8041.1971.0990.4070.8390.6210.895Divisive Hierarchical Clustering123450.9060.7060.9380

23、.8041.1971.0990.4070.8390.6210.895Divisive Hierarchical Clustering123450.7060.8040.4070.621Divisive Hierarchical Clustering123450.7060.8040.4070.6211,2,3,4,5Divisive Hierarchical Clustering12,3,4,5123450.7060.8040.4070.621Divisive Hierarchical Clustering12,53,4123450.7060.8040.4070.621Divisive Hiera

24、rchical Clustering1253,4123450.7060.8040.4070.621Divisive Hierarchical Clustering1253,4123450.7060.8040.4070.621340.40708250.621619670.706397180.803742Hierarchical ClusteringAgglomerativeDivisive(MST)Time costO(m2logm)O(m2)Space costO(m2)AdvantageHierarchical model will returnDistanvageTime and spac

25、e consuming, methods to calculate the distance between clusters is hard to determineTime and space consumingNoteUsually used to build a treeDensity-based ClusteringIn this method, clusters are defined as areas of higher density than the remainder of the data set. Objects in these sparse areas - that

26、 are required to separate clusters - are usually considered to be noise and border points.The most popular density based clustering method is DBSCAN(Density-based spatial clustering of applications with noise).ABCEpsEps: if two points distance is smaller than eps, they are defined as neighbor.Minpts

27、: the threshold to define one core point.Core point: point has more than minpts neighbors.Border point: not core point, but its neighbor.Noise point: not core point, not border point.Density-based ClusteringAlgorithm: Core pointBorder pointNoise pointNeighbor CoreP in same clusterAssign border point to clustersOutputRaw dataNeighbor MinptsYNeighbor of CorePN