可扩展的保序子矩阵挖掘方法研究

In the field of gene expression analysis in bioinformatics, through mining order-preserving submatrices (OPSM) from the gene expression data, biologically significant correlations can be discovered, which successfully achieves the conversion from data to knowledge. However, due to the inherent computational complexity of the OPSM mining problem, most of the research work on this problem is restricted to the analysis of small- to middle-scale matrix data. In this project, we consider challenging data analysis tasks caused by different data characteristics in wider application areas, such as the need for finding correlations from large-scale sparse data, the need for finding correlations with time lagging, and etc. We first try to improve the original OPSM model to well capture the useful order-preserving correlations in these application data. Then, for each improved OPSM model, we design and develop efficient pattern mining methods. Last but not the least, in order to carry out efficient data analysis in Big Data applications, we construct a distributed computing platform for mining OPSM patterns from extremely large-scale data. Our research work in this project form a unified and complete system for OPSM mining, which can meet the needs for data analysis from diverse application areas.

在生物信息学的基因表达分析领域，通过挖掘保序子矩阵从数据中发现了有用的生物关联，成功实现了从数据到知识的转化。然而，由于保序子矩阵挖掘问题本身的计算复杂性，对于该问题的研究大多局限于针对中小规模数据的分析。在本课题中，我们考虑在更广泛应用领域针对不同特征数据的分析需求，比如，从大规模的稀疏数据中发掘关联，以及发掘数据中存在时间延迟的关联等。首先，我们通过扩展保序子矩阵模型，试图刻画不同应用领域数据中存在的有用保序关联。其次，针对每一种扩展模型，我们研究与设计相应的挖掘算法以实现子矩阵的有效挖掘。最后，针对日益重要的大数据应用分析需求，我们设计与构建保序子矩阵挖掘的分布式计算平台以实现在超大规模数据上的子矩阵挖掘。我们基于本课题的研究工作在保序子矩阵挖掘领域将形成一套完整的体系，可以应对不同领域、不同特征数据的分析需求。

以数据驱动的诸多应用中，挖掘数据中的重要关联逐渐成为数据分析不可或缺的关键环节，为决策制定、精准营销、知识发现等提供重要的支撑与参考。在本项目执行期间，项目组成员与合作研究者围绕数据关联分析开展了一系列相关又相互独立的研究工作。我们探索在以数据为中心的应用领域内，如推荐系统及单细胞测序数据分析等，如何利用数据关联挖掘推动数据分析。首先，针对推荐系统的评分预测问题，我们提出基于保序子矩阵挖掘的分布式评分预测方法。我们的方法不仅可以有效处理推荐系统中的海量稀疏数据，在真实音乐推荐系统上的应用更进一步证实我们的方法在评分预测上的有效性。其次，针对单细胞测序数据分析领域的细胞分类问题，我们提出利用双聚类挖掘方法寻找细胞表达模式之间的局部关联，然后通过合并这些关联信息生成高置信度的的细胞分类结果。我们采用大量具有不同特征的真实单细胞测序数据集，全面验证了我们方法的有效性。与相关工作相比，我们的方法不仅具有很高的运行效率同时显著提高了细胞分类的准确度。另一方面，我们还研究如何从技术与实现上进一步提高数据关联分析方法。相似性检索是与数据关联分析紧密相关的问题。基于位置敏感哈希的相似性检索是针对海量高维数据进行相似性检索的重要方法，也是目前十分热门的研究领域。我们探索LSH技术在高维数据相似性检索领域更广泛的应用，研究针对最远邻检索问题的LSH机制，针对更通用的Lp距离的LSH机制，以及针对最大类积搜索的LSH机制。我们在这些问题上都取得了重要的研究成果，推动了该领域的研究进展。