一种基于svd和rough集的信息过滤方法-centerforcombinatorics.doc

一种基于SVD和Rough集的信息过滤方法*陈彩云 李治国 南开大学组合数学研究中心，天津 300071 摘 要 本文提出了一种信息过滤方法，即在奇异值分解（SVD）的基础上，运用粗糙集（Rough Sets）理论进行信息过滤。通过对词语×文档矩阵进行奇异值分解得出近似矩阵，改变了一些词语在相应文档中的重要性，从而使得词语更好的体现文档内容。然后运用粗糙集理论中决策表上的规则推理方法，生成我们感兴趣信息的规则库，将未知文的条件属性与规则库里规则进行相似匹配，进行信息过滤。 关键字： 奇异值分解 粗糙集 信息过滤 规则提取 引言 随着因特网上信息量的迅速增加，人们往往为了找到自己需要的信息花费大量的时间和精力，如何能够更有效的，更准确的找到自己感兴趣的信息，滤除与自己的需求无关的信息已经成为基于Internet网络信息处理的当务之急。随之产生的信息过滤技术正得到越来越广泛的关注，信息过滤系统根据用户的信息需求对动态信息流进行过滤，仅把用户的文档传送给用户，可以提高获取信息的效率，对信息过滤主要的需求是对文档与用户信息需求相关性的判断要准确，同时查全率也需要提高。本文提出了一种信息过滤方法，在奇异值分解的基础上，运用粗糙集理论中规则推理方法，建立信息过滤的规则库，对于任意一个未知文，我们只要将其条件属性与规则库中的规则进行相似匹配，进行过滤。实验证明该方法较传统的向量法和LSI方法都要好。 粗糙集相关理论 粗糙集是波兰Z. Pawlak教授提出的一种数据推理方法[1]。该理论为发现重要数据结构和复杂对象的分类提供了强有力的基础。我们首先描述与本文相关的粗糙集理论中的一些概念。（下面提到的概念和符号源自文献[2]） 2.1 信息系统（Information System） 信息系统由4元集组成，记为，其中： ：由个研究对象组成的非空集合，称为闭域（Closed Universe）； Q：由n个属性组成的有限非空集合； ：表示Q中所有属性的值域，其中是属性的值域。 ：全决策函数（Total Decision Function），使得对于任一，，有。通过作用，信息系统S能用一个有限的数据表表示，表的第i行研究对象和第j列属性有对应的值。 2.2 决策表（Decision Tables） 如果信息系统的属性集Q可以分成互不相交的条件属性集C和决策属性集D，即满足且，满足这样条件的信息系统称为决策表，记。一般情况下，集合D包含多个决策属性，但是在本文中根据研究的需要，我们只包含一个决策属性d，即D={d}。通过决策表，我们就可以对数据集进行规则推理。下面的过滤方法就是在决策表的基础上进行规则推理的。 奇异值分解（SVD） 给定m×n的矩阵M，可以分解成三个矩阵的乘积，其中U和V分别为和的正交矩阵，S为对角矩阵，S的非零对角元叫做矩阵M的奇异值，r为非零对角元的个数。 定义m×n矩阵，其中由U的前k（）列列向量组成的m×k的矩阵，由S的前k个最大的奇异值组成的k×k的对角矩阵，由V的前k列列向量组成的n×k矩阵。由此构造的矩阵秩为k的矩阵中与M距离最近的矩阵，称之为秩为k的最好近似矩阵[3]。 构造信息过滤方法 第一步：准备数据，建立词语-文档矩阵（Term-Document）[4]M 首先我们收集一定数量的文档数据集。将之分成训练集和测试集，一般情况下，取所有文档的0%-80%作为训练集，其它的作为测试集。假设有m个文，选取n个关键词语，建立词语-文档矩阵M，矩阵的每一行代表一个文档，每一列代表词语在文档中的出现的频率，即M=(mij) ，mij表示第j个词语在第i个文档中出现的频率。 第二步：将该矩阵M进行奇异值分解，构造秩为k的最好近似矩阵Mk 我们将矩阵M进行奇异值分解，估计文档使用的词语结构。分解M得到，再构造秩为k的最好近似矩阵，其中，r是非零奇异值的个数。通常情况下，我们面临的数据量是很大的，而使用奇异值分解，使我们找到了M的秩为k的最好近似矩阵Mk，从而降低了词语-文档的空间维数。 通过这样的变换，使得原来比较稀松的词语-文档矩阵变得稠密，改变了不同的词语在不同文中的相对比重，从而使词语能更好的表达文档的内容。同样对于任何一篇新的文章，我们统计n个关键词在该文章中出现的频率，得到n的向量，可以通过公式变换，将转化成词语-文档向量空间的向量的形式。第三步：构造决策表DT，生成决策规则 我们用上面预处理过的文档数据来构造决策表。表示一个决策表，其中闭域U是由词语-文档矩阵中m个文档组成，条件属性集C由词语-文档矩阵M的n个词语作为条件属性构成，决策属性集D={d}由文的类别属性构成。值域，其中条件属性的取值我们直接取M 的最好近似矩阵Mk的值，即，决策属性的取值根据我们感兴趣的或者是有价值的文档的属性决定，可以分别用文档的属性