Logical analysis of numerical data
Logical analysis of numerical data
复制标题
DOI：
10.1007/bf02614316
复制
发表时间：
1997-10-01
影响因子：
2.7
通讯作者：
Kogan, A
中科院分区：
文献类型：
--
作者：
Boros, E;Hammer, PL;Kogan, A
数据逻辑分析(LAD)是八十年代末发展起来的一种方法，旨在发现数据集中隐藏的结构信息。LAD最初是为了利用部分定义的布尔函数理论分析二进制数据而开发的，LAD的扩展用于数值数据集的分析是通过将每个数值变量替换为二进制值变量(每个变量都表示原始变量的值高于或低于某一水平)的过程来实现的。二值化被成功地应用于各种现实生活数据集的分析，本文发展了二值化过程的理论基础，研究了与二元变量个数最小化相关的组合优化问题，为这类问题的实际求解提供了一个算法框架，我们构造了它们的紧致线性整数规划公式。我们为其中一些极小化问题开发了多项式时间算法，并证明了其他问题的NP难度，(C)1997，数学规划学会，Inc.由Elsevier Science B.V.出版。
''Logical analysis of data'' (LAD) is a methodology developed since the late eighties, aimed at discovering hidden structural information in data sets. LAD was originally developed for analyzing binary data by using the theory of partially defined Boolean functions, An extension of LAD for the analysis of numerical data sets is achieved through the process of ''binarization'' consisting in the replacement of each numerical variable by binary ''indicator'' variables, each showing whether the value of the original variable is above or below a certain level. Binarization was successfully applied to the analysis of a variety of real life data sets, This paper develops the theoretical foundations of the binarization process studying the combinatorial optimization problems related to the minimization of the number of binary variables, To provide an algorithmic framework for the practical solution of such problems, we construct compact linear integer programming formulations of them. We develop polynomial time algorithms for some of these minimization problems, and prove NP-hardness of others, (C) 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.