陶性留，俞 璐，王晓莹

(1.陆军工程大学 通信工程学院，江苏 南京 210007；2.陆军工程大学 指挥控制工程学院，江苏 南京 210007)

0 引言

随着物联网、电子商务等技术的广泛应用，可收集的数据越来越多，越来越复杂，数据特征的维度也越来越高。如何快速检索有用的相关信息，越来越成为人们关注的热点问题。聚类是机器学习和数据挖掘中的基础课题之一，它的目的是将数据样本划分为不同的簇，使同一簇的数据样本具有较高的相似性。到目前为止，很多研究提出了一些有效的聚类方法，例如K-means[1-2]、FCM[3-4]、SOM聚类[5]、层次聚类[6]、谱聚类(SC)[7-8]。

人们获得的数据普遍具有如下两个特点：(1)数据量庞大，检索困难；(2)数据维数巨大，处理困难。虽然高维数据也许含有更多的信息，但将其直接用于分类、聚类或概率密度估计等任务，必将付出巨大的时间和空间代价。因此降维已经成为许多数据挖掘问题的一种预处理手段。数据降维的本质是寻找一个低维表示来反映原始数据的内在特征，并使后续任务在这个低维表示上的工作量更低，同时泛化性能和识别率更高。通过利用非负矩阵分解(Non-negative Matrix Factorization, NMF)的独特优势，不仅可以进行降维，而且物理意义明确，能够很好地改善聚类的效率[9]。本文将NMF与模糊C均值算法相结合，提出了新的目标函数。由交替迭代产生的新的低维表示矩阵可以用来描述样本之间的本质关系。与传统聚类方法相比，本文算法提高了聚类效果。

1 相关工作

1.1 NMF算法[10]

s.t.W≥0,HT≥0

(1)

(2)

(3)

其中，⊙是Hadamard积运算符，代表矩阵对应元素相乘。这时用系数矩阵HT代替原始矩阵，就可以实现对原始矩阵进行降维，从而减少存储所占空间，减少计算所需资源。

1.2 模糊C均值聚类(FCM)

FCM算法是一种基于划分的聚类算法，它的思想就是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。模糊C均值算法是普通C均值算法的改进，普通C均值算法对于数据的划分是硬性的，而FCM则是一种柔性的模糊划分。硬聚类把每个待识别的对象严格地划分到某类中，具有非此即彼的性质，而模糊聚类建立了样本对类别的不确定描述，更能客观地反映客观世界。

1≤i≤c;1≤j≤n

(4)

1≤i≤c;1≤j≤n

(5)

1≤i≤c;1≤j≤n

(6)

FCM算法是一个交替迭代的过程，收敛后可以得到隶属度矩阵U和聚类中心矩阵V。通过模糊聚类分析，每个样本不再固定地属于某一个类，可以得到不同样本的不确定性，并可以从样本到类别建立不确定性描述。

2 FCM-NMF算法

本节将描述FCM-NMF算法并给出多个更新规则。在较小的矩阵上运行NMF算法可以节省更多的时间和存储空间，但也有可能破坏数据样本之间的本质结构，影响聚类效果。为了减少负面影响，本文希望在NMF压缩样本数据的过程中进行模糊聚类。对于大量高维数据，通过NMF提取样本的本质特征，保留作FCM模糊分析聚类。将NMF分解对原始数据样本的影响加入到FCM的目标函数中。最小化以下代价函数：

(7)

其中，λ≥0是平衡系数，第一项表示模糊C均值对聚类的影响程度，第二项表示利用NMF算法处理原始数据的过程对聚类的影响程度。很明显，式(7)的目标函数是非凸的，解出它的全局最优是不实际的。因此，利用交替迭代法则去探索非凸函数的局部最优解是一个不错的选择。

通过迭代以下步骤来解决优化问题，直到收敛:

(1)固定W、H、V，通过U最优化J。U的更新准则为:

i=1,2,…,c;j=1,2,…,n

(8)

(2)固定W、H、U，通过V最优化J。V的更新准则为:

i=1,2,…,c;j=1,2,…,n

(9)

(3)固定V、H、U，通过W最优化J。W的更新规则与NMF算法一致，为:

(10)

(4)固定W、V、U，通过H最优化J。将目标函数J展开：

目标函数J对hj偏导数：

其中，Aδ是控制梯度下降步长的参数。令

可以得到:

H最终的更新公式为：

(11)

FCM-NMF算法描述如下：

