模式识别与智能系统研究生论文开题报告

专业

研究方向

学号

研究生姓名

学位级别

导师姓名

本人已查阅过哪些科研资料及调研情况：

本人通过查阅近年国内外相关论文，对聚类算法和网络嵌入算法的研究工作现况有所了解：

[1]Cai D, Chen X.Large scale spectral clustering via landmark-based sparse representation[J].IEEE transactions on cybernetics, 2015, 45(8): 1669-1680.[2]Jia H, Ding S, Du M, et al.Approximate normalized cuts without Eigen-decomposition[J].Information Sciences, 2016, 374: 135-150.[3]赵晓晓,周治平.结合稀疏表示与约束传递的半监督谱聚类算法[J].智能系统学报,2018,13(05):855-862.[4] 张桂玲, 杜艳梦.拉普拉斯正则化双曲正切低秩子空间聚类算法[J].控制与决策, 2018, v.33(01):166-171.[5] Wang J, Shi D, Cheng D, et al.LRSR: low-rank-sparse representation for subspace clustering[J].Neurocomputing, 2016, 214: 1026-1037.[6] Yin M , Gao J , Lin Z , et al.Dual Graph Regularized Latent Low-Rank Representation for Subspace Clustering[J].IEEE Transactions on Image Processing, 2015, 24(12):4918-4933.[7] ENG X , FENG J , XIAO S , et al.Structured AutoEncoders for Subspace Clustering[J].IEEE Transactions on Image Processing, 2018, 27(10):5076-5086.[8] YANG B , FU X , SIDIROPOULOS N D ,et al.Towards K-means-friendly Spaces: Simultaneous Deep Learning and Clustering[J].In: Proceedings of the 34th International Conference on Machine Learning.Sydney, NSW, Australia :PMLR，2017:3861-3870.[9] Li X, Zhao X, Chu D, et al.An autoencoder-based spectral clustering algorithm[J].Soft Computing, 2019: 1-11.[10] 姜雅文.复杂网络社区发现若干问题研究[D].北京交通大学, 2014.[11] Tang X, Xu T, Feng X, et al.Learning community structures: Global and local perspectives[J].Neurocomputing, 2017, 239: 249-256.[12] Ding Z, Zhang X, Sun D, et al.Low-rank subspace learning based network community detection[J].Knowledge-Based Systems, 2018, 155: 71-82.[13] Tang J, Qu M, Wang M, et al.Line: Large-scale information network embedding[C].In: Proceedings of the 24th International Conference on World Wide Web.Florence, Italy: Springer, 2015: 1067-1077.[14] Yang C, Liu Z, Zhao D, et al.Network representation learning with rich text information[C].In: Proceedings of the 24th International Joint Conference on Artificial Intelligence.Buenos Aires, Argentina: AAAI Press, 2015:2111-2117.[15] Wang D, Cui P, Zhu W.Structural deep network embedding[C].In: Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining.San Francisco, California, USA: ACM Press , 2016: 1225-1234.[16] Ye F, Chen C, Zheng Z.Deep Autoencoder-like Nonnegative Matrix Factorization for Community Detection[C].In: Proceedings of the 27th ACM International Conference on Information and Knowledge Management.Torino ,Italy: ACM Press , 2018: 1393-1402.[17] 尚敬文, 王朝坤, 辛欣, et al.基于深度稀疏自动编码器的社区发现算法[J].软件学报，2017,28（3）：648-662.[18] Patel V M , Nguyen H V , Vidal R.Latent Space Sparse and Low-Rank Subspace Clustering[J].IEEE Journal of Selected Topics in Signal Processing, 2015, 9(4):691-701.[19] Wang X, Nie F, Huang H.Structured doubly stochastic matrix for graph based clustering: Structured doubly stochastic matrix[C].In: Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining.San Francisco, California, USA: ACM Press , 2016:1245-1254.[20] Tolić D, Antulov-Fantulin N, Kopriva I.A nonlinear orthogonal non-negative matrix factorization approach to subspace clustering[J].Pattern Recognition, 2018, 82: 40-55.[21] Yang X, Yu W, Wang R, et al.Fast Spectral Clustering Learning with Hierarchical Bipartite Graph for Large-Scale Data[J].Pattern Recognition Letters, 2018, 6(2): 10.1016/j.patrec.2018.06.024.[22] Vladymyrov M, Carreira-Perpiñán M.The Variational Nyström method for large-scale spectral problems[C].In: Proceedings of the 33nd International Conference on Machine Learning.New York City, USA: 2016:211-220.[23] Tian F, Gao B, Cui Q, et al.Learning deep representations for graph clustering[C].In: Proceedings of 28th AAAI Conference on Artificial Intelligence.Québec City, Québec, Canada: AAAI Press, 2014:1293-1299.[24] Song C, Liu F, Huang Y, et al.Auto-encoder Based Data Clustering[J].Lecture Notes in Computer Science, 2013, 8258:117-124.[25] Ghasedi Dizaji K, Herandi A, Deng C, et al.Deep clustering via joint convolutional autoencoder embedding and relative entropy minimization[C].In: Proceedings of the IEEE International Conference on Computer Vision, ICCV 2017.Venice, Italy: IEEE Computer Society, 2017: 5736-5745.[26] Perozzi B, Al-Rfou R, Skiena S.Deepwalk: Online learning of social representations[C].In: Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining.New York, USA: ACM Press, 2014: 701-710.[27] Grover A, Leskovec J.node2vec: Scalable feature learning for networks[C].In: Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining.San Francisco, CA, USA :ACM Press, 2016: 855-864.[28] Chang S, Han W, Tang J, et al.Heterogeneous network embedding via deep architectures[C].In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Sydney, NSW, Australia: ACM Press, 2015: 119-128.[29] Cao S, Lu W, Xu Q.Grarep: Learning graph representations with global structural information[C].In: Proceedings of the 24th ACM international on conference on information and knowledge management.Melbourne, VIC, Australia: ACM Press, 2015: 891-900.[30] Cao S, Lu W, Xu Q.Deep neural networks for learning graph representations[C].Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence.Phoenix, Arizona, USA:AAAI Press,2016:1145-1152.[31] Ng A Y , Jordan M I , Weiss Y.On Spectral Clustering: Analysis and an algorithm[C].In: Proceedings of Neural Information Processing Systems 14,NIPS 2001.Vancouver, British Columbia, Canada: Advances in neural information processing systems,2002:849-856.[32] Xie J , Zhou Y , Ding L.Local Standard Deviation Spectral Clustering[C].In: Proceedings of 2018 IEEE International Conference on Big Data and Smart Computing(BigComp).Shanghai, China :IEEE Computer Society, 2018:242-250.

