【作者】 刘波；

【导师】 王红军；

【作者基本信息】 西南交通大学 ， 计算机技术， 2014， 硕士

【摘要】 子空间聚类算法能有效减少数据冗余和不相关属性对聚类过程的干扰,从而提高在高维数据集上的聚类效果。已有的子空间聚类算法主要强调在各个子空间中簇的发现,通常忽略了子空间的划分。高维数据中,子空间划分的正确与否,直接影响到高维数据聚类正确率的高低,因此想要提升高维数据的聚类准确率,就必须采用正确的子空间划分方法来对高维数据进行子空间划分。本论文提出了两种划分数据子空间的方法,第一种是基于最小冗余特征子集的子空间划分法,第二种是基于属性最大间隔的子空间划分法。基于最小冗余特征子集的子空间划分法是在K-means算法的基础上改进的,将计算数据特征变量间的互信息替换K-means算法中计算数据特征变量间的距离,根据数据特征变量间互信息值的大小来对数据进行子空间划分,用这种方法划分出来的子空间叫做最小冗余特征子集。基于属性最大间隔的子空间划分法是通过计算数据两两属性间的互信息,然后将属性间的互信息值归一化后构建一个特征矩阵。得到特征矩阵后,再利用网格划分法将特征矩阵划分成不同的子块,通过搜索子块中互信息的最大值得到数据集中两个属性变量之间的最大信息系数,最大信息系数体现了两个属性之间关联性的大小,关联性越大,属性间间隔越小,关联性越小,属性间间隔越大,因此在得到最大信息系数后,我们就可以利用最大间隔原理来对数据集进行子空间划分。最后,通过实验验证本论文提出的两种子空间划分方法的有效性,采用UCI和NIPS2003比赛等数据来进行实验,实验结果表明,在大多数数据上采用基于最小冗余特征子集法和属性最大间隔法对数据集进行子空间划分后得到比其他子空间聚类算法更好的聚类结果。更多还原

【Abstract】 Subspace clustering algorithm can reduce the influence of redundancy and irrelevant attributes effectively during the clustering process, and improve the clustering accuracy. Existing subspace clustering algorithms emphasize the find of clusters in all subspace, and ignore the divide of subspace. In a high-dimensional dataset, the divide of subspace affects the clustering accuracy of high-dimensional dataset directly. In order to improve the clustering accuracy of high-dimensional dataset, a correct subspace dividing method must be used to divide the subspace.In this thesis, two methods are proposed to divide dataset. The first is the method of subspace dividing based on minimum redundancy feature subset, and the second method based on maximum margin. The method based on the minimum redundancy feature subset was improved based on K-means algorithm. We calculate the mutual information between data characteristic variables instead of calculating the distance between characteristic variables, according to the value of mutual information, data subspace is divided, and subspace divided by this method is called the minimum redundancy feature subspace.The method of subspace dividing based on the maximum margin is determined by the mutual information between each pair of attributes. Characteristic matrix is built based on the mutual information value between each pair of attributes. Meshing method is used on characteristic matrix to get different sub-blocks. Maximal information coefficient is obtained through research the maximal mutual information value of these sub-blocks. Maximal information coefficient reflects the correlation between each pair of attributes. The greater relevance, the smaller margin; The smaller relevance, the greater margin. According to the maximal information coefficient, the subspace could be divided based on the maximum margin principle.Finally, experiments are performed to verify the validity of two subspace dividing methods. Experiments on UCI and NIPS2013competition datasets show that the method of subspace dividing based on minimum redundancy feature subset and the method of subspace dividing based on maximum margin on most datasets perform better than other subspace clustering algorithms.更多还原