一种基于稀疏均值的模糊聚类方法

摘要

本发明涉及一种基于稀疏均值的模糊聚类方法，将待聚类的文档用向量空间模型表示为高维稀疏向量，设置参数，初始化均值，基于当前均值更新所有隶属度的值，更新权重，然后基于隶属度更新对应的均值，当对应的均值不再变化或迭代次数最大时迭代结束，输出聚类结果，否则重复。本发明通过稀疏均值使得均值也就是类中心点和样本点一样具有局域稀疏特性，增加基于样本点和均值欧氏距离来描述样本点和类相似性的有效性，在时间上更加高效，产生具有稀疏特性的均值使得类中心点更加自然地代表稀疏样本点的特性，同时为了增加对均值的稀疏性的控制，还在目标函数中加入均值范数的正则项以得到新的最小化目标函数，使得可以更加快速的求解。

说明书

技术领域

本发明属于计算；推算；计数的技术领域，特别涉及一种为高维稀疏数据设计的基于稀疏均值的模糊聚类方法。

背景技术

在很多领域的现实问题中，需要借助有效的聚类方法对高维稀疏数据集中的对象进行分组从而分析数据的内在结构并挖掘有用知识来帮助人们进一步决策，比如对新闻文档进行分组来检测其中包含的话题。

模糊聚类分析是根据客观事物间的特征、亲疏程度、相似性，通过建立模糊相似关系对客观事物进行聚类的分析方法，其比起硬聚类的优势是借助模糊集理论引入模糊隶属度的概念，从而能够自然的描述类之间的重叠性。

然而，根据统计学理论，在向量空间中对潜在概率分布的正确估计需要的样本数会随着维度的增加成指数增长，这使得传统的模糊聚类对高维数据如文本数据的处理结果并不是很好，同时，传统的模糊k均值算法基于欧氏距离来衡量样本点到类中心点的距离，在没有任何约束的情况下，高维稀疏数据的均值并非稀疏，这导致样本点(高维稀疏向量)和均值(高维非稀疏向量)之间的欧氏距离不能有效衡量样本点与类之间的相似性。

发明内容

本发明解决的技术问题是，现有技术中，在向量空间中对潜在概率分布的正确估计需要的样本数会随着维度的增加成指数增长，同时，传统的模糊k均值算法基于欧氏距离来衡量样本点到类中心点的距离，在没有任何约束的情况下，高维稀疏数据的均值并非稀疏，而导致的传统的模糊聚类对高维数据如文本数据的处理结果并不是很好，样本点(高维稀疏向量)和均值(高维非稀疏向量)之间的欧氏距离不能有效衡量样本点与类之间的相似性的问题，进而提供了一种优化的基于稀疏均值的模糊聚类方法。

本发明所采用的技术方案是，一种基于稀疏均值的模糊聚类方法，所述方法包括以下步骤：

步骤1.1：将待聚类的文档用向量空间模型表示为高维稀疏向量X＝{x₁,x₂,…x_n}，其中每个样本点为s维向量，即x_i∈R^s，s＞0，1≤i≤n；n为样本总数，n＞0；

步骤1.2：设置参数，所述参数包括类数k、模糊化系数m、初始正则项权重β⁰、结束判断参数ε及最大迭代次数T；0＜k＜n，1＜m＜2；β⁰＞0；设定带有均值l₁范数正则项的最小化目标函数其中，u_ci表示第i个样本到第c个类的隶属度，δ_c表示第c个类的均值；

步骤1.3：初始化均值，得到与最后结果相近的k个初始均值分别为[δ₁,δ₂,…δ_k]；计迭代次数l＝1；

步骤1.4：基于当前均值，利用式更新所有隶属度的值，1≤c≤k；

步骤1.5：对每一类c＝1,2,…,k，更新权重β，然后基于步骤1.4的隶属度u_ci更新对应的k个均值；

步骤1.6：当对应的k个均值不再变化或迭代次数l＞T，迭代结束；否则重复步骤1.3；

步骤1.7：输出聚类结果。

优选地，所述步骤1.2中，最小化目标函数应当同时满足的约束条件为：对所有c和i满足u_ci≥0，对所有i，

优选地，所述步骤1.2中，模糊化系数m≤1.2。

优选地，所述步骤1.2中，初始正则项权重β⁰≤10。

优选地，所述步骤1.5中，基于步骤1.4的隶属度u_ci更新权重β，

优选地，所述步骤1.5中，采用式更新对应的k个均值，其中，sign(δ′_c)返回该向量中对应元素的符号。

优选地，所述步骤1.5中，选出每个δ_c中权重最大的字符作为关键词用于描述或解释该类别。

优选地，所述步骤1.6中，当时，迭代结束。

优选地，所述步骤1.7中，所述聚类结果为k个均值和记录所有样本到类的隶属度矩阵U。

优选地，所述步骤1.7中，将隶属度矩阵U中的每个样本k分配给隶属度最大的类，得到每个样本点k的类标签。

本发明提供了一种优化的基于稀疏均值的模糊聚类方法，通过稀疏均值使得均值也就是类中心点和样本点一样具有局域稀疏特性，增加了基于样本点和均值欧氏距离来描述样本点和类相似性的有效性，在时间上更加高效，产生具有稀疏特性的均值使得类中心点更加自然地代表稀疏样本点的特性，同时为了增加对k个均值的稀疏性的控制，本发明还在目标函数中加入均值l₁范数的正则项以得到新的最小化目标函数，使得可以更加快速的求解。

