數(shù)據(jù)挖掘和分析29-W19A

1、聚類分析2014.12.30 第十九周數(shù)據(jù)挖掘和分析(fnx)共三十一頁簇的確認(qurn) Cluster Validity 如何驗證和評價聚類分析的結(jié)果？ “goodness” of the resulting clusters?But “clusters are in the eye of the beholder”! 為何(wih)評價聚類分析的結(jié)果?避免發(fā)現(xiàn)噪聲產(chǎn)生的模式比較不同的聚類算法比較不同的簇集合簇之間的比較共三十一頁隨機(su j)數(shù)據(jù)中被發(fā)現(xiàn)的簇 Clusters found in Random DataRandom PointsK-meansDBSCANComplete

2、 Link共三十一頁確定數(shù)據(jù)集的聚類趨勢 clustering tendency ，即是否(sh fu)存在非隨機結(jié)構(gòu) 確定正確的簇的個數(shù).評估聚類分析結(jié)果對數(shù)據(jù)的擬合情況 - Use only the data將聚類分析的結(jié)果跟已知的客觀結(jié)果（如，外部提供的類標號）比較比較不同的聚類方法的優(yōu)劣.1,2,3 非監(jiān)督3,4,5 進一步區(qū)分是評估整個聚類還是單個簇 簇確認(qurn)的重要問題 Cluster Validation共三十一頁三種度量方式外部指標(zhbio) External Index: 監(jiān)督的 Used to measure the extent to which cluste

3、r labels match externally supplied class labels.Entropy 熵內(nèi)部指標 Internal Index: 非監(jiān)督的 Used to measure the goodness of a clustering structure without respect to external information. Sum of Squared Error (SSE)相對指標 Relative Index: Used to compare two different clusterings or clusters. Often an external o

4、r internal index is used for this function, e.g., SSE or entropySometimes these are referred to as criteria instead of indicesHowever, sometimes criterion is the general strategy and index is the numerical measure that implements the criterion.簇確認(qurn)的度量 Measures of Cluster Validity共三十一頁兩個矩陣 Two m

5、atrices 鄰近性矩陣 Proximity Matrix理想的鄰近性矩陣 “Incidence” Matrix每個數(shù)據(jù)點對應(yīng)一行(yxng)一列矩陣中每項對應(yīng)的兩點如果是同簇，為1否則為 0 計算兩個矩陣的相關(guān)性Since the matrices are symmetric, only the correlation between n(n-1) / 2 entries needs to be calculated.高相關(guān)-簇中的點相近. Not a good measure for some density or contiguity based clusters.非監(jiān)督(jind)簇

6、評估：通過相關(guān) Via Correlation共三十一頁非監(jiān)督(jind)簇評估：通過相關(guān)Correlation of incidence and proximity matrices for the K-means clusterings of the following two data sets. Corr = -0.9235Corr = -0.5810共三十一頁根據(jù)簇對數(shù)據(jù)排序(pi x)后的相似性矩陣Order the similarity matrix with respect to cluster labels and inspect visually. 通過(tnggu)相似性

7、矩陣共三十一頁通過(tnggu)相似性矩陣Clusters in random data are not so crispDBSCAN共三十一頁通過(tnggu)相似性矩陣Clusters in random data are not so crispK-means共三十一頁通過(tnggu)相似性矩陣Clusters in random data are not so crispComplete Link共三十一頁通過(tnggu)相似性矩陣DBSCAN共三十一頁Clusters in more complicated figures arent well separated內(nèi)部指標 Int

8、ernal Index: 不需要外部(wib)信息Used to measure the goodness of a clustering structure without respect to external informationSSESSE 適合評估多個簇集或者多個簇 (average SSE).也可以用來估計簇的個數(shù)非監(jiān)督(jind)的 Internal Measures: SSE共三十一頁Internal Measures: SSESSE curve for a more complicated data setSSE of clusters found using K-mean

9、s共三十一頁需要框架來解釋度量. For example, if our measure of evaluation has the value, 10, is that good, fair, or poor?統(tǒng)計學角度聚類結(jié)果(ji gu)的分典型性意味著結(jié)果(ji gu)的正確性比較隨機數(shù)據(jù)和聚類后的數(shù)據(jù)的某項指標If the value of the index is unlikely, then the cluster results are validThese approaches are more complicated and harder to understand.如果比

10、較兩個不同的簇集, 框架必要性降低.However, there is the question of whether the difference between two index values is significant簇確認(qurn)的框架 Framework for Cluster Validity共三十一頁ExampleCompare SSE of 0.005 against three clusters in random dataHistogram shows SSE of three clusters in 500 sets of random data points o

