基于几何特征加权和选择的数据空间聚类算法研究

聚类分析是一种非常重要的数据处理技术和方法，在识别数据内在结构方面有着重要作用，通过聚类分析，人们能够识别不同区域。密集的或稀疏的，进而发现全局的分布模式和数据间的相互关系。当前，聚类分析已成为计算机、人工智能领域的研究热点，广泛被应用于数据探测、模式识别、信息检索、文本挖掘、生物信息学、医学诊断的研究中。然而，现存的数据规模越来越大，数据特征不断增加，且数据挖掘越来越强调多学科的交叉，不仅需要灵活运用统计学、计算机、数学等建模技术，还需要有生物学、经济学等学科的知识背景，为此，我们必须对现有聚类算法进行深入研究，并做出合理改进。基于此，笔者针对数据的高维特征，提出了高维聚类方法——基于竞争合并策略的软子空间聚类算法和基于基于空间实体约束的空间聚类算法。

一、聚类分析过程与要求

聚类在数据挖掘中是一个很重要的概念。聚类过程一般为：数据准备——从原有特征中选取有效特征存入向量中——进行特征提取——选择并利用合适的距离函数对特征进行聚类或分组——采取内外部有效性评价法和相关性测试评价法对聚类结果进行评价。

聚类分析时一项极具挑战性的工作，由于应用领域不同，提出了聚类的典型要求：①聚类算法应能高度扩展，具有良好可伸缩性。②具备处理不同类型属性的能力，以实现对多种数据类型的有效聚类。③一个簇可能是任意形状的，要求提出能发现任意形状的聚类算法对任意形状的簇进行有效聚类。④录入数据时可能会存在错误或异常数据，聚类算法应能处理噪声数据。⑤进行聚类是需要输入一些参数，聚类算法应能使输入参数的领域知识最小化。⑥许多传统聚类算法无法在高维空间中聚类数据对象，要求找到具有高维性、能有效聚类高维数据的聚类算法。⑦现实世界的应用可能需要在各种约束条件下进行聚类，要求找到基于约束的聚类算法。⑧通过聚类算法获得的聚类结果应是可解释的、可理解的、可用的。

二、基于竞争合并策略的软子空间聚类算法

在过去十年中，模糊加权软子空间聚类算法（FWSC）、熵加权软子空间聚类算法（EWSC）、基于竞争合并策略的模糊聚类算法（FCA）、基于主动模糊约束的聚类算法（AFCC）等被提出并被应用于各个领域，但与多数传统聚类算法一样，FWSC和EWSC算法易陷入局部最小值情况，而不能得到恰当的聚类划分，FCA和AFCC算法则不能发现各个数据簇的子空间结构。在现有聚类算法基础上，笔者将竞争合并策略应用于软子空间聚类算法研究中，提出了基于竞争合并策略的模糊加权软子空间聚类算法（FWSCA）。

最小化FWSCA算法目标函数公式：

   （1）

（0≤≤1，=1，0≤≤1，=1）

根据公式（1）定义目标函数L（,,,,）：

L（,,,,）

=   （2）

其中，V=[v1,...,vc]、U=[u1,...,uc]、W=[w1,...,wc]分别表示聚类中心矩阵、模糊隶属度矩阵和特征加权系数矩阵。

假设给定U=[u1,...,uc]和W=[w1,...,wc]，m>1，α>0，最小化目标函数JFWSCA，当且仅当聚类中心vik迭代公式为（3）时，为最小化目标函数JFWSCA的必要条件。

   （3）

假设给定U=[u1,...,uc]和V=[v1,...,vc]，m>1，α>0，最小化目标函数JFWSCA，当且仅当特征加权系数wik迭代公式为（4）时，为最小化目标函数JFWSCA的必要条件。

   （4）

给定V=[v1,...,vc]和W=[w1,...,wc]最小化公式（2），关于uij和求偏导，令优化方程值为0，并假设模糊隶属度在两次迭代之间变化不大，本文定义第i个数据簇的势为：

   （5）

根据公式（5），按照迭代顺序进行迭代后得到uij，重新审视可发现：

   （6）

其中，

   （7）

   （8）

式中，表示单个样本xj对于所有数据簇的势的加权平均。

公式（6）中的为传统FWSC算法的隶属度迭代公式，根据样本，可计算聚类中心的特征加权距离；用于消减某些虚假聚类中心隶属度大小，按照公式（5）可得到势Ni，当其小于某个阈值，聚类中心可被消去。根据公式（8）计算聚类中心vi的势Ni和样本xj对于所有数据簇加权平均势之间的差异，若Ni小于，则为负值，uij减小。我们可以将看作是一个放大因子，使其随样本xj到聚类中心vi之间距离的增加而减小，进而逐渐将虚假类聚中心的势的大小消减。

对于参数α的选择，应考虑、比值情况，根据公式（1），将参数α定义为：

   （9）

