不平衡数据软子空间聚类算法在临床医学中的应用与研究

程铃钫 陈黎飞 赖晓燕

摘  要： 聚类分析是数据挖掘中重要的研究课题，在信息过滤、生物信息学，医学等领域得到广泛应用。本课题着重于自上而下的子空间聚类方法，主要原因是当前主要的此型算法都是以K-means或K-modes为基础的，在均匀效应的影响下，不平衡数据的问题是现有的软子空间算法不能有效聚类的，所以提出了一种基于划分的不平衡数据软子空间聚类新算法。所提算法提高了不平衡数据的聚类精度，在生物信息学和临床医学等领域具有一定的理论意义和实际应用价值。

关键词： 聚类分析;子空间聚类;不平衡数据;聚类精度

【Abstract】： Cluster analysis is an important research topic in data mining. It is widely used in information filtering， bioinformatics， medicine and other fields. This topic focuses on the top-down subspace clustering method. The main reason is that the current major algorithms are based on K-means or K-modes. Under the influence of uniform effects， the problem of unbalanced data The existing soft subspace algorithm cannot be effectively clustered， so a new algorithm based on partitioning unbalanced data soft subspace clustering is proposed. The proposed algorithm improves the clustering accuracy of unbalanced data， and has certain theoretical significance and practical application value in the fields of bioinformatics and clinical medicine.

【Key words】： Cluster analysis; Subspace clustering; Unbalanced data; Clustering accuracy

0  引言

数据挖掘领域的重要研究方法之一是聚类，由于聚类分析具有无监督学习性，所以在众多领域的得到应用，包括医学、生物信息、Web日志分析以及金融交易等等。本文是针对在临床上的应用，我们通常要在手术后最快的预测该病人是否可以正常愈合以便为后续的护理工作提供更好的决策支持。然而，许多临床药物产生的数据通常是不平衡的。显然这些数据是混合数据，这是我们面临的第一个问题。同时我们还发现在采集的这些混合数据中，不是每个特征对我们最后进行区分病人是否能够正常愈合都是重要的，其中有的特征是不重要的，这样一来，我们面对的第二个问题就是特征如何选择的问题。最后，在实际的临床应用中，大多数病人都是可以正常愈合的，只有少数的病人不能够正常愈合，在数据挖掘中，我们将大部分可以正常愈合的人群看做一个类，不能正常愈合的看做另外一个类，很明显两大类的数量上具有较大差异，所以我们面对的第三个问题就是类不平衡的问题。 我们将以上3个问题归纳起来称其为不平衡子空间的聚类的问题。这在临床医学应用中是非常有意义的。

子空间聚类是可以识别和生成与每个集群类相关联的一组特征（或属性）以形成依赖于集群的子空间。目前的子空间算法有两种：自下而上的和自上而下的方法。自上而下方法是在整个空间范围为每个候选聚類计算最佳子空间。实际上，这种类型的当前主要算法基于K均值或K-模式。其研究思想是在原本的算法中增加为每个属性的增加一个特征权重。这构造了目标集群类的软子空间。 许多实际应用产生的数据通常是不平衡的[2]。 反例对应于那些没有患病的人，样本量相对较大; 基于以上内容本文提出了一种“双加权”方法，称为 BWIC（ Bi- Weighting for Imbalanced data Clustering）不平衡数据软聚类算法。

1  国内外研究动态

20世纪30年代，Driver 和 Kroeber 第一次提出聚类分析的思想，并将其运用到人类学的研究领域。在之后的几年，Robert Tryon在心理学领域继续使用了聚类分析。在接下来的70年中，聚类分析方法已被广泛开发并应用于许多领域。新提出的算法对低维空间数据集的聚类具有良好的效果。随着信息时代快节奏的发展，人们更多的开始研究互联网、人脸文档等高维数据，这个时候大家发现传统的聚类算法已经没有办法较好的处理这些数据了。Aggarwal在1998年第一次提出子空间聚类之后，阐述了高维数据的尺寸冗余，局部相关性和稀疏性[1]。