课题的意义及我国在这方面已进行的工作情况：

随着以社交网络、微博为代表的新型信息发布方式不断涌现，以及云计算、物联网等技术的兴起，数据正以前所未有的速度在增长，这种增长主要体现在数据的量以及它的维度。现存的大多数谱聚类算法在处理大规模高维数据时往往得不到较好的性能，在处理海量数据时可能需要高昂的计算时间，并且随着数据集维度的不断增加，算法的处理能力往往不断下降，最终导致无法获得较为准确的聚类结果。本课题主要通过分析谱聚类算法存在计算复杂度高、存储需求大的问题难以适应于大规模数据集，同时利用以自编码器为代表的降维技术，构建深度嵌入模型学习深层次数据特征，较好地捕获数据间的几何结构信息，获得良好的特征表示，从而突破传统聚类算法在面临大规模高维数据时无法兼顾运行效率及聚类质量的局限，研究出高效率、高精度的聚类方法，并且改进的算法能够适用于复杂网络社区发现中。

另一方面，大规模复杂网络的信息挖掘在学术界和工业界引起越来越多的关注。其中一个重要分支便是网络表征学习，即网络嵌入。近年来，网络表征领域是复杂网络分析方面的研究重点，也是深度学习应用到网络分析中的表现之一。网络嵌入目前依旧面临许多挑战（1）高维且非线性，深层的网络结构特征通常是非线性且高维的，因此，如何去描述学习这种高维非线性的特征是非常具有挑战性的。（2）结构保持，为了能够将结果应用到一些具体的网络分析任务中，网络嵌入方法需要能够将网络结构较好的保存下来，包括局部结构信息以及全局结构信息，但隐藏的网络结构是非常复杂并且难以发现的，节点的特性往往依赖于其局部和全局的网络结构。（3）稀疏性，真实世界中大部分网络都是稀疏的，只能够利用极少数已发现的关系连接，因此还远远不能依次得到满意的效果。所以针对聚类算法存在的问题展开相应的研究工作，并将改进的聚类算法应用到复杂网络社区发现中具有重要的意义。

