MS<sup>2</sup>BC-a Multi-view Space Structure-Based Clustering Algorithm

SHI Xin-rui; QIAN Yu-hua; Li Fei-jiang

doi:10.13718/j.cnki.xdzk.2020.11.007

2020 Volume 42 Issue 11

Article Contents

Previous Article Next Article

SHI Xin-rui, QIAN Yu-hua, Li Fei-jiang. MS2BC-a Multi-view Space Structure-Based Clustering Algorithm[J]. Journal of Southwest University Natural Science Edition, 2020, 42(11): 59-67. doi: 10.13718/j.cnki.xdzk.2020.11.007

Citation:

SHI Xin-rui, QIAN Yu-hua, Li Fei-jiang. MS²BC-a Multi-view Space Structure-Based Clustering Algorithm[J]. Journal of Southwest University Natural Science Edition, 2020, 42(11): 59-67. doi: 10.13718/j.cnki.xdzk.2020.11.007

MS²BC-a Multi-view Space Structure-Based Clustering Algorithm

1.
Institute of Big Data Science and Industry, Shanxi University, Taiyuan 030006, China
2.
Key Laboratory of Computational Intelligence and Chinese Information Processing, Ministry of Education(Shanxi University), Taiyuan 030006, China
3.
School of Computer and Information Technology, Taiyuan 030006, China

More Information

Received Date: 14/10/2020
Available Online: 20/11/2020
MSC: TP391

Abstract

Clustering analysis is an important task in the field of machine learning and data mining. In recent years, a large number of clustering algorithms have been proposed and successfully used in many fields. However, the complex development of data at this stage has brought great challenges to the existing clustering algorithms, in which the rapid increasing number of potential clusters is very representative. To address this problem, a multi-view space structure-based clustering method (MS²BC) is proposed in this paper. Space structure is a data representation method that can maintain the structure of data clusters and provide richer measurement information. Based on the space structure representation method and the bagging feature sampling technology, this paper constructs and integrates the space structure of the data from multiple views, and uses the integrated space structure representation to complete the clustering. Finally, the superiority of this method over other representative clustering methods in clustering performance is verified based on 10 real data.
- clustering analysis,
- multi-cluster,
- space structure,
- clustering ensemble,
- data mining

References

