传统无监督聚类算法在划分数据时并不需要任何数据属性，但在实际应用中，存在少量带有独立类标签或成对
约束
的监督信息的数据样本，学者们致力于将这些为数不多的监督信息运用于聚类，以得到更优的聚类结果，从而提出 了半监督聚类。
1.无监督聚类
先说无监督聚类，如图 1-2 所示，现有的无监督聚类算法按照度量数据样本间相似度的方式， 以及聚类过程中数据样本之间的关系被划分为五大类，即基于划分方法的聚类、 基于层次方法的聚类、基于密度方法的聚类、基于网格方法的聚类、基于模型方 法的聚类[7]。所谓基于划分方法的聚类（基于划分方法的聚类算法在处理非标准正态分布和非均匀数据集时，聚类效果会比较差。）是指：在对数据对象进行聚类之前，需要创建 k 个划分个数，即提前设定好 k 个簇数。k 均值（k-means）聚类算法[8-10]、 PAM（Partitioning Around Melodies）聚类算法[11]、k 中心点（k-mediods）聚类 算法[12,13]等等聚类算法都是相对经典的划分聚类算法；基于层次聚类方法是采用 “自底而上”的聚合策略或者“自顶向下”的拆分策略，试图在不同层次上对数 据样本集进行划分，从而形成树形的聚类结构。AGNES 聚类算法[14]采用的是“自 底而上”的聚类策略，DIANA 聚类算法[15]采用的另一种“自顶而下”的拆分策 略；基于密度的聚类算法，本质上来说就是定义一种密度的概念来进行聚类，而 密度定义的本质来自于数据样本集的数据点与点之间的距离。这类算法不仅能改 善基于距离的算法只能发现球形、凸形的簇类的缺陷，可以发现任意形状的聚类， 并且对噪声数据样本点不敏感。具有代表性的密度聚类有 DBSCAN[16]高密度连 通区域聚类、OPTICS 点排序识别聚类结构聚类[17,18]、DENCLUE[19,20]密度分布函 数聚类算法等；基于网格的聚类方法是将空间量划分为一定数目的单元，使之形 成一个网格结构，所有数据样本对象都在此网格上进行聚类。这种网格聚类方法 速度快，算法复杂度相对较低，改善了划分聚类、层次聚类等相关算法复杂度高的问题。相关的网格聚类算法有 STING 统计信息网络聚类算法[21]、WaveCluster 利用小波变换聚类算法[22,23]；统计学方法 COBWEB[24,25]、神经网络方法 SOMs[26,27] 都归属于基于模型的聚类算法。
2.半监督聚类
再说半监督聚类，半监督聚类是结合半监督学习与聚类分析而提出的新的学习方法，
目前半监督聚类中常见的先验知识表现为反映样本间相似关系的约束条件，
约束条件主要有两大类方法:基于约束的方法和基于距离的方法。
前者将约束作为聚类目标的一部分直接作用于聚类算法,并且依靠用户提供的标号或约束来指导算法,产生更合适的数据划分;后者是使用一种自适应距离度量,该度量已经被训练,以满足监督数据中的标号或根据约束构造某种距离度量并以此为基础运行各种聚类算法。大致来看，半监督聚类方法分为三种不同的类型：基于约束方法的半监督聚类[28-30]，基于距离方法的半监督聚类[31,32]，以及基于距离和约束混合方法的半监督聚类算法 [33,34]。
2.1基于约束方法的半监督聚类
- Ｃｏｐ－Ｋｍｅａｎｓ算法
Ｗａｇｓｔａｆｆ等［２８］将成对约束的思想运用到传统Ｋ－ｍｅａｎｓ 算法中，提出了Ｃｏｐ－Ｋｍｅａｎｓ算法。Ｃｏｐ－Ｋｍｅａｎｓ算法的基本 聚类思想与Ｋ－ｍｅａｎｓ相同，只是在数据分配过程中要求数据 对象必须满足Ｍｕｓｔ－ｌｉｎｋ（ＭＬ）约束和Ｃａｎｎｏｔ－Ｌｉｎｋ（ＣＬ）约束 条件（ＭＬ代表被选中的两个点一定是属于同一类，而ＣＬ代 表被选中的两个点一定不是同一类的元素），并且约束具有对 称性和传递性［２９］。对称性和传递性在成对约束中至关重要，这种特性导致 样本在强制分配约束关系时，只有在ＣＬ约束情况下才会造 成约束违反，在其他情况下并不会有样本分配失败的情况。Ｃｏｐ－Ｋｍｅａｎｓ算法要求样本数据在划分过程中满足约束 关系，因此
针对有约束信息的样本来说，这种算法的效率极 高
。但是，
约束信息的质量会直接影响聚类结果的好坏
，因此 只有获得更优的约束信息，才能提高聚类效果。
- ＬＣｏｐ－Ｋｍｅａｎｓ算法
基于广度优先搜索（Ｂｒｅａｄｔｈ Ｆｉｒｓｔ Ｓｅａｒｃｈ，ＢＦＳ）的ＣＯＰＫｍｅａｎｓ 算法，也可以命名为ＬＣｏｐ－Ｋｍｅａｎｓ（Ｌｉｎｋｅｄ Ｃｏｐ－ Ｋｍｅａｎｓ）算法［３０］。
此算法主要解决了ＣＬ约束造成违反的问 题
，主要思想是：数据在迭代过程中将有约束的数据和无约束 的数据区分开来，对于无约束的数据，在进行分类时可以直接 将其分配到最近的聚类中，之后确定其他有约束数据之间的 关系。当ＭＬ约束存在时，按照传递性进行分配，以保证约束 不违反，并且得到分配结果。当ＣＬ约束存在时，采用ＢＦＳ搜 索算法，将与某顶点有关联的所有ＣＬ约束的数据都按顺序 插入一个先进先出的Ｌｉｓｔ结构中，然后再访问与该顶点相邻 的所有顶点。此方法不仅可以防止数据被重复访问，还可以 保证ＣＬ约束不违反。ＬＣｏｐ－ｋｍｅａｎｓ算法
解决了之前所提到的约束违反的问 题
，可以让成对约束的聚类结果更加安全可靠。但是，该算法
在数据样本稳定性上的表现并不突出
，可能会将样本分配到 不合适的簇中，从而导致最后的聚类结果不准确。
- Ｓｅｅｄｅｄ－Ｋｍｅａｎｓ算法
与之前介绍的成对约束算法不同，当先验知识是独立的类标签，而不再是成对的约束信息时，Ｂａｓｕ等［３１］基于Ｓｅｅｄｓ 集改进的思想，提出Ｓｅｅｄｅｄ－Ｋｍｅａｎｓ算法。
该算法的主要目的是将标记样本引入Ｋ－ｍｅａｎｓ中
，其中标记样本可以是少量 的，将其作为Ｓｅｅｄｓ集，同时采用最大期望算法将样本划分成 Ｋ 个簇，初始化的集群中心是每个簇类的均值。在数据样本的监督信息是独立的类标签的情况下，Ｓｅｅｄｅｄ－ Ｋｍｅａｎｓ算法可以对数据进行聚类，优化了聚类的结果。
但是，当遇到先验知识同时包括类标签成对约束时，如果只拿出其中的某一方面来指导聚类，得出的结果则并不是很理想。
- ＳＣ－Ｋｍｅａｎｓ算法
ＳＣ－Ｋｍｅａｎｓ算法［３２］是Ｓｅｅｄｅｄ－Ｋｍｅａｎｓ算法的一种改进， 针对如何充分利用半监督聚类算法中有效的先验知识而提 出。该算法可以同时
利用成对约束和独立类标签这两种监督信息，
并将主动学习算法引入到ＳＣ－Ｋｍｅａｎｓ算法中，提高了 ＳＣ－Ｋｍｅａｎｓ算法的聚类精度。在这个算法中，需要扩充成对 约束，得到新的ＭＬ和ＣＬ约束集，即Ｎｅｗ－ＭＬ和Ｎｅｗ－ＣＬ约 束。ＳＣ－Ｋｍｅａｎｓ算法可以同时利用类标签和成对约束这两 种监督信息进行聚类，尤其是加入了主动学习来主动标记样 本，能获得质量更高的监督信息，得到更好的聚类结果。但是，
在处理大规模数据方面，此算法的效率并不是很高
。
在基于约束的半监督聚类中，最典型、最基础的算法是 Ｓｅｅｄｅｄ－Ｋｍｅａｎｓ算法和Ｃｏｐ－Ｋｍｅａｎｓ算法（
半监督Kmeans
）。这两种算法分别从监督信息的不同角度出发，在半监督聚类的发展中发挥着 至关重要的作用。Ｌｉ等［３３］提出了
半监督层次聚类
算法，在层 次聚类中也可以使用成对约束。朱煜等［３４］在ＬＣｏｐ－Ｋｍｅａｎｓ 算法的基础上提出了改进的基于广度优先搜索的Ｃｏｐ－ Ｋｍｅａｎｓ算法，该算法提高了数据稳定性，使得聚类结果更加准确。文献［３５］证明半监督聚类算法可以在顶点低层和组件高层两个部分随机游走。低层随机游走时得到的约束顶点可 以对其他顶点的约束能力进行估测，然后在高层随机游走中 传播约束，最终将其归结在一个簇里。文献［３６］提出了一种 基于ＡＰ算法的半监督聚类方法，间接地使聚类效果得到优 化。Ｙａｎｇ等［３７］利用ＭａｐＲｅｄｕｃｅ对Ｃｏｐ－Ｋｍｅａｎｓ算法进行改 进，让大规模的数据集可以并行运算。李晁铭等［３８］提出了基 于成对约束的交叉熵半监督聚类算法，这种方法利用样本的 交叉熵来表达成对约束信息，能够在成对约束信息较少的情 况下获得较高的聚类精度和较优的结果。柴变芳等［３９］提出 了主动学习先验的半监督Ｋ－ｍｅａｎｓ聚类算法来补充监督信 息。该方法
将主动学习加入到约束半监督聚类
中，可以主动 选择每个聚类中最有用的无标签数据样本。相比传统的半监 督聚类算法，这种方法的效率更高，并且得到的结果更佳。除 此之外，半监督聚类
还可以与马尔可夫模型
相结合。例如， Ｂａｓｕ等［４０］提出了一种基于隐马尔可夫随机场的成对约束的半监督聚类；Ｊｉａ等［４１］提出了一种基于ＨＭＲＦ模型的监督近似谱聚类算法。
2.2基于距离方法的半监督聚类
传统的聚类算法采用某种距离度量准则描述样本间的相似度，距离越小则相似度越高，距离越大则 相似度越低．而在实际操作中，如何选取一个合适的 度量方式是非常困难的，没有适合所有问题的距离 度量标准．基于距离的半监督聚类的基本含义是，首 先训练相似性度量以满足类别或限制信息，然后使 用基于距离度量的聚类算法进行聚类．常用的相似 性度量包括：使用凸优化的马氏距离（Ｍａｈａｌａｎｏｂｉｓ Ｄｉｓｔａｎｃｅ）［１５］、由最短路径算法改进的欧式距离［１６］、 使用梯度下降算法的ＫＬ散度（ＫｕｌｌｂａｃｋＬｅｉｂｌｅｒ Ｄｉｖｅｒｇｅｎｃｅ）及谱聚类方法．
例如，2012年 Horng[35]提出一种基于 K 近邻（K-NN）的半监督聚类算法，采用每个簇的未标记数据样本点和其周围 K 个最近的数据点之间的距离关系，以便对未标记数据样本进行划分聚类。这种半监督方法算法简单，聚类准确并且快速；Ａｌｏｋ等［４２］将特征选择和半监督聚类相结合，解决了无监督分类框架下的特征选择问 题。相比基于多目标的自动聚类技术，单个客观聚类技术和 传统Ｋ－ｍｅａｎｓ聚类能够从具有点对称聚类的数据集中检测 出适当的特征组合和划分。Ｗｅｉ等［４３］提出了基于成对约束 与度量的半监督聚类集合，在成对约束标记的数据情况下，分 别使用基于约束的半监督聚类和基于度量的半监督聚类来生 成不同的基础聚类分区，然后通过积分得到目标聚类。这种 方法能够提高聚类精度。Liu 等[36] 在 2014 年提出一种对半监督 k-means 算法加权的信息增益的思想。通过少量带 有类标记的数据样本进行信息增益权重计算和初始中心的确定，进而改善聚类初 始中心的敏感度和数据维度问题，提高半监督 k-means 算法的聚类精确度并保持 了聚类的稳定性；2016 年，Ye 等[37]针对于半监督 k-means 聚类算法稳定性的问 题，提出一种改进的半监督 k-means 聚类算法来处理具有少量带有类标记的数据 样本集合。结合标记数据样本外部索引，该算法能够确定整个数据样本集最佳的 簇的个数和聚类中心，使得整个数据样本集的群集效果得到改善。
2.3基于距离和约束混合方法的半监督聚类算法
Ｂａｓｕ等人提出一个基于Ｋ-ｍｅａｎｓ的半监督算法 （Ｍｅｔｒｉｃ Ｐａｉｒｗｉｓｅ Ｃｏｎｓｔｒａｉｎｅｄ Ｋ-ｍｅａｎｓ，ＭＰＣ Ｋ- ｍｅａｎｓ）［１９］．该算法融合了基于约束和基于距离的方 法．在Ｋ-ｍｅａｎｓ算法基础上，引入成对约束作为监督信息，体现在目标函数上就是增加了不满足约束的惩罚项，目标函数为
其中，Ｍ和Ｃ分别为ｍｕｓｔ-ｌｉｎｋ约束集和ｃａｎｎｏｔ-ｌｉｎｋ 约束集，ｗｉｊ和ｗｉｊ分别为两个集合中对应的权值，ｌｉ 为类标记，ＩＩ为指示函数（ＩＩ（ｔｒｕｅ）＝１，ＩＩ（ｆａｌｓｅ）＝ ０），｛μｌｉ｝Ｋ ｌｉ＝１表示Ｋ个聚类中心.
作为对上述算法的拓展，Ｂａｓｕ等人随后提出一 种基于隐马尔可夫随机域模型（ＨｉｄｄｅｎＭａｒｋｏｖ ＲａｎｄｏｍＦｉｅｌｄｓ，ＨＭＲＦｓ）的半监督聚类方法［２０］．将 算法度量从欧式距离推广到任意的Ｂｒｅｇｍａｎ散度．
2.4基于模型方法
基于模型方法就是为每个聚类假设一个模型,然后再去发现符合相应模型的数据对象。一个基于模型 的算法可以通过构造一个描述数据点空间分布的密度函数来确定具体聚类。它根据标准统计方法并考虑到噪声或异常数据,可以自动确定聚类个数。
在上世纪 70 年代末源于统计力学的马尔可夫随机场(Markov Random Field,MRF)理论开始应用于图像处理领域。MRF通过描述图像相邻像素之间的相 互关系,有效地表达了图像的上下文信息。自1984年以来 , 在 S. Geman 和 D. Geman 所做的奠基性工作之上,在图像处理领域中许多研究者开始不断地改进 或者提出新的基于 HMRF 模型。模型的图像分割算法文献[5] [3]
提出了一种隐马尔可夫随机场(HMRF),这 种模型是一种距离与约束条件相结合的半监督聚类分析方法,利用它可以解决图像分割问题,对于每一阶模型的图像分割,该算法充分利用了相邻模型之间 的相关信息,该算法克服了均值场算法对初始化条件要求非常苛刻的缺点。文献[6] [4]
提出一种基于 HMRF 模型的无监督图像分割算法,这种算法克服了均值场 算法对初始化条件要求非常苛刻的缺点,并且算法避免了对某些无意义的模型阶次进行分析,减少了整个算法的计算量。
隐马尔科夫树模型(HMT)在图像去噪方面应用较多的一种模型。由于HMT需要大量的迭代运算，随着小波系数的增多，计算的复杂度也随着增大。张伟等人提出多小波描述的通用隐马尔可夫树模型图像去噪算法,小波域通用隐马尔可夫树(uHMT)模 型充分利用了实际图像内部的自相似性,仅用极小参数与图像的大小和小波的尺度数目无关就可以完全确定实际图像的隐马尔可夫树模型 ,极大地简化了隐 马尔可夫树模型 ,但这使得图像去噪的精度降低。多小波描述在图像去噪方面取得了较好的效果,但是没 有更有效的解决算法的复杂性。基于模型的算法依赖 于可用数据的类型,又依赖于应用的特定目标。 [5]
2.5基于密度的方法
文献[7~8]密度敏感的距离测度在特定图像聚类中的应用算法以及一种改进的密度敏感的半监 督聚类算法[7]。 在文献[8]中提出一种新的基于图的半监督学习算法, 称为密度敏感的半监督聚类算法 (DS-SC),该算法引入一种密度敏感的距离测度,它能 较好地反映聚类假设,并且充分挖掘了数据集中复杂的内在结构信息,同时与基于图的半监督学习方法相 结合,使得算法在聚类性能上有了显著的提高。 文献 [7] [6]
提出一种改进的密度敏感的半监督聚类算法,一种改进的密度敏感的距离测量,可有效地扩大数据点 之间的距离在不同的高密度地区和在同一高密度地 区缩短数据点之间的距离。此外,半监督学习算法改 进了密度敏感的半监督聚类 (入侵检测系统-SC)的 算法。 [5]
2.6基于网格的方法
这种算法首先将数据空间划分成为有限个单元 的网格结构, 所有的处理都是以单个的单元为对象的。处理速度通常与目标数据库中记录的个数无关, 它只与单元的个数有关,故这种算法的一个突出优点就是处理速度很快。代表算法有DenClue算法和 CLIQUE算法 。 [5]
2.7判别法
从传统的聚类方法中,适当地加入约束条件进行 判别分析,该方法更加有效,有利于提高算法的性能。比较著名的算法有 Bayes 判别法、Fisher 判别函数法、距离函数法和K-近邻法、Jensen-Shannon 梯度下降法、欧式距离修改最短路径法[9]等。Bayes判别法利用以往对研究对象的认识, 以先验概率来辅助判断,希望得到更精确的分析结论。误判概率最小、风险最小,但是 Bayes 判别法需要已知条件概率,而且其决策面往往是超曲面,形状复杂,难以计算和构造。文献[11] [9]
提出一种基于成对约束的判别型半监督聚类分析方法(Discriminative Semi-Supervised Clus- tering Analysis with Pairwise Constraints,DSCA)。这种方法第一步利用Must-Link 和Cannot-Link 成对约束产生投影矩阵,在投影空间中对数据聚类生成聚类标 号;第二步,利用线性判别分析(Linear Discriminant Analysis,LDA)选择子空间;第三步,使用基于成对约 束的 K 均值算法对子空间中的数据聚类。 DSCA 有效 地利用了监督信息集成数据降维和聚类, 降低了基于 约束的半监督聚类算法的计算复杂度。 [5]
3.总结
未来，
- 0.半监督聚类算法可以基于不同的聚类思想，可以形成不同的半监督聚类算法，如半监督层次聚类、半监督密度聚类和半监督谱聚类等。
- 1.半监督聚类要考虑聚类方法是形状无关的。
- 2.需要的标记样本要尽可能少。
- 3.要尽可能利用无标记数据的结构信息和有标记数据的标记信息。
- 4.适当考虑如何集成半监督聚类方法