基于图的高维数据分类Ratio Cut模型及其快速算法

Graph-based Ratio Cut Model for Classification of High-dimensional Data and Fast Algorithm

数据分类是数据挖掘研究的重要内容,随着数据量以及数据维度的增加,对大规模、高维数据的处理成为关键问题。为提高数据分类的准确率,受计算机视觉中图像分割算法的启发,针对经典的Ratio Cut分类模型提出一种基于非局部算子的实现算法。引进拉格朗日乘子,建立新的能量泛函,并采用交替优化的策略来求解该能量泛函。数值实验表明,算法的准确率及计算效率与传统分类方法相比都有较大提高。

Data classification is an important part of data mining.With the increase of the amount of data and the dimension of data,the processing of large-scale and high-dimensional data becomes the key problem.In order to improve the accuracy of data classification,inspired by the image segmentation algorithm in computer vision,an algorithm based on nonlocal operator was proposed for the classic Ratio Cut classification model.A new energy functional is modeled by introducing Lagrange multipliers,and the energy functional is solved by the alternating optimization method.Numerical experiments show that the accuracy and computational efficiency of the proposed algorithm are greatly improved compared with the traditional classification method.