基于图割的线性无监督学习框架、扩展模型及大数据应用研究

There exist some problems for the existing graph cut based unsupervised learning methods: 1) high space complexity, 2) very high time complexity, 3) difficult to set parameter for constructing similarity matrix, 4) difficult to eliminate the effect of noise data and features on the similarity matrix and 5) usually use k-means to obtain the final clustering partition result. But its performance cannot be guaranteed because it does not directly optimize the objective function. .To solve the above problems, this project researches new graph cut based unsupervised learning framework, linear learning methods and extension models which beat the exiting methods in both effectiveness and efficiency. The main contents of this project include: 1) studying new graph cut based unsupervised learning framework and linear learning methods which will radically solve the big data problem, 2) extending the new framework to a series of unsupervised learning problems, including feature selection, multi-view clustering, cluster ensembles and feature tree based clustering and 3) applying the proposed methods to classical big data applications..We plan to publish over 15 SCI/EI cited papers, including at least 4 papers in conferences or journals which are listed in CCF A/B and at least 4 papers in journals listed in 1 or 2 divisions of Chinese Academy of Sciences JCR list. We will submit 4-6 patients, and supervise 1-2 Ph.D students and 6-8 master students.

基于图割的无监督学习方法存在如下问题：1）空间复杂度高，2）计算复杂度高，3)计算相似度时的参数难以设置，4）很难消除相似度矩阵受噪声数据及特征的影响，5）一般使用k-means来获得聚类结果。但这种方法并非直接优化目标函数，其性能无法保证。.针对以上问题，本项目从基础理论入手进行创新，以在不影响算法性能的前提下降低算法的复杂度为研究目标，研究基于图割的线性无监督学习框架及扩展模型。主要研究内容包括：1）研究具有线性空间及时间复杂度的图割框架及优化算法，从根本上解决处理大数据的难题；2）将新方法扩展到包括特征选择、多视图聚类、聚类集成以及基于特征树的聚类等问题上；3）项目所研发的新技术将在典型的大数据应用上进行测试验证。.预期发表SCI/EI收录论文15篇以上，其中包括CCFA/B类论文4篇以上，中科院1-2区期刊4篇以上。申报专利4-6项。培养博士1-2名，硕士6-8名。

基于图割的无监督学习方法存在如下问题：1）存储复杂度高，2）计算复杂度高，3)计算相似度时的参数难以设置，4）很难消除相似度矩阵受噪声数据及噪声特征的影响，5）一般使用k-means来获得聚类结果。但这种方法并非直接优化目标函数，其性能无法保证。.为了提高这类方法处理大数据的能力，传统的研究方法一般包括：1）对算法并行化；2）使用抽样方法减小数据处理量； 3）计算近似的特征向量。但以上的方法无法从根本上解决处理大数据时的问题。.针对以上问题，本项目从基础理论入手进行创新，以在保证甚至提升算法性能的前提下同时降低算法的复杂度为研究目标，研究新的方法。主要包括：1）研究具有线性复杂度的图割模型及框架，从根本上解决处理大数据的难题；2）将新方法推广到包括特征选择、多视图聚类、聚类集成以及特征树数据聚类等问题上；3）将项目所研发的新技术在典型的大数据应用上进行测试验证。.通过项目的开展，在三个问题上都取得了一定的成果：研发了一系列的算法，主要包括基于图嵌入的局部投影框架LAP、快速谱聚类算法DNC/LABIN/FINC、新的谱聚类算法EBMC、面向客户交易数据的谱聚类算法；开发了基于图割的聚类软件系统。项目的相关成果正通过与包括腾讯、珍爱网等公司的合作进行转化。发表了高水平论文16篇，包括本领域CCF A/B类高水平论文14篇，中科院1/2区高水平论文 11篇；申请专利4个，1个已授权，3个进入实审阶段；培养研究生10个（已毕业），在读研究生15个，协助指导已读博士生1个。.