信息过滤中的特征选择分析

本科毕业论文论文题目： 网络信息过滤中特征选择方法研究 学生姓名： 1 2008 年 5 月 25 日II毕业论文（设计）内容介绍论文（设计）题 目网络信息过滤中特征选择方法研究 选题时间 2008.1.11 完成时间 2008.5.25论文（设计）字数11517关 键 词 网络信息过滤、分词技术、特征选择 论文（设计）题目的来源、理论和实践意义：随着计算机科学与技术的发展，人们越来越认识到信息的价值。在信息爆炸的今天，人们迫切需要一种方法从大量的数据信息中提取并找到有用的信息，网络信息过滤，就是根据用户的信息需求，利用一定的工具从大规模的动态信息流中自动筛选出满足用户需求的信息，同时屏蔽掉无用的信息的过程。对网页信息进行过滤，使网络用户更有效地查找感兴趣的信息，远离非友善信息的侵扰，让网络环境更加纯净、美好，对研究和开发多主题、具有网络信息过滤功能的高效系统十分重要。论文（设计）的主要内容及创新点：本文主要介绍了特征选择的背景及国内外相关研究、网络信息过滤中的分词技术，重点阐述了特征选择的研究及发展方向、典型算法和特征选择技术的改进。本文的创新有三点，首先通过分析分词对特征选择的影响改进分词技术，其次是根据各特征项对文档内容的贡献，我们使用了公式的特征项权值函数来计算特征子集中特征项的权重。最后考虑将特征权值函数应用于特征选择，以获得较好的效果。附：论文（设计） 本人签名： 年 月 日III目 录摘要 .1Abstract.11 引言 .21.1 背景 .21.2 相关研究 .22 网络信息过滤中的相关技术 .32.1 基本概念 .32.2 分词 .32.2.1 分词系统存在的问题 .42.2.2 常用分词算法分析 .52.3 特征选择 .53 特征选择 .63.1 特征选择 .63.2 研究现状及发展方向 .103.3 典型特征选择算法介绍 .113.4 特征选择技术改进 .123.4.1 分词 .123.4.2 特征选择 .143.4.3 权重计算 .154 总结与展望 .164.1 所做的主要工作 .164.2 研究展望 .17参考文献 .181网络信息过滤中特征选择方法研究马娟（山东师范大学信息科学与工程学院计算机系 2006 级 1 班）摘要：网络信息过滤，就是根据用户的信息需求，利用一定的工具从大规模的动态信息流中自动筛选出满足用户需求的信息，同时屏蔽掉无用的信息的过程。分词处理是信息过滤的第一步，分词准确性的高低直接关系到信息过滤后面的一系列操作，因此要引起重视。特征选择就是从一个原始的特征集合中选择一个最优特征子集的过程，这个特征子集应当保留原始特征集合的全部或大部分类别信息。本文阐述信息过滤相关领域国内外的研究现状，研究关于特征选择的相关技术，主要有特征选择的算法、过程等。关键词：网络信息过滤、分词技术、特征选择Research of Feature Selection in Network Information FilteringMaJuan(School of Information Science and Engineering, Shandong Normal University)Abstract: Network information filtering is based on the users information needs, the use of certain tools from large-scale developments in the information flow automatically filter to meet the information needs of users, while shielding out useless information process. Word processing information filtering is the first step, at the level of accuracy of the word directly related to information filtering behind a series of operations, to pay attention. Feature selection is from a collection of original features, select a subset of the best features of the process, this subset of the features of the original features of the collection should be preserved all or most types of information. In this paper, the information filtering related fields at home and abroad of the status quo, study of the feature selection and feature selection algorithm, such as the process. Keyword: Network Information filtering, segmentation, feature selection21 引言1.1 背景Internet 网的迅猛发展改变了人们的生活和思维方式，极大地推动了全球信息化进程。越来越多的信息都在网络上出现，给人们带来了更加快捷的获得信息的途径。人们在享受网络所带来的便利的同时，不可避免地接触到大量的不良信息，如色情、暴力、反动、邪教等。另外，网络中也存在大量冗余信息，没有使用价值却令人们无从下手。信息过滤就是解决这个矛盾的主要方法之一。网络信息过滤，就是根据用户的信息需求，利用一定的工具从大规模的动态信息流中自动筛选出满足用户需求的信息，同时屏蔽掉无用的信息的过程。网络信息过滤具有重要的现实意义和巨大的应用价值。信息过滤可以克服重复查询，避免用户不断地在网络上查询同样的内容，节省了用户大量的时间。信息过滤能实现有害信息的过滤，比如一些反动言论、色情内容；能实现垃圾信息过滤，比如常见的垃圾邮件；能实现有用信息推荐，比如可以根据不同用户之间需求的相关性来推荐信息。人们迫切需要一种方法从大量的数据信息中提取并找到有用的信息，数据特征选择就是在这种情况下诞生的。特征选择就是从一个原始的特征集合中选择一个最优特征子集的过程，这个特征子集应当保留原始特征集合的全部或大部分类别信息。特征选择涉及两个关键问题：一是有效的特征子集的搜索策略；二是合适的评价标准。首先按某种搜索策略得到一个特征子集，然后使用选定的评价准则对此子集做出评价或比较，以决定是保留还是放弃。此过程反复进行，直到找到一个满意的特征子集。特征选择的过程可以手动进行或通过一些自动化程序进行。1.2 相关研究1982 年，Denning 提出信息过滤（ Information Filtering）的概念 5。他描述了一个信息过滤的实例，在电子邮件系统中，利用过滤机制区分紧急的邮件和一般的例行邮件，Denning 构造了一种 “内容过滤器” ，采用的主要技术包括有层次组织的邮箱、3独立的私人邮箱、特殊的传输机制、阈值接受、资格认证等。随着因特网的迅速发展，研究领域也从最初的电子邮件延伸到其他相关领域，在文本过滤以及相关技术方面，取得了长足的进展，许多文本过滤系统相继开发完成。如 Standford 大学开发的 SIFT 系统、基于协作过滤的系统 Tapestry 和 Grouplens2。也有一些过滤方案试图将内容过滤和协作过滤相结合，如 Fab 系统就是结合了内容过滤和协作过滤两种模式的典型系统，该系统用于推荐网页。2 网络信息过滤中的相关技术2.1 基本概念网络信息过滤是根据一定的标准运用一定的工具从动态的网络信息流中选取用户需要的信息或剔除用户不需要的信息的方法和过程。这个定义包涵了如下几个方面的内容：(1) 信息过滤的对象是动态的网络信息流；(2) 信息过滤的目的是要满足特定用户的信息需求；(3) 信息过滤的依据是信息与用户信息需求的相关性；(4) 信息过滤从网络信息流中选取需要的信息，也从中剔除不需要的信息。网络信息过滤的主要方法：(1) 分级法(2) URL 地址列表法(3) 动态文本分析法2.2 分词分词处理是信息过滤的第一步，分词准确性的高低直接关系到信息过滤后面的一系列操作，因此要引起重视。由于中文文档没有明显的分隔符的存在，所以在特征提取之前要首先进行分词处理。42.2.1 分词系统存在的问题(1)歧义分解分词系统要处理的一个关键问题是文本中歧义切分字段的判别。汉语中歧义切分字段最基本有以下两种类型：a.交集型歧义：在字段 ABC 中，这里，A,B,C 分别代表有一个或多个汉字组成的字串。A,AB,BC,C 分别都是词表中的词，则称该字段为交集型歧义字段。b.组合型歧义：在字段 ABC 中，A,B,AB 分别都是词表中的词，则称该字段为组合型歧义字段。这里我们介绍几种最主要的歧义切分算法： 全切分：全切分算法可以给出一个句子所有可能的切分结果。由于全切分的结果数随着句子长度的增加呈指数增长，因此这种方法的时空开销非常大。 最大匹配：从左到右或从右到左，每次取最长词，得到切分结果。分为前向最大匹配、后向最大匹配和双向最大匹配三种方法。但最大匹配法无法发现组合型歧义（覆盖歧义） ，对于某些复杂的交集型歧义（交叉歧义）也会遗漏。 最短路径法：采用动态规划方法找出词图中起点到终点的最短路径，这种方法比最大匹配法效果要好，但也存在遗漏的情况。(2)未登录词识别因为语言在不断的发展和变化，新词不断的出现、衍生，词表中不能囊括所有的词，这就要求分词系统具有一定的未登录词识别能力，提高分词的正确性。所谓未登录词主要是指分词系统的词典中未收录的词。主要来源于：a.命名实体：人名、地名、组织机构名、外国译名、术语等，如：林徽因。b.新出现的词汇、术语、个别俗语等，例如：博客，禽流感。c.关于中文姓名、地名：目前使用的用字范围广，分布松散，规律不明显。现有的未登录词解决方案主要有以下几种：a. 建立专有名词词库。例如对中文姓名的识别，建立中文姓名词库。5b.利用上下文信息识别未登录词。主要利用人名前或后加的一些限制成分。c.有穷多层列举法。建立单字词和多字词表(不包括双字词)，分词时先把这些词切分出来，剩余的字串，每两个字切一刀；用此来换取客观分词的效果。d.语料库统计方法。利用汉字的共现概率从语料中自动提取出生词，实现无词典分词，但对普通词的识别却并不理想。e.局部统计策略。未登录词往往在局部上下文中出现的频率较高，通过计算它共现的频率来识别未登录词，但很难识别只出现一次的未登录词。2.2.2 常用分词算法分析以上我们大致了解了分词系统所面临的关键问题，下面介绍三种分词算法：(1)基于字典的字符串匹配方法这种方法又称机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功（识别出一个词） 。(2)基于统计的分词首先切分出与词表匹配的所有可能的词，然后运用统计语言模型和决策算法决定最优的切分结果，可以发现所有的切分歧义，但是解决歧义的方法很大程度上取决于统计语言模型的精度和决策算法。(3)基于规则和基于统计相结合首先运用最大匹配作为一种初步切分，再对切分的边界处进行歧义探测，发现歧义。再运用统计和规则结合的方法来判别正确的切分，运用不同的规则解决人名、地名、机构名识别，运用词法结构规则来生成复合词和衍生词。2.3 特征选择特征选择是统计学领域的经典问题，自上个世纪 60 年代起就有学者对特征选择问题进行研究 3-5。特征选择也是机器学习领域的重要问题，对机器学习领域的所有问题都有重大意义，包括文本分类，数据挖掘，生物信息学，计算机视觉，信息检索6等。特征选择就是一个从原有的特征集合中选择一个(相对某种评价准则)最优特征子集的过程。这个特征子集应当保留原有特征集合的全部或大部分类别信息 1-5。分词将文档表示为词的形式，然而训练集中包含了大量的词汇，如果把这些词都作为特征，将带来一系列问题。首先是向量的维数太大，给计算带来了非常大的压力，存储空间大、处理速度慢。其次是这些词中实际上有很大一部分是与类别无关的，对分类作用不大，甚至存在较大副作用。因此，我们要降低向量的维数，选择那些有代表意义的词作为特征。先对文本进行预处理，去掉那些常用的对分类用处不大的词（称为停用词，stop word） ，然后采用某种特征选择方法对所有的词排序，选出排在前面的一定数量的词作为特征。特征选择的一般过程如图 2.1 所示。子集产生 子集评估结果有效性验证子集否是子集的优势度原特征集合停止准则 则图 2.1 特征选择的一般过程3 特征选择3.1 特征选择对于特征选择的不同方法，按机器学习的方式不同，可分为有指导的特征选择和无指导的特征选择。无指导的特征选择是指在数据集中，通过数据集中的特征之间自身的关系进行特征选择的方式。有指导的特征选择是指在给定类别的前提下，利用特7征之间和特征与类别之间的关系对特征集进行选择的过程。本文就是针对有指导的特征选择做出的研究。文档分类使用的方法，是有指导的学习方法。也就是说，我们有一组事先知道类别的文档作为训练样本，根据这些样本，我们可以建立一个分类模型，利用该模型，可以求得未知类别的文档的类别。文档分类的基本原则，是找到同一类别的文档的特征，当未知类别的文档到来时，比较其特征，将其归入特征最相似的一类。特征选择涉及两个关键问题：一是有效的特征子集的搜索策略；二是合适的评价标准。首先按某种搜索策略得到一个特征子集，然后使用选定的