基于有序聚类方程的数据相似性识别数学建模

于春艳,张育梅

(长春工业大学人文信息学院,吉林 长春130000

1 引言

聚类指将数据集合内的数据依据固定的相似性度量准则划分为多组数据的方法。完成划分的相同组数据具有较高的相似性[1];完成划分后的不同组数据间存在较大差别。聚类算法是电子商务等众多领域中应用极为广泛的算法。目前各应用领域中的数据具有较高维度,样本与样本间的差异并不明显[2],提升了数据聚类的难度,容易存在某数据样本无法精准确定属于何种类别的问题,聚类算法无须先验信息即可获取数据中的相似信息。目前聚类算法应用于不同领域中,各领域中的复杂数据类型以及巨大数据量,提升了数据聚类难度[3]。传统聚类算法无法满足高维度以及大数据量的数据聚类需求。快速搜寻数据聚类中心,将完成划分的数据高效合并是大规模数据聚类的难点[4],提升聚类精度以及聚类速度已成为聚类领域的研究重点。相比于低维空间内的数据,高维空间内的数据聚类难度更高,聚类过程中容易出现维度灾难问题。

某些领域中数据集内的数据与数据间存在着固定顺序关系,存在固定顺序关系的变量称之为有序变量,有序变量间的差异无法通过简单的数值差异描述[5]。有序数据目前在市场调查、心理学等领域较为常见。有序数据通常为多元有序观测数据,多元有序数据的聚类精度极为重要。现有研究通常采用属性数据处理方法衡量不同有序观测量间的距离[6],利用不同有序观测量间存在的差异实施聚类。目前针对有序数据聚类的方法众多,王治和等人以密度敏感距离为基础[7],采用改进模糊C均值聚类算法实现有序数据的聚类;何韩吉等人将趋势性度量方法应用于有序数据聚类中[8]。以上两种方法均可以实现有序数据的聚类,但由于未考虑有序数据维度对聚类结果的影响,聚类效果并不理想。针对以上两种方法的缺陷,研究基于有序聚类方程的数据相似性识别数学建模,数学建模是常应用于数据统计分析中的重要方式,利用有序聚类方程建立识别数据相似性的数学模型,为数据相似性识别提供技术支持。通过仿真测试验证所建立的基于有序聚类方程的数据相似性模型具有较高的数据相似性识别性能,应用性极高。

2 数据相似性识别数学建模

设置所建立的基于有序聚类方程的数据相似性识别数学模型的输入和输出分别为多元有序数据样本集X={x1,x2,…,xn}以及聚类结果,基于有序聚类方程的数据相似性识别数学建模过程如下:

1)数据预处理

对待聚类的有序数据集实施归一化处理,将数据集内的数据归一化处理至[0,1]区间内,获取归一化后的数据集Data={x1,x2,…,xN};

2)依据网格粒化算法将完成归一化后的有序数据空间划分为多个均匀的网格空间;

3)扫描完成网格空间划分后的数据集X={x1,x2,…,xn},将数据集内的数据划分至相应网格单元中,计算各网格单元内数据的密度信息;

4)依据网格单元内数据密度信息计算结果识别各网格单元的中心点;

5)以网格单元中心点为基础,利用有序聚类方程计算各网格单元内有序数据的相似性[9],利用相似性计算结果将数据划分至不同类簇中,直至完成全部数据空间的网格扫描,将有序数据集内的数据点标记为相应类别,相同类别内的有序数据即为具有较高相似性的有序数据。通过以上过程完成基于有序聚类方程的数据相似性识别数学模型建立。

2.1 多元有序数据空间的网格粒化算法

选取STING网格划分方法作为多元有序数据空间的网格粒化算法。采用STING网格划分方法对多元有序数据空间内的有序数据实施粒化,将多元有序数据空间内的原始有序数据点利用网格单元数据替代[10],降低多元有序数据维度,实现多元有效数据的有效压缩。

设置STING网格划分算法的输入有序数据样本集以及输出网格单元集分别用X={x1,x2,…,xn}与G={g1,g2,…,gn}表示。STING网格划分方法的多元有序数据空间的网格粒化过程如下:

1)将多元有序数据空间集内全部数据归一化至维度为D={d1,d2,…,dn}的数据空间内,令[0,1]d⊂D。