本人通过查阅近年国内外相关文献，对聚类算法和网络嵌入技术有了比较全面的了解。谱聚类作为聚类分析一种新兴分支，近十几年得到了巨大的关注与发展，不仅简单易实现，可以将数据集从原始空间转换到低维的特征空间，使得原始数据变成线性可分，并且在文献中成功应用于复杂网络社区划分中。但现存的多数谱聚类算法在面对高维大规模数据时往往需要高昂的时空开销，并且算法执行结果有较大的偏差，这种现象产生的主要原因：一方面在于传统谱聚类算法需要存储数据的相似度矩阵且要对拉普拉斯矩阵进行特征分解，在空间和时间的计算复杂度比较高，对大规模数据集来说是难以承受的负担；另一方面在于高维大规模数据的所有对象在空间中分布过于稀疏，欧式距离度量相似性得不到高的聚类精度。为实现对大规模高维数据集的高效聚类分析，目前国内不少专家学者从多个方面并使用不同策略进行大量的探索，涌现了不少实用的算法。为了提升谱聚类算法的扩展性，针对谱聚类算法降低时空复杂度的研究逐渐多了起来。蔡登等人[1]提出基于地标点的谱聚类算法，通过数据点与地标点之间的相似度矩阵来近似得到整体数据点的相似度矩阵，但是该方法通过随机采样确定地标点会造成采样结果不稳定。贾洪杰等人[2]通过理论证明Ncut图聚类与加权核k-means都等价于矩阵迹的最大化问题，利用加权核k-means算法来优化Ncut的目标函数，避免对拉普拉斯矩阵进行特征分解，同时提出近似加权核k-means算法降低空间复杂度。赵晓晓等人[3]提出一种结合稀疏表示和约束传递的半监督谱聚类算法，将约束集合中的数据作为地标点构造稀疏表示矩阵，近似获得图相似度矩阵，同时利用约束传递进一步提高聚类准确度。此外，基于降维的谱聚类方法也是处理高维大规模数据集的一个行之有效的手段，典型的降维算法有主成分分析（PCA）、奇异值分解（SVD）、等度量映射（Isomap）、非负矩阵分解（NMF）、自编码器（Autoencoder）等，不同的方法适合于不同的数据结构。但由于高维数据的许多属性都是冗余的，只有少量的主要特征决定数据的结构，这启发了子空间聚类的产生。目前较通用的方法是基于谱聚类框架的方法，已有大量文献围绕低秩和稀疏约束展开，将基于谱聚类的子空间聚类算法应用于高维数据中，并在精度和效率上不断进行改进与提高。张桂玲等人[4]针对低秩表示模型（LRR）对高维数据聚类精确度低问题，利用双曲正切函数代替核范数逼近秩函数，并采用拉普拉斯正则项刻画数据本身几何结构。王军等人[5]提出一种低秩子空间稀疏表示框架，通过对核范数优化得到干净字典矩阵，并利用线性交替方向法得到低秩稀疏系数矩阵。尹明等人[6]提出一种双正则化低秩模型保留数据几何结构信息，同时考虑数据流形和特征流形的几何结构，并对模型施加非负约束，从而实现对数据的特征表示。随着深度学习在机器学习各应用中获得较大成功，深度自编码器因其能在非线性降维的同时较好地保留数据的局部特性，成为近年来基于谱聚类的子空间聚类算法的研究热点。彭玺等人[7]通过引入结构自编码器，学习一组显示转换，结合先验信息，将输入数据点逐步映射到非线性潜在空间。杨波等人[8]通过学习深度神经网络来进行降维操作，将神经网络近似成任意非线性函数，以提高聚类性能。李昕咛等人[9]选取具有代表性的数据点作为地标点，利用地标点与所有数据点的相似性作为自编码器的输入，同时将学习嵌入表示和执行聚类结合，利用聚类损失同时更新自编码器参数及聚类中心，从而防止嵌入空间失真，保持数据的局部结构。可见，将谱聚类算法结合深度学习理念应用到高维大规模数据集中具有广阔的研究前景。

聚类分析中的簇与社交网络中的社区结构有着相似的概念。因此，可以把聚类分析方法应用到社交网络中来进行社区发现。用聚类分析的方法来识别社区结构时，首先要解决的问题就是如何把网络拓扑结构转化为适合聚类分析的数据结构，即如何把网络中节点间的联系用数据对象的相似性来描述。传统方法采用邻接矩阵，仅仅能记录节点间的一阶相似性信息，且维度较高，具有的空间复杂度。且针对网络拓扑相关的重要信息，需兼顾捕获整个网络中节点重要性的全局信息和描述节点之间相似性的局部信息。姜雅文等人[10]利用信号传递的方法将网络拓扑结构转化为空间向量信息，结合k-均值聚类，提出Signal算法。唐献超等人[11]将全局和局部信息同一集成到一个新的基于非负矩阵因子分解的模型中，采用PageRank来度量节点的全局重要性，同时利用Jaccard指标来度量节点之间的相似性。丁转莲等人[12]提出了一种新的基于低秩子空间学习的网络社区检测方法，设计了一种低秩分解组合策略，将几何空间中的每个节点向量分解为生成相同子空间的其他节点向量的线性组合，寻求所有节点向量的最低秩表示，较好地捕捉网络的全局结构，对网络中的扰动和异常值具有较强的鲁棒性。唐健等人[13]定义了两种相似性关系，一阶相似性定义为网络中节点连接关系（局部特性），二阶相似性作为一阶相似性的补充，定义为不直接相连节点的共同邻居节点（全局特性）。但考虑到转化后的高维矩阵不能反映网络拓扑结构的主要特征，对网络社区结构的表示不佳，导致使用经典聚类算法得到的社区结构往往不够精确且效率较低。因而，实现网络节点的低维表示也是亟待需要解决的问题。在大规模复杂网络背景下，网络嵌入是实现网络低维表示的一种重要方法，其目的是捕获和保留网络结构。近些年来，许多网络嵌入的方法相继被提出，它们大多采用了一些浅显的模型，比如过去比较经典的网络嵌入算法IsoMAP，Laplacian Eigenmap(LE)等等。但由于这些模型的局限性，它们很难获得高维的非线性网络结构，导致网络表示不够理想。因此，如何一种能够有效捕获高度非线性网络结构并保持全局和局部信息的方法是一个开放且重要的话题。深度学习因为其展现强大的表示学习能力，能够从复杂的网络中学习低维的特征表示，近年来很多学者开展了一系列关于设计网络深层模型的研究。杨城等人[14]研究节点与文本特征相关联的情况，首先证明了 DeepWalk 实质上是将转移概率矩阵 M 分解为两个低维矩阵。受此结果的启发，TADW 包含文本特征矩阵 T 通过将 M 分解为 W，H 和 T 的乘积，进入矩阵分解过程。最后，将 W 和 H×T 连接起来作为节点的潜在表示。王岱鑫等人[15]提出了一种将一阶近似和二阶近似结合的方案，二阶近似被无监督部件用来捕获全局网络结构，而一阶近似作为监督部件中的监督信息，被用来保存局部网络结构，通过深度自动编码器保持 2 跳邻居之间的接近度。叶方华等人[16]提出一种用于社区检测的类深度自编码器的NMF模型，该模型由编码器和自编码器组成，能够学习到原始网络和最终社区分配之间的层次映射，并在中间层学习到原始网络从低到高的隐式属性。尚敬文等人[17]提出基于跳数的处理方法，对稀疏的邻接矩阵进行优化处理，得到的相似度矩阵不仅能够反映网络拓扑结构中相连节点间的相似关系，同时还反映了不相连节点间的相似关系。然后基于无监督深度学习方法构建深度稀疏自编码器，对相似度矩阵进行特征提取，得到低维的特征矩阵。目前国内关于聚类算法结合深度网络嵌入模型，应用于社区划分的研究还比较少，尚有诸多问题需要解决。

