Dualization, decision lists and identification of monotone discrete functions
Dualization, decision lists and identification of monotone discrete functions
复制标题
DOI：
10.1023/a:1018993014297
复制
发表时间：
1998-01-01
影响因子：
1.2
通讯作者：
Bioch, JC
中科院分区：
文献类型：
--
作者：
Bioch, JC
机器学习，数据设计和许多其他学科的许多数据分析算法基本上在离散的多属性数据集上运行。通过离散化或二进制，还可以成功分析数值数据集。因此，在本文中，我们将（部分定义）离散函数的理论视为分析多属性数据集的重要理论工具。特别是我们研究单调（部分定义）离散函数。与布尔函数理论相比，关于（部分定义）单调离散函数的知识相对较少。看来决策列表对于表示单调离散函数的表示很有用。由于双重化是（单调）布尔函数理论中的重要工具，因此我们研究了（单调）二进制或离散功能的双重偶性的解释和特性。我们还介绍了伪树状功能的双重双重功能。结果用于研究部分定义的单调离散函数的扩展以及单调离散函数的识别。特别是，我们提出了一种多项式时间算法，用于识别所谓的稳定离散函数。
Many data-analysis algorithms in machine learning, datamining and a variety of other disciplines essentially operate on discrete multi-attribute data sets. By means of discretisation or binarization also numerical data sets can be successfully analysed. Therefore, in this paper we view/introduce the theory of (partially defined) discrete functions as an important theoretical tool for the analysis of multi-attribute data sets. In particular we study monotone (partially defined) discrete functions. Compared with the theory of Boolean functions relatively little is known about (partially defined) monotone discrete functions. It appears that decision lists are useful for the representation of monotone discrete functions. Since dualization is an important tool in the theory of (monotone) Boolean functions, we study the interpretation and properties of the dual of a (monotone) binary or discrete function. We also introduce the dual of a pseudo-Boolean function. The results are used to investigate extensions of partially defined monotone discrete functions and the identification of monotone discrete functions. In particular, we present a polynomial time algorithm for the identification of so-called stable discrete functions.