{"id":461,"date":"2011-06-20T20:06:00","date_gmt":"2011-06-20T12:06:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=461"},"modified":"2023-11-02T20:08:12","modified_gmt":"2023-11-02T12:08:12","slug":"clustering","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/461","title":{"rendered":"Clustering"},"content":{"rendered":"\n

clustering(\u5206\u7fa4)<\/strong>
\u7121\u4e2d\u751f\u6709:\u4e00\u958b\u59cb\u6c92\u6709\u660e\u986f\u7684\u7fa4,\u662f\u6563\u4e82\u7684\u8cc7\u6599
unsupserised learning(\u975e\u76e3\u7763\u5f0f\u5b78\u7fd2)
\u901a\u5e38\u5148\u6709\u5206\u7fa4\u624d\u6709\u5206\u985e
ps:
classification(\u5206\u985e)
\u6709\u4e2d\u751f\u6709:\u7fa4\u5df1\u7d93\u5f62\u6210\u53ca\u53ef\u985e
supserised learning(\u76e3\u7763\u5f0f\u5b78\u7fd2)<\/p>\n\n\n\n

\u8aaa\u660e<\/strong>
\u8cc7\u6599\u5206\u7fa4\u80fd\u5c07\u6bcf\u7b46\u8cc7\u6599\uff0c\u900f\u904e\u8cc7\u6599\u7684\u5c6c\u6027\u503c\u4e4b\u76f8\u4f3c\u7a0b\u5ea6\uff0c\u81ea\u52d5\u805a\u96c6\u6210\u597d\u5e7e\u500b\u7fa4\u7d44\uff08cluster\uff09\uff0c\u4e00\u500b\u7fa4\u7d44\u8868\u793a\u7fa4\u7d44\u5167\u7684\u8cc7\u6599\u90fd\u975e\u5e38\u76f8\u4f3c\uff0c\u800c\u4e0d\u540c\u7fa4\u7d44\u7684\u8cc7\u6599\u90fd\u4e0d\u76f8\u4f3c\uff0c\u5728\u8cc7\u6599\u63a2\u52d8\u4e0a\uff0c\u9019\u7a2e\u53ea\u900f\u904e\u8cc7\u6599\u672c\u8eab\u7684\u5c6c\u6027\u5373\u80fd\u9032\u884c\u904b\u7b97\u7684\u65b9\u5f0f\uff0c\u4e5f\u7a31\u70ba\u975e\u76e3\u7763\u5f0f\u5b78\u7fd2\uff08unsupervised learning\uff09\u3002\u76f8\u5c0d\u65bc\u76e3\u7763\u5f0f\u5b78\u7fd2\uff08supervised learning\uff09\uff0c\u5fc5\u9808\u4f9d\u8cf4\u9810\u8a2d\u7684\u985e\u5225\u8207\u5305\u542b\u985e\u5225\u7684\u8a13\u7df4\u8cc7\u6599\uff0c\u50cf\u662f\u5206\u985e\uff08Classification\uff09\uff0c\u5fc5\u9808\u5148\u5b9a\u7fa9\u5404\u7fa4\u6240\u4ee3\u8868\u7684\u610f\u7fa9\u8207\u4e3b\u8981\u5c6c\u6027\uff0c\u7136\u5f8c\u4f9d\u7167\u8cc7\u6599\u8207\u5404\u7fa4\u7684\u76f8\u95dc\u6027\u9032\u884c\u904b\u7b97\u3002

\u61c9\u7528<\/strong>
\u8cc7\u6599\u5206\u7fa4\u88ab\u61c9\u7528\u7684\u9818\u57df\u5f88\u5ee3\uff0c\u4e0d\u7ba1\u662f\u5728\u5546\u696d\u6216\u751f\u7269\u5b78\u7b49\u9818\u57df\uff0c\u800c\u5728\u7570\u5e38\u5206\u6790\u4e2d\uff0c\u53ef\u4ee5\u900f\u904e\u5206\u7fa4\u7684\u65b9\u5f0f\u627e\u51fa\u96e2\u7570\u503c\uff0c\u5354\u52a9\u7a3d\u6838\u4eba\u54e1\u6aa2\u6e2c\u53ef\u7591\u7684\u8cc7\u6599\u3002 <\/p>\n\n\n\n


\u5206\u7fa4\u6b65\u9a5f<\/strong>
1.define attribute(\u5b9a\u7fa9\u5c6c\u6027):\u6b64\u90e8\u5206\u8207\u672c\u884c\u9ad8\u5ea6\u76f8\u95dc
2.coding(\u8f49\u78bc)
3.similarity measures
4.clustering\u548cexplain<\/p>\n\n\n\n

\u5206\u7fa4\u7684\u54c1\u8cea\u6307\u6a19<\/strong>
high intra-class similarity(\u7fa4\u5167\u9ad8\u76f8\u4f3c)
low inter-class similarity(\u7fa4\u9593\u4f4e\u76f8\u4f3c)
ps:\u4ee5\u4e0a\u5169\u9805\u53d6\u6c7a\u65bcsimilarity measure\u65b9\u5f0f
<\/strong><\/p>\n\n\n\n

\u5e38\u898b\u5206\u7fa4\u65b9\u6cd5
distance-based clustering:<\/strong>
\u5206\u5272\u5f0f\u5206\u7fa4\u6cd5(partitional clustering):\u9069\u5408\u7403\u9762\u5f62\u72c0\u8cc7\u6599,\u4e0d\u9069\u5408\u8907\u96dc\u5f62\u72c0
ex:k-mean,k-medoids\/pam,clara
\u968e\u5c64\u5f0f\u5206\u7fa4\u6cd5(hierarchical clustering):\u8a08\u7b97\u6210\u672c\u5c0f\u4f46\u7121\u6cd5\u4fee\u6b63\u932f\u8aa4,\u9664\u975e\u7528\u5176\u4ed6\u65b9\u5f0f\u505a\u4fee\u6b63
ex:birch,cure,rock
\u5bc6\u5ea6\u70ba\u57fa\u790e\u7684\u5206\u7fa4\u6cd5(density-based clustering):\u9069\u5408\u8907\u96dc\u5f62\u72c0,
ex:dbscan,optics,denclue,dbclasd,wavecluster 
\u683c\u72c0\u70ba\u57fa\u790e\u7684\u5206\u7fa4\u6cd5(grid-based clustering):\u8655\u7406\u6642\u9593\u8207\u8cc7\u6599\u591a\u5be1\u7121\u95dc,\u800c\u662f\u53d6\u6c7a\u65bc\u683c\u7684\u6578\u91cf ex:sting,qlique,wavecluster
model-based clustering<\/strong>:ex:EM-algorithm,SOM,
high-dimensional data <\/strong>clustering<\/strong>:\u9069\u5408\u5927\u91cf\u5c6c\u6027,\u53ef\u5206\u70ba\u5b50\u7a7a\u9593\u5206\u7fa4\u53ca\u983b\u7e41\u6a23\u5f0f\u5206\u7fa4 
constraint-based(\u9650\u5236\u5f0f\u5206\u7fa4)<\/strong>:ex:COD CLARANS
fuzzy clustering<\/strong>:ex:Fuzzy C-Means
[Paquet2004;datamining concepts and techniques2]<\/p>\n\n\n\n

hierarchical clustering methods<\/strong>
\u968e\u5c64\u5f0f,\u53ef\u5728\u5206\u70ba
agglomerative(\u805a\u5408\u5f0f),\u4f9d\u6548\u7387\u6392\u5e8f\u5982\u4e0b
\u3000single linkage(\u55ae\u4e00\u93c8\u7d50),\u6700\u5dee
\u3000complete linkage(\u5b8c\u5168\u93c8\u7d50),
\u3000average linkage(\u5e73\u5747\u93c8\u7d50),
\u3000ward’s method:\u6700\u597d
divisive(\u5206\u88c2\u5f0f),\u5148\u628a\u8cc7\u6599\u8996\u70ba\u540c\u4e00\u7fa4,\u5728\u540c\u4e2d\u6c42\u7570
\u3000\u5305\u62ecmst <\/p>\n\n\n\n

agglomerative hierarchiaal method<\/strong>
1\u958b\u59cb\u500b\u5225\u7269\u4ef6
2\u805a\u96c6\u5c07\u6700\u76f8\u4f3c\u7684\u7269\u4ef6
3\u4f9d\u4ed6\u5011\u7684\u76f8\u4f3c\u5ea6\u5408\u4f75\u6700\u521d\u7684\u7fa4
4\u7576\u76f8\u4f3c\u5ea6\u905e\u6e1b,\u6240\u6709\u5b50\u7fa4\u5408\u6210\u4e00\u500b\u5927\u7fa4<\/p>\n\n\n\n

…………………………………..<\/p>\n\n\n\n

similarity measures(\u76f8\u4f3c\u5ea6\u8a08\u7b97)<\/strong>
\u5206\u7fa4\u5c0d\u8c61\u5169\u5169\u4e4b\u9593\u76f8\u4f3c\u5ea6
\u5206\u985e\u8907\u96dc\u8cc7\u6599\u6642\u5148\u6e2c\u91cf\u76f8\u4f3c\u5ea6
\u9700\u8003\u616e\u7684\u6709
\u3000\u8b8a\u6578\u7279\u6027,\u5305\u62ecdiscrete(\u96e2\u6563),continuous(\u9023\u7e8c),binary(\u662f\u6216\u5426)
\u3000\u6e2c\u91cf\u5c3a\u5ea6,\u5305\u62ecnominal(\u540d\u76ee),ordinal(\u9806\u5e8f),interval(\u5340\u9593),ratio(\u6bd4\u7387)
\u3000subject matter knowledge(\u672c\u884c\u4e8b\u52d9\u77e5\u8b58)<\/p>\n\n\n\n

ps:
\u4f7f\u7528distance(\u8ddd\u96e2)\u63cf\u8ff0dissimilarities(\u76f8\u7570\u5ea6)
\u5e38\u898b\u516c\u5f0f\u6709
euclidean distance(\u6b50\u5e7e\u91cc\u5f97\u8ddd\u96e2)
minkowski metric
canberra metric
czekanowski coefficient
ps:\u4ee5\u4e0a\u7686\u70banonnegative variables(\u975e\u8ca0\u8b8a\u6578)<\/p>\n\n\n\n


…………………………………………………<\/p>\n\n\n\n

\u76f8\u4f3c\u5ea6\u4fc2\u6578\u8a08\u7b97
1\u5b9a\u7fa9\u5c6c\u6027<\/strong>
2\u5b9a\u7fa9\u8b8a\u6578<\/strong>
3\u9078\u53d6\u5176\u4e2d2\u9805\u6bd4\u8f03<\/strong>
\u76f8\u540c\u8868\u793a0,\u76f8\u7570\u8868\u793a1
a=abs(1-1)=0=match
b=abs(1-0)=1=mismatch
c=abs(0-1)=1=mismatch
d=abs(0-0)=0=match
4\u88fd\u4f5ccontingence table<\/strong><\/p>\n\n\n\n

 <\/td>k_1 k_0 <\/td>total <\/td><\/tr>
i_1
i_0 <\/td>		a b
c d <\/td>		a+b
c+d <\/td><\/tr>
total <\/td>a+c b+d <\/td>p=a+b+c+d  <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

5\u5957\u5165\u76f8\u4f3c\u5ea6\u4fc2\u6578<\/strong>
\u5e38\u7528\u7684\u6709
(a+d)\/p
a\/(a+b+c):0-0\u4e0d\u8003\u616e,\u53ea\u8003\u616e\u6709\u51fa\u73fe\u7684\u72c0\u614b
ex
1
\u5b9a\u7fa9\u5c6c\u6027<\/strong>
item mb flow os
ip1 68mb 1400flow xp
ip2 73mb 1850flow linux
ip3 67mb 1650flow mac
2
\u5b9a\u7fa9binary\u8b8a\u6578<\/strong>
x1={1 mb>=72, 0 mb<72}
x2={1 flow>=1500, 0 flow<1500}
x3={1 os=xp, 0 otherwise}
3
\u53d6\u5176\u4e2d2\u500bitem\u6bd4\u8f03<\/strong>
item x1 x2 x3
ip1 0 0 1
ip2 1 1 0
0-1\u67092\u500b
1-0\u67091\u500b
4
match\u548cmismatch\u6578\u91cf<\/strong><\/p>\n\n\n\n

 <\/td>ip2_1 ip2_0 <\/td>total <\/td><\/tr>
ip1_1
ip1_0 <\/td>		0 1
2 0 <\/td>		1
2 <\/td><\/tr>
total <\/td>2 1 <\/td>3  <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

5<\/strong>
\u5957\u5165\u76f8\u4f3c\u5ea6\u4fc2\u6578<\/strong>
(a+d)\/p=(0+0)\/3=0\/3=0<\/p>\n\n\n\n

…………………………………………………………………………………………………………………<\/p>\n\n\n\n

single linkage<\/strong>
1\u70ba\u6240\u6709\u53ef\u80fd\u6210\u5c0d\u7269\u4ef6\u8a08\u7b97\u76f8\u4f3c\u4fc2\u6578
2\u5f9e\u7b2c\u4e00\u500b\u7fa4\u4e2d\u9078\u64c72\u500b\u6700\u50cf\u7269\u4ef6
3\u964d\u4f4e\u76f8\u4f3c\u7a0b\u5ea6\u4e26\u5f62\u6210\u65b0\u7fa4,\u8a72\u65b0\u7fa4\u662f\u5305\u62ec\u6240\u6709\u76f8\u4f3c\u4fc2\u6578\u4e0d\u4f4e\u65bc\u9580\u6abb\u503c\u7684\u7269\u4ef6
4\u7e7c\u7e8c\u7b2c3\u6b65\u76f4\u5230\u5404\u7fa4\u6f38\u6f38\u8b8a\u6210\u4e00\u500b\u5927\u7fa4,\u6216\u5df1\u9054\u6307\u5b9a\u7684\u7fa4\u6578\u70ba\u6b62<\/p>\n\n\n\n

ex:
step1<\/strong><\/p>\n\n\n\n

 <\/td>1 <\/td>2 <\/td>3 <\/td>4 <\/td>5 <\/td><\/tr>
1 <\/td>0 <\/td> <\/td> <\/td> <\/td> <\/td><\/tr>
2 <\/td>9 <\/td>0 <\/td> <\/td> <\/td> <\/td><\/tr>
3 <\/td>3 <\/td>7 <\/td>0 <\/td> <\/td> <\/td><\/tr>
4 <\/td>6 <\/td>5 <\/td>9 <\/td>0 <\/td> <\/td><\/tr>
5 <\/td>11 <\/td>10 <\/td>2<\/strong> <\/td>8 <\/td>0 <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

\u8a72\u7fa4\u4e2d2\u6700\u5c0f
2\u5728\u7b2c5\u5217\u7b2c3\u884c,\u4ee5d(5,3)\u8868\u793a
\u7b2c1,2,4\u884c\u6216\u5217,\u4e0d\u57282\u7684\u884c\u5217,\u4ee5\u6b64\u7522\u751f\u65b0\u503c\u5982\u4e0b
d(5,3)1 = min{d(5,1),d(3,1)} = min{11,3}=3
d(5,3)2 = min{d(5,2),d(3,2)} = min{10,7}=7
d(5,3)4 = min{d(5,4),d(3,4)} = min{8,9}=8<\/p>\n\n\n\n

step2<\/strong><\/p>\n\n\n\n

 <\/td>(53) <\/td>1 <\/td>2 <\/td>4 <\/td><\/tr>
(53) <\/td>0 <\/td> <\/td> <\/td> <\/td><\/tr>
1 <\/td>3<\/strong> <\/td>0 <\/td> <\/td> <\/td><\/tr>
2 <\/td>7 <\/td>9 <\/td>0 <\/td> <\/td><\/tr>
4 <\/td>8 <\/td>6 <\/td>5 <\/td>0 <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

\u8a72\u7fa4\u4e2d3\u6700\u5c0f
3\u5728\u7b2c1\u5217\u7b2c(53)\u884c,\u4ee5d(1,(53))\u8868\u793a
\u7b2c2,4\u884c\u6216\u5217,\u4e0d\u57283\u7684\u884c\u5217,\u4ee5\u6b64\u7522\u751f\u65b0\u503c\u5982\u4e0b
d(1,(53))2 = min{d(1,2),d((53),2)} = min{9,7}=7
d(1,(53))4 = min{d(1,4),d((53),4)} = min{6,8}=6<\/p>\n\n\n\n

step3<\/strong><\/p>\n\n\n\n

 <\/td>(1(53)) <\/td>2 <\/td>4 <\/td><\/tr>
(1(53)) <\/td>0 <\/td> <\/td> <\/td><\/tr>
2 <\/td>7 <\/td>0 <\/td> <\/td><\/tr>
4 <\/td>6 <\/td>5<\/strong> <\/td>0 <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

\u8a72\u7fa4\u4e2d5\u6700\u5c0f
5\u5728\u7b2c4\u5217\u7b2c2\u884c,\u4ee5d(4,2)\u8868\u793a
\u7b2c(1(53))\u884c\u6216\u5217,\u4e0d\u57285\u7684\u884c\u5217,\u4ee5\u6b64\u7522\u65b0\u503c\u5982\u4e0b
d((4,2)(1(53)))=min{d(4,(1(53))),d(2,(1(53)))} = min{6,7} = 6<\/p>\n\n\n\n

step4<\/strong><\/p>\n\n\n\n

 <\/td>(1(53)) <\/td>(24) <\/td><\/tr>
(1(53)) <\/td>0 <\/td> <\/td><\/tr>
(24) <\/td>6 <\/td>0 <\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

…………………………………………………….<\/p>\n\n\n\n


\u4f7f\u7528\u5de5\u5177
minitab<\/p>\n\n\n\n

single,average,ward,complete,…\u7b49linkage\u6b65\u9a5f<\/strong>
1\u5148\u5c07\u8cc7\u6599\u8cbc\u5230worksheet
\u4f9d\u8f38\u5165\u8cc7\u6599\u5f62\u5f0f\u4e0d\u540c\u67092\u7a2e\u505a\u6cd5
\u82e5\u8f38\u5165\u8cc7\u6599\u70bamatrix\u5f62\u5f0f
\u30002\u9ede\u64cadata > copy > copy columns to matrix ,\u6703\u8df3\u51fa\u5c0d\u8a71\u8996\u7a97
\u30002.1\u5c07\u5de6\u6b04\u8981\u7528\u5230\u7684\u6b04\u4f4d\u9078\u53d6\u597d\u5f8c\u6309select,\u5247\u8981\u7528\u5230\u7684\u6b04\u4f4d\u6703\u51fa\u73fe\u5728\u53f3\u6b04copy from columns\u4e2d
\u30002.2\u5728store copied data\u5340\u57df\u4e2d\u8f38\u5165\u4e00\u6b04\u4f4d ex:d
\u30002.3\u9ede\u64caok,copy from columns\u5c0d\u8a71\u8996\u7a97\u95dc\u9589
\u30003\u9ede\u64castat > multivariate > cluster variables ,\u6703\u8df3\u51fa\u5c0d\u8a71\u8996\u7a97
\u82e5\u8f38\u5165\u8cc7\u6599\u70ba\u4e00\u7b46\u7b46\u7684\u5f62\u5f0f
\u30002\u8a72\u6b65\u9a5f\u53ef\u7701\u7565
\u30003\u9ede\u64castat > multivariate > cluster observation ,\u6703\u8df3\u51fa\u5c0d\u8a71\u8996\u7a97
3.1\u5c07\u5de6\u6b04\u4e2d\u57282.2\u5efa\u7684\u6b04\u4f4d\u9078\u53d6\u597d\u5f8c\u6309select,\u5247\u8a72\u6b04\u4f4d\u6703\u51fa\u73fe\u5728\u53f3\u6b04variables or distance matrix\u4e2d
3.2linkage method\u53ef\u9078\u64c7single,ward,complete,average,…\u7b49,\u4e26\u52fe\u9078show dendgrogram
3.3\u9ede\u64cacustomize,\u6703\u8df3\u51fa\u5c0d\u8a71\u8996\u7a97
3.3.1\u5728label y axis with \u9078\u64c7distance
3.3.2\u9ede\u64caok,customize\u5c0d\u8a71\u8996\u7a97\u95dc\u9589
3.4\u9ede\u64caok,cluster variables\u5c0d\u8a71\u8996\u7a97\u95dc\u9589
4\u7d50\u679c\u986f\u793a<\/p>\n","protected":false},"excerpt":{"rendered":"

clustering(\u5206\u7fa4)\u7121\u4e2d\u751f\u6709:\u4e00\u958b\u59cb\u6c92\u6709\u660e\u986f\u7684\u7fa4,\u662f …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[13],"tags":[],"class_list":["post-461","post","type-post","status-publish","format-standard","hentry","category-dataanalysis"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/461","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=461"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/461\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=461"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=461"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=461"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}