[1]	LECUN Y, BENGIO Y, HINTON G. Deep Learning [J]. Nature, 2015, 521(7553): 436-444. doi: 10.1038/nature14539 CrossRef Google Scholar
[2]	XU D K, TIAN Y J. A Comprehensive Survey of Clustering Algorithms [J]. Annals of Data Science, 2015, 2(2): 165-193. doi: 10.1007/s40745-015-0040-1 CrossRef Google Scholar
[3]	ZHENG L, YANG Y, TIAN Q. SIFT Meets CNN: a Decade Survey of Instance Retrieval [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2018, 40(5): 1224-1244. doi: 10.1109/TPAMI.2017.2709749 CrossRef Google Scholar
[4]	ANNUNZIATA R, SAGONAS C, CALI J. Jointly Aligning Millions of Images with Deep Penalised Reconstruction Congealing [EB/OL]. 2019: arXiv: 1908. 04130 [cs. CV]. https://arxiv.org/abs/1908.04130. Google Scholar
[5]	LUAN Y, LI H. Clustering of Time-course Gene Expression Data Using a Mixed-effects Model with B-splines [J]. Bioinformatics, 2003, 19(4): 474-482. doi: 10.1093/bioinformatics/btg014 CrossRef Google Scholar
[6]	DHILLON I S, MODHA D S. Concept Decompositions for Large Sparse Text Data Using Clustering [J]. Machine Learning, 2001, 42(1/2): 1-31. Google Scholar
[7]	LI Z C, LIU J, YANG Y, et al. Clustering-Guided Sparse Structural Learning for Unsupervised Feature Selection [J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(9): 2138-2150. doi: 10.1109/TKDE.2013.65 CrossRef Google Scholar
[8]	ERHAN D, BENGIO Y, COURVILLE A, et al. Why Does Unsupervised Pre-training Help Deep Learning? [J]. Journal of Machine Learning Research, 2010, 11(3): 625-660. Google Scholar
[9]	MACQUEEN J B. Some methods for classification and analysis of multivariate observations [C] // Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. California: University of California Press, 1967. Google Scholar
[10]	PARK H S, JUN C H. A Simple and Fast Algorithm for K-medoids Clustering [J]. Expert Systems With Applications, 2009, 36(2): 3336-3341. doi: 10.1016/j.eswa.2008.01.039 CrossRef Google Scholar
[11]	KAUFMAN L, ROUSSEEUW P J. Partitioning around Medoids (Program PAM) [M] //Finding Groups in Data. Hoboken: John Wiley & Sons, 2008: 68-125. Google Scholar
[12]	SARLE W S, KAUFMAN L, ROUSSEEUW P J. Finding Groups in Data: an Introduction to Cluster Analysis [J]. Journal of the American Statistical Association, 1991, 86(415): 830. Google Scholar
[13]	ZHANG T, RAMAKRISHNAN R, LIVNY M. BIRCH: an Efficient Data Clustering Method for very Large Databases [J]. ACM SIGMOD Record, 1999, 25(2): 15-34. Google Scholar
[14]	GUHA S, RASTOGI R, SHIM K. Cure: an Efficient Clustering Algorithm for Large Databases [J]. Information Systems, 2001, 26(1): 35-58. Google Scholar
[15]	GUHA S, RASTOGI R, SHIM K. Rock: a Robust Clustering Algorithm for Categorical Attributes [J]. Information Systems, 2000, 25(5): 345-366. doi: 10.1016/S0306-4379(00)00022-3 CrossRef Google Scholar
[16]	BEZDEK J C, EHRLICH R, FULL W. FCM: The Fuzzy C-means Clustering Algorithm [J]. Computers & Geosciences, 1984, 10(2-3): 191-203. Google Scholar
[17]	DAVE R N, BHASWAN K. Adaptive Fuzzy C-shells Clustering and Detection of Ellipses [J]. IEEE Transactions on Neural Networks, 1992, 3(5): 643-662. doi: 10.1109/72.159055 CrossRef Google Scholar
[18]	YAGER R R, FILEV D P. Approximate Clustering via the Mountain Method [J]. IEEE Transactions on Systems, Man, and Cybernetics, 1994, 24(8): 1279-1284. doi: 10.1109/21.299710 CrossRef Google Scholar
[19]	XU X, ESTER M, KRIEGEL H P, et al. A Distribution-Based Clustering Algorithm for Mining in Large Spatial Databases [C] // IEEE International Conference on Data Engineering. New York: IEEE Press, 1998. Google Scholar
[20]	Rasmussen C E. The Infinite Hidden Markov Model [M] //Advances in Neural Information Processing Systems 14. Massachusetts: The MIT Press, 2002. Google Scholar
[21]	ESTER M. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise [C] // Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining. California: AAAI Press, 1996. Google Scholar
[22]	ANKERST M, BREUNIG M M, KRIEGEL H P, et al. OPTICS: Ordering Points to Identify the Clustering Structure [C] //Proceedings of the 1999 ACM SIGMOD international conference on Management of data - SIGMOD′99. May 31-June 3, 1999. Philadelphia, Pennsylvania, USA. New York: ACM Press, 1999. Google Scholar
[23]	COMANICIU D, MEER P. Mean Shift: a Robust Approach Toward Feature Space Analysis [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(5): 603-619. doi: 10.1109/34.1000236 CrossRef Google Scholar
[24]	SCHÖLKOPF B, SMOLA A, MVLLER K R. Nonlinear Component Analysis as a Kernel Eigenvalue Problem [J]. Neural Computation, 1998, 10(5): 1299-1319. doi: 10.1162/089976698300017467 CrossRef Google Scholar
[25]	Macdonald D, Fyfe C. The kernel self-organising map [C] // International Conference on Knowledge-based Intelligent Engineering Systems & Allied Technologies. IEEE, 2000. Google Scholar
[26]	BENHUR A, HORN D, SIEGELMANN H T, et al. Support Vector Clustering [J]. Journal of Machine Learning Research, 2002, 2(2): 125-137. Google Scholar
[27]	Xu L, Neufeld J, Larson B, et al. Maximum Margin Clustering [C] // Neural Information Processing Systems 1. Massachusetts: MIT Press, 2004: 1537-1544. Google Scholar
[28]	LI F J, QIAN Y H, WANG J T, et al. Clustering Ensemble Based on Sample's Stability [J]. Artificial Intelligence, 2019, 273: 37-55. doi: 10.1016/j.artint.2018.12.007 CrossRef Google Scholar
[29]	FREY B J, DUECK D. Clustering by Passing Messages between Data Points [J]. Science, 2007, 315(5814): 972-976. doi: 10.1126/science.1136800 CrossRef Google Scholar
[30]	RODRIGUEZ A, LAIO A. Machine Learning. Clustering by Fast Search and Find of Density Peaks [J]. Science, 2014, 344(6191): 1492-1496. doi: 10.1126/science.1242072 CrossRef Google Scholar
[31]	BONNIER B. Random Sequential Adsorption Ofk-mers on a Square Lattice: The Largekregime [J]. Physical Review E, 1996, 54(1): 974-976. doi: 10.1103/PhysRevE.54.974 CrossRef Google Scholar
[32]	Chitta R, Jain A K, Jin R. Sparse Kernel Clustering of Massive High-Dimensional Data sets with Large Number of Clusters [C] // Proceedings of the 8th Workshop on Ph. D. Workshop in Information and Knowledge Management 2015. New York: ACM Press, 2015. Google Scholar
[33]	CURTIN R R. A Dual-Tree Algorithm for Fast K-means Clustering with Large K [M] //Proceedings of the 2017 SIAM International Conference on Data Mining. Philadelphia, PA: Society for Industrial and Applied Mathematics, 2017: 300-308. Google Scholar
[34]	QIAN Y H, LI F J, LIANG J Y, et al. Space Structure and Clustering of Categorical Data [J]. IEEE Transactions on Neural Networks and Learning Systems, 2016, 27(10): 2047-2059. doi: 10.1109/TNNLS.2015.2451151 CrossRef Google Scholar
[35]	CAO J, ZHENG Q, WENG N, et al. Low Dimensional Representation of Space Structure and Clustering of Categorical Data [C] //IEEE International Conference on Ubiquitous Computing. New York: IEEE Press, 2018: 1079-1086. Google Scholar
[36]	王齐, 钱宇华, 李飞江.基于空间结构的符号数据仿射传播算法[J].模式识别与人工智能, 2016, 29(12): 1132-1139. Google Scholar
[37]	HUANG D, WANG C D, WU J S, et al. Ultra-Scalable Spectral Clustering and Ensemble Clustering [J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(6): 1212-1226. doi: 10.1109/TKDE.2019.2903410 CrossRef Google Scholar
[38]	FAN Z Y, JIANG J, WENG S Q, et al. Adaptive Density Distribution Inspired Affinity Propagation Clustering [J]. Neural Computing and Applications, 2019, 31(S1): 435-445. doi: 10.1007/s00521-017-3024-6 CrossRef Google Scholar

Access History

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(2) / Tables(6)

Export Citation

PDF

XML

Article Metrics

Article views(493) PDF downloads(82) Cited by(0)

Access History

Other Articles By Authors

on this site
on Google Scholar

HTML

无监督学习^[1]是机器学习中的一项重要技术，其中聚类分析与应用^[2-30]在近年来得到了广泛关注.

传统的聚类方法大致可以分为：基于划分的聚类算法^[9-12]、基于模糊理论的聚类算法^[16-20]、基于密度的聚类算法^[21-23]等.除此之外，受传统聚类算法的启发，为完成更广泛的任务，越来越多的新颖的聚类算法被提出^[24-30].但以上算法在解决超多类聚类问题时却并不理想^[31-33].

文献[34]提出了空间结构表示框架，可有效应对符号型数据空间结构模糊的问题，并应用于符号数据聚类问题中^[35-36].基于空间结构的表示方法将原始符号型数据映射到一个概率表示空间，在保持原有类结构信息的前提下，该方法提供了更加丰富的测度信息，从而使原始符号数据的类结构信息更加清晰.借助该思想，本文提出了一种多角度空间结构的数据聚类算法，从多个角度构建数据的空间结构，以期更全面地识别数据空间中存在的类结构，从而应对多类簇数据聚类问题.该方法利用特征抽样从多个视角刻画原始数据集，然后构建不同视角下的空间结构表示，再集成这些不同视角下的数据表示得到一个统一的表示矩阵，最后利用该矩阵完成聚类.

本文的主要贡献包括3个方面：

1) 多角度空间结构表示方法.本文提出了一种从多个角度对原始数据集进行空间结构表示的方法，以更加准确地识别复杂的类簇分布结构；

2) 多角度空间结构聚类方法.本文提出多角度空间结构聚类算法框架，集成多个视角所形成的空间结构来对数据进行更有效地聚类；

3) 本文在10个真实数据集上验证了多角度空间结构聚类算法相较于传统聚类算法的优越性.

1. 空间结构表示方法

本章内容将分别介绍符号型数据和数值型数据的空间结构表示方法.

1.1. 符号型数据的空间结构表示方法

符号型数据是由一组有限和无序的特征向量来表示，所以无法像数值型数据那样直接度量样本间的相似度或距离，且难以准确刻画符号型数据的空间分布结构，这导致许多聚类算法无法处理符号型数据.

为更清晰地刻画符号型数据的空间结构，文献[34]基于样本间相似性概率提出了一种空间结构表示方法，具体如下：

假设U={x₁，x₂，…，x_n}为数据集合，A={a₁，a₂，…，a_m}为特征集合，如果A中的特征均为符号型特征，则数据集U为符号型数据集.

假设T=(U，A)为符号数据集，其中U为样本集，A为属性集，表 1给出了一个表示示例.

样本x_i和样本x_j的相似性概率为：

其中：α_l(x)为数据x的第l个特征值，

通过计算两两样本间的相似性概率，可得到符号型数据的空间结构表示矩阵为：S_C=[p_ij]_n×n，在符号型数据的空间结构中，一个样本的特征为{b_i=x_i，1≤i≤n}，表 2给出了符号型数据的空间表示示例.

空间结构表示矩阵可以将符号型数据映射到一个欧式空间.

1.2. 数值型数据的空间结构表示方法

虽然空间结构表示方法最初是针对符号型数据提出，但该方法很容易扩展至处理数值型数据任务.

对于数值型特征a_l，样本x_i和样本x_j相似的概率为：

其中$ \max \left( {{\boldsymbol{a}_l}} \right) = \mathop {\max }\limits_{1 \le i \le n} \left\{ {{\boldsymbol{a}_l}\left( {{\boldsymbol{x}_i}} \right)} \right\}, \min \left( {{\boldsymbol{a}_l}} \right) = \mathop {\min }\limits_{1 \le i \le n} \left\{ {{\boldsymbol{a}_l}\left( {{\boldsymbol{a}_i}} \right)} \right\} $.基于公式(3)，样本x_i和样本x_j相似的概率为：

通过计算两两样本间的相似性概率，可得到数值型数据的空间结构表示矩阵为S_N=[p_ij]_n×n.

本文借助上述空间结构表示方法的思想，提出了一种多角度空间结构聚类算法，通过从多个角度构建原始数据集的空间结构，使得类簇结构信息更加清晰准确，进而解决数值型数据的超多类聚类问题.

2. 多角度空间结构

2.1. 多角度数据表示

为从多个角度刻画原始数据集，本文采用装袋(Bagging)算法.装袋算法被广泛地应用于监督学习任务中，通过有放回地抽样数据集，训练多个模型，这样可以降低模型泛化误差，其采用的策略为模型平均，即使用训练好的若干学习器来对新的未知样本预测.这种算法是一种集成方法，通过集成多个弱学习器来提高模型的学习性能.

在这种集成思想的启发下，本文通过对原始数据集的特征进行有放回地抽样，以从多个不同的视角来刻画原始数据.这样可以从不同的角度来描述一个样本，以期为后续揭示更清晰的类簇分布信息奠定基础.令U={x₁，x₂，…，x_n}为数据集合，A={a₁，a₂，…，a_m}为特征集合，通过对特征集A进行有放回采样可得到新视角下的特征集描述B={b₁，b₂，…，b_m}以及新视角下的数据集合U^′={x₁^′，x₂^′，…，x_n^′}.

本文所提算法每次随机有放回地抽取与原始数据集相同维数的特征，形成新视角下的数据集.为进一步提升特征对原始数据结构的表达能力，本文在每次特征抽取完成之后，均对新的数据进行特征提取.另外，当原始数据集的特征较多时，每次形成的数据也具有较高的维度，会导致存储空间的浪费以及降低计算效率.因此，特征提取在减少存储空间的同时提高了计算效率.

本文所提算法采用PCA降维技术来对数据集进行降维处理.PCA是一种被广泛使用的数据降维算法.其主要思想是将数据从n维输入空间映射到k维特征空间.即将每个n维数据点通过映射转换成另一个数据点.其工作原理是，从原始数据空间中依次找出相互正交的坐标方向.第一个坐标方向选择数据集中方差最大的维度所在的方向，第二个坐标方向选择与第一个方向呈正交的平面中与方差最大的坐标方向，第三个坐标方向选择与前两个坐标方向呈正交的平面中方差最大的坐标方向，依次类推.最后会发现大部分数据基本集中在k个坐标方向中，所以后面的坐标方向可直接忽略，从而达到降维目的.对于数据矩阵U_n×d^′，PCA降维流程如下：

1) 求U_n×d^′的协方差矩阵C_n×n=COV(U^′)；

2) 求解协方差矩阵的特征值和特征向量；

3) 选取最大的k个特征值所对应的特征向量组成的矩阵P_d×k；

4) 计算B_n×k=X_n×dP_d×k；

将B视为一个视角下的数据集.通过多次对特征的重抽样和提取，可得到多个视角下的数据集描述.

2.2. 多角度空间结构融合

为了可以提供更清晰的类簇分布结构信息，本文结合数据的空间结构表示和多角度表示提出一种多角度空间结构表示方法.

样本间距离度量可以反应更加精细的结构信息，由此本文通过集成多个视角下的空间结构度量信息来构建统一地、更精细的数据表示，同时将多角度数据映射到同一个欧式空间中，便于之后的聚类分析.

首先，定义一个单一视角下的数据空间结构表示矩阵：

假设$ B' = \left\{ {{{\boldsymbol{x}'}_1}, {{\boldsymbol{x}'}_2}, \cdots , {{\boldsymbol{x}'}_n}} \right\} $为第t个视角下的数据集合，基于公式(1)可求得B^′的空间结构表示$ \boldsymbol{S}' = {\left[ {{{s'}_{ij}}} \right]_{n \times n}} $，其中$ {s'_{ij}} = p\left( {{{\boldsymbol{x}'}_i}, {{\boldsymbol{x}'}_j}} \right) $.

由空间结构的构造方法易知，空间结构表示的数据由规范化的特征描述，数据存在于第一象限，且取值范围区间为[0, 1].另外，一个数据在多个视角下的空间结构表示的特征维数相同，均为样本个数n.因此，可通过对应位置求平均的方法对一个数据的多个空间结构表示进行融合，即：

至此完成了原始数据的多角度空间结构的表示.

3. 多角度空间结构

基于数据的多角度空间结构表示方法，提出了一个多角度空间结构聚类算法MS²BC(multi-viewspacestructure-basedclustering).该方法一方面借助了空间结构表示方法在数据类结构清晰化上的优势，另一方面从多个角度刻画数据的空间结构.因此，当类簇数量增多时，该方法有望缓解直接在原始数据上聚类难以识别类簇结构的问题，进而提升聚类性能.具体步骤如下：

1) 对特征进行与原始特征空间维数相等的装袋算法抽样，得到映射到多个视角的数据集合；

2) 对每个视角下的数据集合进行空间结构表示，再集成所有的结构表示信息；

