（模式识别与智能系统专业论文）农业搜索引擎中的异常数据检测.pdf

摘爨 摘要 随着农业信息化的快速发展，互联网上的涉农信息快速增加。据不完全统计， 目前我国有超过3 0 0 0 0 个涉农网站。然而这些网站上的信息大多是无组织、多结 构、动态的，这严重影响了农业信息个性化服务的发展。在国家重大科技支撑项 目子课题“基于本体的农业搜索引擎”( 2 0 0 6 b a d l 0 a 0 5 0 2 ) 的支持下，我们研究 丌发出了针对农业的垂直搜索引擎“搜农”。实践证明，该垂直搜索引擎能够为 用户提供完善的个性化服务。 随着农业信息的爆炸式增长，异常数据也在大量增加，异常数掘的存在大大 降低了垂直搜索引擎个性化服务的质量。这些异常数据包括模糊数据、不完整数 据以及取值异常的数据等。针对不完整数据，( 刘峰等2 0 0 9 ) 提出了一种不完 整数据的处理方法，并把此方法应用于“搜农 搜索引擎中。实际应用表明，该 方法能够很好的工作。本文将重点研究如何识别农产品价格数据数值上的异常。 本文重点研究了针对农产品价格数据的异常数据检测方法。本文首先简要介 绍了常用异常数据检测方法，把这些常用的异常数掘检测方法进行一定的修改以 应用于农产品价格数据；同时本文对农产品价格数据的特征进行了详细的分析， 并根据该数掘特征提出了一种针对农产品价格数据的异常数据检测方法；最后对 各个检测方法做了实验。实验表明，本文提出的针对农产品价格数据的异常数据 检测算法能够很好的完成任务。 同时，本文研究了如何把异常数据检测算法应用于垂直搜索引擎中。本文详 细分析了该垂直搜索引擎的系统架构，并着重阐述了该搜索引擎的数掘流向，在 此分析基础上，详细讲述了如何把异常数据检测系统完好的融入已有系统，实现 各子系统的对接。最后，本文分析了该异常数据检测系统的特性，详细分析了添 加该异常数据检测系统后的垂直搜索引擎的数据流向。实际应用表明，添加了异 常数据检测系统的垂直搜索引擎，能够为用户提供更高质量的个性化服务。 关键词：垂直搜索异常数掘检测农产品价格农业信息化 a b s t r a c t a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fi ta p p l i c a t i o ni na g r i c u l t u r e ，i n f o r m a t i o no f a g r i c u l t u r eo nt h ei n t e r n e t i si n c r e a s i n gr a p i d l y a c c o r d i n gt oi n c o m p l e t es t a t i s t i c s ， t h e r ea r em o r et h a n3 0 ，0 0 0a g r i c u l t u r e r e l a t e ds i t e si nc h i n a b e c a u s em u c ho ft h e i n f o r m a t i o no nt h e s es i t e si s u n o r g a n i z e d ，m u l t i s t r u c t u r e d a n dd y n a m i c ，t h e p e r s o n a l i z e ds e r v i c eq u a l i t yo fa g r i c u l t u r a li n f o r m a t i o ni sr e d u c e d av e r t i c a ls e a r c h e n g i n ef o ra g r i c u l t u r e s o u n o n g ”i sd e v e l o p e dw i t ht h es u p p o r to fp r o j e c tw h i c hi s g r a n t e d n o 2 0 0 6 b a d10 a1410n a m e d “a na g r i c u l t u r es e a r c h e n g i n eb a s e do n o n t o l o g y ”t h i sr e s e a r c h i s s u p p o r t e db y t h en a t i o n a ls c i e n c ea n dt e c h n o l o g y a p p l i c a t i o ns h o w st h a tg o o dp e r s o n a l i z e d s e r v i c eo fa g r i c u l t u r a li n f o r m a t i o ni s p r o v i d e db yt h i sv e r t i c a ls e a r c he n g i n e w i t ht h ee x p l o s i v eg r o w t ho fa g r i c u l t u r a li n f o r m a t i o n ，a b n o r m a ld a t ai sa l s o g r e a t l yi n c r e a s e d t h e s ea b n o r m a ld a t ai n c l u d ef u z z yd a t a , i n c o m p l e t ed a t aa n d a b n o r m a lv a l u ed a t a f o rt h e s ea b n o r m a li n f o r m a t i o n ，( l i uf e n g ，e t c 2 0 0 9 ) p r o p o s e d at r e a t m e n to fi n c o m p l e t ed a t a t h i st r e a t m e n ti sa p p l i e dt ot h ev e r t i c a ls e a r c he n g i n e ； t h ea c t u a la p p l i c a t i o ns h o w st h a tt h i sm e t h o dc o u l dw o r kw e l l t h i sa r t i c l ef o c u s e so n h o wt oi d e n t i f ya g r i c u l t u r a lp r i c ed a t aw h i c hh a sa b n o r m a lv a l u e t h i sp a p e rf o c u s e so nt h eo u t l i e rd e t e c t i o nm e t h o df o ra g r i c u l t u r a lp r i c ed a t a f i r s t ，t h i sp a p e ri n t r o d u c e sc o m m o no u t l i e rd e t e c t i o nm e t h o d sb r i e f l y , a n da p p l i e s t h e s em e t h o d s a n a l y s i so nt h e t ot h ea g r i c u l t u r a lp r i c ed a t a t h i sp a p e ra l s o f e a t u r e sad e t a i l e d c h a r a c t e r i s t i c so ft h ea g r i c u l t u r a lp r i c ed a t a a c c o r d i n gt ot h e s e c h a r a c t e r i s t i c s ，an e wm e t h o do fa b n o r m a ld a t ad e t e c t i o nl sp r e s e n t e d a l s o ，w e c a r r i e do u te x p e r i m e n t so ft h e s em e t h o d s a c c o r d i n gt ot h e s ee x p e r i m e n t s ，t h e p r o p o s e do u t l i e rd e t e c t i o na l g o r i t h mf o ra g r i c u l t u r a li n f o r m a t i o n c a r lw o r kw e l l h o wt oa p p l yo u t l i e rd e t e c t i o na l g o r i t h mt ov e r t i c a ls e a r c he n g i n e si sd i s c u s s e d i nt h i sp a p e rt o o t h es y s t e ma r c h i t e c t u r eo fv e r t i c a ls e a r c he n g i n e si sa n a l y z e d ，a n d t h ed a t af l o wo ft h es e a r c he n g i n ei sd i s c u s s e dt o o b a s e do nt h ea n a l y s i s ，h o wt o i n t e g r a t et h i ss u b s y s t e mt ot h e v e r t i c a l a p p l i c a t i o ns h o w st h a tt h es y s t e mw h i c h p r o v i d eh i 曲q u a l i t yp e r s o n a l i z e ds e r v i c e s e a r c he n g i n es y s t e mi sp r e s e n t e d t h e h a sa b n o r m a ld a t ad e t e c t i o ns y s t e mc a l l k e yw o r d s ：v e r t i c a ls e a r c he n g i n e ，o u t l i e rd e t e c t i o n ，a g r i c u l t u r a lp r i c ed a t a ， a g r i c u l t u r a li n f o r m a t i o n i i 中囝科学技术入学学位论文原创悻和授十义使用声l j 中国科学技术大学学位论文原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作 所取得的成果。除己特别加以标注和致谢的地方外，论文中不包含任 何他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究 所做的贡献均己在论文中作了明确的说明。 本人授权中国科学技术大学拥有学位论文的部分使用权，即：学 校有权按有关规定向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅，可以将学位论文编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 保密的学位论文在解密后也遵守此规定。 作者签名： 年月日 第一帝绪论 1 1 选题背景及意义 第一章绪论 随着互联网的快速发展，数以千亿的网页出现在互联网上。由于这些网页包 含着大量的信息，使得互联网已经成为真f 的海量信息源。然而互联网上的数据 多数是无组织、多结构、动态的，并且由于信息是动态增加的，导致了保存的信 息是变化的、模糊的，甚至是不完整的，这些都严重的影响了互联网信息服务的 发展：同时，由于互联网上的数据是海量的，人们面临着“信息过量”的问题， 这使得人们不z 日- , , 匕匕，t b 方便的找到自己真f 需要的信息。因此，如何高效、精准的从 海量信息源上查找用户真正需要的信息，成为互联网用户的一大难题。搜索引擎 帮助他们解决了这一难题。 搜索引擎主要分为全文搜索引擎、目录索引类搜索引擎和元搜索引擎。憎洲。 然而这三类搜索引擎都存在以下几点缺陷i 1 ( 1 ) 查准率无法得到保证。用户在 使用时往往不能用简单的词汇来表达自己想要搜索的内容，导致搜索出的内容很 大一部分跟用户的本意是不相符合的，使得用户要花很长时问去寻找自己真f 需 要的信息，甚至会导致用户对搜索引擎感到绝望；( 2 ) 搜索引擎查询出的信息是 一个指向该信息的网址而不是用户真f 需要的信息；( 3 ) 查全率得不到保障。由 于网页数量呈几何式增长，使得搜索引擎很难覆盖所有相关网页。据统计，单个 搜索引擎的覆盖率一般都低于3 0 ，很少能够覆盖所有网页。 在此背景下，垂直搜索引擎 2 3 4 1 得以发展。垂直搜索引擎是针对某一个行业 的专业搜索引擎，是搜索引擎的细分和延伸。垂直搜索引擎对网页库中的某类专 门的信息进行整合，定向分字段的抽取出需要的数据进行处理后再以某种形式返 回给用户。垂直搜索引擎是相对通用搜索引擎的信息量大、查询不准确、深度不 够等提出来的新的搜索引擎服务模式。垂直搜索引擎的特点就是“专、精、深”， 且具有行业色彩，相比较通用搜索引擎的海量信息无序化，垂直搜索引擎则显 得更加专注、具体和深入。 随着我国农业信息化的发展，全国共有超过3 0 0 0 0 个涉农网站。竹1 。这使得 互联网上积累了丰富的农业技术、农产品价格信息、供求信息、政策法规、农业 新闻等信息资源。这些网站由于信息资源缺少统一的形式化表达方法与网页格 式，使得网页信息资源异质、异构、分散i 重复现象严重，形成所谓的“信息孤 岛 ，这样就很难发挥农业信息资源的最大效用。同时考虑到我国农户的文化基 础、计算机操作水平以及农业网络信息服务的复杂性，要求“三农”用户利用传 第一章绪论 统的搜索引擎去直接搜索、捕捉和筛选其需要的真实信息，不仅是不现实的，也 是不可能的。因此，建立专业化以及高度智能化的农业垂直搜索引擎意义重大。 在国家重大科技支撑项目子课题“基于本体的农业搜索引擎” ( 2 0 0 6 b a d l 0 a 0 5 0 2 ) 的支持下，我们研究开发出了针对农业的垂直搜索引擎“搜 农”( h t t p ：w w w s o u n o n g n e t ) f 5 】，实践证明，该垂直搜索引擎在查准率和查全率 上都要远远优于现有的通用搜索引擎。 然而，随着互联网的快速发展，互联网上的信息呈爆炸式增长，在信息量增 加的同时，一些瑕疵数据也在急剧增加，比如一些不完整数据，甚至一些错误数 据也在大量增加。这些异常数据的存在大大降低了垂直搜索引擎的个性化服务的 质量，因此，如何把搜索引擎采集到的数据进行适当的处理，检测出这些异常数 据就显的尤为重要。 在我们的垂直搜索引擎“搜农”( h t t p ：w w w s o u n o n g n e t ) 中，随着全国涉农 网站的大量涌现，涉农数据大量增加，这同时也导致了大量异常数据的增加。本 文主要研究农产品价格数据，该价格数据采集自全国各个涉农网站，但是有很多 原因造成了我们采集到的数据是有异常的。这些异常主要有数据信息的不完整和 数据本身的错误。( 刘峰等2 0 0 9 ) 提出了一种不完整数据的处理方法，并把此 方法应用到了“搜农 搜索引擎中，实际应用表明，该方法能够很好的工作。本 文将重点研究如何识别农产品价格数据取值的异常。针对农产品价格数据，其异 常性主要表现在该价格数据严重偏离了其应该属于的数据域。例如我们采集到的 一条黄瓜的价格可能是1 0 0 0 元公斤。在我们采集到的价格数据中，存在着大量 的这种异常数据，如果我们不能够识别出这些异常数据，那么由于这些异常数据 的存在可能会导致大量用户的流失。 因此，我们要寻求一种能够应用于农产品价格数据的异常数据检测方法。目 前，常用的异常数据检测算法有基于统计的算法、基于距离的算法、基于聚类分 析的算法等等。然而，当我们把这些常用的异常数据检测算法应用于农产品价格 数据时，却发现效果十分不理想。通过分析，我们发现农产品价格数据具有其自 身非常明显的特征，正是由于这些特征的存在，使得这些常用的异常数据检测算 法不能够很好的工作。因此，我们在进行异常数据检测时应该充分考虑这些数据 的特征，根据这些数据特征研究出一种能够很好工作的异常数据检测算法。 1 2 主要研究内容 1 2 1 异常数据检测算法 2 第一章绪论 本文重点研究了农业垂直搜索引擎中异常农产品价格数据的检测方法。目i 对于异常数据的检测方法，主要有：基于统计的方法、基于距离的方法以及基于 聚类分析的方法。本文对各个常用的异常数据检测算法进行了详细的分析，并把 它们进行一定的修改以应用于农产品价格数掘。 对于基于统计的方法，本文首先描述了基于统计的异常数据检测算法的基本 思想，并着重阐述了基于统计的异常数据检测算法的优缺点。根据这些优缺点， 本文提出了一个基于f 态分布的异常数据检测算法，并把该算法应用于农产品价 格数据。实际应用表明，该算法能够检测出异常数据，但效果却并不理想。 本文对基于距离的异常数据检测算法进行了阐述，并分析了基于距离的异常 数据检测算法的要点，同时根据农产品价格数据的特征，提出了一个基于距离的 异常农产品价格数据的检测算法，并把它应用于农产品价格数据。实际应用表明， 该方法同样能够检测出异常数据，但是效果也不够理想。 同时，本文研究了如何把聚类分析的思想应用于异常数据检测，并根据农产 品价格数据的特征提出了一个基于聚类分析的异常农产品价格数据的检测算法。 然而，当我们把以上提出的异常数据检测算法应用于农产品价格数据时，却 总达不到理想的效果。通过分析，我们发现农产品价格数据具有其自身非常明显 的特征，正是由于这些特征的存在，使得这些常用的异常数据检测算法不能够很 好的工作。因此，我们详细分析了农产品价格数据的基本特征，并根据该特征提 出了一种针对农产品价格数据的异常数据检测算法。 我们把以上提出的异常数据检测算法应用于农产品价格数据，并做了实验。 本文详细描述了实验方法以及实验结果，并对实验结果做了详细的分析。 1 2 2 异常农产品价格数据检测系统 由于本文所研究的异常数据检测系统是一个在已有系统上添加的新系统，因 此要充分考虑该子系统与其他系统之间的关系。本文首先详细介绍了异常数据检 测系统在垂直搜索引擎中的位置，并详细说明了异常数据检测系统的工作过程。 本文重点分析了农业垂直搜索引擎中数据的流向，并在此基础上设计了异常数据 检测系统的数据流向。 对于异常数据检测算法来说，不可避免的会遇见误判问题，产生误判的原因 有很多，有些是异常数据检测算法自身的问题，有些是数据采集的问题，而有些 则是参考数据的问题。本文通过对垂直搜索引擎中数据流向的分析，设计出了异 常数据检测系统的数据流向，确定了参考数据的数据源。实际应用表明，该参考 数据的数据源能够提供相对较好的参考数据。 第一帝绪论 1 。3 论文的组织 本文重点研究了农业搜索引擎中异常农产品价格数据的检测方法。本文首先 简单介绍了本研究的背景及意义，接着介绍了常用的异常数扼检测方法，之后着 重分析了农产品价格数据的基本特征，根据该特征提出了一种有效的异常数据检 测方法，最后本文研究了如何把异常数据检测算法应用于农业垂直搜索引擎。本 文的组织结构： 第一章：绪论。介绍了本文的研究背景和研究方法。 第二章：背景知识和相关方法。着重介绍了与本文相关的一些背景知识和相 关方法。 第三章：农产品价格异常数据检测算法。分析了常用的异常数据检测算法， 并把这些算法应用于农产品价格数据，最后对这些算法进行了实验，并进行了实 验分析。 第四章：农产品价格数据异常检测系统。详细分析了农业垂直搜索引擎的系 统结构，在此基础上分析了异常检测系统在该搜索引擎中的位置，并着重分析了 添加该异常数据检测系统后的垂直搜索引擎的特性。 第五章：总结与展望。对本文进行了总结，并做了进一步的展望。 4 第二章相关投术背景 第二章相关技术背景 本章主要介绍了垂直搜索引擎丌发所需要的基本技术。本章首先对搜索引擎 的基本框架结构进行了简单介绍，同时简要描述了全文检索l u c e n e 的系统架构， 其次简单的介绍了常用的异常数据检测算法，并对各个常用算法做了简要说明。 2 1 搜索引擎的通用系统结构 搜索引擎是一个根据用户输入的查询请求，通过一定算法为用户提供查询结 果的软件系统。它首先从互联网上抓取网页，并以此建立索引数据库，当用户提 交其要查询的内容时，系统从索引数据库中检索用户要检索的信息，并通过一定 的处理和排序把查询结果展现给用户。 因此搜索引擎的实现m l 也舢主要分为四个基本步骤： 1 从互联网上抓取网页。在此步骤中需要一个称之为网络蜘蛛的程序，该程 序能够自动收集互联网上的网页，并能够沿着任何网页中的超链接爬到其他网页 上，重复该过程，并把访问过的网页收集到后台服务器中。 在该过程中，网页分析程序首先把采集到的h t m l 文档进行分析，提取 出其中的信息。这些信息包括该网页内容中的关键词、关键词所在的位置、网页 的u r l 、网页所采用的编码形式等。 2 建立索引数据库。该步骤把步骤l 中从互联网上获得的网页进行分析，提 取出网页中的信息，通过计算得到每个页面内容与超链接中每一个关键词之白j 的 相关度，再以此建立网页索引数据库。 在建立索引数据库时，要对这些数据进行一定的处理。这些处理包括对信息 进行清洗。由于抓取网页时，一个网页有可能被抓取多次，因此，在该过程中要 对数据进行消除重复等清洗工作。同时，由于各种原因，采集到的数据有可能是 错误的，因此作为信息提供者我们有责任把这些错误信息剔除，或者把这些信息 进行标记。 3 检索用户输入 当用户输入关键词后，系统首先分解该搜索请求，然后根据该分解后的搜索 请求对索引数据库进行查询，从中查找出与用户所提交请求最为相关的网页。 在该过程中，需要对用户的输入进行分解。体现在搜索引擎系统中，即需要 对用户提交的查询条件进行分词n l 删。因此，搜索引擎系统中需要一个好的分词 系统。分词系统的主要任务就是找到用户提交信息中的关键词，然后根据该关键 词在索引数据库中进行查询。 * 一 t 一* m $ n 4 查询结果的展示 泼过程剐步骤3 中检索到的信息进行处理“5 。，井对结果进行排序然后系 统把排序后的结果展示给用户。 在醣过程中，需要一个排序算法。在全文检索搜索引擎中通常有个相似度 计算程序，该程序计算所查询信息与网页关键词之闻的相似度，通过该相似度对 检索结果进行排序，把相似度最高的检索结果放在榆索结果的前面。最后把搜索 到的结果组织起柬显示给用户。 从以上所述知道，搜索引擎主要有信息采集系统、索引系统和检索系统构成。 由以上描述可以知道，搜索引擎的系统结构如图21 所示。 l 竺竺：竺i 圈2 , 1 通削搜索引擎结构酗 22 全文检索框架l u o e n e 技术概述 本文所描述的搜索引擎是一个基于l u c e n e “”架构的垂直搜索引擎，因此本 节简要介绍一下全文检索框架l a c e n e 。 l u c e n e 是一个可以免费使用的全文检索引擎工具包而不是一个完整的可 以直接使用的全文检索引擎它是一个a p a c h e 软件基金会下面的开源项目。 l u c e n e 提供了完整的查询引擎、索引引擎以及部分分析引擎。由于其是一个开 源软件因此它具有一般开源软件所具有的优点：功能和结构的透明性、具有很 好的可扩展性、具有较强的技术支持。l u c e n e 也有其自身的优点，首先它是一 个功能强大并且简单易用的软件包，它有一个简单的a p i 这使得用户可以很容 易的在自己的应用程序中实现查询、索引以及分析功能。其次，它有清晰的架构， 并且易于学习和扩展，用户可以根据自己的需要对系统进行扩展。l u c e r l c 具有 j 磊t 第二市拥关技术背景 强大的文件索引功能，它的索引文件独立于应用平台，因此该索引文件可以跨平 台进行共享。同时它实现了分块索引，因此获得了高速和优化的索引功能。同时， l u c e n e 还支持多种文档格式和多种不同的语言。 l u c e n e 工具包中，包含了几个实现了搜索引擎基本功能的子包。这些功能 子包有语言分析子包、存储管理子包、索引管理子包、查询分析子包、数掘存储 子包、检索功能子包以及一些常用工具子包。每个子包中的类实现了一定的功能。 语言分析子包中，包含了一些对语言进行分词的类。在文档建立索引之前， 分词是一项必须进行的工作。所谓分词就是指对一组输入文本，进行一定的切割， 以找到该文本中所包含的词语或者短语，力求找到该文本所要表达的语义。在 l u c e n e 中，目前较为成熟的是对英语进行分词，包括根据空格和停用词进行分 词的技术，而并没有很成熟的中文分词。 存储管理子包中，包含了一些对索引文档进行管理和操作的类。该工具包向 用户提供了一个完整的索引文件的逻辑结构，通过它当中的类，可以很明了的理 解一个索引文档的组织结构。它还包含了一个能够对时l 日j 进行转换的工具类，该 工具类能够对文档中的时间字段进行操作。同时它还提供了一个能够控制索引文 档如何加载的类。 索引管理子包提供了管理索引文档的功能。包括索引文件的建立、索引文件 的删除、索引文档的修改以及索引文档的加锁解锁等等功能。同时，该包实现了 索引文档分片以及合并的功能，并因此获得了高速和优化的索引功能。 查询分析子包提供了查询分析器的功能。该包实现了查询中关键词之间的逻 辑运算，同时它提供了对一个查询的解析功能。 数据存储子包实现了对数据的存储功能。这些功能主要包括了一些底层的 i 0 操作。它为用户提供了一个完善的数据存储功能，它同时提供了内存存储以 及硬盘存储功能，以及这两个存储之间的相互转化功能。在程序运行期间，我们 可以把数据存储在内存中，当程序快要运行结束时，我们再把数据从内存中写到 硬盘中，这样就有效的减少了i 0 操作次数，提高了系统的效率。 检索功能子包向用户提供丰富的检索功能。它实现了范围查询、模糊查询、 组合查询等等功能，同时提供了查询结果的集合类，这样我们就能够方便的对查 询结果进行操作。该功能子包还提供了对检索结果进行排序的功能，这使得我们 可以按照我们自己的意愿对检索结果进行排序。 以上简要介绍了l u c e n e 的基本功能，本文所描述的垂直搜索引擎就是建立 在l u c e n e 的基础上的。 2 3 常用异常数据检测方法 第_ 二帚相关技术背最 目前，对于异常数据的检测方法，主要有：基于统计的方法、基于距离的方 法、基于偏离的方法以及基于聚类分析的方法。 2 3 1 基于统计的方法 基于统计的方法邑“。川是最早的异常数据检测方法，同时也是最为成熟的异 常数据检测方法。其基本思想是：首先假设被检测数据服从某种分白，给出分布 模型；然后根据已有观察数据来对未知参数进行估计，使用假设检验的方法来计 算出精确的或者近似的概率分布模型；最后根据该概率分布模型束计算某个特定 值取值的概率，并根据一个先验阈值来判断一个数据是否是异常的。 基于统计的异常数据检测方法有其自身的优点。首先其捐j 有完善的数学理论 基础，其次现实中有很多待检测数据的全体确实服从某种分布。这使得基于统计 的异常数据检测方法得到了很大的发展。然而，基于统计的异常数据检测方法也 有其自身很多缺点，这些缺点主要有三个：大多数异常数据检测算法都是针对 某一个单属性，然而许多异常数据的检测是要求在多维空间中发现异常；在使 用该方法的时候，我们要先知道分布，或者知道数据的近似分御。然而实际上数 据的分布情况我们是不知道的，因此当没有特定的检验时，该方法不能确保发现 所有的异常数据；该方法通常只能对数值型数据进行异常挖掘，对高维数据、 周期性数据却不能够很好的工作。虽然我们可以把一些非数值型的数据映射到数 值型数据，然而我们要花费很大的功夫去寻找一个合适的映射关系。 2 3 2 基于距离的方法 基于距离的异常定义是由e k n o r r 和r n g 与1 9 9 8 年提出的1 ，他们把基于 距离的异常定义为：对于数据集s 中的一个对象o 和一个给定距离值d ，如果数 据集s 中至少有p ，i c l 0 0 的对象与o 的距离大于距离d ，那么我们可以称该对象0 是异常的，并称之为d b ( p ，d ) 异常。当采用不同参数p 和d 时，d b ( p ，d ) 异常 可以表示所有的基于统计方法的异常情况。同时，他们还提出了基于索引的算法、 基于循环嵌套的算法以及基于单元的算法等三种异常数据挖掘算法，但是这三种 算法都相对较为复杂。 根据以上关于异常数据的定义可以看出，一个数据是异常的是指在一个数 据集中远离这个数据的数据相对较多，至少要占p * 1 0 0 ，也就是说接近这个数 据的数据量较少，至多有( 卜p ) * 1 0 0 。因此，实质上所谓异常数据就是指相对孤 立的数据，也即是在其邻域内数据量比较小。 基于距离的异常数据检测方法6 “ 也是由e k n o r r 和r n g 于1 9 9 8 年提出 8 第二章相关技术背景 的。基于距离的异常数掘检测方法的基本思想是：对于一组给定数据，给定一个 距离阂值d 和一个数量阈值n ，计算该组数据中各个数掘的d 一邻域值的个数，即 计算该组数据中与其中任意一个数据的距离小于d 的数据的个数，如果与该数据 距离小于d 的数据的大于n ，则说明与该数据距离相近的数据是充分多的，否则 说明与该数据距离相近的数据是不充分多的，我们据此来判断一组数据中的异常 数据。因此，基于距离的异常数据的定义即为：对于数据集s 中的一个对象o 和一个给定距离值d ，如果数据集s 中至少有p * 1 0 0 的对象与0 的距离大于距离 d ，那么我们可以称该对象0 是异常的，并称之为d b ( p ，d ) 异常。在此定义中， 当给出不同的p 和d ，d b ( p ，d ) 异常可以表述所有基于统计的异常。在此定义下， 所谓的异常数据可以简单的理解为孤立数据，也就是说在该数据的某个邻域内的 数据量是比较小的。 当被检验的数据量很大时，我们要充分考虑算法的性能，并因此产生出了三 种常见的算法：基于索引的算法、基于嵌套循环的算法以及基于单元划分的算法。 基于索引的算法凹1 依赖于多维索引结构，该算法为被检测数据中的所有数据 建立一个索引，然后根据该索引进行以0 为中心的范围查询。显然该算法的难点 是建立一个合理的索引结构，通常我们建立r 树索引或者k d 树索引。在该算法 中，我们要建立多维索引结构，这通常是比较浪费时间的，并且随着维数的不断 增加，使得索引的效率大幅下降。 基于嵌套循环。沁川的算法的基本思想是：首先把内存缓冲区划分为对等的两 部分，把数据集合划分成几个与内存缓冲块大小相同的逻辑块，然后通过一定的 算法，依次选择合适的逻辑块放进内存缓冲区，以此来降低i 0 次数。嵌套循环 算法和基于索引的算法具有相同的计算复杂度，都为0 ( k n 木n ) ，k 为数据的维数， n 为该组数据的个数。该算法虽然能够很好的减少磁盘i 0 数量，但选择合适的 划分区域却是相当费时的，并且当遇到大量数掘集时，其效率还是很低下。 基于单元划分。地3 的算法基本思想是：根据数据的离群来判断一个数掘是否 是异常的。它首先将数据空间划分为彼此独立的单元结构，然后利用一个选择算 法进行多次选择，并以此来判断离群数据。但是，该算法对于每个参数的变化都 要对划分的单元结构进行调整，显然这会严重影响算法的性能。但是该算法当数 据量增加或者数据维数增加时，其性能要高于基于索引的算法和嵌套循环的算 法。 2 3 3 基于聚类分析的方法 基于聚类分析的异常数据检测方法是把聚类分析订的基本思想应用到异常 数据检测中束，它的基本思想是：给定一组数据，使用某种聚类算法把该组数据 9 第_ 二章相关技术背景 进行聚类，也就是把他们划分为不同的数据类别，然后利用数掘本身的特性和分 类后的各个类的特点来确定哪个类中的数据是异常的，哪个类中的数据是非异常 的。 聚类分析的基本思想是根掘各个待分类模式特征相似程度进行分类，模式特 征相似的归为一类，把非相似的作为另外一类。因此，聚类分析就包括了两个基 本内容：相似性度量和聚类算法。 模式的相似性度量主要有距离测度、相似测度以及匹配测度。距离测度是常 用的模式相似性度量，它是以两个矢量之间的距离作为考虑基础的，任意两个矢 量数据之间的距离越小则说明这两个矢量数据之间的相似性越强，反之则说明这 两个矢量数据之间的相似性越低。常用的距离测度有欧氏距离、绝对值距离、切 氏距离、明氏距离以及马氏距离。 相似测度是以两个矢量的方向是否一致作为考虑的，而矢量的长度并不重 要。常用的相似测度有矢量角度相似系数、相关系数、指数相关系数以及几种最 值相关系数。 匹配测度主要应用于医学和生物分类中。对于一个n 维空问数据，其中这n 维数据对应对象的n 个特征，则对于任意一个对象，如果该对象据有某个特征， 则相应特征位上的数据取值l ，否则取值o ，也即是二值特征。 聚类分析算法有很多，有的较为简单，有的则较为复杂。从算法的基本思想 上看，聚类分析算法主要有根据相似性阈值和最小距离原则的简单聚类方法、按 最小距离原则不断进行两类合并的算法、依据准则函数动念聚类算法。 根据相似性阈值和最小距离原则的简单聚类方法的基本思想是：首先由具体 问题来确定相似性度量以及其阈值，将模式到各个聚类中心间的距离与阈值相比 较，当都大于阈值时就把该模式作为另外一个类的类心，小于阈值时按照最小距 离准则把该模式归为某一个类别中去。这种方法旦类的中心以及模式的类别确 定，那么随着算法的继续进行它们是不会更改的。 按最小距离原则不断进行两类合并的算法，其基本思想是：首先把各个待分 类模式看成是自成一个类别，然后将两类间距离最小的两类合并成个类别，如 此反复，直到合并成为两类。在该种算法中，类心是不断进行修改的，但是一个 模式一旦被划分到某个类别后，该模式就不能够被划分到其他类别中了。这类方 法也称之为谱系聚类法。 由以上描述可知，以上两种聚类分析算法要么类心是固定不变的，要么一旦 把某个模式划分到一个类别后该模式就不能够被划分到其他类别中。聚类分析算 法中有一种较为复杂的算法可以克服上述两个缺点，那就是依据准则函数动态聚 类算法。该算法的基本思想是：首先定义一个能够表征聚类过程或者聚类结果的 i o 第一二章相关技术背景 准则函数以及相应的参数，聚类过程就是伎准则函数取极值的最优化过程。在这 类算法中，类心是不断修f 的，同时各个模式的类别指定也是不断更改的。 2 4 本章小结 本章介绍了本文研究的技术背景。本文首先描述了搜索引擎的通用系统结 构；然后简要介绍了开源工具包l u c e n e ，本文所描述的垂直搜索引擎系统就是 一个以l u c e n e 为基础的垂直搜索引擎系统；最后简单介绍了目前常用的异常数 据检测算法。 第三章农产品价格异常数据检测算法 第三章农产品价格异常数据检测算法 目前，对于异常数据的检测方法，主要有：基于统计的方法、基于距离的 方法、基于偏离的方法以及基于聚类分析的方法。文献阳1 还提出了一种基于滑动 窗口的多变量时间序列异常数据的挖掘算法；文献陋副提出了基于s v r 的异常数据 检测算法。本章首先对异常数据的定义进行了说明，并分析了异常数据的特点； 接着介绍了常用异常数据检测算法，并把这些常用算法经过一定修改使之能够应 用于农产品价格数据的异常检测中去；之后，本章详细分析了农产品价格数据的 特征，并根据此特征提出了一种针对农产品价格数据的异常数据检测算法；最后， 对这些异常数据检测算法进行了实验，得出实验结果，并对实验结果进行了详细 分析，通过实验结果的分析对各个算法进行了比较，并最终得出结论。 3 1 异常数据的定义 异常数据f 1 2 2 0 】，顾名思义就是存在异常的数据。异常数据的定义主要有两个， 分别称之为广义定义和狭义定义。 广义上的定义：在所获得的统计数据中相对误差较大的观察数据称之为异常 值，又叫奇异值。 狭义上的定义：一批数据中有部分数据与其余数据相比明显不一致的称为异 常值，又称为离群值。 对于我们处理的农产品价格数据，狭义上的定义是较为合适的。由狭义上定 义，异常值就是离群值，即远离正常数据群的数据。对于一维数据，假如把数据 进行从小到大排序，那么异常数据就会在两侧的位置上，那么针对这种情况，任 意一组一维待检测数据排序后，其异常数据的分布就会有三种情况： ( 1 )仅有异常小值，在排序数列的前端，可能存在多个； ( 2 )仅有异常大值，在排序数列的后端，可能存在多个； ( 3 )既有异常小值又有异常大值，在排序数列的两端，并且可能存在多 个。 3 2 基于统计的异常数据检测算法 3 2 1 基于正态分布的异常数据检测算法 1 2 第三帝农产品价十各异常 数据榆测算：法 基于统计的算法是最早的异常点检测算法点”。1 。对给定的数据集合假设概 率模型，然后根据模型采用不一致性检验来确立异常点。基于统计的方法的主要 缺点是：绝大多数检测算法都是针对单个属性的，而许多数掘挖掘问题都要求 在多维空| 日j 中发现异常；使用陔方法需要事先知道数据的分布，但在大多数情 况下，数据分布可能是未知的，或者观测到的分布不能恰当地被任何标准的分布 来模拟，所以，当没有特定的检验时，该方法不能确保发现所有的异常；通常 对数值型数据有效，而对高维、周期性数据、分类数据则较难进行挖掘。 基于统计的异常数据检测方法是当今研究最多也是最成熟的方法，基本上是 一些假设检验的方法，设计出供检验用的统计量，利用距离之比或者利用似然估 计量等，以求出其精确分命或者近似分布。 然而对于我们的农产品价格数据，假设我们采集来的数据中，品种名称有n 个，全国有m 个城市，则我们每一次进行检验时都要求一个近似分布，这样我们 至少要求n * m 个近似分布，这样显然是不可能的。因此我们只有利用数据本身的 一些特性束对数据进行异常检测。 事实上，农产品价格数据具有相对集中性，即通常情况下我们采集到的某个 地区某个农产品的价格数据是相对集中的，因为在同个地区、同一个时间、同 一产品的价格的差异是不大的。通过观察大部分的农产品价格数据，我们发现具 有相似属性的农产品价格数据大都相对的集中在某个数据周围，并且远离该数据 的数据量通常是很少的，这很符合正态分布的特征。因此，我们假设农产品价格 数据服从f 态分布。虽然这个假设未必正确，然而实际应用中却具有一定的效果， 并对农产品价格数据的异常检测具有一定的指导作用。 在此，基于j 下态分布的异常数据检测方法主要分三步： s t e p l ：读取一条数据，根据该条数据中的农产品名称和地区名称查询已经 建立的统计索引。提取出统计索引中的最近七天该产品该地区采集数据的条数、 均值、方差。( 方差和均值的建立是采用9 0 0 4 的数据建立的) s t e p 2 ：用s t e p l 中读取的均值和方差来近似该分布的均值和方差。根据该 均值和方差计算出点a 和b ，使得f ( 一o o ，a ) = o 0 2 5 ，f ( 一，b ) = o 9 7 5 。 s t e p 3 ：若该条数据中的价格数据在区间( a ，b ) 之间则认为该条数据是非异常 的，否则该条数据被判断为异常的。 基于j 下态分布异常农产品价格数据检测算法分析： 在该算法中，我们假设了农产品价格数据服从于整体分伟。原因在于，我们 观察了农产品价格数据，这些数据很大一部分分布在某个很小的范围内，即很大 一部分价格数据变化是很小的，这样这些数据的分布很像一个方差很小的正念分 布。其次，即使我们能够精确的计算出了某地区某产品农产品价格数据的精确分 第三帝农产品价 各异常数据榆测算法 布，那么该分布却未必符合其他产品的分布，那么每当我们处理一条价格数据时， 我们就要计算一次该品种价格数据所服从的分布，这显然是不可能的。 我们对该算法进行了实验，实验表明该算法能够工作，然而效果却不好。实 验结果将在后面章节重点介绍。原因在于，很多地区采集到的数据量是很小的。 由于各个地区农业信息化发展的情况不同，各个地区的农业网站的个数有很大差 异，这样就导致了我们采集到的数据在某些地区的数量是很小的，这样我们的统 计数据就失去了实际的意义，因此利用该方法的误判率是很高的。 3 2 2 基于跳跃度的异常数据检测算法 由以上可知，单纯的利用传统的基于统计的方法，效果是不太理想的。然而 农产品价格数据的一些统计特性还是很有用的。张德然2 1 提出了一种统计数据中 的异常值检验方法，该方法不需要计算数据所服从的精确分布，而仅仅假设数据 服从某种不确定分布，进而从数据本身的分布特征来判断数据是否是异常值。实 验表明，当把该方法应用于随机数据时，其能够检测出一组数据中的异常值。在 此，我们把该方法做相应修改后应用于农产品价格数据，算法基本思想描述如下： 首先假设所检测的一组数据符合某种分布，并有以下定义： 设x ( 1 ) ，x ( 2 ) ，x ( n - 1 ) ，x ( n ) 为来自总体的分布f ( x ：0 ) 的样本容量 为n 的次序统计量，u ( k ) 为依赖于x ( 1 ) ，x ( 2 ) ，x ( k ) 的期望为u 的点估计， 则称u ( k + 1 ) u ( k ) 为u 在k 点的跳跃度。 由于任何一组n 个数据都可以看成是来自某个分布的n 个观察值，因此我们 把这n 个数据进行从4 , n 大的排序，那么排序后异常数据必然在数列的两侧。同 时异常数据的存在也会使得该点所在的跳跃度很大，因此期望点估计的最大跳跃 点就可能是异常数据的起始点。 该算法分为三个步骤： s t e p l ：读取一条数据，根据该条数据中的农产品价格名称和所来自的地区， 对已经建立的统计索引进行检索，即查询出与该条数据具有相同地区、相同品种 名称的统计数据。有以上可以知道，统计索引中存储了一个产品某个地区最近七