基于低秩稀疏子空间的数据挖掘算法研究

发布时间：2018-08-20 17:25

【摘要】：高维数据不仅具有高维的属性特征,通常还含有大量的冗余和噪声以及离群点,这使得高维数据的空间结构变得复杂,不利于数据挖掘算法使用数据中的真实关联结构来构建效果更好的模型。其中,构造系数矩阵是寻找数据中关联结构的重要步骤,即通过学习系数矩阵来捕捉样本之间或属性之间的关联大小,然而其学习过程对噪音和离群点等干扰较敏感。稀疏学习可以使系数矩阵变得稀疏,即相关的样本或属性之间具有大系数值,不相关的样本或属性之间的系数值很小甚至为零,因而所获得的稀疏系数矩阵能非常有效地反映数据之间的关联关系,从而使数据挖掘算法能有效的去除冗余和噪声以及离群点的干扰,从而获得非常好的鲁棒性。此外,高维数据可通过多个低维子空间组成的集合来表示,因此,使用子空间学习将复杂的高维数据空间转为结构较简单的低维子空间,更有利于数据挖掘算法找到数据中隐藏的全局结构和局部结构,从而得到更有效的数据挖掘结果。另外,数据中含有的噪声和离群点会使学习获得的系数矩阵的秩变大,使得数据挖掘算法无法捕捉到高维数据中真实的低秩结构,所以,通过在系数矩阵的学习过程中使用低秩约束来明确地降低其秩的大小。然而,现有的数据挖掘算法仍然存在一些不足:第一,仅考虑到高维数据中的片面关联结构,例如模型仅使用全局结构信息或局部结构信息,少部分算法能够通过较全面的结构信息来构建模型,然而却没有同时把稀疏学习和低秩约束以及子空间学习相结合来获取数据中的互补结构信息,以便得到更有效的数据挖掘模型;第二,将数据挖掘任务分成多个独立进行的步骤来完成,即使这些独立的步骤可以在各自优化过程中得到每个步骤的最优解,但是却不能确保最终获得的解是全局最优解。为此,本文主要研究稀疏学习和低秩约束以及子空间学习等技术,针对现有数据挖掘算法存在的一些不足,分别提出创新的多输出回归算法和子空间聚类算法来更有效的对高维数据进行挖掘。本文的主要研究成果可以归纳如下:1)提出了一种基于低秩约束和特征选择的多输出回归算法(Low-rank Feature Reduction for multi-output regression,简称为LFR),来解决现有多输出回归分析算法没有充分使用高维数据中固有的多种关联关系的问题。LFR算法结合使用稀疏学习和低秩约束以及子空间学习等技术来考虑多输出回归高维数据集里的属性特征与属性特征之间的关联关系、输出变量与输出变量之间的关联关系以及训练样本与训练样本之间的关联关系,提高多输出回归模型对多输出变量实值预测的能力。具体而言,LFR算法创新的使用稀疏学习理论中的l,,-范数正则化项来寻找高维数据中特征与特征之间的关联关系,并通过特征选择来选出具有重要信息的特征与去除噪声的干扰;此外,通过两个带有低秩约束的新矩阵的乘积来表示回归系数矩阵,从而间接地对回归系数矩阵进行低秩约束来探寻输出变量与输出变量之间的关联关系;另外,通过将l2,1-范数与损失函数项相结合来进行样本选择,从样本与样本之间的关联关系来去除离群点对回归模型学习的影响。通过在大量多输出回归数据集上进行的实验,结果表明本文第三章中所提出的LFR算法具有非常好的多输出回归预测能力。2)提出了一种基于低秩约束和稀疏学习的子空间聚类算法(Low-rank Sparse Subspace clustering,简称为LSS)。现有子空间聚类算法通过两个分开独立的步骤实现聚类,即首先构造相似度矩阵和然后进行谱聚类,不能确保最终获得的解是最优解,并且没有考虑从原始数据的低维结构中学习相似度矩阵。本文在第四章中提出LSS算法,创新地结合稀疏学习、低秩约束、样本自表达和子空间学习等技术来获得更好的高维数据聚类效果。具体而言,LSS算法通过稀疏学习对系数矩阵进行特征选择来去除冗余特征和噪声;并且从原始数据空间中及其低维空间中分别学习相似度矩阵,然后让这两个矩阵在迭代优化过程中相互得到优化,使相似度矩阵能更好地反映数据真实的相似度;此外,通过低秩约束来约束相似度矩阵的拉普拉斯矩阵,从而能在迭代优化的过程中同时获得最好的相似度矩阵和最优的聚类结果。通过大量聚类实验的结果,验证了本文第四章中所提出的LSS算法能够非常有效地对高维数据进行聚类。本文主要研究稀疏学习和低秩约束以及子空间学习等技术,提出了两种新的数据挖掘算法来分别解决数据挖掘领域中现有多输出回归算法和子空间聚类算法存在的一些不足,为数据挖掘算法的研究增加了新的想法和应用。通过在真实的公开数据集上的实验,验证了本文所提出的两种算法在各种评价指标下均能够取得非常好的挖掘效果。
[Abstract]:High-dimensional data not only has high-dimensional attributes, but also contains a lot of redundancy, noise and outliers, which makes the spatial structure of high-dimensional data more complex. It is not conducive to data mining algorithm using the real association structure of data to build a better model. An important step is to capture the size of association between samples or attributes by learning coefficient matrices. However, the learning process is sensitive to noise and outliers. Sparse learning can make coefficient matrices sparse, i.e. there are large coefficient values between related samples or attributes, and coefficient values between uncorrelated samples or attributes. Because the sparse coefficient matrix is very small or even zero, it can effectively reflect the relationship between data, so that the data mining algorithm can effectively remove redundancy, noise and outliers, thus achieving very good robustness. In addition, high-dimensional data can be represented by a set of low-dimensional subspaces. Therefore, the use of subspace learning to transform complex high-dimensional data space into simple low-dimensional subspace is more conducive to the data mining algorithm to find hidden global structure and local structure in the data, so as to obtain more effective data mining results. Because the rank of matrix becomes larger, data mining algorithms can not capture the real low-rank structure in high-dimensional data. Therefore, the size of rank can be clearly reduced by using low-rank constraints in the learning process of coefficient matrix. For example, the model only uses global structure information or local structure information. A few algorithms can construct the model through more comprehensive structure information. However, they do not combine sparse learning with low rank constraints and subspace learning to obtain complementary structure information in the data, so as to get more effective data mining model. Secondly, the data mining task is divided into several independent steps to complete, even though these independent steps can get the optimal solution of each step in their respective optimization process, but can not ensure that the final solution is the global optimal solution. To overcome the shortcomings of existing data mining algorithms, innovative multiple output regression algorithm and subspace clustering algorithm are proposed to mine high-dimensional data more effectively. The main research results of this paper can be summarized as follows: 1) A low-rank feature based on low-rank constraints and feature selection is proposed. Reduction for multi-output regression, or LFR for short, solves the problem that existing multiple-output regression analysis algorithms do not fully utilize the inherent associations in high-dimensional data. The correlation between attributes and attributes, the correlation between output variables and output variables, and the correlation between training samples and training samples can improve the prediction ability of multiple output regression models. In addition, the regression coefficient matrix is represented by the product of two new matrices with low rank constraints, and the output variables are searched indirectly by low rank constraints on the regression coefficient matrix. In addition, sample selection is carried out by combining l2,1-norm with loss function term to remove the influence of outliers on regression model learning. LFR algorithm has very good ability of multiple output regression prediction.2) A subspace clustering algorithm based on low rank constraints and sparse learning (LSS) is proposed. Line spectrum clustering can not ensure the final solution is the optimal solution, and does not consider learning similarity matrix from the low-dimensional structure of the original data. In the fourth chapter, LSS algorithm is proposed, which combines sparse learning, low rank constraints, sample self-expression and subspace learning to achieve better clustering results. For example, LSS algorithm uses sparse learning to select features of coefficient matrices to remove redundant features and noises, and learns similarity matrices from the original data space and its low-dimensional space respectively, and then optimizes the two matrices in the iterative optimization process, so that the similarity matrix can better reflect the real data phase. In addition, the Laplacian matrix of the similarity matrix is constrained by low rank constraints, so that the best similarity matrix and the best clustering results can be obtained simultaneously in the iterative optimization process. In this paper, sparse learning, low rank constraints and subspace learning are studied, and two new data mining algorithms are proposed to solve the shortcomings of the existing multiple output regression algorithm and subspace clustering algorithm in the field of data mining, which adds new ideas and applications to the research of data mining algorithms. Experiments on real open datasets show that the two algorithms proposed in this paper can achieve very good mining results under various evaluation indicators.
【学位授予单位】：广西师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13

【相似文献】