2. 奥本大学计算机科学与软件工程学院 奥本 36849 美国
2. Department of Computer Science and Software Engineering, Auburn University, Auburn 36849, USA
聚类是根据数据对象之间的相似程度, 将数据集合理划分成若干数据子集的过程, 每个子集称为一个簇.聚类分析的目标是使得划分后的数据点在簇内彼此相似, 在簇间彼此相异.经典的聚类算法主要包括划分聚类算法[1-3]、层次聚类算法[4-6]、基于密度[7]和网格[8]的聚类算法以及谱聚类[9]等, 但没有任何一种聚类算法可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构[10].随着高维海量数据的广泛应用, 数据类型也日益复杂化和多样化, 以处理数值型数据为主的传统聚类算法已无法满足高维分类数据的聚类需求.而分类数据广泛分布在各应用领域中, 分类数据的聚类分析已成为目前数据挖掘领域中极具挑战性的研究方向之一[11-16].
目前, 分类数据聚类研究需要解决以下两个问题: 1)由于高维属性空间的稀疏性, 大量冗余属性或不相关属性使得全属性空间下的聚类结果毫无意义[17], 因此, 属性权重的度量成为提高高维分类数据聚类效果的关键问题之一; 2)由于分类数据缺乏数值型数据固有的几何特征, 不能进行数值运算, 同时, 也无法使用衡量数值型数据的距离方法去判定分类数据的相似性[18], 因此, 适合分类数据的簇集质量判断标准会直接影响聚类精度.本文针对分类数据, 定义了一种基于多属性频率的属性权重计算新方法, 并在此基础上, 采用多目标聚类准则, 结合层次聚类思想, 提出了一种适合分类数据的子空间聚类算法.该算法无需设定初始参数, 可以识别和处理噪音点, 并根据数据自身的结构特征, 在相关属性子空间上聚类.本文的主要贡献如下:
1) 定义了一种基于多属性频率的属性权重计算方法;
2) 给出了一种基于多目标簇集质量的聚类准则;
3) 提出了一种基于多属性权重的分类数据子空间聚类算法.
1 相关工作传统分类数据聚类算法[1, 19-20]认为各属性维在聚类过程中的作用是无差别的, 全属性空间下的聚类算法虽然可以有效解决低维数据的聚类问题, 但面对高维数据时, 有效性会显著降低.为了克服传统聚类算法存在的不足, 各种降维技术被用于降低高维属性空间维度, 主要的解决思路包括:特征转换[21]和特征选择[22-23].文献[21]总结对比了几种主要的特征转化技术, 如主成分分析(Principal components analysis, PCA)、核主成分分析(Kernel principal component analysis, KPCA)和独立分量分析(Independent component analysis, ICA)在高维空间向低维空间映射过程中的效果差异, 上述技术均采用将高维属性组合生成新属性的思路, 存在新组合属性的解释性差, 数据簇不易理解的缺陷.文献[22]在粗糙集理论的基础上, 提出一种贪婪的混合属性约简算法, 该算法利用所推导出的属性重要性度量规则, 可以有效降低属性空间的维度; 文献[23]提出一种基于对偶图特征选择聚类算法, 该算法使用自表示特征保存数据空间和属性空间的几何信息, 在数据空间的自表示系数矩阵上加入稀疏约束以分析属性重要性, 选取重要属性提高聚类质量.特征选择的方法可有效约简属性空间, 但这种将原属性空间中的若干属性提取出来构成新属性空间的方法, 会造成部分信息丢失.因此, 针对高维数据, 基于特征转换和特征提取技术的聚类效果仍无法满足实际需求.
近几年, 在传统降维技术研究的基础上, 基于属性子空间的聚类研究受到了广泛关注.大量文献[24-35]均验证了在高维数据背景下, 全属性空间上无法形成有意义的簇集, 类簇存在于不同的相关属性子空间中, 属性权重的度量不再以整个属性维为单元, 同一属性在不同数据点上的重要度不同, 因此, 属性子空间算法是目前解决高维数据聚类问题的有效途径之一[24].子空间聚类算法不仅可以将相似数据聚合成若干类簇, 同时针对不同类簇会给出各自独立的相关属性子空间.子空间的思想最初用于解决数值型数据的聚类问题[24-27].随着针对分类数据挖掘需求的不断增长, 各种高维分类数据的子空间聚类算法应运而生[28-35], 典型算法有:文献[28]采用最小化目标函数的思想, 提出了一种面向分类数据近似最优划分的子空间算法(Subspace clustering for categorical data, SUBCAD), 该算法奠定了与聚类相关子空间的理论基础, 但该算法所给出的目标函数无法确保在迭代过程是递减的; 文献[29]提出了一种基于图论的分类数据子空间聚类算法(Mining subspace clustering algorithm, CLICKS), 利用密度参数将聚类问题转化成加权图的思想, 以属性值之间的共现频次作为权值, 反复搜索
综上所述, 子空间聚类算法思想是基于各属性在聚类过程中权重的差异, 在重要属性组成的相关属性子空间中, 根据聚类目标函数将数据点划分到不同类簇内.多数子空间聚类算法[30-35]在选取构成子空间的相关属性时, 仅以属性取值的单属性权重作为衡量标准, 没有考虑到其他属性对于该属性值权重的影响, 即属性取值在整个属性空间上的分布特征.文献[29]在考虑多属性之间的关联对属性权重的影响时, 需遍历整个数据空间以统计属性值的同现次数, 从而增加了聚类过程的时空复杂性.作为判断聚类质量的关键, 数据点与簇的相似度计算是整个聚类算法的核心, 仅以类内数据点紧凑作为聚类目标会影响到簇集质量[33-35], 聚类结果容易受到非平衡数据分布的影响, 同时, 参数也会干扰聚类算法的稳定性.因此, 要有效地解决高维分类数据背景下的子空间聚类问题, 需要解决的关键问题为:利用属性值在多维属性上的分布特征, 获取高权值属性以构建各数据点的相关属性子空间; 在属性子空间的基础上, 将类内紧凑与类间分离相结合作为判断簇集质量的聚类准则, 以解决基于单目标函数聚类算法无法有效处理非平衡数据集的问题.
2 问题描述与求解策略分类数据(Categorical data)是指数据属性值是分类型的数据, 分类属性又称标称属性, 分类属性取值都是有限无序的, 且不可比较大小, 也无法进行数值运算.参考文献[30]与表 1定义的符号, 问题描述如下:
![]() |
表 1 符号表示及含义 Table 1 Symbol and notation |
分类数据的子空间聚类目标是将数据集
![]() |
图 1 聚类示例图 Figure 1 Clustering sample |
从图 1可以发现, 各簇对应的相关子空间规模不一定相同, 例如, 簇
针对上述子空间聚类问题, 由第1节的相关工作分析可知, 现有分类数据聚类方法在计算属性权重时存在的问题: 1)尽管单属性权重计算方法有利于提高时间效率, 但仅以单属性评价属性权值会造成属性值聚类区分度下降, 例如图 1, 属性
采用多属性频率计算属性权重, 有效地体现了属性值在属性空间中的分布特征, 可解决单属性计算权重所带来的聚类区分度下降等问题, 例如, 从属性空间分布上分析, 由于属性值
由第2节可知, 分类数据聚类步骤主要由四个阶段构成, 即:分类属性权重计算, 基于多目标聚类准则的层次凝聚聚类, 噪音点识别和识别属性相关子空间.
3.1 分类属性权重 3.1.1 分类属性权重计算依据解决第2节所提出的权重计算问题, 需要考虑两个因素: 1)属性取值在本地属性上的出现频率, 该值反映了属性值的局部重要程度; 2)用其他相关属性度量该属性值与相关属性值的共现频率, 该值刻画了属性值的全局重要性.为了避免计算共现频率而增加的时间成本, 可按照属性值将各属性划分为若干个数据集合, 为了表述方便, 用符号
在粗糙集理论[38]中,
对于任意
$ \begin{align} W_{a_i}(x_{ki}) =&\ \frac{|[x_k]_{a_i}|}{n}\times\lg\bigg\{{|[x_k]_{a_i}|} \times\nonumber\\ &\ \left(1-\frac{|[x_k]_{a_i}|}{n}\right)+1\bigg\} \end{align} $ | (1) |
其中,
从相关属性
$ \begin{align} W_{a_j}(x_{ki}) = \frac{|{[x_k]}_{a_j}\cap {[x_k]}_{a_i}|}{|{[x_k]}_{a_i}|} \end{align} $ | (2) |
其中,
用
$ \begin{align} W(x_{ki}) = \frac{W_{a_i}(x_{ki})\times \Big[\textstyle\sum\limits_{j=1, j\neq i}^{d} W_{a_j}(x_{ki})\Big]^{2}}{\textstyle\sum\limits_{k=1}^{n}\left\{W_{a_i} (x_{ki})\times\Big[\textstyle\sum\limits_{j=1, j\neq i}^{d} W_{a_j}(x_{ki})\Big]^{2}\right\}} \end{align} $ | (3) |
基于粗糙集的多属性度量方法可以有效提高属性的聚类能力, 解决仅依靠单属性无法区分同频次属性值权重的问题.例如图 1, 使用式(1)计算得,
聚类准则是聚类过程中判断数据点划分的主要依据, 通常采用簇集质量函数表示.簇集质量是指聚类结果的质量, 该值代表数据划分的合理程度, 簇集质量可以采用单目标和多目标两种方式, 多目标簇集质量更有利于挖掘数据集的内部结构.
3.2.1 多目标聚类准则依据基于单目标准则的聚类算法, 常用最小化类内误差平方和的方法聚类, 该方法容易导致大类边缘的数据点被误划到其他类中, 因此, 在簇内数据紧凑的基础上, 采用簇间数据分离的原则可避免边缘数据误判, 有效处理非平衡数据的聚类问题.
综合簇内紧凑和簇间分离两个目标来评价簇集质量, 1)簇集质量应取决于簇内数据是否紧凑, 簇内紧凑程度与簇投影到重要属性上的属性值相关, 该属性值权值越大, 出现的频率越高, 则簇集质量越好; 2)簇集的质量也与簇间数据分离程度相关, 为了使不同的簇尽可能分离, 簇投影在重要属性上的属性值应尽量集中, 不同的簇在高权值属性维上的取值应尽可能不同.
3.2.2 多目标簇集质量判断为了计算簇集总质量, 需要先分别计算各簇质量.参照文献[20]和文献[31], 基于属性值采用如下定义的
$ \begin{align} &Q(C_s)= \sum\limits_{x_k\in C_s}\sum\limits_{i=1}^{d}\left\{\left[Com(x_{ki})\right]^{2}\times Sep(x_{ki})\right\} \end{align} $ | (4) |
$ \begin{align} &Com(x_{ki})= [P(a_i=x_{ki}) \times \nonumber\\ &\qquad\qquad\quad\ \ P(a_i=x_{ki}|C_s)]\times W(x_{ki})=\nonumber\\ &\qquad\qquad\quad\ \ \frac{count(x_{ki}, a_i, C_s)}{n}\times W(x_{ki}) \end{align} $ | (5) |
$ \begin{align} &Sep(x_{ki})= \frac{P((a_i=x_{ki})\wedge (x_k\in C_s))}{P(a_i=x_{ki})}= \nonumber\\ &\qquad\qquad\quad\frac{count(x_{ki}, a_i, C_s)}{count(x_{ki}, a_i)} \end{align} $ | (6) |
簇内紧凑度
假设簇集
$ \begin{align} Q(C)=\sum\limits_{s=1}^{K}\left[P(C_s)\times Q(C_s)\right] \end{align} $ | (7) |
在多目标聚类准则的基础上, 层次凝聚聚类过程可分为初聚类和合并聚类两个阶段.初聚类阶段, 随机挑选一个数据点作为第一个子簇, 使用式(7), 依次计算其他待聚类数据点与现有子簇的簇集质量, 根据簇集质量最大化原则, 决定该数据点分配到已有的某个子簇中或者生成的新子簇.初聚类的目标是将数据中最相似的数据点划分为若干子簇, 子簇具有纯度高、规模小的特点, 可以代表大类的多个类中心, 子簇的形成不仅可以有效避免非平衡数据的均匀化, 同时也为迭代合并阶段提高了时间效率; 初聚类阶段利用簇集质量函数, 按照簇集质量最大化原则, 将每个数据点依次选择分配到已有的子簇中或者生成的新子簇.合并聚类的任务是找到同属一个类簇的所有子簇, 迭代合并各子簇以提高数据集的聚类质量, 直到整个迭代过程中没有产生合并子簇的操作为止; 该过程采用层次凝聚思想, 以式(7)度量的簇集质量函数最大化为基础, 将最相近的两个子簇合并.该阶段充分利用了高纯度子簇, 来迭代合并最相似的子簇, 有效地加速了聚类形成的过程.
3.3 噪音点检测噪音点是指那些与正常数据点有显著区别的特殊点.对于各属性权重都相对偏低的数据点, 可认为投影到任何维上都无法找到相似点, 即为噪音异常点.为了判断噪音点, 可引入如下定义的聚合度概念
$ \begin{align} Os(x_k)=\sum\limits_{i=1}^{d}{W(x_{ki})} \end{align} $ | (8) |
具体识别步骤:按照聚合度
上述步骤中提到的区间离散度用
$ \begin{align} {Ds}_i^j=\frac{1}{|j-i|}\times \sum\limits_{k=i}^{j}[Os(x_k)-\overline{Os(x_k)}]^{2} \end{align} $ | (9) |
属性相关子空间是由最能反映类簇特征的一组属性组成.计算各属性相对于簇的依附程度是确定属性子空间的关键, 采用
$ \begin{align} R(a_i, C_s)=& \sum\limits_{x_k \in C_s}\Bigg\{{\left[\frac{count(x_{ki}, a_i, C_s)}{n}\right]}^{2}\times \nonumber\\ &\ \left[W(x_{ki})\right]^{2}\times \frac{count(x_{ki}, a_i, C_s)}{count(x_{ki}, a_i)}\Bigg\} \end{align} $ | (10) |
属性子空间的识别方法与噪音点识别类似, 根据属性依附度
依据第2节和第3节, 基于多属性权重的子空间聚类算法SAC基本思想, 可归纳为:首先利用粗糙集概念分别计算属性值权重, 由式(1) ~ (3)完成, 计算过程可由函数WAC来实现; 其次利用式(8)计算各数据点的聚合度, 采用式(9)划分数据区间, 判断并去除噪音点, 此过程由函数NAI完成; 利用式(7), 实现将数据集到簇集的转化过程, 该过程由初聚类阶段和合并聚类阶段构成, 分别由两个函数INC和MEC实现; 最后基于式(10)给出的属性相对簇的依附度, 确定与簇相关的属性子空间, 具体实现由函数SUI完成.具体算法描述如下:
1) 函数WAC:计算属性权重函数
输入. 属性取值
输出. 权值
begin
保存
分别根据式(1)、式(2), 式(3), 计算
end
2) 函数NAI:噪音点识别
输入. 数据集
输出. 噪音集
begin
根据式(8)计算各点聚合度
for
{将数据序列分割为
根据式(9), 分别计算区间
end
3) 函数INC:初聚类
输入.
输出. 子簇集
begin
for
{
for
{
if (
{
if (
else {
输出子簇集
end
4) 函数MEC:合并聚类
输入. 子簇集
输出. 最终的簇集
begin
repeat
for
for
{利用式(7), 计算
迭代的簇集质量值;
if (
{
合并
until
end
5) 函数SUI:相关子空间识别
输入. 簇集
输出. 各簇
begin
用式(10), 计算
并将簇内各属性降序排序;
for
{将属性序列分割为
end
上文描述的SAC算法, 运行时间随数据量的增加呈线性增长.该算法主要由三个函数组成, 分别为属性权重计算、初步聚类和合并聚类, 因此, 算法SAC的时间复杂度分析主要包含以下三个阶段:设
1) 计算属性值权重的时间复杂度.该阶段的时间消耗主要集中在相关属性对属性值权重的度量上, 由于算法SAC采用粗糙集的等价类概念, 统计同现属性值的比较范围由
2) 初步聚类的时间复杂度.该阶段的主要操作是计算子簇内数据属性值对簇集质量的影响, 该阶段的时间复杂度为O
3) 合并聚类的时间复杂度.该阶段的时间消耗主要集中在寻找可合并子簇的操作上, 该阶段的时间复杂度为O
综合上述三个阶段的分析, 算法SAC时间复杂度为O
实验环境: 3.2 GHz Intel Core i5处理器, 2 GB内存, windows 7的操作系统, ECLIPSE 1.0的编辑环境, 并采用Java 7.0语言实现了本文SAC算法、CLICKS [29]算法、PROCAD [30]算法以及EWKM [35]算法, AT-DC [31]、DHCC [32]算法代码由作者提供.上述5种算法用于进行对比实验, 这些算法均可以解决高维分类数据的聚类问题.其中, CLICKS算法是一种基于图论的聚类算法, 该算法以属性值同现信息作为聚类依据; PROCAD算法是针对分类数据的子空间聚类算法, 该算法以属性值在单属性上的频率计算属性权重; AT-DC和DHCC是无参数的层次聚类的典型算法, 其中, AT-DC算法以属性值在簇中的条件概率作为属性权重, DHCC算法采用多元对应分析思想决定各属性在聚类过程中的作用; EWKM算法是基于经典K-Modes算法的改进算法, 利用最小化簇内误差平方和的思想计算属性权重. SAC算法是一种分类数据的子空间聚类算法, 算法基于粗糙集, 利用多属性维取值的频次衡量各属性权重, 采用层次凝聚策略聚类. SAC算法、PROCAD算法、AT-DC算法和DHCC算法均是无参算法, 无需设置参数; CLICKS算法的主要参数包括
![]() |
表 2 数据集 Table 2 Dataset |
聚类算法的评价指标可以分为内部和外部两类, 外部评价指标通常适用于有人工标示聚类结果的数据集, 使用聚类算法所得到的聚类结果与根据人的先验知识给出的结果进行对比, 可以有效地评价聚类算法是否适合于该数据集.参照文献[30-31], 分别采用调整兰德系数ARI (Adjusted rand index)、纯度Purity、雅克比系数Jaccard、兰德指数RI (Rand index)四个外部评价指标, ARI主要测试聚类结果和真实类之间的相似度. Purity评测聚类结果中各簇起支配作用的数据比例. Jaccard系数主要判断隶属于同一类的数据对在同一簇的比例. RI主要评测同类数据对是否被聚合以及异类数据对是否可以分开.其中, ARI, Jaccard和RI三个指标不仅注重对比两种结果中各簇内元素的分布状况, 更偏重两种聚类结果在类簇数目上的差距; 而指标Purity更侧重于衡量簇内占主导地位数据点的比例.
5.1 人工合成数据集为了全面测试算法的聚类效果, 结合文献[40]给出的合成数据方法, 构造了图 2所示的四种合成数据集.
![]() |
图 2 合成数据集示例图 Figure 2 Synthetic data sets sample |
如图 2(a)所示, 数据集Type 1各簇之间的数据点以及属性相关子空间独立存在, 互不相交; Type 2代表簇间数据点有交集, 如图 2(b)所示, 从不同的子空间分析,
在数据集Type 3上, 主要测试各算法在数据容量上的可扩展性, 分别选取6 000, 10 000, 20 000, 40 000和60 000作为数据量测试节点, 实验结果如图 3.从图 3可以发现, 随着数据量的增加, 所有算法的聚类时间都呈现近似线性增长的趋势, SAC算法所消耗的时间在所对比的算法中仅比PROCAD少.在数据集Type 2上, 主要测试各算法在属性维度上的可扩展性, 维度测试节点分别选择50, 100, 150和200维, 结果如图 4.如图 4所示, 随着维度的增加, 除CLICKS以外, 其余算法的聚类耗时呈现线性增长的态势, SAC算法消耗的时间虽然比算法AT-DC和DHCC多, 但远低于CLICKS算法, 略低于PROCAD算法.
![]() |
图 3 数据量可扩展性 Figure 3 Scalability with data |
![]() |
图 4 维度可扩展性 Figure 4 Scalability with dimendionality |
从图 3可知, SAC算法与PROCAD算法时间成本高于其他三种算法, 原因是这两种算法在衡量属性权重时, 需要计算数据点所有属性值的重要度, 当数据量增加时, 会比以整个属性为度量单位的算法费时.从图 4可知, CLICKS算法的时间效率明显受限于维数, 原因是该算法将聚类问题转化为有权图划分问题, 而图上的权值取决于数据点之间的同现次数, 当属性维增多或者属性值域元素增多时, 统计各维度上所有属性值的同现次数非常耗费时间.尽管SAC算法基于属性值间的同现频次计算权重, 随着数据集属性规模的增长, 会增加计算成本, 但该算法在聚类过程中采用粗糙集缩小属性查找范围, 缩短权重计算时间, 同时基于子簇的合并过程可以大大提高聚类迭代速度, 因此, 图 3与图 4所示的扩展性实验结果表明, SAC算法的运行时间随数据量和维度呈线性增长.
5.1.2 抗噪性抗噪性实验主要包括两方面: SAC算法在合成数据上对比不同维度之间的抗噪性能变化以及在真实光谱数据上的抗噪性能; SAC算法与其他5种聚类算法在合成数据集上的抗噪性对比实验.
在Type 1数据集上, 数据总量为10 000, 分别包含900, 1 800, 3 150和4 500个噪音点作为测试节点, 并观察在15, 30, 40和50维属性空间上算法SAC抗噪性能的变化. 图 5(a)和图 5(b)分别反映了在不同维度空间下, 噪音点数量的变化对算法SAC聚类指标ARI和Purity的影响.从图 5可知, SAC算法在噪音点的影响下, 性能较稳定, ARI与Purity指标均高于90 %, 尤其是50维的属性空间, 所有指标均在96 %以上, 说明SAC算法具有良好的抗噪性能.由图 5(a)和图 5(b)可知, SAC算法的抗噪能力与属性空间规模, 噪音点比例有关.在加入相同噪音点的数据环境下, 抗噪性能与属性空间的维数成正比.当属性空间越小、噪音点越多, 聚类效果所受影响越大, 其主要原因是SAC算法是基于属性之间的同现概率获取属性权重, 当属性空间过小时, 不利于挖掘簇的聚类模式.
![]() |
图 5 抗噪性实验 Figure 5 Immunity to noise |
为了测试SAC算法在真实数据上的抗噪能力, 选择包含8 315条208维恒星光谱记录的数据集, 分别加入1 000, 2 000和3 000条噪音记录.表 3显示在不同噪音环境下, SAC去除噪音点的数目以及各性能指标的变化, 表明噪音点对真实数据的聚类影响以及SAC算法的抗噪能力.从表 3可知, 与无噪音点时SAC性能指标相比, 所有指标值均下降, 其中, ARI下降最多, Purity最少; 同时, 聚类性能下降的程度与噪音数目成正比.算法SAC可以识别并去除大部分噪音点, 少量残留的噪音基本上会聚为若干类簇, 这些类簇仅包含噪音点, 这样的聚类结果对Purity影响最小, 但增加的类簇数目使得其他性能指标显著下降.
![]() |
表 3 SAC在光谱数据上性能指标变化 Table 3 Noise immunity on the spectral data for SAC |
在Type 1数据集上, 选取50维属性, 10 000个数据点构成测试数据, 包含噪音点数分别为900, 1 800, 3 150和4 500.随着噪音点数的增加, 对比SAC算法和其他五种算法的聚类效果. 图 5(c)反映了噪音点数量的变化对不同算法聚类指标ARI的影响.从图 5(c)可知, 算法SAC和PROCAD在抗噪性上的表现均优于其他4种算法, 原因是算法SAC和PROCAD都具有检测噪音点的能力, 聚类之前已去除了噪音点的干扰, 保证聚类性能的稳定.同时, 由于多属性权重有助于更精准地反映出数据点各属性的聚类能力, 可以更准确地检测到噪音点, 因此, 基于单属性权重算法PROCAD的抗噪性比算法SAC略低.
5.1.3 不同类型数据集的聚类性能对比采用图 2所描述四个合成数据集Type 1, Type 2, Type 3, Type 4作为实验数据集.四个数据集规模相同, 即10 000个数据点, 50维属性, 可聚为6个簇; Type 1, Type 2, Type 3是平衡数据, 各簇尺寸基本一致, Type 4簇的尺寸差异较大, 其中,
图 6显示在四种合成数据集上, 随维度变化, SAC聚类指标ARI、Purity的变化情况.由图 6可知, 尽管Type 1和Type 4数据分布相同, 但簇的尺寸有差异, 特别是Type 4各簇规模差距很大. SAC算法在Type 1和Type 4上的聚类效果良好, 各指标均可达到100 %, 说明SAC算法的聚类效果与簇尺寸是否平衡无关; 而Type 2和Type 3的实验结果显示, SAC聚类效果与数据分布紧密相关, 随着维度的增加, Type 2和Type 3数据分布的变化可能会造成最终聚类性能的下降.
![]() |
图 6 SAC算法在四种数据集上的对比实验 Figure 6 Contrast experiment on four data sets for SAC |
由于大簇的边缘数据容易受到小簇类中心的干扰, 单一类中心无法反映大簇特征等原因, 非平衡数据往往更容易聚成尺寸相等的类簇.由图 6 Type 1和Type 4上的聚类效果可知, SAC算法没有受到类簇尺寸差异的影响.原因是SAC算法利用多目标聚类准则, 强化大类边缘数据与小簇之间的类间分离作用; 同时分阶段的层次聚类过程采用子簇的形式, 利用多个类中心表示大类, 从而避免出现“均匀效应”的现象.在Type 2和Type 3上, SAC算法的ARI和Purity值, 随着维数增加而下降.原因是随数据维度增加, Type 2中数据交集和Type 3中的属性子空间交集范围均在扩大, 当交集比例过大时, 类簇之间的差异会随之减少, 在合并聚类阶段, 原本分属两个类的数据点会聚为一类.
图 7显示在50维, 10 000个数据点的数据规模上, SAC与其他5种算法在四类数据集上的ARI性能指标差异.从图 7可见, SAC算法在四类数据集上的聚类效果均优于其他算法, 并且该算法在不同数据集上的聚类性能较稳定.
![]() |
图 7 各算法在四种数据集上的(ARI)对比 Figure 7 Contrast experiment on four data sets (ARI) for all algorithms |
文献[15]指出, CLICKS算法在数据集Type 2和Type 3上聚类性能不佳的主要原因是该算法会产生大量冗余簇; 而算法PROCAD、DHCC和AT-DC在四类数据集上的性能差别不大, 尽管算法DHCC和AT-DC无法给出簇集的相关子空间, 但在高维属性空间下, 这三类算法对数据集结构不敏感; 算法EWKM是基于K-Modes提出的, 这类算法在识别尺寸差别较大的簇集时, 会出现“均匀效应”, 因此, 该算法在数据集Type 4上的聚类性能会降低.
5.2 UCI数据集实验分别选取Voting, Splice, Mushroom和Zoo四个UCI数据集, 这些数据集均由分类数据组成, 其中, Zoo中只含有一个数值型属性; 数据集均带有类别标识, 可以用外部评价指标, 更客观地度量各算法的聚类效果.
Voting数据集共包含435条记录, 每条记录由16个议题的投票结果和一个类标签构成; 属性值域{
从表 4和图 8可知, SAC算法在Voting和Splice上的聚类效果均优于其他三种算法; 在Mushroom上, PROCAD算法ARI、Jaccard和RI指标均高于其他算法; 而AT-DC算法在Zoo上的实验效果最优.其主要原因: 1) SAC在Voting和Splice数据集上的效果最优, 原因是这两类数据集的共同特点是属性值域元素个数都较少, 其中, Congressional Voting的属性值是布尔型; 数据集Splice的属性值仅有四个, 通常属性值的取值范围较小, 会造成单属性权值的区分度不明显, 进而影响到基于单属性聚类算法的最终聚类结果, 而SAC算法利用多属性的同现概率可以很好地解决这一问题, 进一步提高算法的聚类效果, 该结论可由表 5和表 6的聚类结果得到验证. 2) SAC在Mushroom上的聚类性能仅次于PROCAD, 而在Zoo上也是略低于AT-DC, 原因是SAC算法用式(3)强化了多属性频率对属性权重的影响, 所以, 即使同一个类的数据, SAC会根据子簇模式上的差异划分出若干纯度极高的子簇, 经过合并所形成的簇集纯度依旧非常高, 但同时也会造成簇划分较细的问题, 簇集细化会保证算法的聚类纯度, 但也影响了其他三项指标, 该现象在表 7和表 8中都有体现.
![]() |
表 4 UCI数据集上的算法性能 Table 4 Algorithm performance on UCI |
![]() |
图 8 UCI数据集上的算法性能 Figure 8 Algorithm performance on UCI |
![]() |
表 5 Voting集上的实验结果 Table 5 Experimental results on Voting |
![]() |
表 6 Splice集上的实验结果 Table 6 Experimental results on Splice |
![]() |
表 7 Zoo集上的实验结果 Table 7 Experimental results on Zoo |
![]() |
表 8 Mushroom集上的实验结果 Table 8 Experimental results on Mushroom |
Zoo数据集规模较小, 但属性维较多, 有利于分析结果, 且该数据集所对应的类别较多, 可以更全面地反映出数据中不同结构的差异, 因此Zoo数据集有利于测试SAC算法在属性相关子空间上的识别能力.
从表 9可知, SAC算法的聚类结果可以分为三类:划分完全准确的簇, 例如
![]() |
表 9 Zoo数据集中的相关子空间 Table 9 Relevant subspace on Zoo data set |
1) 被准确划分的数据点特征是:该类数据间具有很强的结构特征, 同时, 簇内数据点在该结构特征上属性取值也非常一致.例如
2) 本属异类却聚合在一起的数据点特征是:该类数据点在某种划分方式下可以分为两类, 而从其他分类角度上分析, 这些数据又具有一些共同的特殊特征, 可以归为一类.例如,
3) 本属同类却分为两个簇的数据点特征是:该类数据点虽然同属一类, 但数据点仍具有各自特点.例如, 同属于无脊椎动物的Octopus (章鱼)、Scorpion (蝎子)和Starfish (海星), 根据腿数的不同也可以分为
从上述分析中可知, SAC算法在识别属性相关子空间时, 可以识别出特征信息明显的关键属性子集作为属性子空间, 该属性子集不仅在簇内具有高权值的特点, 而且高权值的属性取值又具有专属性, 例如, 属性Legs在每个簇上的取值几乎都不同, 原因是多属性权重计算方法在挖掘重要属性时更注重该属性在整个属性空间中的分布特征, 并非仅依靠单属性的出现频率, 因此, 基于多属性频率的属性权重聚类方法所提取的属性子空间对聚类结果更具解释性.
5.4 天体光谱数据根据国家天文台提供的恒星光谱数据, 选取了8 315条208维光谱记录作为实验数据, 该数据集按照恒星温度由低至高排序可以将恒星光谱分为7类(分别用
表 10给出各种等距离散化方法与SAC聚类性能指标之间的关系.指标Purity与离散化程度是单调递增的关系, 而其他三项指标会呈先扬后抑趋势.造成该现象的主要原因是SAC算法擅长处理具有独立不相关的属性子空间(如Type 1)的数据集, 离散化程度越高, 对于簇的特征划分的越细致, 因此, 聚类结果中的大量高纯度簇, 会提高聚类结果的纯度, 但划分过细也会造成其他三项性能指标的下降.
![]() |
表 10 各种离散化方法下的SAC聚类性能指标对比 Table 10 Clustering performance of different discretization methods |
使用11等距离散化方法预处理光谱数据, 并实验对比SAC算法与其他5种算法在真实数据上的聚类性能差异.从表 11可知, 算法SAC的各性能指标均高于其他算法, PROCAD、DHCC和AT-DC性能无明显差异, 算法EWKM的性能最低.光谱数据实验得到了与合成数据相似的实验结果, 主要原因是光谱数据是非平衡数据, 其中类
![]() |
表 11 各算法在光谱数据上的对比实验 Table 11 Algorithm performance on spectral data |
采用属性相关子空间, 挖掘隐藏在高维属性空间中的簇是高维分类数据聚类领域中的研究难点和热点之一.本文基于粗糙集采用多属性频率权重, 提出一种分类数据子空间聚类算法SAC.该算法基于粗糙集采用多属性频率计算属性权重, 解决了使用单属性计算权重所带来的问题, 同时借助粗糙集可以提高统计多属性频率的时间效率; 针对噪音点对聚类效果的影响, 使用区间离散度方法, 有效地删除了噪音点; 基于层次凝聚聚类思想, 利用多目标簇集质量函数迭代合并子簇, 解决单目标聚类函数聚类结果不精确的问题; 利用属性相对簇的依附度, 提取属性相关子空间, 提高了聚类簇的可理解性; 大量的实验结果验证了算法SAC的正确性和有效性.下一步研究工作是将SAC算法由分类数据扩展到混合数据.
附录A性质A1. 当
证明. 由下近似集的定义可知:
因为
该情况表明, 对于数据
性质A2. 当
证明. 因为
$ W_{a_j }(x_{ki} )=\dfrac{|[x_k]_{a_j} \cap [x_k]_{a_i }|}{|[x_k]_{a_i }|}=\dfrac{1}{|[x_k]_{a_i }|} $ |
当
性质A3. 当
证明. 由上近似集定义可知,
1 |
Wu X H, Wu B, Sun J, Qiu S W, Li X. A hybrid fuzzy K-harmonic means clustering algorithm. Applied Mathematical Modelling, 2015, 39(12): 3398-3409. DOI:10.1016/j.apm.2014.11.041 |
2 |
Jiang Yi-Zhang, Deng Zhao-Hong, Wang Jun, Qian Peng-Jiang, Wang Shi-Tong. Collaborative partition multi-view fuzzy clustering algorithm using entropy weighting. Journal of Software, 2014, 25(10): 2293-2311. ( 蒋亦樟, 邓赵红, 王骏, 钱鹏江, 王士同. 熵加权多视角协同划分模糊聚类算法. 软件学报, 2014, 25(10): 2293-2311.) |
3 |
Bai L, Liang J Y. Cluster validity functions for categorical data:a solution-space perspective. Data Mining and Knowledge Discovery, 2015, 29(6): 1560-1597. DOI:10.1007/s10618-014-0387-5 |
4 |
Bouguettaya A, Yu Q, Liu X, Zhou X, Song A. Efficient agglomerative hierarchical clustering. Expert Systems with Applications, 2015, 42(5): 2785-2797. DOI:10.1016/j.eswa.2014.09.054 |
5 |
Zhou Chen-Xi, Liang Xun, Qi Jin-Shan. A semi-supervised agglomerative hierarchical clustering method based on dynamically updating constraints. Acta Automatica Sinica, 2015, 41(7): 1253-1263. ( 周晨曦, 梁循, 齐金山. 基于约束动态更新的半监督层次聚类算法. 自动化学报, 2015, 41(7): 1253-1263.) |
6 |
Jeon Y, Yoon S. Multi-threaded hierarchical clustering by parallel nearest-neighbor chaining. IEEE Transactions on Parallel and Distributed Systems, 2015, 26(9): 2534-2548. DOI:10.1109/TPDS.2014.2355205 |
7 |
Kim Y, Shim K, Kim M S, Sup Lee J. DBCURE-MR:an efficient density-based clustering algorithm for large data using MapReduce. Information Systems, 2014, 42: 15-35. DOI:10.1016/j.is.2013.11.002 |
8 |
Mansoori E G. GACH:a grid-based algorithm for hierarchical clustering of high-dimensional data. Soft Computing, 2014, 18(5): 905-922. DOI:10.1007/s00500-013-1105-8 |
9 |
Shang R H, Zhang Z, Jiao L C, Wang W B, Yang S Y. Global discriminative-based nonnegative spectral clustering. Pattern Recognition, 2016, 55: 172-182. DOI:10.1016/j.patcog.2016.01.035 |
10 |
Sun Ji-Gui, Liu Jie, Zhao Lian-Yu. Clustering algorithms research. Journal of Software, 2008, 19(1): 48-61. ( 孙吉贵, 刘杰, 赵连宇. 聚类算法研究. 软件学报, 2008, 19(1): 48-61.) |
11 |
Park I K, Choi G S. Rough set approach for clustering categorical data using information-theoretic dependency measure. Information Systems, 2015, 48: 289-295. DOI:10.1016/j.is.2014.06.008 |
12 |
Chen L F, Wang S R, Wang K J, Zhu J P. Soft subspace clustering of categorical data with probabilistic distance. Pattern Recognition, 2016, 51: 322-332. DOI:10.1016/j.patcog.2015.09.027 |
13 |
Cao F Y, Liang J Y, Bai L, Zhao X W, Dang C Y. A framework for clustering categorical time-evolving data. IEEE Transactions on Fuzzy Systems, 2010, 18(5): 872-882. DOI:10.1109/TFUZZ.2010.2050891 |
14 |
Li M, Deng S B, Wang L, Feng S Z, Fan J P. Hierarchical clustering algorithm for categorical data using a probabilistic rough set model. Knowledge-Based Systems, 2014, 65: 60-71. DOI:10.1016/j.knosys.2014.04.008 |
15 |
He X, Feng J, Konte B, Mai S T, Plant C. Relevant overlapping subspace clusters on categorical data. In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 2014. 213-222
|
16 |
Ji J C, Pang W, Zheng Y L, Wang Z, Ma Z Q. A novel artificial bee colony based clustering algorithm for categorical data. PLoS ONE, 2015, 10(5). |
17 |
Gan G, Wu J, Yang Z. PARTCAT: a subspace clustering algorithm for high dimensional categorical data. In: Proceedings of the 2006 IEEE International Joint Conference on Neural Network Proceedings. IEEE, 2006: 4406-4412 http://ieeexplore.ieee.org/xpls/icp.jsp?arnumber=1716710
|
18 |
Bouveyron C, Girard S, Schmid C. High-dimensional data clustering. Computational Statistics and Data Analysis, 2007, 52(1): 502-519. DOI:10.1016/j.csda.2007.02.009 |
19 |
Guha S, Rastogi R, Shim K. ROCK: a robust clustering algorithm for categorical attributes. In: Proceedings of the 15th International Conference on Data Engineering. Sydney, Australia: IEEE, 1999. 512-521 http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=754967&tag=1
|
20 |
Barbará D, Li Y, Couto J. COOLCAT: an entropy-based algorithm for categorical clustering. In: Proceedings of the 11th ACM International Conference on Information and Knowledge Management. McLean, VA, USA: ACM, 2002. 582-589 http://dl.acm.org/citation.cfm?id=584888
|
21 |
Cao L J, Chu K S, Chong W K, Lee H P, Gu Q M. A comparison of PCA, KPCA and ICA for dimensionality reduction in support vector machine. Neurocomputing, 2003, 55(1-2): 321-336. DOI:10.1016/S0925-2312(03)00433-8 |
22 |
Hu Q H, Xie Z X, Yu D R. Hybrid attribute reduction based on a novel fuzzy-rough model and information granulation. Pattern Recognition, 2007, 40(12): 3509-3521. DOI:10.1016/j.patcog.2007.03.017 |
23 |
Shang R H, Zhang Z, Jiao L C, Liu C Y, Li Y Y. Self-representation based dual-graph regularized feature selection clustering. Neurocomputing, 2016, 171: 1242-1253. DOI:10.1016/j.neucom.2015.07.068 |
24 |
Parsons L, Haque E, Liu H. Subspace clustering for high dimensional data:a review. ACM SIGKDD Explorations Newsletter, 2004, 6(1): 90-105. DOI:10.1145/1007730 |
25 |
Yip K Y, Cheung D W, Ng M K. HARP:a practical projected clustering algorithm. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(11): 1387-1397. DOI:10.1109/TKDE.2004.74 |
26 |
Müller E, Günnemann S, Assent I, Seidl T. Evaluating clustering in subspace projections of high dimensional data. Proceedings of the VLDB Endowment, 2009, 2(1): 1270-1281. DOI:10.14778/1687627 |
27 |
Bouguessa M, Wang S R. Mining projected clusters in high-dimensional spaces. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(4): 507-522. DOI:10.1109/TKDE.2008.162 |
28 |
Gan G J, Wu J H. Subspace clustering for high dimensional categorical data. ACM SIGKDD Explorations Newsletter, 2004, 6(2): 87-94. DOI:10.1145/1046456 |
29 |
Zaki M J, Peters M, Assent I, Seidl T. CLICKS:an effective algorithm for mining subspace clusters in categorical datasets. Data and Knowledge Engineering, 2007, 60(1): 51-70. DOI:10.1016/j.datak.2006.01.005 |
30 |
Bouguessa M. Clustering categorical data in projected spaces. Data Mining and Knowledge Discovery, 2015, 29(1): 3-38. |
31 |
Cesario E, Manco G, Ortale R. Top-down parameter-free clustering of high-dimensional categorical data. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(12): 1607-1624. DOI:10.1109/TKDE.2007.190649 |
32 |
Xiong T K, Wang S R, Mayers A, Monga E. DHCC:divisive hierarchical clustering of categorical data. Data Mining and Knowledge Discovery, 2012, 24(1): 103-135. DOI:10.1007/s10618-011-0221-2 |
33 |
Bai L, Liang J Y, Dang C Y, Cao F Y. A novel attribute weighting algorithm for clustering high-dimensional categorical data. Pattern Recognition, 2011, 44(12): 2843-2861. DOI:10.1016/j.patcog.2011.04.024 |
34 |
Chan E Y, Ching W K, Ng M K, Huang J Z. An optimization algorithm for clustering using weighted dissimilarity measures. Pattern Recognition, 2004, 37(5): 943-952. DOI:10.1016/j.patcog.2003.11.003 |
35 |
Jing L P, Ng M K, Huang J Z. An entropy weighting k-means algorithm for subspace clustering of high-dimensional sparse data. IEEE Transactions on Knowledge and Data Engineering, 2007, 19(8): 1026-1041. DOI:10.1109/TKDE.2007.1048 |
36 |
Xiong H, Wu J J, Chen J. K-means clustering versus validation measures:a data-distribution perspective. IEEE Transactions on Systems, Man, and Cybernetics, Part B:Cybernetics, 2009, 39(2): 318-331. DOI:10.1109/TSMCB.2008.2004559 |
37 |
Liang J Y, Bai L, Dang C Y, Cao F Y. The k-means-type algorithms versus imbalanced data distributions. IEEE Transactions on Fuzzy Systems, 2012, 20(4): 728-745. DOI:10.1109/TFUZZ.2011.2182354 |
38 |
Qu Kai-She, Zhai Yan-Hui, Liang Ji-Ye, Li De-Yu. Representation and extension of rough set theory based on formal concept analysis. Journal of Software, 2007, 18(9): 2174-2182. ( 曲开社, 翟岩慧, 梁吉业, 李德玉. 形式概念分析对粗糙集理论的表示及扩展. 软件学报, 2007, 18(9): 2174-2182.) |
39 |
Liu Shao-Hui, Sheng Qiu-Jian, Wu Bin, Shi Zhong-Zhi, Hu Fei. Research on efficient algorithms for rough set methods. Chinese Journal of Computers, 2003, 26(5): 524-529. ( 刘少辉, 盛秋戬, 吴斌, 史忠植, 胡斐. Rough集高效算法的研究. 计算机学报, 2003, 26(5): 524-529.) |
40 |
Kim M, Ramakrishna R S. Projected clustering for categorical datasets. Pattern Recognition Letters, 2006, 27(12): 1405-1417. DOI:10.1016/j.patrec.2006.01.011 |
41 |
Zhang Ji-Fu, Jiang Yi-Yong, Hu Li-Hua, Cai Jiang-Hui, Zhang Su-Lan. A concept lattice based recognition method of celestial spectra outliers. Acta Automatica Sinica, 2008, 34(9): 1060-1066. ( 张继福, 蒋义勇, 胡立华, 蔡江辉, 张素兰. 基于概念格的天体光谱离群数据识别方法. 自动化学报, 2008, 34(9): 1060-1066.) |
42 |
Zhang J F, Zhao X J, Zhang S L, Yin S, Qin X. Interrelation analysis of celestial spectra data using constrained frequent pattern trees. Knowledge-Based Systems, 2013, 41: 77-88. DOI:10.1016/j.knosys.2012.12.013 |