Fuzzy c-means (FCM)聚类算法

刺骨的言语ヽ痛彻心扉 2022-09-28 05:45 155阅读 0赞

<table style="table-layout: fixed; width: 100%"> 
 <tbody> 
 <tr> 
 <td> 
 <div> 
 算法原理 允许同一数据属于多个不同的类。该算法(developed by <a href="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/cmeans.html#dunn" rel="nofollow">Dunn in 1973</a> and improved by <a href="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/cmeans.html#bezdek" rel="nofollow">Bezdek in 1981</a>)经常用于模式识别，基于最小化 
 下列目标函数： 
 <img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image019.gif" align="absMiddle">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ,&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image021.gif" align="absMiddle"> 
 其中， m 是大于1的实数，uij 是xi 属于类别 j隶属度， xi 第i个测量到的d维数据, cj 是类j的聚类中心，||*|| 表示任一测量数据与聚类 
 中心的相似度。 
 
 
 Fuzzy partitioning is 通过下列两式的更新迭代来使得上述目标函数达到极小： 
 
 <img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image023.gif" align="absMiddle">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ,&nbsp;&nbsp;&nbsp;&nbsp; 
 <img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image025.gif" align="textTop"> 
 当<img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image027.gif" align="absMiddle">,时迭代停止，0&lt;<img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image002.gif" align="absMiddle"> &lt;1是迭代终止参数，k是迭代轮数。该过程收敛到Jm的一个极小值。 
 算法由下列步骤组成： 
 <table> 
 <tbody> 
 <tr> 
 <td> 
 <ol> 
 <li>初始化隶属度矩阵U=[uij] , U(0) </li> 
 <li>第k轮迭代: 计算中心向量 C(k)=[cj] with U(k) <img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image025.gif"> </li> 
 <li>更新隶属度矩阵 U(k) , U(k+1) <img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image023.gif"> </li> 
 <li>If || U(k+1) - U(k)||&lt;<img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image002.gif"> then STOP; otherwise return to step 2. </li> 
 </ol> </td> 
 </tr> 
 </tbody> 
 </table> 
 说明 如前所述，数据属于某个类是由隶属度函数确定的，这正是该算法的模糊行为的体现。在该算法中用一个由0和1之间元素组成的矩阵表达 
 对象与类别的隶属关系。 举一个一维的例子来说，给定一个特定数据集，分布如下图： 
 <img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image031.gif"> 
 从图中可以很容易分辨出两类数据，分别表示为‘A’ and ‘B’. 利用前述的k-means 算法，每个数据关联一个特定的质心，隶属度函数 
 如下所示： 
 <img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image033.gif"> 
 利用FCM 算法，同一个数据并不单独属于一个分类，而是可以出现在中间。在这个例子中，隶属函数变得更加平滑，表明每个数据 
 可能属于几个分类。 
 <img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image035.gif"> 
 上图中，红色点表示的数据更可能属于类别B，而不是A， ‘m’ 的值0.2表明了数据对A的隶属程度。现在，不用图表示，我们引入 
 一个矩阵，其元素取自隶属函数： 
 <img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image037.gif">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image039.gif"> 
 (a)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (b) 
 矩阵的行数和列数取决于数据和类别的个数，确切的说，行数表示数据个数，列数表示类别个数，矩阵元素表示为 uij. 上面的例子中，我们考虑了k-means (a) and FCM (b) 的例子，可以看出在第一个例子(a) 中的稀疏总是二值，表明每个数据只能属于一个 
 分类，其他属性表示如下： 
 <ul> 
 <li><img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image041.gif" align="absMiddle"> </li> 
 <li><img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image043.gif" align="absMiddle"> </li> 
 <li><img src="http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/images/image045.gif" align="absMiddle"> </li> 
 </ul> 
 参考文献 
 <ul> 
 <li> 
 <div> 
 <a rel="nofollow"></a>J. C. Dunn (1973): "A Fuzzy Relative of the ISODATA Process and Its Use in Detecting Compact Well-Separated Clusters", 
 </div> </li> 
 <li> 
 <div> 
 Journal of Cybernetics 3: 32-57 
 </div> </li> 
 <li> 
 <div> 
 <a rel="nofollow"></a>J. C. Bezdek (1981): "Pattern Recognition with Fuzzy Objective Function Algoritms", Plenum Press, New York 
 </div> </li> 
 <li> 
 <div> 
 Tariq Rashid: “Clustering” <a href="http://www.cs.bris.ac.uk/home/tr1690/documentation/fuzzy_clustering_initial_report/node11.html" rel="nofollow">http://www.cs.bris.ac.uk/home/tr1690/documentation/fuzzy_clustering_initial_report/node11.html</a> 
 </div> </li> 
 <li> 
 <div> 
 Hans-Joachim Mucha and Hizir Sofyan: “Nonhierarchical Clustering” <a href="http://www.quantlet.com/mdstat/scripts/xag/html/xaghtmlframe149.html" rel="nofollow">http://www.quantlet.com/mdstat/scripts/xag/html/xaghtmlframe149.html</a> 
 </div> </li> 
 </ul> 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

[link][]

[link]: http://hi.baidu.com/xyp86/blog/item/8cba9787648b4d2cc75cc348.html