在视频处理、图形分割等超高维数据问题方面，可惜的是子空间聚类不能给我们较好的结果。但是，对于处理高维数据有较好的效果主要是由于其算法的目标函数都是在欧氏距离度量的基础上展开研究的。2009年，一种基于自表示模型的稀疏子空间聚类子空间聚类算法诞生了，在之后自适应的k-means 型软子空间聚类算法出现了，它是由陈黎飞等提出的。次算法需要首先设置一些全局的关键参数，在没有考虑子空间优化问题前提下，通过新的软子空间聚类优化目标函数最小化了子空间的簇内紧凑度，同时最大化了每个簇类所在的投影子空间[3]。

2  相关工作

双加权方法可以为每个群集提供反映其重要性的权重，赋予各个属性一个特征权重，用来衡量聚类和测量属性之间的相关性。另一方面，实际数据通常与不同类型的属性混合，例如数字和分类。导致他们对这两个重量的“不平衡”贡献。与K-Means软子空间算法相比较，该算法提高了不平衡数据的聚类精度。我们可以在手术后最快的预测该病人是否可以正常愈合以便为后续的护理工作提供更好的决策支持。

2.1  属性平衡的距离度量

3  数据集和实验设置

该实验使用了五个常用的UCI数据集，表1中的Hypothyroid（甲状腺功能低下者）、Heart（心脏疾病数据）是由数值型数据和类属型数据混合组成的，而其他的三个数据集单纯只含有类属型属性，首先前提对所有数据中的所有数值型属性都预先做了[0，1]规范化处理。此次实验是对各种算法聚类复杂类型数据的性能的验证。

所有样本数据都含“不平衡”的性质，由表1看到，甲状腺功能低下者Hypothyroid的数据可以分为三组，分别是Hyperfunction超功能、Normal正常和Subnormal次正常表示），最多数据的一组有3489个样本，而最小的只有94个对象。再有Soybean数据中包含10个样本数据的有3组，然而第4各组却有18个样本，分别用D1～D4表示。还有数据集Splice里的每个对象，都是61个核苷酸序列（位点编号从-30到+ 30），将其分为三组：EI、IE和Neither，对象数分别为768、768和1656;

另外两组数据集Mushroom、Heart中，尽管各组样本个数较接近，但却有明显的正负例子的区别，Heart数据集可分为“Presence（有心脏疾病）”和Absence（无心脏疾病）”两种，Mushroom分为“Edible（可食用蘑菇）”和“Poisonous（有毒蘑菇）”两种。使用这些数据集的原因就是，在实际的临床应用中，许多临床药物产生的数据通常是不平衡的。由于这些数据是混合数据所以实验数据集这样安排就是为了解决面临的第一个问题。同时还解决了前文中提出的第三个问题，实际临床实验中，大多数病人都是可以正常愈合的，只有少数的病人不能够正常愈合，在数据挖掘中，我们将大部分可以正常愈合的人群看做一个类，不能正常愈合的看做另外一个类，很明显两大类的数量上具有较大差异。

该实验过程中使用聚类类属型数据的K-Modes算法[8-9]（以下简称为KM）为基准算法。为了增加对比性，另外选用一种较新的KM改进型算法：基于互补熵的特征加权重KM算法（以下简称为WKM），作为对比算法。

3.1  聚类结果

通过调用BWIC算法聚类每个数据集各20次，分别根据式（9）计算反映结果质量的Silhouette值，再计算平均的Silhouette值。实验结果表明（见表2）BWIC算法在五个数据集中都取得了较好的聚类结果。由于使用了局部特征加权技术，WKM算法表现出比传统的KM算法更高的性能。表2也显示，WKP算法的性能多数情况胜过MKP，其部分原因在于WKP使用了（全局）特征加权技术[7]，可以在聚类过程中识别各属性对簇类的重要性，进行子空间聚类。相较而言，由于在特征加权基础上增加了簇类权重的识别功能，BWIC算法的聚类结果显得更为准确，尤其在样本分布显著不平衡的Splice和Hypothyroid数据集上，例如，在Splice数据集上，BWIC算法的平均MacroF1指标和MicroF1指标都超出对比算法近50%。

