NovaPIM中查询智能建议与信息可视化-优秀毕业设计论文缩写

NovaPIM中查询智能建议与信息可视化-优秀毕业 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 缩写 NovaPIM中查询智能建议与信息可视化 学生姓名:吕超帅 专业班级:计算机科学与技术0904班 指导老师:杨良怀 摘 要 NovaPIM是浙江工业大学PIM研究组通过在个人信息管理的相关研究探索而基于管理概念空 间的思想研发出的一套新颖的个人信息管理系统原型。本文的主要贡献是在NovaPIM系统已有的 基础上，利用自然语言处理和机器学习等知识添加了信息提取与信息处理、查询智能建议、聚类分 析、可视化这四个信息智能化功能。目的是为了提高管理的质量和效率;智能导入个人信息，方便 知识转换;智能建议查询结果，提高信息准确率;展示个人信息的可视化，使枯燥的数据变成清晰 的图文。整体目标是为用户提供对一个个人信息和个人知识的高效、智能、便捷、清晰的管理平台， 以有效地促进用户对个人信息和个人知识的管理。 关键词:个人信息管理，信息提取，数据可视化，自然语言处理，聚类分析，文本挖掘 Intelligent query suggestions and information visualization of NovaPIM Abstract NovaPIM is a novel personal information management prototype based on the idea of concept space, which was developed by Zhejiang University of Technology PIM Research Group. The main contribution of this work consist in exploiting natural language processing and machine learning techniques to enhance the functionality of NovaPIM. (e.g., information extraction and processing, intelligent query suggestions, clustering analysis, visualization). And the purpose of this project is to improve the quality and efficiency of personal information management, to support automatic and intelligent personal information importing and facilitate knowledge conversion; to offer intelligent suggestion related to the search results and to present personal information vividly through data visualization. The overall goal is to provide an efficient, intelligent, convenient and clear personal information management platform, and to promote the process of personal information and knowledge management effectively. Keywords: Personal Information Management, Information extraction, Data Visualization, Natural Language Processing, Clustering Analysis, Text Mining 1 引言 个人信息是人类在生活中遇到、收集、思考出来的一系列固定格式的信息。由于个人信息的 量会随着时间而不断的增多，它的总量会变得越来越庞大。所以，近年来对个人信息的管理的需求 不断增加，如何清晰高效地管理个人信息成了值得关注的问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 之一。NovaPIM是浙江工业大学PIM 1 研究组通过在个人信息管理的相关研究探索而基于管理概念空间(Concept Space)的思想研发出的一套新颖的个人信息管理系统原型。近年来，随着人工智能(Artificial Intelligence)、自然语言处理(Natural Language Processing)、机器学习(Machine Learning)以及HTML5/CSS3等网页可视化技术为 [1]代表的新兴智能领域的发展，对NovaPIM添加这些智能化的新功能已成为必然需求。 2 信息提取与信息处理 2.1 信息提取 在对NovaPIM进行信息化功能添加目标中，信息提取是最至关重要的一步，因为后期无论是对信息数据文件进行的自然语言处理如分词(Word Segmentation)、停用词过滤(Stopwords Filter)，还是英文的词干提取(Stemming)等操作，都需要在各种类型文件的信息已经提取出来的基础上才能进行。本项目主要针对纯文本文档格式TXT，超文本标记语言文档格式HTML以及微软公司的DOC格式以及便携式文件格式PDF进行了提取。NovaPIM中的信息提取流程如图1所示。 2.2 自然语言处理 自然语言处理(Natural Language Processing)是信息挖掘和使用中影响准确率最大的一个步骤，通常也叫做信息处理。由于自然语言包含着词语、句子、语法、语义、语境甚至一词多意等多种复杂的概念，计算机作为数据的解释者，并不能直接对数据内在含义进行解析。其中需要人类将每种特定自然语言的特性教予计算机，并且为计算机设定好一系列语言解释的算法，才能将提取出来的信息进一步的进行分析、可视化展示等操作。在NovaPIM中我们选定的流程如图2所示。 开始开始 待提取文件待处理文本 调用分词器文件类型TXT or HTML分词处理 DOC PDF去除停用词文件类型是TXT,HTML 调用Apache 调用Apache POI - 对文件内容预处英文文本语言PDFBox进行解析HWPF进行解析Y理，过滤html标签词干提取 算法中文通过Java字符流直接解析 输出提取输出提取内容内容 结束结束 图1 信息提取流程 图2 自然语言处理流程 (1) 中文分词处理 中文分词与英文分词有很大的不同，对英文而言，词与词之间是人为以空格分隔开的，而中文是以句与句之间以标点符号分隔开，在词与词之间并没有人为设定的分隔标记，所以中文分词需要设定特殊的算法。在本项目中主要选择基于Java的轻量级IKAnalyzer分词组件作为分词工具，一 2 [2]方面是由于其特有的“正向迭代最细粒度切分算法”，支持细粒度和智能分词两种切分模式，另一方面是其支持添加停用词的功能，在整合的效率上更高。NovaPIM中分词的效率如图3所示。 图3 NovaPIM中分词效率 (2) 停用词的过滤 停用词是指自然语言处理信息前后自动去除掉的对全局意义不是很大的词语，如英文中的“a”、“the”、“this”、“that”、“there”以及中文的“的”、“个”、“是”等等。绝大部分自然语言中的功能词以及应用过广泛、概念过泛的词语在被去除后可以提高自然语言信息数据分析效率。 本项目通过对互联网上收集的百度停用词表、哈工大停用词表、四川大学机器智能实验室停用词表等常见停用词表合并并去重后，我们将5279个常见停用词(包括一些符号以及数字)压缩到2248个词。假设使用二分查找算法或者平衡二叉树数据结构判断一个词是否为停用词的话，只需要O(log(N))的时间复杂度即可完成停用词去重，而log(2248)?11，即表明了在增加停用词过滤步22 骤后，整体信息处理算法效率不会显著变慢。 对于停用词的过滤效果测试，本文采用的方法是:随机选取文章，比对过滤前后筛选出的关键词，按照词频排序选出前20个关键词，并分析研究他们与文章内容的相关性。 表1停用词过滤测试结果 编号 文章内容 分词效果(未过滤) 分词效果(过滤后) 长三角地区罗氏沼1 虾|病|氏|为|罗|沼|细菌|3|菌|主要|5|j|2|1|虾|病|氏|罗|沼|细菌|菌|样|致病菌|病原 虾成虾主要疾病的和|样|致病菌|进行|10|结果| |shb1|gyb8|成|研究|hzl2|图|鉴定|试验|形态| 病原研究 株| 长期定位施肥对石2 amf|和|施肥|of|the|土壤|中|水稻|属|处理amf|施肥|土壤|中|水稻|属|土|多样性|性|农家 灰性紫色水稻土|and|土|多样性|0|性|in|农家肥|囊|石灰|肥|囊|石灰|肥|霉|soil|种|度|影响|小麦|紫色| AMF多样性的影响 不同| 运动认知心理学研3 运动员|运动|研究|决策|认知|of|and|中|运动员|运动|研究|决策|认知|中|训练|技能 究进展述评 训练|技能|in|sport|预测|the|工作记忆|其|sport|预测|工作记忆|视觉|判断|信息|动|心 |视觉|判断|信息|任务| 理学|领域|表现|知觉|眼| 退役运动员再就业4 运动员|退役|再就业|和|山东省|就业运动员|退役|再就业|山东省|就业|中|职业|体 状况调查研究_以|1|2|the|中|3|职业|为|2.|体育|of|年|5|4|3.| 育|年|人数|研究|社会|运动|占|调查|业|状况| 山东省为例 工作|影响|因素| 从上表不难发现，分词前大多数文本的前20个关键字都蕴含着25%到50%的无用词(包括词语、数字及标点符号)，而分词后提前出来的关键词，大多数是文章的核心词语，而且肉眼可以根据前20个关键词快速推测出文章的内容，这样的效果证明停用词的过滤是有效的。 (3) 英文词干提取 3 词干提取(Stemming)是指对于增加特定词缀形成的新词还原为词根的过程。也即得到单词最朴素的表达方式。在NLP领域中，词干提取主要针对英语等语言，而在语言信息统计方面，将不同词语映射到它们对应的词根是相当有用的。比如可以通过统计文章中与happy相关的词happier、happies、happiest、happily、happiness以及与glad相关的词gladded、gladding、gladly、gladness等词，将它们提取词干后，再统计happy与glad的加权词频，可以分析出一篇文章的高兴程度到底有多少，这对于一个文本实体的情感分析来说是效果显著的。 在NovaPIM中，我们采用词干提取领域评判 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的算法Porter Stemming Algorithm来处理英文的词干提取，以便后期的统计分析使用，核心思想是通过元音辅音的判断以及固定词缀的消除来达到通用的词干提取目的。 3 智能查询建议 智能建议最早起源于互联网，现多用于搜索引擎和网络应用方面。本领域的最大的挑战是怎样提供与用户输入的最相关和最准确的信息。最具有特点的智能提示功能目前是人机交互设计中的及 [3]时回答技术，它可以在用户没输完关键字的情况下就为它们提示最匹配的信息，使用户能够在边思考，边操作的情况下，获得预期的、甚至是额外的搜索结果。使用这种即时回答的技术，可以使用户在使软件的时候的体验更加良好。 3.1 智能查询建议实现 NovaPIM中默认支持模糊查询功能，可以对内容进行精确匹配、对物理和概念路径执行模糊匹配，使用户可以方便快捷地获得较为直观的信息，但是由于搜索界面需要用户不断地在对话框之间切换。所以我们在底部增加了一个智能建议搜索框，便于用户在查看文档或者对文档进行操作时候方便快捷地以最短屏幕距离移动到提示框内。同时对搜索框增加了监听器事件以及时监测用户输入的动态，同时后台调用模糊查询的API接口进行查找，对于返回来的结果列表，我们将其放在弹出的Shell中，而Shell窗口又通过额外的事件设置为即时隐藏显示，且能够根据内容自动调整大小。 为了能够在显示标题的情况下又显示更多的信息，诸如路径、图标等内容，我们又给SWT的table控件增加了三个能够监测大小的Listener，使得结果表中的每个项目可以显示多行数据，从而能够让我们的搜索结果不仅显示个人信息文档名称，同时又可以显示个人信息文档路径。我们还为常见类型的个人信息文档设置了图标，以便用户可以直接方便的知道文件类型。 3.2 网络查询功能实现 智能建议功能另一个重要领域是利用互联网上已有的各种服务，例如搜索、计算、甚至翻译等等。所以我们给智能建议功能增加了一个接口，在这个接口上面，只要输入按照符合 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 的URL和服务名称，并且设置正确的URL，就可以方便地将用户输入的关键词作为参数传递给其他网络服务。在程序中，我们默认提供给用户Google搜索、百度搜索、维基百科搜索和WolframAlpha智能计算引擎搜索等四个常用的网络服务。用户可以根据在管理个人信息文档中所想要查询的功能去选择相应的服务，便可以较方便地获得相应的功能。例如用户可以通过Google或百度来搜索一下输入关键字的内容，也可以通过维基百科搜索一下相关术语概念的定义，甚至可以通过WolframAlpha搜索引擎直接计算十分复杂的公式(甚至可以用自然语言输入，如convert 10 to base 2这种操作等等)。我们默认设置的网络服务智能建议默认紧跟在模糊查询智能建议之后。默认界面与设置界面如图4和图5所示。 4 图4模糊查询的智能建议界面 图5模糊查询的智能建议设置界面 3.3 智能建议测试 在样本中我们一共有18篇随机的个人信息文档，文档格式均为PDF格式，来源为知网文献库。其中包含3篇模糊查询(Fuzzy/Flexible Querying)相关文档，2篇个人信息管理(PIM)相关文档，另有其他不同学科论文与文章若干，文章中并不包含某种通用模式，使得测试结果比较真实可信。为了更好地测试，我们对于所有所列出的文档均使用不完全一样的文件名称格式，以减少规范化文件名带来的偏见。详细目录如表2所示: 表2 测试使用文档列表 编号 论文名称 wsn位置检测系统的隐私保护.pdf 1 论大众传媒文化的价值取向.pdf 2 影响食管癌FDG摄取的临床因素探讨.pdf 3 铁路旅客感知的列车服务质量实证研究.pdf 4 论_因侵权而犯罪_与_因犯罪而侵权_.pdf 5 Flexible Querying of Personal Information09.pdf 6 评美国_2012年中国军事与安全发展_报告.pdf 7 马克思的国际产业转移理论及其当代价值.pdf 8 退役运动员再就业状况调查研究_以山东省为例.pdf 9 运动认知心理学研究进展述评.pdf 10 大气CO_2浓度非均匀动态分布条件下的气候模拟.pdf 11 Flexible Query Answering on Graph-modeled Data.pdf 12 长期定位施肥对石灰性紫色水稻土AMF多样性的影响.pdf 13 Fuzzy Multi-Dimensional Search in the Wayfinder File System-icde-2008.pdf 14 长三角地区罗氏沼虾成虾主要疾病的病原研究.pdf 15 Multi-Dimensional Search for Personal Information Management Systems-EDBT-2008.pdf 16 A Novel PIM System and its Effective Storage Compression Scheme 5911-16147-1-PB.pdf 17 律学与乐学_1982年全国高师中国音乐史暑期讲习班专题_下_.pdf 18 5 输入6次不同测试的测试搜索结果如表3所示: 表3 智能建议测试结果表 编号 搜索词 结果编号集合 目标编号集合 准确率 1 flexible {6, 12, 14, 16, 17} {6, 12, 14, 16, 17} 100% 2 query {1, 6, 12, 14, 16, 17} {1, 6, 12, 14, 16, 17} 100% 运动 3 {8, 9, 10} {8, 9, 10} 100% 美国 4 {2, 3, 7, 8} {2, 3, 7, 8} 100% 运动员 5 {9, 10} {9, 10} 100% 全集 全集 6 pdf 100% 从上表可以看出，由于模糊搜索的存在，算法查找一个特有的单词的准确率均为100%。而且针对中英文的差异，智能建议模块也均能很好地正常工作，所以能够改善用户在使用NovaPIM时的体验。 NovaPIM中智能建议模块的添加主要复杂度在于NovaPIM背后的搜索引擎Lucene所执行的倒 [4]排索引搜索。而其内部又使用了Levenshtein自动机算法，所以整个搜索的效率非常高效。 4 聚类分析 4.1 TF*IDF权重评估 在NovaPIM中按照TF*IDF(Term Frequency * Inverse Document Frequency)评估方法结合关键词提取算法实现了聚类分析的预处理过程，以获得每个文档的关键词向量。TF*IDF权重评估是一种统计学方法，它的主要特性是一个单词在文本或者文档中的权重随着它在文本中出现的次数增加而正比增加，但同时权重又会根据其在全局语料库中出现的频率增加而反比下降。这样就可以很好 错误～未找到引用源。使部分功能性停用词在文本关键词统计中被自动忽略。从而使文档更好的被分析地。 词频(Term Frequency, TF也叫Word Frequency)是指一个词在文档中出现的频率，即: (1) 其中occurencei,j表示词i在文档Docj中的出现次数。 逆向文档频率(Inverse Doucement Frequency, IDF)是指一个词的重要程度，即某个词的IDF越大，该词的重要程度就越高，反之就越小。第i个单词ti的IDF定义如下: (2) 其中|D|是全局语料库的文件总数，表示单词ti在文档Docj中出现的次数，但是当Docj不包含单词ti时，被除数就会等于0，所以一般使用修正的IDF公式防止浮点数出错: (3) 最后可以得到修正后的TF*IDF的公式: (4) 6 根据以上几式也可发现，在所有文件中出现越频繁的单词，相应的TF*IDF权重也就越低，反之比较独特明显的单词，权重就会越高。所以TF*IDF权重可以很好地区分出常用功能词和关键词。 4.2 K-Means聚类 错误～未找到引用源。K-Means算法是在聚类分析的非层次聚类方法中最被广泛使用的一种。它的主要思想是基于划分，算法每次输入样本数量n和预期类数量k，输出的是k个具有高相似度的类。算法首先针对输入的聚类个数K，随机选择K个样本作为初始聚类中心，然后不停地迭代，每次对所有样本选择其新的聚类中心点，再对所有聚类选择新的中心。重复运行直到中心点不再发生变化，此时称结果已经收敛。即按照如下步骤循环执行: 初始化k个聚类中心，每次循环如下两步，直到算法收敛。 1. 对每个样本选择距离他最近的类，即根据当前状态按照Voronoi图划分平面 (5) 2. 对每个类计算新的聚类中心 (6) 在NovaPIM中，我们将通过模糊查询搜索出来的个人信息文档作为样本，对其的聚类分析就转换为为个人信息文档内容进行聚类分析。每个文档尽可能按照相似度来划分为同一类，故采用K-Means算法时我们将采用余弦相似度来衡量两个文档内信息之间的相似度。 (7) 4.3 聚类分析测试 根据本章结果，对NovaPIM样本测试数据进行了聚类分析，首先人为地选择了聚类个数K=3，调用NovaPIM中实现好的K-Means分析聚类，并对每个类进行带权重的关键词提取出前五个类关键词。结果如图6所示。 由于聚类算法是NP-Hard的，而K-Means只是一个近似算法，能够得到一个局部最优解，也有时候不能收敛，所以对聚类分析的研究还有待改进。 在提取关键字的时候，由于样本较小，不能完全展示TF*IDF在取词方面的优化，相反一些专业术语可能由于类中每篇文章都有而被遗漏，但是比较前后之间取词频的准确度，TF*IDF已经比直接取词要优一些。 5 信息可视化 5.1 文本信息云可视化 信息可视化具有多种形式，但是针对知识可视化的并不多。其中最直观的是文字云(WordCloud)项目。本项目采用台湾Mozilla工程师Timothy Chien在GitHub开发社区上开源的WordCloud项目来支 7 持文字云的绘制工作。但是由于其内置的分词算法效率不高，并且不支持停用词的过滤，容易造成信息混淆从而忽略重要信息。所以，NovaPIM中采用了二次开发，以先分词，后调用的模式进行文字云的展示，同时将WordCloud作为原有NovaPIM中界面右侧的窗体中的标签之一，使整个集成工作显得更加流畅。 NovaPIM中的文字信息云范例效果如图7所示。 图6 KMeans聚类分析 图7 NovaPIM中的文字信息云效果 5.2 动态词频饼图 为了更好地体现本项目可视化的效果，对NovaPIM中的文本添加了词频分析动态饼图的可视化功能。由于饼图可以展示项目在整体中所占比例的大小，所以对NovaPIM词频分析来说刚好可以借助饼图来展示与比较分词效果。 在NovaPIM里采用网页可视化展示方法来绘制动态饼图。其中主要用到了Raphaël——一个支持在网页端显示向量图形的开源JavaScript库。其对矢量特性的支持使得绘制出的可视化程序可以在不同东西的屏幕分辨率的屏幕上都显示出细腻的效果。 在NovaPIM中可以指定了分析每个文档词频前K名(默认设置为20)的关键词，并通过将它们整体作为字符串保存在原有的XML文档中，同时对左侧的概念空间节点进行了MD5验证，一旦发现文档的MD5与XML文档中的MD5不一致后，即意味着文档有变化，此时将自动重新对文档分词并统计词频前K名并重新写入XML文档以保持一致。经测试，在采用缓存关键字与MD5校验更新后，对词频查看统计的功能效率大大增高，用户不必每次再等待文件重新分词，程序将会自动保留个人信息文档最新版本的分词结果。 NovaPIM中的动态饼图对前K个关键词通过渐变色彩来区分，根据饼图的大小可知每个词在原文中所占比例，也可以估测为重要程度，从而可推测出文章大体内容。详细效果如图8所示。 5.3 关系图可视化 以上两种可视化主要是针对单个文件内部的信息，即用户个人信息文档中某个特定文档的信息，而NovaPIM在可视化方面还需求文件与文件直接的信息，即内容与内容之间的联系，这种关联性的可视化并不能用文字云或者是词频统计来描绘。所以提出关系图可视化概念，即针对图的概念，用点和边来描绘实体之间的关系。 针对这个特定的需求，对6.1节中的可视化展现形式进行评估后，发现网络图是最适合用于关系图可视化的一种。其描述的特定二元关系正式关系图中所需求的。在评估中，发现国内淘宝公司可视化实验室的dataV.js组件展示了一系列效果较好的动态样例。故NovaPIM中的关系图可视化将 8 与文字云可视化一样，采用内部操作，外部绘图策略，将两部分的工作分开，Java中负责关系的生成，调用dataV.js组件进行动态网络图的绘制，可以保证集成的无缝性。 NovaPIM中的关系图主要有两种，均针对查询结果分析的可视化。其一是第四章中分析的聚类分析结果可视化，将聚类分析分出的K个类以可视化的方式展现出来。另一个是针对词频统计的联系，将搜索结果中有共同关键词的文件连边，将结果的网络图绘制出来。 对于聚类分析的图，由于聚类分析中已经给出了某个聚类的所有成员，所以只需要在NovaPIM中将每个节点连接到该聚类中的新中心点，将此新中心点的描述设置为聚类全体关键词TF*IDF带权词频统计前几名即可。由于聚类分析是NP-Hard问题，所以整体复杂度并不是多项式的。而且K-Means聚类只能得到局部较优解。针对局部解，分析出来的图如图9所示，其中紫色的点是关键词点，蓝色的点是文档结点。 图8 动态词频饼图效果 图9 关系图可视化效果 对于关键词联系图，是以各文档的关键词提取并去重后，将每个文件前K个关键词与其他文件的前K个关键词做比较，如果有文件i和文件j前K个关键词中有相同的个数超过一个阈值T，则连一条边。假设共有N个文档，每个文档有K个关键词作比较。直接两两比对关键词的复杂度 22是O(N*K*L)，其中L是关键词平均长度 如果采用二分查找算法或者平衡二叉树等数据结构，例如Java中的HashMap，则两两对比的 22复杂度变为O(N*K*log(M))，其中M是每个节点的平均单词表大小。如果采用HashMap统计全部的单词并记录每个单词在哪些文档中出现过，然后再将枚举每个单词所出现的文档，在这些文档之间两两连边，那么复杂度就降低到O(N*K*log(M) + E*log(M)) = O((N*K+E)*log(M))，其中E表示网络图的边数，虽然在完全图的时候E=N2，但是算法已经比两两比对的连边方法优化了许多。关键词联系图在阈值T=5的时候效果如图10所示: 图10 关键词联系图 由上图可以发现，基本上有联系的文档之间已经有边相连。在关键词联系图中，重要的是阈值T的设定。不同的T设定出来的结果将会是十分不同的。 9 6 结束语 本文以NovaPIM原型为研究对象，研究并实现了其中的信息智能化功能:信息提取功能、自 然语言处理功能、智能提取功能、可视化功能、简单的聚类分析功能。经过测试分析，改进后的 NovaPIM系统能够智能高效地根据用户的个人信息文档来自动化地将枯燥的文本数据转化为用户 可以直接了解到内容的美观的可视化界面，并且用户可以在使用查询功能过程中方便地得到程序的 建议内容。 参考文献 [1] 黄义侠. 国外个人信息管理中信息检索方法分析[J]. 现代情报, 2007, 27(9): 61-63. [2] 张云. 基于开源软件的中文学术文献计量软件的开发实践[J]. 现代图书情报技术, 2010, 4(191): 87-91. [3] Nandi A, Jagadish H V. Assisted querying using instant-response interfaces[C]//Proceedings of the 2007 ACM SIGMOD international conference on Management of data. ACM, 2007: 1156-1158. [4] Prasad A R D, Patel D. Lucene search engine: an overview[J]. 2005. [5] 维基百科. TF-IDF[EB/OL].(2013-5-13) [2013-5-25]. [6] MacQueen J. Some methods for classification and analysis of multivariate observations[C]//Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. 1967, 1(281-297): 14. 10