📄 csdn技术中心 聚类算法的一个教程.htm
字号:
<TD vAlign=top bgColor=#ededed>
<TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
<TBODY>
<TR>
<TD align=right background="CSDN技术中心 聚类算法的一个教程.files/top.gif"
height=27><FONT
class=fonttitle>积极原创作者 </FONT></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=1 cellPadding=2 width="100%" border=0>
<TBODY>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/ixue">ixue</A> <FONT
color=#ff0000>(20)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/Solstice">Solstice</A> <FONT
color=#ff0000>(7)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/retni">retni</A> <FONT
color=#ff0000>(2)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/zhangweis">zhangweis</A> <FONT
color=#ff0000>(4)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/legendinfo">legendinfo</A> <FONT
color=#ff0000>(12)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/NETOCOOL">NETOCOOL</A> <FONT
color=#ff0000>(23)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/leek2000">leek2000</A> <FONT
color=#ff0000>(4)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/alon21">alon21</A> <FONT
color=#ff0000>(1)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/niaoked">niaoked</A> <FONT
color=#ff0000>(4)</FONT></TD></TR>
<TR>
<TD align=right><A
href="http://dev.csdn.net/user/huitiansou">huitiansou</A> <FONT
color=#ff0000>(3)</FONT></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></TD>
<TD vAlign=top width=786>
<TABLE cellPadding=4 width="100%" border=0>
<TBODY>
<TR>
<TD width=10 height=19></TD>
<TD height=19>
<TABLE cellSpacing=3 cellPadding=3 width="100%" border=0>
<TBODY>
<TR>
<TD><A href="http://www.csdn.net/">CSDN</A> - <A
href="http://dev.csdn.net/">文档中心</A> - <FONT color=#003399><A
id=ArticleTitle1_ArticleTitle1_hlClass
href="http://dev.csdn.net/articlelist.aspx?c=13">其他</A></FONT>
</TD>
<TD align=right>阅读：<SPAN
id=ArticleTitle1_ArticleTitle1_lblReadCount>170</SPAN>
评论： <SPAN
id=ArticleTitle1_ArticleTitle1_lblCommentCount>0</SPAN>
<A
href="http://dev.csdn.net/Develop/article/42/article/46/46175.shtm#Comment">参与评论</A>
</TD></TR></TBODY></TABLE>
<TABLE cellSpacing=3 cellPadding=3 width="100%" bgColor=#eeeeee
border=0>
<TBODY>
<TR>
<TD noWrap width=60 height=0></TD>
<TD></TD></TR>
<TR>
<TD noWrap align=middle bgColor=#003399 height=16><FONT
color=#ffffff>标题</FONT></TD>
<TD><B> <SPAN
id=ArticleTitle1_ArticleTitle1_lblTitle>聚类算法的一个教程</SPAN></B>
选择自 <A id=ArticleTitle1_ArticleTitle1_AuthorLink
href="http://dev.csdn.net/user/laughcry2002">laughcry2002</A>
的 Blog </TD></TR>
<TR>
<TD align=middle bgColor=#003399 height=16><FONT
color=#ffffff>关键字</FONT></TD>
<TD width=500> <SPAN
id=ArticleTitle1_ArticleTitle1_lblKeywords>聚类算法的一个教程</SPAN></TD></TR>
<TR>
<TD align=middle bgColor=#003399 height=16><FONT
color=#ffffff>出处</FONT></TD>
<TD> <SPAN
id=ArticleTitle1_ArticleTitle1_lblSource></SPAN></TD></TR></TBODY></TABLE></TD></TR>
<TR>
<TD width=10></TD>
<TD><SPAN id=ArticleContent1_ArticleContent1_lblContent>原文出自: <A
href="http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/hierarchical.html">http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/hierarchical.html</A><BR>辅助资料:
<A
href="http://149.170.199.144/multivar/ca.htm">http://149.170.199.144/multivar/ca.htm</A><BR><BR>层次式聚类方法<BR><BR>
<P align=justify><FONT face="Arial, Helvetica, sans-serif"
size=+1><EM>How They Work</EM></FONT><FONT
face="Times New Roman, Times, serif"><BR><BR>给定要聚类的N的对象以及N*N的距离矩阵(或者是相似性矩阵),
层次式聚类方法的基本步骤(参看<A
href="http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/hierarchical.html#johnson">S.C.
Johnson in 1967</A>)如下:</FONT></P>
<OL>
<LI><FONT face="Times New Roman, Times, serif"
align="justify">将每个对象归为一组, 共得到N组, 每组仅包含一个对象.
组与组之间的距离就是它们所包含的对象之间的距离.</FONT>
<LI><FONT face="Times New Roman, Times, serif">将最近的两个组合并成一组,
于是总的组数少了一个.</FONT>
<LI><FONT
face="Times New Roman, Times, serif">重新计算新的组与所有旧组之间的距离.</FONT>
<LI><FONT face="Times New Roman, Times, serif">重复第2步和第3步,
直到最后合并成一个组为止(此组包含了N个对象).</FONT></LI></OL>
<P><FONT face="Times New Roman, Times, serif">根据步骤3的不同,
可将层次式聚类方法分为几类: <EM>single-linkage,</EM> <EM>complete-linkage</EM> 以及
<EM>average-linkage</EM> 聚类方法等.<BR><EM>single-linkage</EM> 聚类法(也称
<EM>connectedness</EM> 或 <EM>minimum</EM> 方法):
组间距离等于两组对象之间的<U>最小距离</U>. <BR><EM>complete-linkage</EM> 聚类法 (也称
<EM>diameter</EM> 或 <EM>maximum</EM> 方法):
组间距离等于两组对象之间的<U>最大距离</U>.<BR><EM>average-linkage</EM> 聚类法:
组间距离等于两组对象之间的<U>平均距离</U>.<BR>average-link 聚类的一个变种是<A
href="http://www.elet.polimi.it/upload/matteucc/Clustering/tutorial_html/hierarchical.html#dandrade">R.
D'Andrade (1978)</A> 的UCLUS方法, 它使用的是<U>median</U>距离, 在受异常数据对象的影响方面,
它要比平均距离表现更佳一些.<BR><BR></P>
<P align=justify><FONT face="Arial, Helvetica, sans-serif"
size=+1><EM>Single-Linkage Clustering: The
Algorithm</EM></FONT><FONT
face="Times New Roman, Times, serif"><BR>Let’s now take a deeper
look at how Johnson’s algorithm works in the case of single-linkage
clustering.<BR>The algorithm is an agglomerative scheme that erases
rows and columns in the proximity matrix as old clusters are merged
into new ones.</FONT></P>
<P align=justify><FONT face="Times New Roman, Times, serif">The N*N
proximity matrix is D = [d(i,j)]. The clusterings are assigned
sequence numbers 0,1,......, (n-1) and L(k) is the level of the kth
clustering. A cluster with sequence number m is denoted (m) and the
proximity between clusters (r) and (s) is denoted d [(r),(s)].
</FONT></P>
<P align=justify><FONT face="Times New Roman, Times, serif">The
algorithm is composed of the following steps:<BR></P>
<OL>
<LI><EM><FONT face="Times New Roman, Times, serif"
align="justify">Begin with the disjoint clustering having level
L(0) = 0 and sequence number m = 0.<BR></FONT></EM>
<LI><EM><FONT face="Times New Roman, Times, serif">Find the least
dissimilar pair of clusters in the current clustering, say pair
(r), (s), according to</FONT><BR><FONT
face="Times New Roman, Times, serif"><BR>d[(r),(s)] = min
d[(i),(j)]</FONT><BR><FONT
face="Times New Roman, Times, serif"><BR>where the minimum is over
all pairs of clusters in the current clustering.<BR></FONT></EM>
<LI><EM><FONT face="Times New Roman, Times, serif">Increment the
sequence number : m = m +1. Merge clusters (r) and (s) into a
single cluster to form the next clustering m. Set the level of
this clustering to</FONT><BR><FONT
face="Times New Roman, Times, serif"><BR>L(m) =
d[(r),(s)]<BR></FONT></EM>
<LI><EM><FONT face="Times New Roman, Times, serif">Update the
proximity matrix, D, by deleting the rows and columns
corresponding to clusters (r) and (s) and adding a row and column
corresponding to the newly formed cluster. The proximity between
the new cluster, denoted (r,s) and old cluster (k) is defined in
this way:</FONT><BR><FONT
face="Times New Roman, Times, serif"><BR>d[(k), (r,s)] = min
d[(k),(r)], d[(k),(s)]<BR></FONT></EM>
<LI><EM><FONT face="Times New Roman, Times, serif">If all objects
are in one cluster, stop. Else, go to step 2.</FONT></EM>
</LI></OL></FONT></FONT></SPAN><BR>
<DIV
style="FONT-SIZE: 14px; LINE-HEIGHT: 25px"><STRONG>作者Blog：</STRONG><A
id=ArticleContent1_ArticleContent1_AuthorBlogLink
href="http://blog.csdn.net/laughcry2002/"
target=_blank>http://blog.csdn.net/laughcry2002/</A></DIV>
<DIV
style="FONT-SIZE: 14px; COLOR: #900; LINE-HEIGHT: 25px"><STRONG>相关文章</STRONG></DIV>
<TABLE id=ArticleContent1_ArticleContent1_RelatedArticles
style="BORDER-COLLAPSE: collapse" cellSpacing=0 border=0>
<TBODY>
<TR>
<TD><A
href="http://dev.csdn.net/Develop/article/42/article/46/article/46/46175.shtm">聚类算法的一个教程</A>
</TD></TR>
<TR>
<TD><A
href="http://dev.csdn.net/Develop/article/42/article/46/article/42/42413.shtm">JDK
1.5引入的新特性 -- 泛型</A> </TD></TR>
<TR>
<TD><A
href="http://dev.csdn.net/Develop/article/42/article/46/article/38/38009.shtm">DNA单字符表示法的兼并性</A>
</TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><A name=#Comment></A>
<TABLE cellPadding=0 width="100%" border=0>
<TBODY>
<TR>
<TD>
<TABLE cellSpacing=0 cellPadding=0 width="100%" align=center
bgColor=#006699 border=0>
<TBODY>
<TR bgColor=#006699>
<TD id=white align=middle width=556 bgColor=#006699><FONT
color=#ffffff>对该文的评论</FONT> </TD></TR></TBODY></TABLE>
<DIV align=right><A id=CommnetList1_CommnetList1_Morelink
href="http://comment.csdn.net/Comment.aspx?c=2&s=46175">【评论】</A>
<A id=CommnetList1_CommnetList1_Hyperlink1
href="javascript:window.close();">【关闭】</A>
</DIV><BR></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE></FORM><!-- 版权 -->
<HR align=center width=770 noShade SIZE=1>
<TABLE cellSpacing=0 cellPadding=0 width=500 align=center border=0>
<TBODY>
<TR>
<TD vAlign=bottom align=middle height=10><A
href="http://www.csdn.net/intro/intro.asp?id=2">网站简介</A> - <A
href="http://www.csdn.net/intro/intro.asp?id=5">广告服务</A> - <A
href="http://www.csdn.net/map/map.shtm">网站地图</A> - <A
href="http://www.csdn.net/help/help.asp">帮助信息</A> - <A
href="http://www.csdn.net/intro/intro.asp?id=2">联系方式</A> - <A
href="http://www.csdn.net/english">English</A> </TD>
<TD align=middle rowSpan=3><A
href="http://www.hd315.gov.cn/beian/view.asp?bianhao=010202001032100010"><IMG
height=48 src="CSDN技术中心 聚类算法的一个教程.files/biaoshi.gif" width=40
border=0></A></TD></TR>
<TR>
<TD vAlign=top align=middle>北京百联美达美数码科技有限公司 版权所有 京ICP证020026号</TD></TR>
<TR align=middle>
<TD vAlign=top><FONT face=Verdana>Copyright © CSDN.NET, Inc. All Rights
Reserved</FONT></TD></TR>
<TR>
<TD height=15></TD></TR></TBODY></TABLE><!-- /版权 -->
<SCRIPT>
document.write("<img src=http://count.csdn.net/count/pageview1.asp?columnid=4&itemid=11 border=0 width=0 height=0>");
</SCRIPT>
</BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -