Improved SUBCLU subspace clustering algorithm for high dimensional data

doi:10.3778/j.issn.1002-8331.1609-0111

Computer Engineering and Applications ›› 2017, Vol. 53 ›› Issue (14): 130-137.DOI: 10.3778/j.issn.1002-8331.1609-0111

Previous Articles Next Articles

Improved SUBCLU subspace clustering algorithm for high dimensional data

LUO Jing, QIAN Xuezhong, HAN Lizhao, SONG Wei

Engineering Research Center of Internet of Things Technology Applications Ministry of Education, School of Internet of Things Engineering, Jiangnan University, Wuxi, Jiangsu 214122, China

Online:2017-07-15 Published:2017-08-01

一种改进的SUBCLU高维子空间聚类算法

罗靖，钱雪忠，韩利钊，宋威

江南大学物联网工程学院物联网技术应用教育部工程研究中心，江苏无锡 214122

Abstract

Abstract: SUBCLU algorithm is a subspace clustering algorithm for high dimensional data. However, it produces a lot of intermediate clusters during the iteration of finding maximum interesting subspace clusters by using bottom-up search strategy. A large amount of time is consumed in the process of generating these intermediate clusters. Focus on this problem, algorithm BDFS-SUBCLU （the deep-first search with back-trace-based SUBCLU） is proposed. To avoid producing the intermediate clusters and reduce the time complexity, this algorithm uses deep-first search with back-trace to find maximum interesting subspace clusters. To avoid that the adjacent clusters affected by those special data points merge to one, BDFS-SUBCLU constraints the key point in every subspace. The experiments conducted on synthetic datasets and real datasets show that BDFS-SUBCLU improves efficiency and accuracy compared to SUBCLU.

Key words: SUBCLU, subspace clustering, high dimensional data, interesting subspace

摘要： SUBCLU高维子空间聚类算法在自底向上搜索最大兴趣子空间类的过程中不断迭代产生中间类，这些中间类的产生消耗了大量时间，针对这一问题，提出改进算法BDFS-SUBCLU，采用一种带回溯的深度优先搜索策略来挖掘最大兴趣子空间中的类，通过这种策略避免了中间类的产生，降低了算法的时间复杂度。同时BDFS-SUBCLU算法在子空间中对核心点增加一种约束，通过这个约束条件在一定程度上避免了聚类过程中相邻的类由于特殊的数据点合为一类的情况。在仿真数据集和真实数据集上的实验结果表明BDFS-SUBCLU算法与SUBCLU算法相比，效率和准确性均有所提高。

关键词: SUBCLU, 子空间聚类, 高维数据, 兴趣子空间

LUO Jing, QIAN Xuezhong, HAN Lizhao, SONG Wei. Improved SUBCLU subspace clustering algorithm for high dimensional data[J]. Computer Engineering and Applications, 2017, 53(14): 130-137.

罗靖，钱雪忠，韩利钊，宋威. 一种改进的SUBCLU高维子空间聚类算法[J]. 计算机工程与应用, 2017, 53(14): 130-137.

[1]	WANG Yusi, LU Deyang, LI Haiyang. Sparse Subspace Clustering Method Based on Fractional Function Constraints [J]. Computer Engineering and Applications, 2020, 56(7): 39-47.
[2]	ZHENG Yi, MA Yingcang, YANG Xiaofei, XU Qiuxia. Sparse Subspace Clustering Based on [k]-Nearest Neighbors and Local Similarity [J]. Computer Engineering and Applications, 2020, 56(4): 99-108.
[3]	ZHU Dan, CHEN Xiaohong, WU Qingyuan, LI Shunming. Subspace Clustering Induced by Adaptive Graph Learning [J]. Computer Engineering and Applications, 2020, 56(21): 30-37.
[4]	GUO Sheng, ZHONG Zhaoman, LI Cunhua. Multi-view Subspace Clustering Network Based on Deep Autoencoder [J]. Computer Engineering and Applications, 2020, 56(17): 60-68.
[5]	LIU Wenfen, MU Xiaodong, HUANG Yuehua. Anomaly Detection Method Based on Multi-resolution Grid [J]. Computer Engineering and Applications, 2020, 56(17): 78-85.
[6]	LI Dan. Structured Weighted Correlation Adaptive Subspace Clustering [J]. Computer Engineering and Applications, 2020, 56(13): 137-142.
[7]	DENG Tingquan, LIU Jinyan, WANG Ning. Locally linear embedding method for high dimensional data outlier detection [J]. Computer Engineering and Applications, 2018, 54(6): 115-122.
[8]	XIE Hao1, ZHAO Zhigang1, LV Huixian2, LIU Xinyue1, LIU Chengshi1, DONG Xiaochen1. Nonnegative local constrained low rank subspace clustering algorithm [J]. Computer Engineering and Applications, 2018, 54(23): 137-143.
[9]	TIAN Shuai, CHEN Yi. A survey of high dimensional data visual analysis methods based on subspace clustering [J]. Computer Engineering and Applications, 2018, 54(13): 19-26.
[10]	ZHANG Hong, WANG Weiwei, KONG Shengjiang. Structured sparse and low rank subspace clustering [J]. Computer Engineering and Applications, 2017, 53(24): 23-29.
[11]	QIU Yunfei, DI Longjuan. Soft subspace clustering algorithm based on self-adaption of intercluster distance [J]. Computer Engineering and Applications, 2016, 52(21): 88-93.
[12]	HUANG Hongyan, HU Jichao. Application of subspace clustering in intrusion feature selection [J]. Computer Engineering and Applications, 2012, 48(8): 96-98.
[13]	WU Sen，WANG Jing，TAN Yisong. Improved CABOSFV clustering considering data sort [J]. Computer Engineering and Applications, 2011, 47(34): 127-129.
[14]	WANG Bao-wen¹，YAN Jun-mei¹，LIU Wen-yuan¹，SHI Yan². High dimensional datas fuzzy clustering based on genetic algorithm [J]. Computer Engineering and Applications, 2007, 43(16): 191-192.

Improved SUBCLU subspace clustering algorithm for high dimensional data

一种改进的SUBCLU高维子空间聚类算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 14

Recommended Articles

Metrics