国外的研究动态及发展趋势：

相对于国内而言，国外关于聚类算法和网络嵌入算法的研究则更丰富、更全面些。由于时间和精力有限，这里主要针对基于谱聚类的子空间聚类算法的研究，以及其在网络嵌入算法方面作相应的讨论。首先主要列举基于谱聚类的子空间聚类算法在国外的一些研究动态和发展趋势。Patel等人[18]提出隐空间稀疏低秩的子空间聚类算法，通过投影方法在低维隐空间内寻找稀疏或者低秩表示从而建立相似矩阵。Wang等人[19]提出一种新型凸模型，低秩约束图像拉普拉斯矩阵，运用此模型学习结构化双随机矩阵，所获得的新型双随机矩阵能够直接显示聚类结构，并为将要连接在一起的成对数据点的概率编码，由此来改善聚类结果。Dijana Tolic等人[20]引入了一个具有显式正交性的非线性NMF，并推导出基于核的正交乘法更新规则来解决子空间聚类问题。Yang等人[21]提出了一种新的基于层次二部图的谱聚类方法，采用无参数而有效的邻域分配策略构造相似矩阵，避免了调整相似度矩阵的需要，大大降低了算法的计算复杂度。Vlaydymyrovd等人[22]针对大规模的谱聚类对Nyström方法进行改进，提出一种局部线性地标点方法，简化特征分解问题，且和普通的地标点方法相比在相同个数的前提下包含更多的信息，降低复杂度且减少近似误差。虽然众多改进的谱聚类算法虽然一定程度上减小了时间复杂度，但仍然要对拉普拉斯矩阵进行特征分解，对于高维大规模的数据集来说内存消耗过大，具有巨大的空间复杂度，同时数据集高维度特性也会增加算法分析的计算时间和存储需求。随着深度学习在机器学习各应用中获得较大成功，深度自编码器作为目前较为流行的数据特征表示方法，通过多层神经网络将原始数据编码成低维数据，再进行解码重构，其获得低维特征表示能较好地保留数据分布特性，对于高维大规模数据的特征学习具有重要意义。Tian等人[23]利用叠加稀疏自编码器得到原始图的非线性嵌入，然后对嵌入表示进行k-均值聚类，得到聚类结果，用叠加的自动编码器代替特征分解，有效地降低了计算复杂度。Song等人[24]提出了一种新的基于自编码网络的聚类方法，通过设计数据与聚类中心之间距离的约束，得到了一种更适合于聚类的稳定而紧凑的表示形式。这种深层次的结构可以学习到强大的非线性映射，数据可以很好地在变换后的空间中进行分割。Dizaji等人[25]在联合学习框架下，通过多层卷积自编码器有效地将数据映射到判别嵌入子空间，并在编码层顶部叠加多项逻辑回归函数，精确地预测聚类划分。上述基于深度自编码的聚类算法可以提高聚类精度，但它们都需要使用整个数据集的相似度矩阵作为自动编码器的输入，保存了所有数据点的相似性，由于内存消耗大，不适用于大规模复杂数据集，因此针对这些问题对聚类算法从效率和准确率两方面进行改进。