11、f size 100 distributed over the range 0.2 0.8 for x and y valuesSSE的統(tǒng)計學框架(kun ji) Statistical Framework for SSE共三十一頁Correlation of incidence and proximity matrices for the K-means clusterings of the following two data sets. Statistical Framework for CorrelationCorr = -0.9235Corr = -0.5810共三十一頁簇凝聚(nn

12、gj)度 Cluster Cohesion: Measures how closely related are objects in a clusterExample: SSE簇分離度 Cluster Separation: Measure how distinct or well-separated a cluster is from other clustersExample: Squared ErrorCohesion is measured by the within cluster sum of squares (SSE)Separation is measured by the b

13、etween cluster sum of squaresWhere |Ci| is the size of cluster i Internal Measures: Cohesion and Separation共三十一頁凝聚(nngj)度和分離度Internal Measures: Cohesion and SeparationExample: SSEBSS + WSS = constant12345m1m2mK=2 clusters:K=1 cluster:共三十一頁A proximity graph based approach can also be used for cohesio

14、n and separation.Cluster cohesion is the sum of the weight of all links within a cluster.Cluster separation is the sum of the weights between nodes in the cluster and nodes outside the cluster.凝聚(nngj)度和分離度Internal Measures: Cohesion and Separationcohesionseparation共三十一頁Silhouette Coefficient combin

15、e ideas of both cohesion and separation, but for individual points, as well as clusters and clusteringsFor an individual point, iCalculate a = average distance of i to the points in its clusterCalculate b = min (average distance of i to points in another cluster)The silhouette coefficient for a poin

16、t is then given by s = 1 a/b if a b, (or s = b/a - 1 if a b, not the usual case) Typically between 0 and 1. The closer to 1 the better.Can calculate the Average Silhouette width for a cluster or a clustering輪廓(lnku)系數(shù) Internal Measures: Silhouette Coefficient共三十一頁外部(wib)指標 External Measures of Clust

17、er Validity: Entropy and Purity共三十一頁確定(qudng)正確的簇個數(shù)共三十一頁 “The validation of clustering structures is the most difficult and frustrating part of cluster analysis. Without a strong effort in this direction, cluster analysis will remain a black art accessible only to those true believers who have exper

18、ience and great courage.”Algorithms for Clustering Data, Jain and DubesFinal Comment on Cluster Validity共三十一頁使用(shyng)R完成Kmeans聚類newiris - iris;newiris$Species - NULL; #對訓練數(shù)據(jù)去掉分類標記kc - kmeans(newiris, 3); #分類模型訓練fitted(kc); #查看具體分類情況table(iris$Species, kc$cluster); #查看分類概括#聚類結(jié)果可視化 plot(newirisc(Sepa

19、l.Length, Sepal.Width), col = kc$cluster, pch = eger(iris$Species); #不同的顏色代表(dibio)不同的聚類結(jié)果，不同的形狀代表(dibio)訓練數(shù)據(jù)集的原始分類情況。points(kc$centers,c(Sepal.Length, Sepal.Width), col = 1:3, pch = 8, cex=2);共三十一頁/yucan1001/article/details/23123043共三十一頁require(graphics)# a 2-dimensional examplex - rbind(matrix(rno

20、rm(100, sd = 0.3), ncol = 2), matrix(rnorm(100, mean = 1, sd = 0.3), ncol = 2)colnames(x) - c(x, y)(cl - kmeans(x, 2)plot(x, col = cl$cluster)points(cl$centers, col = 1:2, pch = 8, cex = 2)# sum of squares# 其中scale函數(shù)提供數(shù)據(jù)中心化功能，所謂數(shù)據(jù)的中心化是指數(shù)據(jù)集中的各項數(shù)據(jù)減去數(shù)據(jù)集的均值，這個函數(shù)還提供數(shù)據(jù)的標準化功能，所謂數(shù)據(jù)的標準化是指中心化之后的數(shù)據(jù)在除以數(shù)據(jù)集的標準差，即

21、數(shù)據(jù)集中的各項數(shù)據(jù)減去數(shù)據(jù)集的均值再除以數(shù)據(jù)集的標準差。見/10/1834.htm。ss - function(x) sum(scale(x, scale = FALSE)2)# cluster centers fitted to each obs.:fitted.x - fitted(cl);head(fitted.x);resid.x - x - fitted(cl);# Equalities : -cbind(clc(betweenss, tot.withinss, totss), # the same two columns c(ss(fitted.x), ss(resid.x), ss(x)# kmeas聚類滿足(mnz)如下條件stopifnot(all.equal(cl$ totss, ss(x), all.equal(cl$ tot.withinss, ss(r