附图说明

图1为本发明的流程图；

图2为本发明中设置不同稀疏度正则权重时得到的Newsgroups数据的以F-measure衡量的聚类结果，其中FSCM为本发明的基于稀疏均值的模糊聚类方法，FCM为传统模糊均值聚类方法。

具体实施方式

下面结合实施例对本发明做进一步的详细描述，但本发明的保护范围并不限于此。

如图所示，本发明涉及一种基于稀疏均值的模糊聚类方法，所述方法包括以下步骤：

步骤1.1：将待聚类的文档用向量空间模型表示为高维稀疏向量X＝{x₁,x₂,…x_n}，其中每个样本点为_s维向量，即x_i∈R^s，s＞0，1≤i≤n；n为样本总数，n＞0；

步骤1.2：设置参数，所述参数包括类数k、模糊化系数m、初始正则项权重β⁰、结束判断参数ε及最大迭代次数T；0＜k＜n，1＜m＜2；β⁰＞0；设定带有均值l₁范数正则项的最小化目标函数：其中，u_ci表示第i个样本到第c个类的隶属度，δ_c表示第c个类的均值；

步骤1.3：初始化均值，得到与最后结果相近的k个初始均值分别为[δ₁,δ₂,…δ_k]；计迭代次数l＝1；

步骤1.4：基于当前均值，利用式更新所有隶属度的值，1≤c≤k；

步骤1.5：对每一类c＝1,2,…,k，更新权重β，然后基于步骤1.4的隶属度u_ci更新对应的k个均值；

步骤1.6：当对应的k个均值不再变化或迭代次数l＞T，迭代结束；否则重复步骤1.3；

步骤1.7：输出聚类结果。

以下以实施例说明。

为了增加对k个均值的稀疏性的控制，本发明提出在目标函数中加入均值l₁范数的正则项得到新的最小化目标函数，使用正则项而非约束是为了更加快速地求解。具体为利用迭代算法求以下最小化问题，最小化目标函数为其应当同时满足的约束条件为：对所有c和i满足u_ci≥0，对所有i，

步骤1.1：把待聚类的Newsgroups文档以向量空间模型表示。进行词干提取(stemming)和删除停用词(stop word removing)的预处理后，保留信息增益最大的1000个词，即每个x_i对应一个1000维向量。实施例中的文档数据来自comp.graphics(计算机.图形)、rec.motocycles(娱乐.摩托车)、rec.sports.baseball(娱乐.体育.棒球)、sci.space(科学.宇宙)、talk.politics.mideast(对话.政治.中东)这5个类别的Newsgroups新闻文本数据，其中每个类别分别选择100个样本组成总共包含500个样本的数据集。

步骤1.2：

设置类的数目k为5，一般情况下k的数目远小于总的样本数n。

设置模糊化参数m以及正则项初始权重β⁰，在实际应用中，m为控制隶属度模糊程度参数，m越大，隶属度越模糊，m的值一般为1＜m＜2，对于文本归类问题，建议m≤1.2；β⁰＞0，由于β⁰的设定值越大则稀疏度越大，但是β⁰过大又会导致结果偏离正常，对于Newsgroups数据，β⁰可以设置在5-15间，图2中结果说明在实施例中，β⁰≤10都能取得比传统方法更好的结果。

设置结束判断参数ε和最大迭代次数T，一般情况下，ε的取值为10^-5≤ε≤10^-3,T的取值为80≤T≤120，如ε＝10-5，T＝100。

步骤1.3：初始化均值，为了得到与最后结果相对接近的k个初始均值[δ₁,δ₂,…δ_k]，选择k个彼此相距较远的样本点作为各个类的初始均值。

具体做法为：先随机产生1个样本点做为其中一个初始均值，然后根据与已选样本点中最近的距离的最大值来逐个产生剩下的k-1个样本点做为类的均值。记迭代次数l＝1；即，k个均值的初始值在选择的时候就尽量接近最后得到的k个均值，则算法最后的输出就是k个均值。

步骤1.4：基于当前均值，利用式更新所有隶属度矩阵中的值。

步骤1.5：

对每一类c＝1,2,…,k，更新权重β，本发明中即随着迭代的进行，各个均值k更加接近最后的解，对稀疏度的控制通过正则项的权重β随着迭代地进行而逐渐减少。具体做法是在每次迭代时，β以的速度减少。

一般情况下，选出每个δ_c中权重最大的字符作为关键词用于描述或解释该类别。

随后，基于隶属度u_ci以式更新对应的k个均值。

步骤1.6：判断是否需要继续执行迭代，一旦满足以下两个条件之一则迭代结束。

条件一：均值几乎不再变化。用两次迭代结果的l₂范数来衡量均值的变化，当k个均值中最大的变化小于设定参数ε，即时，可认为均值无变化。

条件二：实际迭代次数已经超过最大的迭代次数T。

如果以上两个条件均不满足则回到步骤1.3重复进行。

步骤1.7：输出聚类结果，即每个类的均值和记录所有样本到类的隶属度矩阵。

步骤1.7中，聚类结果为k个均值和记录所有样本到类的隶属度矩阵U。

步骤1.7中，将隶属度矩阵U中的每个样本k分配给隶属度最大的类，得到每个样本点k的类标签。