国外对于网络嵌入技术的研究更为深入，且近年来有较多突破性进展，且随着深度学习的热潮，巧妙地将深度模型的思想应用于网络嵌入技术。Perozzi等人[26]提出随机游走（DeepWalk）算法，通过将节点视为单词并生成短随机游走作为句子来弥补网络嵌入和单词嵌入之间的差距。然后，可以将诸如 Skip-gram 之类的神经语言模型应用于这些随机游走以获得网络嵌入。DeepWalk是第一个被提出来使用表示学习（或深度学习）社区的网络嵌入方法，引入了深度学习图形的范例，且之后出现了很多相应的算法变体。Grover等人[27]类似于DeepWalk，主要创新点在于改进了随机游走的策略，定义了返回概率参数p和离开概率参数q，在宽度优先搜索（BFS）和深度优先搜索（DFS）中达到一个平衡，同时考虑到局部和宏观的信息，具有很高的适应性。Chang等人[28]提出了异构网络的深度嵌入框架。他们的模型首先为每种模态（如图像，文本）构建一个特征表示，然后将不同模态的嵌入映射到同一个嵌入空间。优化目标是最大化链接节点的嵌入之间的相似性，同时最小化未链接节点的嵌入。Cao等人[29]通过将图形邻接矩阵提升到不同的幂来利用不同尺度的节点共现信息。将奇异值分解（SVD）应用于邻接矩阵的幂以获得节点的低维表示。Cao等人[30]提出基于深度神经网络的学习网络嵌入的方法，用随机冲浪策略来捕获图形结构信息，进一步将这些结构信息转换为 PPMI 矩阵，并训练堆叠去噪自动编码器（SDAE）以嵌入节点。众所周知，聚类问题和网络划分问题之间可以相互转化，但转换的方法和难易程度不同。在定义了网络节点的相似度以后，就可以比较容易地将网络社区划分问题转化为聚类问题，然后利用聚类算法发现网络中的社区，两者虽然存在内在的一致性，但是在本质上二者并不完全等同，聚类分析问题中的每一个数据点是孤立存在的，只存在于其他数据点的距离信息或者相似度信息，而网络中每一个节点具备聚类分析问题所不具备的网络拓扑结构性质，网络中的每一个节点不仅受到其邻居的影响，而且还要受到其他节点经过拓扑性质传递给它的影响，因此结合谱聚类思想，构造兼顾网络全局和局部结构信息的相似度矩阵，并利用深度学习理念，构造强大的低维网络特征表示成为值得研究的课题。

开题报告

1．立题的依据，选题必须对国民经济或在学术上有一定意义。

2．课题进行的途径，步骤的设想。

3．需使用的仪器，一般应以选择本院现有仪器及设备为主，估计需要经费多少？

4．课题进行时可能出现的问题及准备采取的应变措施。

1、立题的依据

聚类分析作为数据挖掘领域里面发展比较成熟的一种数据分析技术，它可以在没有类标签的前提下对目标数据集的所有数据对象进行归类，在机器学习、模式识别等相关领域有着广泛的研究，已经应用到商业、生物学、地理信息和因特网等诸多方面。目前存在大量成熟有效的聚类算法，其中谱聚类由于它深厚的理论基础和广泛的应用性，近年来受到越来越多研究关注。但是现存的大多数谱聚类算法在处理海量数据时计算复杂度和空间开销比较大，并随着数据集维度的不断增加，算法的处理能力往往不断下降，最终导致无法获得较为准确的分析结果。为了满足当前高维海量数据的分析需求，谱聚类算法的研究需要着眼于降低时空复杂度以及利用降维技术提高聚类精度。另一方面，社交网络的出现同时带来了大量传统社会很难获得的社交数据，对社交网络数据进行挖掘和分析的相关研究也一直是计算机科学、社会学和经济学等各学科的一个热门领域。众所周知，聚类问题和网络社区划分问题之间可以相互转化，但两者虽然存在内在一致性，但本质上二者并不完全等同。聚类分析问题中的每一个数据点是孤立存在的，只存在与其他数据点的距离信息或者相似度信息，而网络中的每一个节点不仅受到其邻居的影响，而且还受到其他节点经过拓扑信息传递给它的影响。且基于聚类思想的复杂网络社区发现算法，多数涉及相似度计算，复杂度较高，同时大规模网络带来的相似度矩阵维度较高的问题也不能忽视。因此针对这些问题对聚类算法进行改进并应用到大规模复杂社区发现开展相应的工作，成为值得研究的问题。

2、课题进行的途径，步骤的设想

A、研究目标

1、针对大多数子空间聚类算法将高维数据映射到低维子空间时，存在无法兼顾数据全局和局部结构信息的问题，将低秩表示与深度自编码器相结合，提高聚类精度。

2、针对传统的谱聚类算法存在相似度矩阵存储开销大和拉普拉斯矩阵特征分解计算复杂度高的问题，引入节点相对质量概念评估PR值择取地标点，并采用改进的自动编码器代替拉普拉斯矩阵的特征分解，从而极大地减小时间和空间复杂度。

