R 中的資料探勘演算法/聚類/模糊聚類 - 模糊 C 均值
< R 中的資料探勘演算法 | 聚類
聚類的目標是將一組資料點最小化到自相似的組中，使得屬於同一組的點比屬於不同組的點更相似。每個組被稱為一個簇。
本文將介紹文獻中討論的一種演算法，稱為模糊 C 均值。在介紹完技術後，將介紹一個實現該演算法的 R 包。最後，將使用該演算法進行一個案例研究，並展示獲得的結果。
模糊 C 均值（FCM - 經常使用 C 方法）是一種聚類方法，它允許一個點屬於一個或多個簇。該方法由 Dunn 於 1973 年提出，並由 Bezdek 於 1981 年改進，它經常用於模式識別。FCM 演算法試圖根據某些給定標準將有限的點集合劃分成 C 個模糊簇的集合。因此，位於簇邊緣的點可能與位於簇中心的點相比，在簇中的程度更低。FCM 演算法基於以下目標函式的最小化
FCM 也被稱為模糊 c 均值，因為它使用模糊邏輯 [Zadeh 1965]，因此每個例項並不只與一個簇相關聯，而是對每個存在的質心都有特定的隸屬度。為此，演算法建立了一個關聯矩陣 U，其中每個項 μij 表示樣本 i 對簇 j 的隸屬度。在 FCM 演算法中，有一個模糊度變數 m，使得 1.0 < m < ，其中 m 是一個實數。m 越接近無窮大 ()，解決方案的模糊度就越高，越接近 1，解決方案就越類似於二進位制 k 均值的聚類 [Bezdek 1981]。一個不錯的選擇是將 m 設定為 2.0 [Hathaway and Bezdek 2001]。
你可以在同一個虛擬碼中看到 k 均值和 FCM，如（演算法 1）中所述。其中，我們只有透過更改計算 μij 項的公式來獲得 k 均值或 FCM，將模糊平均 [Zadeh 1965] 更改為二進位制選擇，表明 FCM 實際上是模糊的 K 均值。
在（演算法 1）中，方式表明 是 a 到 b 的歐幾里得距離，輸入：樣本集 xi（1 < i < N）、簇數 K、模糊因子 m、容差因子，我們輸出：簇向量 ci（1 < i < K）和矩陣 U，它確定每個樣本與每個簇的關聯性。需要注意的是，矩陣 U 的值只取決於 H（儲存示例到簇的距離的陣列）和 m 的值。簇的更新完全取決於迭代中矩陣 U 的值。
上面描述的演算法由 R 包“e1071”實現，該包於 2010 年 4 月 21 日釋出。該包具有 GPL-2 許可證，可以在 CRAN 倉庫中找到。
安裝 CBA 包
install.packages("e1071")
匯入方法和演算法
library("e1071")
用法
cmeans(x, centers, iter.max = 100, verbose = FALSE,
dist = "euclidean", method = "cmeans", m = 2,
rate.par = NULL, weights = 1, control = list())
引數
• x: The data matrix where columns correspond to variables and rows to observations. • centers: Number of clusters or initial values for cluster centers. • iter.max: Maximum number of iterations. • verbose: If TRUE, make some output during learning. • dist: Must be one of the following: If "euclidean", the mean square error, if "manhattan", the mean absolute error is computed. Abbreviations are also accepted. • method: If "cmeans", then we have the c-means fuzzy clustering method, if "ufcl" we have the on-line update. Abbreviations are also accepted. • m: A number greater than 1 giving the degree of fuzzification. • rate.par: A number between 0 and 1 giving the parameter of the learning rate for the on-line variant. The default corresponds to 0:3. • weights: a numeric vector with non-negative case weights. Recycled to the number of observations in x if necessary. • control: a list of control parameters. See Details.
如果一切正常，將返回一個 fclust 物件。該物件具有以下元件
• centers: the final cluster centers. • size: the number of data points in each cluster of the closest hard clustering. • cluster: a vector of integers containing the indices of the clusters where the data points are assigned to for the closest hard clustering, as obtained by assigning points to the (first) class with maximal membership. • iter: the number of iterations performed. • membership: a matrix with the membership values of the data points to the clusters. • withinerror: the value of the objective function. • call: the call used to create the object.
有一種方法可以顯示該演算法的結果。該方法是列印 fclust 物件。
print(fclust)
為了說明所研究的包實現的方法，我們建立了兩個示例。第一個示例建立了一個二維陣列，第二個示例建立了一個三維陣列。在兩個示例中，我們都使用了正態分佈，其平均值範圍不同，並使用 0.3 的標準差。
示例 1
# a 2-dimensional example x<-rbind(matrix(rnorm(100,sd=0.3),ncol=2), matrix(rnorm(100,mean=1,sd=0.3),ncol=2)) cl<-cmeans(x,2,20,verbose=TRUE,method="cmeans",m=2) print(cl)
示例 2
# a 3-dimensional example x<-rbind(matrix(rnorm(150,sd=0.3),ncol=3), matrix(rnorm(150,mean=1,sd=0.3),ncol=3), matrix(rnorm(150,mean=2,sd=0.3),ncol=3)) cl<-cmeans(x,6,20,verbose=TRUE,method="cmeans") print(cl)
輸出 - 示例 1
輸出 - 示例 2
以下主題描述了案例研究，以展示使用模糊 C 均值獲得的結果。
在提出的案例研究中，我們使用了 R 包 Iris 中可用的資料庫。該資料庫包含 150 個例項，每個例項包含花瓣的特徵。資料庫的每個例項都有其分類。資料庫的例項有三種不同的分類（setosa、versicolor 和 virginica）。所研究的資料庫中每個類別都有 50 個示例，總共 150 個例項。除了每個例項中的類別定義之外，其他特徵還有
可以使用以下命令在 R 語言中載入實驗中使用的鳶尾花資料庫。
data(iris)
下表顯示了鳶尾花資料庫中的一部分樣本資料。
表 1: 鳶尾花資料庫樣本
| 例項 | 萼片長度 | 萼片寬度 | 花瓣長度 | 花瓣寬度 | 物種 |
|---|---|---|---|---|---|
| 1 | 5.1 | 3.5 | 1.4 | 0.2 | layak |
| 2 | 4.9 | 3.0 | 1.4 | 0.2 | Tidak layak |
| 3 | 4.7 | 3.2 | 1.3 | 0.2 | layak |
| 72 | 6.1 | 2.8 | 4.0 | 1.3 | layak |
| 73 | 6.3 | 2.5 | 4.9 | 1.5 | layak |
| 114 | 5.7 | 2.5 | 5.0 | 2.0 | layak |
| 115 | 5.8 | 2.8 | 5.1 | 2.4 | layak |
為了使用模糊 C 均值演算法生成結果，請執行以下指令碼。
data(iris) x<-rbind(iris$Sepal.Length, iris$Sepal.Width, iris$Petal.Length) x<-t(x) result<-cmeans(x,3,50,verbose=TRUE,method="cmeans") print(result) s3d <- scatterplot3d(result$membership, color=result$cluster, type="h", angle=55, scale.y=0.7, pch=16, main="Pertinence") plot(iris, col=result$cluster)
執行指令碼後得到的結果如下所示。
Fuzzy c-means clustering with 3 clusters
Cluster centers:
[,1] [,2] [,3]
1 5.003653 3.412805 1.484775
2 5.874034 2.760272 4.382520
3 6.793622 3.054510 5.644347
Memberships:
1 2 3
[1,] 0.9964733414 2.388793e-03 1.137865e-03
[2,] 0.9730096494 1.850758e-02 8.482767e-03
[3,] 0.9776389508 1.515266e-02 7.208389e-03
[4,] 0.9635322892 2.503070e-02 1.143701e-02
[5,] 0.9939984763 4.051202e-03 1.950322e-03
[6,] 0.9304507689 4.703382e-02 2.251542e-02
[7,] 0.9775132049 1.523242e-02 7.254371e-03
[8,] 0.9999369153 4.314160e-05 1.994308e-05
[9,] 0.9225703038 5.279889e-02 2.463081e-02
[10,] 0.9834280681 1.141773e-02 5.154205e-03
[11,] 0.9636309639 2.453957e-02 1.182947e-02
[12,] 0.9914862878 5.851313e-03 2.662399e-03
[13,] 0.9693327053 2.101145e-02 9.655842e-03
[14,] 0.9162524471 5.600693e-02 2.774062e-02
[15,] 0.8773228961 7.968730e-02 4.298980e-02
[16,] 0.8300898328 1.098729e-01 6.003725e-02
[17,] 0.9444844043 3.671434e-02 1.880126e-02
[18,] 0.9964733414 2.388793e-03 1.137865e-03
[19,] 0.8917869903 7.312086e-02 3.509215e-02
[20,] 0.9768481880 1.559135e-02 7.560459e-03
[21,] 0.9638052097 2.505889e-02 1.113590e-02
[22,] 0.9862983266 9.267056e-03 4.434618e-03
[23,] 0.9544955743 3.001379e-02 1.549064e-02
[24,] 0.9879996300 8.348552e-03 3.651818e-03
[25,] 0.9619796590 2.665281e-02 1.136753e-02
[26,] 0.9700883809 2.080884e-02 9.102779e-03
[27,] 0.9978125723 1.505741e-03 6.816871e-04
[28,] 0.9927414381 4.946076e-03 2.312486e-03
[29,] 0.9931235860 4.671305e-03 2.205109e-03
[30,] 0.9770882461 1.581612e-02 7.095630e-03
[31,] 0.9761442368 1.652997e-02 7.325795e-03
[32,] 0.9748518908 1.716740e-02 7.980706e-03
[33,] 0.9320017983 4.510961e-02 2.288859e-02
[34,] 0.8927033428 7.017637e-02 3.712029e-02
[35,] 0.9834280681 1.141773e-02 5.154205e-03
[36,] 0.9833813658 1.121223e-02 5.406405e-03
[37,] 0.9595420958 2.713202e-02 1.332588e-02
[38,] 0.9926144115 4.984365e-03 2.401224e-03
[39,] 0.9331691292 4.525365e-02 2.157722e-02
[40,] 0.9984835370 1.037187e-03 4.792755e-04
[41,] 0.9942973683 3.839814e-03 1.862818e-03
[42,] 0.8379960489 1.102335e-01 5.177041e-02
[43,] 0.9474894758 3.543286e-02 1.707767e-02
[44,] 0.9966468801 2.299980e-03 1.053140e-03
[45,] 0.9422485213 3.983938e-02 1.791210e-02
[46,] 0.9693327053 2.101145e-02 9.655842e-03
[47,] 0.9736866788 1.782324e-02 8.490078e-03
[48,] 0.9713101708 1.953226e-02 9.157566e-03
[49,] 0.9741716274 1.744780e-02 8.380577e-03
[50,] 0.9970704014 1.996528e-03 9.330710e-04
[51,] 0.0396263985 3.645217e-01 5.958519e-01
[52,] 0.0318692598 7.303043e-01 2.378264e-01
[53,] 0.0257989245 2.759514e-01 6.982496e-01
[54,] 0.0547597033 8.587710e-01 8.646929e-02
[55,] 0.0257236267 7.190557e-01 2.552207e-01
[56,] 0.0044884340 9.781328e-01 1.737878e-02
[57,] 0.0312129593 6.547331e-01 3.140540e-01
[58,] 0.2958341637 5.694232e-01 1.347426e-01
[59,] 0.0303580096 6.398237e-01 3.298183e-01
[60,] 0.0880779511 8.134764e-01 9.844565e-02
[61,] 0.2205273013 6.298451e-01 1.496276e-01
[62,] 0.0105098293 9.591134e-01 3.037677e-02
[63,] 0.0462415004 8.537411e-01 1.000174e-01
[64,] 0.0127683343 8.793406e-01 1.078911e-01
[65,] 0.1097850604 7.908698e-01 9.934511e-02
[66,] 0.0439788476 6.323928e-01 3.236284e-01
[67,] 0.0142403104 9.357246e-01 5.003511e-02
[68,] 0.0107489244 9.647242e-01 2.452687e-02
[69,] 0.0297161608 8.212906e-01 1.489932e-01
[70,] 0.0472514422 8.832597e-01 6.948890e-02
[71,] 0.0244685053 7.865167e-01 1.890147e-01
[72,] 0.0231707557 9.204749e-01 5.635439e-02
[73,] 0.0242412459 6.647915e-01 3.109672e-01
[74,] 0.0115014923 8.931765e-01 9.532196e-02
[75,] 0.0252735484 8.457138e-01 1.290126e-01
[76,] 0.0367090402 7.041271e-01 2.591639e-01
[77,] 0.0295101840 4.167745e-01 5.537153e-01
[78,] 0.0196749600 2.703807e-01 7.099444e-01
[79,] 0.0046165774 9.710517e-01 2.433168e-02
[80,] 0.1233870645 7.695546e-01 1.070584e-01
[81,] 0.0763633248 8.316087e-01 9.202798e-02
[82,] 0.0956781157 8.038125e-01 1.005094e-01
[83,] 0.0317355256 9.149948e-01 5.326970e-02
[84,] 0.0237392176 6.474085e-01 3.288522e-01
[85,] 0.0279975037 8.909775e-01 8.102497e-02
[86,] 0.0346333192 7.957193e-01 1.696474e-01
[87,] 0.0327144512 4.847696e-01 4.825159e-01
[88,] 0.0287006017 8.325287e-01 1.387707e-01
[89,] 0.0265872664 9.220512e-01 5.136156e-02
[90,] 0.0425465997 8.901942e-01 6.725921e-02
[91,] 0.0165454512 9.380639e-01 4.539066e-02
[92,] 0.0126391727 8.984548e-01 8.890606e-02
[93,] 0.0217893662 9.356063e-01 4.260431e-02
[94,] 0.2778346035 5.864740e-01 1.356914e-01
[95,] 0.0130250339 9.574755e-01 2.949948e-02
[96,] 0.0143369500 9.506283e-01 3.503480e-02
[97,] 0.0098869130 9.658287e-01 2.428443e-02
[98,] 0.0128272275 9.306614e-01 5.651133e-02
[99,] 0.3958967535 4.819128e-01 1.221905e-01
[100,] 0.0138782641 9.568112e-01 2.931057e-02
[101,] 0.0168213369 1.202409e-01 8.629378e-01
[102,] 0.0261693250 7.099212e-01 2.639094e-01
[103,] 0.0064283347 4.003438e-02 9.535373e-01
[104,] 0.0121558071 1.363357e-01 8.515085e-01
[105,] 0.0051285341 4.386983e-02 9.510016e-01
[106,] 0.0380603711 1.582822e-01 8.036574e-01
[107,] 0.0796613905 7.682136e-01 1.521250e-01
[108,] 0.0215250742 1.079049e-01 8.705700e-01
[109,] 0.0133896976 1.083710e-01 8.782393e-01
[110,] 0.0222927779 1.077325e-01 8.699748e-01
[111,] 0.0188704621 2.634073e-01 7.177222e-01
[112,] 0.0170114260 2.579486e-01 7.250400e-01
[113,] 0.0012069886 1.088884e-02 9.879042e-01
[114,] 0.0272794217 7.782927e-01 1.944279e-01
[115,] 0.0260263274 7.022101e-01 2.717635e-01
[116,] 0.0143300831 1.808070e-01 8.048629e-01
[117,] 0.0055448160 6.051225e-02 9.339429e-01
[118,] 0.0542553271 1.919346e-01 7.538101e-01
[119,] 0.0522340053 2.006703e-01 7.470957e-01
[120,] 0.0331219678 6.903576e-01 2.765205e-01
[121,] 0.0016396213 1.177291e-02 9.865875e-01
[122,] 0.0232292512 8.358772e-01 1.408936e-01
[123,] 0.0446065451 1.785215e-01 7.768719e-01
[124,] 0.0214638942 6.565434e-01 3.219927e-01
[125,] 0.0033893690 2.584416e-02 9.707665e-01
[126,] 0.0114583443 6.335614e-02 9.251855e-01
[127,] 0.0173352405 7.863541e-01 1.963106e-01
[128,] 0.0207474129 7.187218e-01 2.605308e-01
[129,] 0.0101190052 1.107064e-01 8.791746e-01
[130,] 0.0076951023 4.751066e-02 9.447942e-01
[131,] 0.0203964684 1.059183e-01 8.736853e-01
[132,] 0.0542244082 1.915598e-01 7.542157e-01
[133,] 0.0101190052 1.107064e-01 8.791746e-01
[134,] 0.0209695496 4.545456e-01 5.244849e-01
[135,] 0.0248052462 2.990893e-01 6.761055e-01
[136,] 0.0299588767 1.357829e-01 8.342583e-01
[137,] 0.0163979126 1.472580e-01 8.363440e-01
[138,] 0.0087535054 9.693234e-02 8.943141e-01
[139,] 0.0169168345 8.303003e-01 1.527828e-01
[140,] 0.0037050972 3.198944e-02 9.643055e-01
[141,] 0.0006389323 5.579855e-03 9.937812e-01
[142,] 0.0153630352 1.530446e-01 8.315924e-01
[143,] 0.0261693250 7.099212e-01 2.639094e-01
[144,] 0.0036930153 2.507113e-02 9.712359e-01
[145,] 0.0033893690 2.584416e-02 9.707665e-01
[146,] 0.0106923302 1.279688e-01 8.613389e-01
[147,] 0.0250155507 5.900274e-01 3.849571e-01
[148,] 0.0138756337 2.012898e-01 7.848346e-01
[149,] 0.0230709595 2.493458e-01 7.275832e-01
[150,] 0.0261065981 6.399365e-01 3.339569e-01
Closest hard clustering:
[1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
[46] 1 1 1 1 1 3 2 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 2 2 2 2
[91] 2 2 2 2 2 2 2 2 2 2 3 2 3 3 3 3 2 3 3 3 3 3 3 2 2 3 3 3 3 2 3 2 3 2 3 3 2 2 3 3 3 3 3 3 3
[136] 3 3 3 2 3 3 3 2 3 3 3 2 3 3 2
Available components:
[1] "centers" "size" "cluster" "membership" "iter" "withinerror"
[7] "call"
下圖顯示了每個樣本對每個生成叢集的相關性。每個生成的叢集可以用一種顏色（綠色、紅色或黑色）來識別。
下面的圖表顯示了每個例項的分類，透過比較資料庫中存在的每對屬性來實現。
模糊 C 均值演算法的應用允許對類別進行同質分組，正如預期的那樣。很快，三個生成的類別具有非常相似的例項數量。除了對給定例項進行分類的類別之外，該演算法還展示了該例項與該類別的相關性。此資訊允許負責分析結果的人員將注意力集中在與特定類別無關程度較高的事件上。
應該分析那些相關性不高的資料庫例項（相關性程度由使用者定義），以確認它們是否確實屬於演算法確定的類別。在顯示相關性的圖表中，可以發現標為紅色的類別 2 中的一些例項相關性程度並不高。這可能表明演算法在分類方面可能存在錯誤，因為這些例項的屬性值並沒有以高度確定的程度識別這些例項。
J. C. Dunn (1973): "A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters", Journal of Cybernetics 3: 32-57
J. C. Bezdek (1981): "Pattern Recognition with Fuzzy Objective Function Algorithms", Plenum Press, New York Tariq Rashid: “Clustering”
L. A. Zadeh (1965): "Fuzzy sets and systems". In: Fox J, editor. System Theory. Brooklyn, NY: Polytechnic Press, 1965: 29–39.
鳶尾花資料庫: http://archive.ics.uci.edu/ml/datasets/Iris
R 統計計算專案: http://www.r-project.org/
W. Meira; M. Zaki: 資料探勘演算法基礎: http://www.dcc.ufmg.br/miningalgorithms/DokuWiki/doku.php