算法1:FCM-NMF输入:原始非负矩阵X,模糊系数f,聚类个数c,平衡系数λ;输出:基矩阵W,系数矩阵H,隶属度矩阵U,聚类中心矩阵V;样本的标签向量Y∈R1×n。1 随机地初始化W和H;2 循环;3 通过式(8)更新U,保持W、H和V固定;4 通过式(9)更新V,保持W、H和U固定;5 通过式(10)更新W,保持U、H和V固定;6 通过式(11)更新H,保持U、W和V固定;7 直到式(7)的目标函数收敛;8 根据U,最终获得样本标签向量Y。

3 实验结果与分析

3.1 实验条件

为了验证本文方法的有效性，本文在两个标准图像集进行实验。一个是GHIM-10k 图像集,另一个是Corel-10k图像集。每个图像集有10 000个图像，都来自不同的种类。从每个数据集中随机选取5个类别的500幅图像作为验证集。

对于每个验证集，提取每幅图像的灰色共生矩阵和颜色直方图分别作为初始样本矩阵X。与本算法对比的5类聚类算法分别是：①在初始矩阵X上运行K均值聚类；②在初始矩阵X上运行模糊C均值聚类；③在初始矩阵X上运行MEC聚类[12]；④在经过NMF的系数矩阵H上运行K均值聚类；⑤在经过NMF的系数矩阵H上运行模糊C均值聚类。所有这些算法都是在MATLAB R2014a中实现，所有实验都是在Windows10下的8 GB内存的Inter Core 2.81 GHz处理器上进行。将这些算法的最大迭代次数设置为10 000次，并在接下来的所有实验中保持不变。图1显示了验证集中部分样本。

图1 验证集部分样本图像

3.2 评价标准

对于每个数据集，选取准确率(ACC)、归一化互信息(NMI)和F度量(F-measure)作为聚类效果的评价指标。

准确性是评价聚类结果质量的一个特别重要的指标，表达式如下：

(12)

其中，TP是指在同一个类中聚集的两个文档是正确分类的，TN是指在同一个类中聚集的两个文档是正确分开的。FP表示不应该属于一个类别的文档应该属于错误的类别，FN表示不应该被分开的文档应该属于错误的类别。

聚类中常用NMI来衡量两种聚类结果的接近程度。

(13)

式中，PAB(a,b)表示A和B的联合概率分布，H(A,B)表示两类结果的联合熵。

F-measure是一种考虑到信息检索的精度和召回程度，以便于不同技术或系统之间的结果进行比较的测量方法。

(14)

在式(14)中，P和R分别表示信息的精度和召回率。上述三个聚类评价指标的取值均在0～1之间，指标值越大，聚类效果越好。

3.3 实验结果与分析

针对每种算法，分别进行20次实验，并记录实验数据结果平均值。

表1和表2分别是提取了标准图像数据集验证集样本的灰度共生矩阵与颜色直方图特征进行数据集聚类的实验结果。从表1和表2中可以看出，在选定的图像集中，提取的灰色共生矩阵和颜色直方图这两种全局特征在与传统聚类算法对比实验中效果表现颇佳,尤其在准确率和标准化互信息方面有比较大的改善。如表1所示，ACC与NMI值最高可达84%和77.21%。 本算法的聚类结果依赖于实验中两个参数的调节，一个是模糊系数f，另一个是平衡系数λ。模糊系数f值取决于样本数据本身的统计数据[13]。大量的实验表明，f值限于1.1与2.5之间[14]。而平衡系数λ是在数量级为10-1至102的范围内搜索得到的最优解。

表1 通过提取灰度共生矩阵特征， 对实验数据集进行聚类

表2 通过颜色直方图特征提取对 实验数据集进行聚类

从另一个角度来看，该算法克服了传统K-means和FCM算法在聚类过程中因初始条件非唯一性导致的聚类结果不稳定的问题。同时，由于乘法迭代的存在，该算法的收敛速度也很快。

4 结束语

本文的数据集需要满足负值要求，这与实际情况一致，所以利用NMF方法在一定程度上是合理的。虽然NMF方法的初始化是随机的，但随着迭代的进行，聚类结果趋于稳定。本文提出了FCM-NMF算法，并在实验中证明了聚类的有效性。它利用NMF作为特征提取的手段，为了尽可能不破坏样本之间的本质联系。结合NMF和FCM算法改变目标函数的形式，生成新的低维表示矩阵。整个过程即通过NMF来改善高维无监督聚类。

本文方法作为聚类方法具有以下优点:(1)由于矩阵分解的灵活性，NMF过程可以模拟不同的数据分布，对于高维数据的优点更加明显；(2)只要分解过程不破坏原始数据的基本结构[15]，NMF可以与现有的其他聚类方法结合，作为特征提取的框架；(3)样本的FCM处理可以更好地描述样品对类的隶属度，丢失信息更少。下一步考虑将少量成对约束条件加入聚类过程中，利用半监督聚类来进一步改善效果。