Fuzzy c-means聚类算法简介
作者简介
本期由东北大学滕月阳教授为我们介绍模糊c聚类算法，滕老师自学成才为人随和，他的研究方向是PET重建和机器学习，欢迎感兴趣的同学报考他的研究生。
Fuzzy c-means聚类算法简介
一、聚类算法
聚类(clustering)是机器学习的重要目标，能够达到物以类聚人以群分之目的，使同类者可以一块研究，节省人力、物力、财力与时间。可见偷懒是科学研究的原动力，诚不欺余！
很多新入门的同学们将聚类和分类算法弄混，这里先对它们进行区分。实际上，聚类和分类(classification)是人类认识世界的两个阶段，是顺序而非并列关系。举例解释，某古代人穿越至今，第一次看到汽车和玻璃球，那么他会根据两者的外观等特征觉察两者不同，这就是聚类。在此之后，他会根据自己的需求，为其贴上不同的标签（起名字），比如跑得快的铁家伙是汽车，圆溜溜且亮闪闪的是玻璃球，再后，遇到和哪个接近的就归到哪一类中，这就是分类。
聚类和分类有效性评估也有很大不同。以一组数据为例，一组数据的真实标签、聚类标签和分类标签如表1所示。其聚类正确率100%，它只说明第1、2个点归于一类，第3、4个点在另一类中；而分类正确率0%，把第一类点分给第二类，第二类点分给第一类，南辕北辙。
表1 聚类与分类的示例
目前如火如荼的深度学习主要进行分类，但是其实聚类是人类认识世界的第一步，更接近于人类本能，如果计算机要模拟人的意识，聚类将是一个重大挑战。
二、Fuzzy c-means（FCM）介绍
那么如何进行聚类呢？首先，需要一种方法度量两个样本的相似性，这个就是距离。然后，将距离近的样本点归于一类。本文以FCM为例，说明聚类过程。
FCM[1-3]是一种重要的聚类算法，其目标是将n维空间中的数据X = {x_1, ..., x_N}分配到C个聚类中心v_1, ..., v_C。在欧氏距离意义下，数据靠近哪个聚类中心就属于哪个类，如图1所示。
图1 FCM聚类示意图
该问题可以使用下面的优化模型表示：
其中‖∙‖表示欧氏距离，m > 1表示模糊水平，C ≥ 2且小于于不同的xi的个数，否则聚类问题无意义。如无特殊指定，所有向量都是列向量。
这个优化问题通常使用交互式策略求解，即给定v关于u求最小，再给定u关于v求最小，它们是两个简单的二次优化问题，因此可以得到下面的迭代算法：
其中：
右角标t表示迭代次数，card(·)表示集合的势，对于有限集合，势就是元素的个数。Bezdek等[1-3]使用Zangwill不动点定理给出了FCM的子序列收敛证明。
定理1. Zangwill不动点定理[4]：映射M:
产生序列{z^t}，给定一个解集Ω ⊂ V，并且假设:
1) 有一个连续函数Z: V → R，满足：
a) 如果z∉Ω，则Z(M(z)) < Z(z)；
b) 如果z∈Ω，则Z(M(z)) ≤ Z(z)。
2) 映射M在V/Ω上连续。
3) 所有迭代点z^t包含在紧致集S且S ⊂ V。
则{z^t}的任意收敛子序列的极限都包含在解集Ω中，并且{Z(z^t)}单调递减收敛于某个Z(z)，其中z∈Ω。
为了使用上面的定理证明收敛性，Bezdek等引入一个简约的FCM目标函数：
如果任一个v_j等于x_i，L(v)显然无意义，但是在极限的意义下，即定义1/0 = ∞和1/∞ = 0，这个函数连续[5]。Bezdek等已经证明FCM模型可以转化为求解一个无约束优化问题。Bezdek等利用简约的目标函数证明FCM算法满足Zangwill定理的所有条件，然后给出了它的收敛证明。原目标函数与简约目标函数相比，前者有明确的物理意义，但是具有更多的变量和约束条件，后者没有明确的物理意义，但是变量很少而且没有约束。
证明细节从简，有兴趣的同学参见文[1-3]。
三、未来的展望
在当今深度学习大行其道之际，聚类方法如何在深度学习中使用时却是我一直致力研究的问题。一个当然的想法是使用下面的聚类LOSS函数：
其中θ代表深度学习中的权重、偏差或卷积核心。但是问题接踵而至，如果θ=0，所有样本点将被映射到0点，一个点的聚类是简单但是无用的，因此如何保证映射不退化是关键问题，将作为我的下一步研究目标。
四、参考文献
[1] Bezdek J C. A convergence theorem for the fuzzy ISODATA clustering algorithms, IEEE Transactions on Pattern Analysis and Machine Intelligence, 1980, 2: 1-8.
[2] Bezdek J C, Hathaway R J, Sabin M J, et al. Convergence theory for fuzzy c-means: counter-examples and repairs, IEEE Transactions on Systems Man and Cybernetics., 1987, 17: 873-877.
[3] Hathaway R J and Bezdek J C. Recent convergence results for the fuzzy c-means clustering algorithms, Journal of Classification, 1998, 5: 237-247.
[4] Zangwill W I. Nonlinear Programming: A Unified Approach. New York: Prentice-Hall, 1969.
[5] Groll L and Jakel J. A new convergence proof of fuzzy c-means, IEEE Transactions on Fuzzy Systems, 2005, 13: 717-720.
写在后面
这是一群致力于科研传播的faculty & PhD记录分享点滴思考的平台，这里有我们在各自领域（机器学习，医疗影像，材料科学，凝聚态物理，生物信息，光学）涉猎研究的点滴感悟，有我们在国内，海外求学工作奋斗的酸甜苦辣，亦有偶尔的风月和我们的诗与远方。