式中，itr指的是FWSCA算法的迭代索引指数。采用指数因子学习法将定义为：

   （10）

式中，为学习因子初始值，、为时间常量。

上述方法对于数据簇消去的阈值比较敏感，为此在上述方法的基础上，本文又提出了一种新的合并过程，即先计算第itr次迭代，得到所有数据簇势的平均值，然后利用聚类中心之间的距离判断整个合并过程的准确性和合理性。将第itr次迭代数据簇势的平均值和阈值分别定义为：

   （11）

   （12）

式中，n表示数据样本个数，c（itr）第itr次迭代时数据簇个数，η为合并阈值参数。按照公式（11）、（12）计算，第itr次迭代时，若某数据簇势小于MCT，将该数据簇消去，消去数据簇的同时对数据簇个数进行更新。

判断整个合并过程时，将聚类中心之间的距离定义为d（r），当其最小值满足公式（13）时，合并数据簇，进行数据簇个数的更新。

   （13）

总结起来，FWSCA算法流程为：设置最大数据簇聚类数目c=cmax（2≤cmax≤n），模糊加权指数m以及竞争合并参数n，初始化模糊隶属度，设置迭代指数itr=1。根据公式（3）计算聚类中心矩阵V（itr+1）。根据公式（4）计算加权系数矩阵W（itr+1）。根据公式（5）计算第i个数据簇的势Ni（1≤i≤c）。根据公式（9）和（10）更新参数α（itr）。根据公式（6）计算模糊划分矩阵U（itr+1）。判断Ni是否小于数据簇势的阈值或者各个聚类中心之间最小距离是否满足公式（13），若满足，则删除该数据簇。更新数据簇聚类数目c（itr+1）。若满足迭代停止条件或数据簇聚类数目保持稳定，则迭代停止并输出最终聚类结果，否则itr=itr+1，并跳转到第二步。

三、基于空间实体约束的空间聚类算法

空间实体的存在会对空间聚类分析产生影响。传统聚类算法中一般是采用样本间的直线距离来衡量样本间、数据簇间的相似性，忽略了空间实体的约束作用，从而影响了聚类结果。比如要在一个城市内设置ATM，对给定的ATM进行选址的时候，为了保证服务网络最优化，不仅要按照空间位置特征对城市所有的居民点进行聚类，还需要考虑道路、桥梁、河流、山脉等可跨越障碍物的便利体的连通作用。

基于约束Delaunay三角网特性提出一种基于Delaunay三角剖分的用于空间约束数据聚类的算法——基于空间实体约束的空间聚类算法（CDC）。CDC算法首先要划分数据集，提取空间位置属性，同时考虑空间障碍和空间便利，利用非空间属性调整初始划分，最后对划分结果进行合并。得到的包含约束点的三角网需首先删除约束点以及与之相连的边，记录与便利点相连的点集和点集间相连的边，对所得边进行统计，若已有边的权值大于通过便利点连接后的权值，则删除已有边，将通过便利点连接的边纳入边集合，若已有边权值小于通过便利点连接的边，则保留原有边。为实现三角网的自动划分，要在三角网中删除便利点和与点相连的边，本文给出三角形Ti的平均值和三条边的方差：

   （14）

   （15）

三角形从长到短的边分别定义为：Timax、Timid、Timin，当Timax-Timin>2Sub（Ti），保留最短边，删除最长边；若Timid-Timin>2Sub（Ti），保留最短边，删除中间长度的边。反之则保留最长边或中间长度的边。重复上述过程直到每个三角形判断完成，停止三角网划分。

四、结语

空间数据挖掘是一个从空间数据中提取或识别有效、有利用价值、可理解的数据的非平凡过程，在这个过程中，需要以空间聚类算法为支撑。本文在现有聚类算法的基础上，提出了FWSCA算法和CDC算法，这两种算法都是对原有聚类算法的改进，具有良好适用性和有效性。但本研究对于聚类分析这一应用广阔的领域来说只是初步的，聚类分析相关理论仍需进一步完善，聚类结果的质量、聚类受初始值影响程度、能否发现任意形聚类及聚类的执行效率也有待提高，只有将理论研究成果实用化，才能使之真正应用于实际问题的解决中。

参考文献：

[1]周涛,陆惠玲.数据挖掘中聚类算法研究进展[J].计算机工程与应用,2012,12:100-111.

[2]朱林,雷景生,毕忠勤,杨杰.一种基于数据流的软子空间聚类算法[J].软件学报,2013,11:2610-2627.

[3]于翔,印桂生,许宪东,王建伟.一种基于区域划分的数据流子空间聚类方法[J].计算机研究与发展,2014,01:88-95.

[4]李婧.基于数据几何特征的空间聚类算法[D].重庆师范大学,2014.

[5]曹世媛.基于密度的数据流子空间聚类算法研究[D].燕山大学,2010.

 本文来源：http://www.zzqklm.com/w/kj/11621.html  《信息技术信息化》