3、在大规模复杂网络背景下，利用现有网络嵌入方案难以捕获并保留网络结构，获得高维非线性网络结构，基于前面两点所提出的低维特征表示方案及构造相似度矩阵，建立深度嵌入网络模型，实现更精确高效的社区划分。

B、研究内容

1、在基于谱聚类的子空间聚类的基础上，利用无监督算法理论即将低秩表示与深度自编码器结合，通过将输入作为自监督信号学习低秩表示，同时利用约束先验来确保流形结构在递进学习表示中的不变性，结合自编码器提供的非线性判别空间，进一步提高聚类精度。

2、引入相对质量评估节点的质量，选取数据亲和图中PR值较高点作为地标点，以构造选定的地标点与其他数据点之间的相似度矩阵作为自编码器的输入，以减少内存消耗，并以自编码器代替拉普拉斯矩阵的特征分解，降低时间和空间复杂度。

3、在非负矩阵分解进行社区划分的基础上，继承深度自编码器独特的特征表示能力，构建NMF深层模型，从而挖掘更深层次网络结构信息。此外，构造新的相似度矩阵，兼顾网络局部和整体信息，适应于大规模复杂社区发现。

C、创新之处

本研究的创新点集中在：

1、将多元逻辑回归函数作为判别模型叠加在编码层顶部，以概率形式预测相关簇分配，并参照引入的辅助目标分布及标签经验分布，获得良好的低维特征表示。

2、有别于传统距离度量计算样本间相似性，采用融合欧式距离和Kendall Tau距离方案，并以自适应局部标准偏差缩放参数代替手动设置，构建新的相似度度量方案以尽可能反映数据集的原始分布。

3、将单层映射的NMF模型转变为包含编码和解码组件的多层映射NMF深层嵌入模型，同时引入二阶近似捕获全局网络结构，进一步提高社区划分的准确度。

D、研究方案

1、谱聚类算法研究

1）基于谱聚类的子空间聚类算法

子空间聚类的目的在于寻求一组隐式的低维子空间来拟合未标注的高维数据，并根据相应的结构关系对这些子空间进行划分。假设数据矩阵 包含个向量，从个不同线性子空间提取.子空间聚类的任务便是求解子空间数并将数据向量划分到相应子空间中.在基于谱聚类的子空间聚类中，其基本思想是将数据矩阵表示为字典矩阵下的线性组合:

(1)

为系数矩阵，表示为，相应地，中的每个列向量.构造优化框架求解得到系数矩阵后，通过构造亲和矩阵，用于计算拉普拉斯矩阵:

(2)

其中，为亲和矩阵中第行列元素.大部分子空间聚类算法均是采用主成分分析（Principal Component Analysis,PCA）获取拉普拉斯矩阵的特征向量，再结合经典聚类算法如K-means算法获得相关子空间分割.基于谱聚类的子空间聚类算法往往需要对自身数据字典构造亲和矩阵，充分利用数据点间相似性，进行样本自表达。低秩表示（Low-Rank Representation, LRR）旨在寻求低秩的数据表示矩阵。低秩表示的基本模型为：

(3)

其中表示矩阵的核范数，即的奇异值之和；为噪声项，表示范数；用于平衡两项.该模型一般采用增广拉格朗日乘子法（Augmented Lagrange Method,ALM）求解上述凸优化问题，获得最优解.此外，也可采用奇异值分解的方法，将奇异值分解为, 在ALM框架下求解该封闭解，那么式（3）的解为：.最优解为分块对角矩阵,描述了类内密相似及类间零相似.稀疏子空间聚类（Sparse Subspace Clustering,SSC）通过引入稀疏约束，提高表示的判别性。现已证明，在子空间独立或无交连的假设下，属于不同子空间的点的表示系数为0。SSC则要求C是稀疏的，通过稀疏约束的控制，SSC可自适应地确定近邻关系，其求解目标为：

（4）

其中，为范数，即非零元的个数，该问题求解是非凸也是NP难题，故考虑用范数代替求解该问题，即

（5）

其中，为范数。

LSR利用Frobenius范数作为正则项，通过求解如下最小化问题得到数据点之间的相似度：

（6）

其中，为正则项，数据项为数据的表示误差，这里主要针对高斯噪声，利用Frobenius范数作为正则项，使系数矩阵具有类内一致性的特征，保证同一子空间数据点之间的联系。

2）相似度矩阵构造

给定数据集，划分为簇。谱聚类中相似度矩阵的元素被定义为：

(7)

通常指点与之间的欧拉距离，参数是手动给出的全局参数，并不能体现数据的真实分布。Andrew等人建议自动选择，用多个值重复运行NJW，选择最优值，很明显该方法会增加计算负载，另外，待测试的值范围仍然存在任意设定，没有任何规律可循。且当输入数据包括具有不同数据来源时，没有一个单独的值适用于所有的数据。在文献中证明了缩放参数对聚类具有非常发的影响，当数据包含多个尺度时，甚至使用最优，NJW也未能找最佳簇划分。自调谐谱聚类算法[31]被提出，克服了NJW的缺点，该算法提出了局部尺度参数的概念，定义如下：

