集值系统基于特定类的广义决策最短约简

近年来，信息技术不断完善并飞速发展，数据呈现出指数型增长趋势，这使得数据挖掘技术效率降低且性能变差。属性约简能去除信息系统中的冗余属性保留重要属性，是一种有效的数据降维方法，而最短约简能最大限度地删除不相关的属性，从而提高系统数据处理和分析的效率。现有在集值系统下的属性约简方法需要所有决策类的参与，算法的效率较低，而一些实际应用中，针对所有决策类的约简可能是非必要的。针对上述问题，本文以集值决策系统为数据背景，给出了特定类广义决策约简的定义，构造了特定类广义决策约简的差别矩阵及差别函数，引入最短约简算法，提出了特定类广义决策最短约简算法，最后使用8组UCI数据集从约简结果、差别矩阵非空项占比以及约简效率三个方法验证了算法的有效性。

粗糙集理论[1] [2] [3] [4]是知识获取的重要工具，可以处理不确定、不完整的知识。作为粗糙集领域的课题研究热点， 属性约简能够消除决策系统中的冗余属性保留重要的属性， 从而减少系统的数据维度， 是一种有效的数据降维方法。经典粗糙集理论通过等价关系实现对单值数据的处理。

集值信息系统是单值信息系统的扩展， 对象在条件属性下的值不是唯一的， 例如一个人可以有活泼、温柔、乐观、大方等多种不同的性格。Guan [5]等提出了集值决策系统中最大相容类相对约简的概念，利用最大相容类定义了上下近似和正域。

Qian 等[6]基于优势关系给出了集值系统的合取和析取两种类型的集值序信息系统，并研究了相应的属性约简和规则提取方法。陈曼如等[7]引入属性无关性和保序性的相关定义，在集值决策系统中提出了快速正域约简的启发式方法。

广义决策的概念由Skowron [8]提出。Zhang 等[9]提出了一种新的广义决策保持的相似度的概念，并在此基础上提出了前向启发式约简算法和后向启发式约简算法。

唐玉凯等[10]在不完备决策系统中提出了基于多特定类的广义决策属性约简的理论框架，并设计了相关算法。最短约简是保证与原系统具有相同分类能力和表达能力的最小属性子集，能最大限度的删除不相关的属性，是包含属性数目最少的属性约简。Zhou 等[11]分析了差别函数中属性出现的次数与最短约简之间的关系，在差别函数的基础上提出了精确计算决策系统最短约简的算法。Yanir 等[12]提出了一种通过剪枝策略高效获取最短约简的算法，该算法能得到决策系统的所有最短约简。由于决策者偏好不同或需求变化，在某些场景下，针对特定决策类的属性约简更有意义。Yao 等[13]提出了基于特定类正域约简的概念。

现有的广义决策约简大都针对决策系统的所有决策类，在集值决策系统中未见有对基于特定类广义决策最短约简的研究。本章在基于相容关系的集值决策系统中给出了特定类广义决策约简的概念，并且结合Zhou [11]所提出的最短约简算法，设计了基于特定类的广义决策最短约简算法。