2)多元有序空间内数据的聚类效果受划分网格粒度影响,选取最合适的网格划分粒度,可以获取最优聚类效果。划分网格数量过多时,网格单元内数据容易丢失,影响聚类精度[11];划分网格数量过少时,网格内数据与原数据空间内数据存在较高相似性,无法实现数据快速处理。网格划分的尺度参数需依据多元有序空间内的数据数量决定。通过尺度参数ξ划分多元有序数据空间网格,尺度参数表达式如下

ξ=N/k

(1)

式(1)中,N与k分别表示样本数量以及聚类数量。

划分多元有序数据空间网格维度的表达式如下

(2)

3)扫描全部多元有序数据空间内数据集,将数据集内全部数据放入完成划分后的数据空间网格中[12],网格单元数量为n。用N与k分别表示数据空间内数据维度以及数据点数量,D={d1,d2,…,dn}与X={x1,x2,…,xn}分别表示数据维度以及数据集,依据尺度参数ξ将多元有序空间内数据的每个维度划分为ε等分,可得不同维度的有序数据划分结果为di={c1,c2,…,cε}。

2.2 有序数据的网格中心点识别

用i表示完成划分后的多元有序网格空间内随机数据,随机数据i的密度计算公式如下

ρi=ϑi+ηi

(3)

式(3)中,ηi与ϑi分别表示多元有序网格空间内数据度数以及该数据全部邻域数据度数之和。通过式(3)获取多元有序空间内其中一个网格全部数据的密度值后,将所获取的数据密度值作为基础[13],可得全部数据间的距离σ。数据i的距离值σi计算表达式如下

(4)

式(4)中,dij表示有序数据i与有序数据j的图论距离,有序数据i的密度值低于有序数据j的密度值。

将数据i的密度值与距离值利用Z-score方法标准化处理。数据i的密度值标准化处理表达式如下

(5)

(6)

式中,μρ与μσ分别表示多元有序网格空间内全部数据的密度均值与距离均值;φp与φσ分别表示多元有序网格空间内全部数据的密度标准差与距离标准差。

(7)

2.3 有序聚类方程的数据相似性计算

识别有序数据相似性前,需要将全部有序数据依据固定的排序准则排列,令相邻有序数据间的相似性最高。以上文获取的网格单元中心点为基础,用C(F)表示有序数据的性质特征,有序数据的性质特征相似度到达固定数值时,即可划分为相同类别中。F表示数据的秩,该值越高时,表示数据重要性越高。有序聚类的实质是令完成聚类后,相同类别的有序数据差异尽可能小,不同类别的数据差异尽可能大[14]。采用有序聚类方程作为识别不同有序数据相似性的聚类算法,有序数据聚类过程如下:

1)对有序数据的相似性实施排秩处理。

以网格单元中心点为基础,依据从小到大原则对数据相似性指标向量内的全部相似性计算结果排秩。完成排秩后建立相似性指标的秩向量R=(r1,2,r2,3,…,rn-1,n)。

分析以上过程可知,相邻数据间的秩越小时,表示数据间相似性较小;相邻数据间的秩越大时,表示数据间相似性越大。

2)确定有序秩聚类的聚类数量k。

数据待聚类数量为k时,数据聚类的断开位置为rij=1,2,…,k-1,相邻断点内的数据即可划分为相同类别。

采用有序聚类方程对有序数据聚类时,需要确定的聚类数量需令不同类别有序数据的误差函数之和为最小。聚类过程中存在相同秩情况时,需要搜寻令误差函数最小的位置,从误差最小位置断开[15],获取最佳聚类结果。

定义有序数据的排序准则如下:

设多元有序空间内包含数据数量为n,Ck(Fk)表示有序数据k的分布特征,依据Fk将全部有序数据从小到大顺序排列。依据以上排序准则实现多元有序数据的同质数据集中化,异质数据分散化。通过有序数据的初步排序为有序数据相似性识别提供基础。

有序数据相似性识别过程如下:

计算多元有序空间内数据特征Ck(Fk),依据上文确定的数据排序准则,重新排序全部数据的Ck(Fk),完成排序后的数据用向量C=(C1,C2,…,Cn)表示。相邻数据相似性识别的有序聚类方程如下

(8)

利用向量S=(S1,2,S2,3,…,Sn-1,n)表示全部有序数据的相似性识别结果。

3 仿真测试