3) 对集成后的空间结构表示进行聚类，获得数据集合的类簇划分结果.

对于步骤3)，可以采用不同的聚类方法对空间结构表示进行聚类.本文采用的是谱聚类算法.

本小节给出本文所提算法的整体算法流程，伪代码描述如下：

算法整体分为2个阶段：第一阶段是构造多视角空间结构表示；第二阶段基于该空间结构表示聚类.从算法框架可以看出，本文算法在第一阶段构造多视角空间结构表示时，循环m次，每轮循环将执行特征装袋算法、PCA降维以及构建空间结构表示矩阵，其中构建空间结构表示矩阵的时间复杂度为O(n²).因此，算法第一阶段的时间复杂度为O(m(d+O(PCA)+n²))，其中m表示循环次数，d表示数据维数，n代表样本个数.算法的第二阶段利用谱聚类对第一阶段得到的空间结构表示进行聚类.因此第二阶段的时间复杂度为O(SC).综上所述，本文所提的算法的时间复杂度为O(m(d+O(PCA))+n²+O(SC)).

此外，本文所提算法可并行性较强，且易扩展至处理大规模数据.首先，多角度构建空间结构部分具有天然的可并行性，不同视角下构建空间结构可分布式运行；其次，在构造空间结构时可选取具有代表性的样本进行度量，构造空间结构表示矩阵S_[n×n^′](其中n^′＜n为代表性样本数)，从而提升该部分的运行速率；最后，算法第二阶段所采用的谱聚类可借鉴现有快速算法来加速聚类过程，如U-SPEC^[37].

5. 总结和未来工作展望

大数据背景下的聚类任务中，类簇数量剧增，给传统聚类方法带来了巨大挑战.针对该问题，本文提出了一种多角度空间结构聚类算法，通过集成数据的多个视角空间结构来加强算法识别类簇的能力，进而提升聚类性能.从实验结果的对比中可以看出，相较于传统聚类算法，本文所提算法取得了较高性能指标.未来我们重点研究本文所提算法的快速算法和并行算法，从而有效应对大规模超多类数据的聚类问题.

Figure (2) Table (6) Reference (38)

Name
	Name cannot be empty!
E-mail
	Mailbox cannot be empty! Mailbox cannot be empty!
Telephone
	Mobile number cannot be empty! Please enter a valid mobile number!
Title

Content
Verification Code

Message Board

MS²BC-a Multi-view Space Structure-Based Clustering Algorithm