一种基于极大熵的快速无监督线性降维方法*王继奎1, 杨正国1, 刘学文1, 易纪海1, 李 冰1, 聂飞平21(兰州财经大学 信息工程学院, 甘肃 兰州730020)2(西北工业大学 光学影像分析与学习中心, 陕西 西安 710072)通信作者: 聂飞平, feipingnie@gmail.com摘　要: 现实世界中高维数据无处不在, 然而在高维数据中往往存在大量的冗余和噪声信息, 这导致很多传统聚类算法在对高维数据聚类时不能获得很好的性能. 实践中发现高维数据的类簇结构往往嵌入在较低维的子空间中.因而, 降维成为挖掘高维数据类簇结构的关键技术. 在众多降维方法中, 基于图的降维方法是研究的热点. 然而, 大部分基于图的降维算法存在以下两个问题: (1) 需要计算或者学习邻接图, 计算复杂度高; (2) 降维的过程中没有考虑降维后的用途. 针对这两个问题, 提出了一种基于极大熵的快速无监督降维算法-MEDR. MEDR 算法融合线性投影和极大熵聚类模型, 通过一种有效的迭代优化算法寻找高维数据嵌入在低维子空间的潜在最优类簇结构.MEDR 算法不需事先输入邻接图, 具有样本个数的线性时间复杂度. 在真实数据集上的实验结果表明, 与传统的降维方法相比, MEDR 算法能够找到更好的将高维数据投影到低维子空间的投影矩阵, 使投影后的数据有利于聚类.关键词: 无监督学习; 线性降维; 邻接图; 聚类; 极大熵中图法分类号: TP18中文引用格式: 王继奎, 杨正国, 刘学文, 易纪海, 李冰, 聂飞平. 一种基于极大熵的快速无监督线性降维方法. 软件学报.http://www.jos.org.cn/1000-9825/6400.htm英文引用格式: Wang JK, Yang ZG, Liu XW, Yi JH, Li B, Nie FP. Fast Unsupervised Dimension Reduction Method Based onMaximum Entropy. Ruan Jian Xue Bao/Journal of Software (in Chinese). http://www.jos.org.cn/1000-9825/6400.htmFast Unsupervised Dimension Reduction Method Based on Maximum EntropyWANG Ji-Kui1, YANG Zheng-Guo1, LIU Xue-Wen1, YI Ji-Hai1, LI Bing1, NIE Fei-Ping21(College of Information Engineering, Lanzhou University of Finance and Economics, Lanzhou 730020, China)2(Center for Optical Imagery Analysis and Learning (OPTIMAL), Northwestern Polytechnical University, Xi’an 710072, China)Abstract: High-dimensional data is widely adopted in the real world. However, there is usually plenty of redundant and noisy informationexisting in high-dimensional data, which accounts for the poor performance of many traditional clustering algorithms when clustering highdimensionaldata. In practice, it is found that the cluster structure of high-dimensional data is often embedded in the lower dimensionalsubspace. Therefore, dimension reduction becomes the key technology of mining high-dimensional data. Among many dimension reductionmethods, graph-based method becomes a research hotspot. However, most graph-based dimension reduction algorithms suffer from thefollowing two problems: (1) most of the graph-based dimension reduction algorithms need to calculate or learn adjacency graphs, whichhave high computational complexity; (2) the purpose of dimension reduction is not considered in the process of dimension reduction. Toaddress the problem, a fast unsupervised dimension reduction algorithm is proposed based on the maximum entropy-MEDR, whichcombines linear projection and the maximum entropy clustering model to find the potential optimal cluster structure of high-dimensionaldata embedded in low-dimensional subspace through an effective iterative optimization algorithm. The MEDR algorithm does not need theadjacency graph as an input in advance, and has linear time complexity of input data scale. A large number of experimental results on realdatasets show that the MEDR algorithm can find a better projection matrix to project high-dimensional data into low-dimensional subspacecompared with the traditional dimensionality reduction method, so that the projected data is conducive to clustering analysis.* 基金项目: 国家自然科学基金 (61772427, 11801345); 甘肃省高等学校创新能力提升项目(2019B-97); 兰州财经大学校级重点项目(Lzufe2020B-0010, Lzufe2020B-011)收稿时间: 2021-02-22; 修改时间: 2021-05-19; 采用时间: 2021-06-16软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cnJournal of Software [doi: 10.13328/j.cnki.jos.006400] http://www.jos.org.cn©中国科学院软件研究所版权所有. Tel: +86-10-62562563网络首发时间：2022-11-15 09:33:15网络首发地址：https://kns.cnki.net/kcms/detail/11.2560.TP.20221113.1126.006.htmlKey words: unsupervised learning; dimension reduction; adjacency graph; clustering; maximum entropy随着科技的发展, 涌现出越来越多的高维数据. 传统的机器学习算法在面对高维数据时存在很多问题, 比如计算复杂度高、样本采样密度过于稀疏导致距离计算困难等. 然而, 高维数据有意义的类簇结构往往嵌入在低维子空间中. 为了寻找高维数据嵌入在低维空间的类簇结构, 研究者们提出了很多降维方法. 这些降维方法主要包括无监督降维、半监督降维和有监督降维3 种. 主成分分析(principal component analysis, PCA)[1]是一种经典的无监督线性投影降维方法, 因其速度快、适用于不同的场景而被广泛使用. 但是PCA 对异常点敏感, 选择投影后数据全局方差最大的投影方向, 忽视了不同类别数据的分布情况, 有时候效果不佳. 为克服这些问题, 研究者们在PCA 的基础上提出了一系列改进算法[2−5]. 随后, 研究人员提出了局部保留投影算法(locality preserving projection, LPP)[6],LPP 算法是基于邻接图的线性降维算法, 其基本思想是使降维前后数据的近邻关系得到保持. 在LPP 的基础上,研究人员进一步开发了系列算法, 如NPE[7]、GoLPP[8]、JGOPL[9]、DGLPGE[10]和AgLPP[11]等. 无监督降维算法AutoEncoder[12]利用编码、解码技术, 最小化重构误差, 使用中间隐层作为样本的抽象表示进行降维.基于PCA 的系列算法和基于LPP 的系列算法都是线性降维算法, 不适用于流形数据. 为了挖掘流形数据嵌入在低维子空间中的类簇结构, 研究人员提出了系列流形学习降维算法, 比如Locally Linear Embedding[13,14]、ISOMAP[15]、RSpLPP [16]及Laplacian Eigenmap[17]等. 因为流形学习降维算法计算复杂度高, 难以适用于新增数据,所以很少应用在实际场景中. 除了上述无监督降维算法, 研究者们也提出了许多半监督降维算法以及许多有监督降维算法[18−21]. 这些降维算法都是基于某种优化目标, 旨在保持数据的某种特性, 比如, PCA 要求降维后的数据方差尽可能大, LPP 要求降维前后数据的近邻关系得到保持, 并没有考虑降维后数据的用途.聚类也是机器学习领域的研究热点之一. K-means[22]是其中最经典的一个聚类算法. 尽管K-means 算法计算速度快, 被广泛使用, 但是其也具有若干缺点, 比如对异常点敏感、鲁棒性不强、计算速度慢及仅适用于球形分布的数据等. 为了解决这些问题, 研究者们也进行了系列研究[23−33]. 文献[34−37] 对K-means 算法进行扩展以完成分类属性数据、混合类型数据聚类. 1948 年, Shannon[38]引入信息熵, 一个系统越有序, 信息熵就越低; 反之, 一个系统越混乱, 信息熵就越高. 所以说, 可以认为信息熵是系统有序化程度的一个度量. 最大熵[39]建模是以最大熵理论为基础的一种选择模型的方法, 即从符合条件的分布中选择熵最大的分布作为最优的分布. 此后, 研究人员将极大熵的思想用于机器学习中. 文献[40] 提出了一种基于极大熵的聚类算法, 引起了广泛关注. 文献[8] 将极大熵的思想与LPP 结合在一起, 提出了图优化的局部近邻保持投影算法. 文献[41,42] 对极大熵聚类算法的收敛性进行了证明.传统的方法将高维数据的聚类分成降维和对降维后数据的聚类两个独立的阶段分别进行. 比如, 先用PCA 进行数据降维, 然后采用K-means 算法进行聚类学习. 目前也有一些研究将降维后数据的聚类信息融入降维过程中,用于指导降维[43−50]. van de Velden 等人[47]指出两阶段的高维数据聚类方法不如优化一个目标函数性能好. 将降维与降维后的用途结合起来设计降维算法成为新的研究思路.以提高降维后数据的聚类性能为目标, 我们提出了一种将极大熵理论与线性投影技术结合的快速无监督线性降维算法(a fast unsupervised linear dimension reduction method based on maximum entropy, MEDR). MEDR 算法将极大熵模型融合进线性降维过程中, 用于监督降维过程. 我们提出了一种有效的迭代优化算法进行MEDR 模型优化. 具体做法如下: 固定权重关系矩阵, 优化投影矩阵和类簇中心; 固定投影矩阵和类簇中心, 优化权重关系矩阵.MEDR 算法迭代地优化投影矩阵、类簇中心和权重关系矩阵, 直至算法收敛. MEDR 算法融合了线性投影技术和极大熵模型, 利用极大熵模型监督降维过程, 使降维后嵌入在低维子空间的数据更适合聚类. 所以, MEDR 算法具有明显的目的, 使降维后的数据更适合进行聚类.1 相关工作1.1 局部近邻保持算法(LPP)LPP 是Laplacian Eigenmaps 的一个线性扩展, LPP 的目标是使高维数据在低维子空间的投影依然保持原空间的近邻关系. LPP 最小化以下目标函数:2 软件学报12Σni; j=1ai jjjyi ���yjjj22(1)ai j = exp(���jjxi ��� xjjj22=2