为了验证所建立数学模型采用有序聚类方程识别数据相似性有效性,采用Bochs仿真平台进行本文模型的仿真测试。选取应用于市场调查中的人工数据集作为本文模型的测试对象,数据集中包含子数据集3个。人工数据集中的有序样本为4维数据,包含样本数量共11889个。

统计本文模型采用有序聚类方程识别数据相似性,差异类别数量以及差异尺度参数时的下近似中类内间距,统计结果如图1所示。

图1 聚类收敛曲线

图1实验结果可以看出,有序聚类方程设置类别数量为12个时,采用本文模型可以在20次迭代次数之内实现快速收敛,且获取聚类结果的下近似中类内距离较高,说明此时本文模型具有良好的聚类收敛效果。采用本文模型识别数据相似性时,设置有序聚类方程的聚类类别数量为12。下近似中类内距离越大时,表示聚类算法准确率越高,此时划分至该类别中的有序样本越多。本文模型在聚类类别数量为12时,具有良好的聚类性能。

设置聚类类别数量为12,采用本文模型对测试数据集中的有序数据实施聚类处理,聚类结果如表1所示。

表1 本文模型聚类结果

表1实验结果可以看出,采用本文模型将测试数据集中的样本,划分为12类,此时相同类别内的有序数据具有较高相似性,验证本文模型可以有效识别有序数据集内的有序数据。本文模型可以利用有序聚类方程实现有序数据的有效识别,具有较高的应用性。

Kappa系数是常见的应用于评价聚类性能的指标,Kappa系数计算公式如下:

(9)

式(9)中,nk+与n+k分别表示类真实的样本数量以及类被分类的样本总数;nk与N分别表示划分至k簇中的样本数量。

设置聚类类别数量为12,统计不同邻居节点数量时,采用本文模型对不同类别有序数据相似性进行识别。不同邻居节点数量时,本文模型的Kappa系数统计结果如图2所示。

图2 Kappa系数对比结果

通过图2实验结果可以看出,邻居数越少时,数据相似性识别的Kappa系数越高,邻居节点数量越多时,影响了有序聚类方程的聚类效果,邻居节点数量为9时,采用本文模型识别有序数据相似性,设置邻居节点数量为9,此时可以获取最佳的有序数据识别结果。

统计采用本文模型识别有序数据相似性的标准互信息结果,统计结果如图3所示。

图3 标准互信息统计结果

通过图3实验结果可以看出,采用本文模型识别有序数据相似性,对不同子数据集内的有序数据样本进行相似性识别,识别结果的标准互信息结果均高于0.9。统计结果验证本文模型具有较高的有序数据相似性识别性能,本文模型可将具有较高相似性的有序数据精准聚类,聚类结果较优。

调节兰德指数是应用于聚类算法评价中的另一重要评价指标。调节兰德指数的取值区间为[-1,1],该指标可以体现聚类算法划分不同类别时的重叠情况。统计采用本文模型识别有序数据相似性的调节兰德指数,统计结果如图4所示。

图4 调节兰德指数

图4实验结果可以看出,采用本文模型识别有序数据相似性的调节兰德指数均高于0.8。图4实验结果验证本文模型具有较高的聚类性能,本文模型可将具有较高相似性的有序数据精准聚类,聚类性能优越,提升了模型的应用性。

采用本文模型识别测试数据集内的有序数据相似性,有序数据相似性识别的平均绝对误差结果如图5所示。

图5 平均绝对误差

图5实验结果可以看出,伴随样本数量的增加,本文模型识别有序数据相似性的平均绝对误差有所降低。实验结果说明本文模型在样本数据量较大时,仍具有较高的聚类性能,可以提升有序数据相似性的识别性能。有序数据具有较高的聚类难度,本文模型可以实现有序数据的精准聚类,获取理想的有序数据相似性识别结果,具有较高的有序数据相似性识别性能。

4 结论

有序数据由于结构过于复杂,增加了数据聚类的难度。多元有序数据的相似性识别已成为目前众多领域研究学者极为重视的重要内容。基于有序聚类方程建立数据相似性识别的数学模型,通过仿真测试验证所建立的数学模型可以实现有效数据相似性的高效识别,避免有序数据维度过多时,受噪声数据影响造成不良影响。所建立的数学模型具有较高的有效性,适用于众多领域中的数据相似性识别中。