Machine Learning and Data Mining with Combinatorial Optimization Algorithms
Machine Learning and Data Mining with Combinatorial Optimization Algorithms
复制标题
DOI：
10.1287/educ.2018.0179
复制
发表时间：
2018-10
期刊：
影响因子：
--
通讯作者：
D. Hochbaum
中科院分区：
文献类型：
--
作者：
D. Hochbaum
二进制分类是一项基本的机器学习任务，定义为基于一组训练对象将新对象正确分配到两个组中的一个。由于二进制分类的实际重要性，在过去的三十年中，许多机器学习技术已经开发和完善。其中最流行的技术是人工神经网络，决策树，集成方法，逻辑回归和支持向量机。我们在这里介绍机器学习和模式识别算法，与常用的技术不同，它们基于组合优化，并利用数据集对象之间的成对关系信息，无论是否是训练对象。这些算法最优和有效地解决了各自的问题，与目前用于模式识别和机器学习中棘手问题模型的主要启发式方法相反。所描述的算法有效地解决了分类问题作为一个网络流问题的图。该算法中使用的技术工具是参数切割过程和一个称为稀疏计算的过程，该过程只计算“相关”的成对相似性。稀疏计算使任何使用成对相似性的算法都能够扩展。我们提出的证据的有效性的方法，测量的准确性和运行时间，在模式识别，图像分割，和一般的数据挖掘。
Binary classification is a fundamental machine learning task defined as correctly assigning new objects to one of two groups based on a set of training objects. Driven by the practical importance of binary classification, numerous machine learning techniques have been developed and refined over the last three decades. Among the most popular techniques are artificial neural networks, decision trees, ensemble methods, logistic regression, and support vector machines. We present here machine learning and pattern recognition algorithms that, unlike the commonly used techniques, are based on combinatorial optimization and make use of information on pairwise relations between the objects of the data set, whether training objects or not. These algorithms solve the respective problems optimally and efficiently, in contrast to the primarily heuristic approaches currently used for intractable problem models in pattern recognition and machine learning. The algorithms described solve efficiently the classification problem as a network flow problem on a graph. The technical tools used in the algorithm are the parametric cut procedure and a process called sparse computation that computes only the pairwise similarities that are “relevant.” Sparse computation enables the scalability of any algorithm that uses pairwise similarities. We present evidence on the effectiveness of the approaches, measured in terms of accuracy and running time, in pattern recognition, image segmentation, and general data mining.