Identification of Threshold, Regular and Submodular Monotone Systems: Theory and Algorithms

阈值、正则和子模单调系统的识别：理论和算法

• 批准号: 0118635
• 负责人: Endre Boros
• 金额: $ 35.43万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-12-01 至 2005-11-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0118635&HistoricalAwards=false
• 关键词: Identification; Threshold; Regular; Submodular; Monotone

The focus of this research is the development of algorithms, theory, and applications for the identification of all minimal representatives, for implicitly given monotone systems. Such systems are a frequent target of knowledge discovery as they represent important information hidden in large databases, complex networks, etc. Problems involving the determination of monotone systems arise naturally in a multitude of areas including: data mining (finding all maximal frequent, minimal infrequent sets); text mining (finding the best linear query in vector space models); machine learning (finding the best rules or patterns); hypergraph dualization (generating all minimal transversals); reliability theory (generating all minimal working and/or maximal failing states); integer programming (generating all minimal feasible solutions); stochastic programming (constructing deterministic equivalents to certain stochastic models); etc. A coherent theory of identification problems for monotone systems based on several recent mathematical results will be developed. Tractable classes will be outlined, efficient algorithms for such classes created and realized by programs. The resulting new methods will be tested on a variety of applications, such as data mining, logical data analysis, machine learning and text mining.

本研究的重点是发展的算法，理论和应用程序的所有最小的代表，隐式给定单调系统的识别。这些系统是知识发现的常见目标，因为它们代表隐藏在大型数据库，复杂网络等中的重要信息。涉及单调系统的确定的问题自然出现在许多领域，包括：数据挖掘（寻找所有最大频繁集，最小不频繁集）;文本挖掘（在向量空间模型中寻找最佳线性查询）;机器学习（寻找最佳规则或模式）;超图二元论（生成所有最小断面）;可靠性理论（生成所有最小工作状态和/或最大故障状态）;整数规划（生成所有最小可行解）;随机规划（构建确定性等价于某些随机模型）;等。单调系统的识别问题的相干理论的基础上最近的几个数学结果将发展。易处理的类将被概述，有效的算法，这样的类创建和实现的程序。由此产生的新方法将在各种应用程序上进行测试，如数据挖掘，逻辑数据分析，机器学习和文本挖掘。