(8)

是点的近邻点，通常是点和之间的欧式距离，点和之间的平方距离为。该算法定义相似度矩阵如下：

(9)

使用特定的缩放参数可以根据点和周围邻域进行自调。该算法虽然在一定程度上克服了NJW算法的缺点，但也有一定的局限性。其聚类可能受到异常值影响，因为本地尺度参数可能扭曲了离群值。为避免该问题，文献[32]提出一种局部标准差谱聚类算法，定义局部标准差：

(10)

是点的最近邻点的个数，亲和矩阵的元素则为：

(11)

2、高维数据降维方法研究

数据降维基本原理是将样本点从输入空间通过线性或非线性变换映射到一个低维空间，从而获得一个关于原数据集紧致的低维表示。通过降维，我们希望减少冗余信息所造成的误差，提高识别的精度，又或者希望降维算法来寻找数据内部的本质结构特征。经典降维算法如主成分分析(PCA)、线性判别分析(LDA)等算法尽管简单易用，但这些算法的线性特质使得在处理复杂的真实数据时力不从心。基于线性的方法很难捕获低维流行上的复杂结构。流形学习算法，诸如等距映射（ISOMAP）、局部线性嵌入(LLE)、拉普拉斯特征映射（LE）、随机近邻嵌入（SNE）是一系列非线性降维算法，它们考虑数据之间的相互关系（如距离等），试图在低维空间还原高维空间的相互关系，尽管流形学习算法的非线性使得它们可以比经典算法处理更复杂的情形，但是由于它们在低维空间还原的数据相互关系是在高维空间定义的，高维空间数据间的相互关系不一定能反映真实的情况。换而言之，这类算法的弱点是如果原始空间的数据并不能真实地反映数据的结构，则不能期待能产生良好的降维效果。因此，迫切需要一种更为强大、可以处理并适应更为复杂情况的降维算法。神经网络降维技术首先出现突破是在2006年，Hinton在《Science》上发表以自编码器算法为基础构筑的深度神经网络，该算法使用多层神经网络对数据进行降维，提取数据低维度的特征。Hinton创新性地提出使用无监督预训练方式训练大型网络，使得大型深度网络的训练变得可行。相比PCA，Hinton等人提取的特征兼具低维度及压倒性的表现力。

自编码器是一种用于有效编码和降维的无监督学习的人工神经网络，以自身作为输出值，但输出值 自身之间还是有差异的。简单的自编码器是一种三层的神经网络模型，包含数据输入层、隐藏层、输出重构层，同时也是一种无监督学习模型。从输入层到隐层称为编码过程，从隐层到输出层称为解码过程。自编码就相当于自己生成标签，而且标签就是样本数据本身。三层自编码神经网络的模型如下：

图1 自动编码器原理简示图

假定是原始输入数据，是丢失函数，和分别是编码和解码的激活函数。编码后的嵌入表示如下：

(12)

解码后的输出如下所示:

(13)

自动编码器的目的是使原始输入和新的嵌入表示的重构输出之间的重构损失最小化。重构损失定义如下:

(14)

其中，是自动编码器的参数。

3、大规模复杂网络下的社区发现研究

1）基于非负矩阵分解的社区发现算法

定义一：对于网络连接拓扑，可使用图描述，表示个节点，表示第个节点，表示第个节点与第个节点存在连接关系。通常情况下，用邻接矩阵表示，元素表示第个节点与第个节点的连接关系。对于无权网络，若节点和节点之间存在边连接，则，否则。若网络是加权的，有真实值，若违背了非负约束，将中的元素规范为。若将个节点的网络划分为个社区，社区集合，表示第个社区。对于不相交社区，而重叠社区这种约束则是不存在的。

非负矩阵分解（NMF）定义为：通过寻找最大近似原始网络数据的两个低秩因子矩阵和，分解后得到的表示网络降维后的社区特征，社区指示矩阵则表示相应节点与社区的隶属程度，那么可以表示为第个社区对于边的贡献。是节点和节点共同参与同一社区的结果。显然的，应该尽可能地与一致，其目标函数为：

（15）

在学习社区指示矩阵的基础上，可以获得节点的社区隶属度。对于不相交的社区检测，每个节点被分配到其所属倾向最大的社区，对于重叠社区，则需要设定一个阈值在确定一个节点是否属于某一社区。如式，NMF仅仅是单层映射，但是，实际生活中的网络通常由复杂多样的组织模式构成。因此，原始网络与社区成员之间的映射极有可能包含相当复杂的层次结构信息，极有隐含的低层隐藏属性。众所周知，深度学习能够缩小原始数据的低层抽象和高层抽象之间的差距。从这个意义上说，可以进一步分解映射，每个元素增加一个额外的抽象层，表示节点之间从低到高的相似性。具体来说，邻接矩阵分解为个非负因子矩阵，如下：