3.2  权重计算结果

为检验BWIC算法“双加权”方法的性能，从表3可以得出BWIC算法在每个数据集学习得到的簇类权重。从表中不难发现，输出的权重值与簇的重要性相关，这样一来就解决了我们在文中前面提到的第二个特征如何选择的问题，因为在实际的临床实验中，采集的这些混合数据中，不是每个特征对我们最后进行区分病人是否能够正常愈合都是重要的，其中有的特征是不重要的，有的特征是重要的。

通过3种混合型数据聚类算法BWIC、WKP和MKP在两个约简数据集上的聚类性能指标值来看，表中的符号↓表示指标值下降的情况。如表所示， MacroF1和MicroF1两个指标值都出现了不同程度的下降。

以上结果表明，BWIC算法的“双加权”可以得到较为准确的结果，尤其是在不平衡数据子空间聚类时[11]。

4  结论

本文通过提出的新的算法-双加权方法，即给予每个簇一个反映其重要性的权重（簇权重（cluster- weight）），为衡量属性与簇类之间的相关性，给予我们每个属性一个特征权重（feature-weight）。另一方面，现实生活中的数据不可能是单一类型的，而是由数值型和类属型不同类型的属性混合组成的，导致它们对两种权重产生“不平衡”的贡献。依据在实际应用数据集上进行了实验，结果表明提出的新算法能够为不平衡数据中的簇类学习提供更准确的软子空间;与现有的软子空间算法相比，新提出的BWIC算法提高了不平衡数据的聚类精度，我们可以在手术后最快的预测该病人是否可以正常愈合以便为后续的护理工作提供更好的决策支持，未来不仅可以在临床上得到广泛的应用，在其他的病种分析中也可以得到应用，这将是非常有意义的。

参考文献

[1]AGGRAWAL C C， Data mining： The textbook， Springer， 2015.

[2]陈黎飞， 郭躬德， 姜青山， 自适应的软子空间聚类算法， 软件学报， 21（10）： 2513-2523， 2010.

[3]HUANG J Z， NG M K， RONG H， LI Z， Automated variable weighting in k-means type clustering [J]. IEEE Transactions

on Pattern Analysis and Machine Intelligence， 27（5）： 657- 668， 2005.

[4]CHEN L， WANG S， WANG K， ZHU J， Soft subspace clustering of categorical data with probabilistic distance[J]. Pattern Recognition， 51： 322-332， 2016.

[5]CAO F， JIANG J， LI D， ZHAO X. A weighting k-modes algorithm for subspace clustering of categorical data [J]. Neurocomputing， 108： 23-30， 2013.

[6]MACQUEEN J. Some methods for classification and analysis of multivariate observation[C]//Proceedings of the 5th Berkley Symposium on Mathematical Statistics and Probability， Berkeley： University of California Press， 1967： 281-297.

[7]HUANG Z， NG M. A note on k-modes clustering[J]. Journal of Classification， 20（2）： 257-261， 2003.

[8]李仁侃， 葉东毅. 粗糙K-Modes聚类算法[J]. 计算机应用， 31（1）： 97-100， 2011.

[9]梁吉业， 白亮， 曹付元. 基于新的距离度量的K-Modes 聚类算法[J]. 计算机研究与发展， 47（10）： 1749-1755， 2010.

[10]ZHOU K， YANG S. Exploring the uniform effect of FCM clustering： A data distribution perspective [J]. Knowledge- Based Systems， 96： 76-83， 2016.

[11]HE H， GARCIA E A. Learning from Imbalanced Data[J]. IEEE Transactions on Knowledge and Data Engineering， 21（9）： 1263-1284， 2009.