大数据集上基于串行进位链规则提取的矩阵分块算法  

Matrix block computation with serial carry chain for rule extraction in massive data sets

作　　者：程玉胜[1,2] 张佑生[2] 胡学钢[2] 

机构地区：[1]安庆师范学院计算机与信息学院,安徽安庆246011 [2]合肥工业大学计算机与信息学院,安徽合肥230009

出　　处：《中国科学技术大学学报》2009年第2期196-203,共8页JUSTC

基　　金：安徽省自然科学基金(070412061);博士学科点专项科研基金(20050359012)资助

摘　　要：分析现有等价矩阵规则提取算法对于大数据集低效性的根源,提出了一种新的等价矩阵以及根据决策类数目分割大数据集的方法,将条件属性和决策属性等价矩阵合并为一个矩阵,称为联合决策矩阵,该矩阵大大降低了等价矩阵的规模;提出了将大数据集转化为在多个子系统上串行进位链计算流程的规则提取快速矩阵算法,充分体现了人工智能领域中分而治之的思想.理论分析表明该算法在效率上较现有算法有显著提高;相应的对比实验结果表明,这种分治策略的矩阵分块和串行进位链法对大数据集上的规则提取的实用性和高效性.The cause of the existing algorithms＇ inefficiency in rule extraction in massive data sets based on equivalence matrix was analyzed and a new definition of equivalence matrix and the method of division for the massive data set based on the numbers of decision classes were presented. By putting equivalence matrices of both the conditional and the decisional attributes into one matrix, called joint decision matrix, it considerably reduced the size of the matrices. A fast matrix computation algorithm for rule extraction with serial carry chain was thus designed by dividing the massive data set into several sub-systems, which shows the strategy of divide and Conquer in artificial intelligence. Theoretical analysis shows that the algorithm is more efficient than the existing algorithms. An example was used to illustrate the efficiency of the new algorithm. Experimental results show that the matrix block and serial carry chain of the divide and conquer algorithm is not only practical but also efficient.

关 键 词：粗集理论 分治策略 等价矩阵 联合决策矩阵 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]