引用本文

李向丽, 曹晓锋, 邱保志. 基于矩阵模型的高维聚类边界模式发现. 自动化学报, 2017, 43(11): 1962-1972. doi: 10.16383/j.aas.2017.c160443

LI Xiang-Li, CAO Xiao-Feng, QIU Bao-Zhi. Clustering Boundary Pattern Discovery for High Dimensional Space Base on Matrix Model. ACTA AUTOMATICA SINICA, 2017, 43(11): 1962-1972. doi: 10.16383/j.aas.2017.c160443

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.2017.c160443

关键词

高维空间，聚类边界，矩阵模型，k近邻，对称率 

摘要

流形学习关注于寻找合适的嵌入方式将高维空间映射至低维空间，但映射子空间依然可能具有较高的维度，难以解决高维空间的数据挖掘任务.本文建立一种简单的矩阵模型判断数据点k近邻空间关于该点的对称性，并使用对称率进行边界提取，提出一种基于矩阵模型的高维聚类边界检测技术（Clustering boundary detection based on matrix model，MMC）.该模型构造简单、直接、易于理解和使用.理论分析以及在人工合成和真实数据集的实验结果表明MMC算法能够有效地检测出低维和高维空间的聚类边界.

文章导读

数据挖掘是从大量未知数据中提取有价值的潜在知识的过程, 这些知识有助于人们更好地认识和理解数据.聚类分析[1-5]旨在挖掘数据内部的非平凡规律, 提取空间中自然存在的模式, 在图像分割[6-7]、生物学[8]和医学[9]等领域获得了广泛应用.与聚类不同, 聚类边界是另一种新颖的具有重要价值的特殊模式.这些数据分布于聚类的边缘, 具有明确的类归属, 但又与类内其他数据存在一定差异.从认知事物的角度而言, 聚类边界代表着那些类归属明确但又具备脱离本类属性特征的一类特殊数据.例如, 在医学检测中, 正常人群的聚类边界代表那些携带病毒但未患病的人群; 手写体图像的聚类边界代表着那些异于常态和不易识别的手写体图像.随着聚类边界应用领域的不断扩大, 必然要求对聚类边界提取技术进行深入的研究.

现有的聚类和聚类边界检测技术普遍采用构造几何模型的方式对数据空间进行合理分割, 以获取空间数据的有效模式结构, 而良好的几何理论为这些研究提供了坚实基础.但随着应用领域的不断扩展, 数据的维度迅速增长, 达到了千维、万维甚至更高, 而低维几何性质在高维空间[10-11]内的时间性能却大幅下降.因此, 如何打开高维数据的``海岸围墙"成为数据挖掘研究者亟待解决的问题, 更是聚类边界研究者所面临的严峻挑战.

本文第1节介绍了聚类边界的相关工作; 第2节介绍了矩阵模型, 提出了边界检测算法; 第3节是本文的实验部分, 包括在人工合成数据集和真实数据集的实验对比和分析; 第4节对算法的时间复杂度和参数分析; 在第5节给出了本文的结论.

图 1  不同算法在人工合成数据集上的最佳聚类边界检测结果

图 2  手写体3的聚类边界和聚类中心

图 3  人脸簇FC1

本文将高维空间转换为多个矩阵, 使用矩阵模型进行理论分析构造, 提出了检测高维空间聚类边界的MMC算法.该算法构造简单, 易于理解, 能够有效地提取低维和高维空间中聚类的边界.理论分析和实验结果验证了该算法的有效性.未来的研究工作集中体现在以下几个方面:

1) 由于$k$近邻空间的计算开销较大, 如何降低算法的时间复杂度是一个重要问题.

2) 减少参数个数甚至无参数技术是当前亟待解决的问题之一.

3) 随着领域的扩展、聚类边界问题的多样化和复杂化, 需要进一步研究复杂结构数据空间的边界检测技术.

作者简介

李向丽

郑州大学信息工程学院副教授.主要研究方向为计算机网络, 数据挖掘.E-mail:iexlli@zzu.edu.cn

邱保志  

郑州大学信息工程学院教授.主要研究方向为数据库, 先进智能系统, 数据挖掘.E-mail:iebzqiu@zzu.edu.cn

曹晓锋  

郑州大学信息工程学院硕士研究生.主要研究方向为模式识别和数据挖掘.本文通信作者.E-mail:18739920964@163.com