（16）

其中，且设。式（11）的构成允许层对原始网络的抽象理解，由以下因子分解得到：

（17）

每一层的抽象体捕获节点之间在不同粒度级别的相似性，从一阶近似到结构特征，最后是社区级相似。这个深层结构将获得更好的，为了学习因子矩阵，构造以下目标函数：

(18)

通过优化上式，可以获得。式 在重构网络的基础上，对应于自编码器的解码器组件。为了更好的继承自编码器的表示学习能力，将编码器组件集成到基于NMF的社区检测模型中，从而产生类自编码器的NMF模型。对于一个理想的社区指示矩阵一方面应该能够通过映射在最小误差下重构网络，另一方面，应该可以在映射下直接将原始网络映射到社区隶属空间，即.通过将编码器和解码器组件集成到一个统一的损耗函数中，这两个组件能够在学习过程中相互引导，从而获得理想的社区指示矩阵。为了在深度模型中实现这一目标，编码器组件的目标函数如下：

(19)

将式(15)和（16）结合，深度类自编码器NMF模型的联合目标函数表示为：

(20)

其中，图正则器进一步介绍了节点对的固有几何结构，表示正则化参数，表示拉普拉斯矩阵。

2）相似度矩阵构造

定义二（一阶相似度）：网络中的一阶相似度是两个节点之间的可观测点对邻近度。对于任意节点对，若，节点和之间存在链路，则为正一阶相似度，否则为0。

往往将邻接矩阵作为一阶相似度，由于一阶相似度是网络最直接的表达，其保留是有必要的。然而，在现实世界的信息网络中，能够观察到的链路只是小部分，许多隐藏的其他关系都没有被观察到。缺失链路上的节点对，即使在本质上非常相似，但一阶相似度为0，因此需定义二阶相似度，其补充了一阶相似度，并能够保留网络结构。

定义三（二阶相似度）:二阶相似度对应于网络中节点对邻域结构的相似。表示节点与其他节点的一阶相似性。和之间的二阶相似性则是由和决定。若不存在节点同时与和相连，那么二阶相似度为0。可考虑将余弦相似性作为二阶相似度，对于和。

3）社区划分指标

①模块度Q(Modularity):也称模块化度量值，是目前常用的一种衡量网络社区结构强度的方法，其定义为：

(21)

其中表示节点的度，函数的取值定义为：如果和在一个社区，则为1，否则为

0。模块度的大小取决于网络中节点的社区划分情况，可以用来定量的衡量网络社区划分质量，其值越接近1，表示网络划分出的社区结构的强度越强，因此可以通过最大化模块度Q来获得最优的网络社区划分。

②兰德指数ARI（Adjusted Rand Index）:若已知样本的真实类别标签和聚类算法得到的标签，ARI是计算两种标签分布相似性的函数，该函数对标签的定义形式没有要求，ARI定义如下：如果C是真实类别，K是聚类结果，a为在C和K中都是同一类别的样本对数，b为在C和K中都是不同类别的样本对数。公式如下：

（22）

其中是样本所有的可能组合对。

3、需使用的仪器

无特殊设备要求

课题与教研室及导师的科研工作有无关系，与已毕业的研究生课题联系：

与教研室及导师的科研工作有关，与已经毕业的研究生学术研究方向相关。

论

文

工

作

计

划

阶段工作内容及预计完成的指标：

2018.09-2019.01 内容：基础课程学习阶段。

指标：掌握学习大纲要求的内容。

2019.02-2019.04 内容：搜集并阅读关于课题的国内外的文献资料。

指标：了解国内外有关课题的发展情况，确定课题，撰写开题报告。

2019.05-2019.08 内容：学习谱聚类框架下的子空间聚类算法、深度学习方法及各种改进算法，对各算法性能进行测试对比分析。

指标：完成第一个研究内容发表小论文。

2019.09-2019.12 内容：学习谱聚类及各种改进算法，并结合自编码器展开理论研究，对各算法性能进行测试对比分析。

指标：完成第二个研究内容发表小论文。

2020.01-2020.03 内容：学习社区划分方法，通过仿真平台进行实验分析。

指标：基本掌握社区划分背景下相关内容的基本算法以及研究进展。

2020.04-2020.07 内容：深入挖掘创新点，研究结合深度学习和社区划分的相关算法改进，通过仿真平台进行实验分析提高算法精度

指标：完成第三个研究内容发表小论文。

2020.08-2021.01 内容：整理前期对课题所作的研究结果，总结并撰写论文

指标：完成学位论文初稿

2021.02-2021.04 内容：结合老师意见，针对论文初稿的不足之处补充完善

指标：初稿的内容基本满足学位论文要求

2021.05-2021.06 内容：不断修改完善论文格式，以达到指定要求

指标：完成论文，通过答辩

审

查

意

见

导师或指导小组意见：

签 名：

年 月 日

教研室意见：

签 名：

年 月 日

学院负责人意见：

签 名：

年 月 日