论文部分内容阅读
[摘 要] 随着信息技术的高速发展以及计算机以及其他智能工具的普及，搜索引擎在人们日常获取信息的渠道中占据了越来越重要的地位。百度、谷歌、必应是目前在世界范围内应用最广泛的三种搜索引擎工具。用户仅需在搜索引擎的对话框界面输入自己所要搜索目标的关键词，搜索引擎便可以迅速返回可能与用户搜索目标相关联的列表搜索结果，极大地节约了用户的工作时间，减少了用户需要面对的冗余信息。然而，随着互联网信息的快速膨胀，信息的多义性也日趋复杂。与此同时，用户使用搜索引擎的需求和方向日益增长。用户群体的发展也对搜索结果的质量提出了更高的要求。本文基于已有的基于聚类技术的搜索引擎设计，提出了针对聚类结果的改进方法以及基于信息可视化技术对聚类结果进行可视化输出。以知识体系化的方式有层次的输出搜索结果，提升用户的信息检索和使用效率。
[关键词] 搜索引擎；可视化；文本聚类
doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2015 . 13. 128
[中图分类号] TP391 [文献标识码] A [文章编号] 1673 - 0194（2015）13- 0211- 03
1 当下的搜索引擎技术发展现状
搜索引擎成为我们最为常用的信息检索工具已经成为了不争的事实，到2014年底，我国的网民规模已达6.5亿。有超过82%的用户使用百度等常用搜索引擎作为获取信息的主要手段。显而易见，搜索引擎技术的发展对于推动互联网的进步和发展具有重要的意义。然而，目前的搜索引擎还存在着很大的局限性。
其一是结果呈现形式，其二是语义。主流搜索引擎呈现形式以列表为主，其主要工作原理是利用网络爬虫，通过用户输入的关键字，遍历信息集并采集相关条目，根据相关性顺序列表展现。用户根据列表，依次浏览搜索结果的标题和摘要来确定他们所感兴趣的信息。由于语义多义性广泛存在，用户也时常无法准确地表达自身需求，导致歧义的搜索结果混合在一起。用户在浏览搜索结果时需要人为将不感兴趣的结果筛选出来并定位自己感兴趣的信息，大大降低效率。[1]
2 信息可视化技术的发展
可视化技术的概念在20世纪80年代中被提出，而“信息可视化”的概念最初出现在1989年。总的来说，信息可视化技术是可视化技术在非空间数据领域的应用，其核心是一个将数据和数据包含的信息转化为直观的符合人思维习惯的图形的过程。信息可视化技术使用户能够以直观的方式实现对数据和数据间的关系进行观察，进而更全面地发现数据中隐藏的特征、关系和模式。
经过近20年的发展，信息可视化技术已经被细化到多个领域，包括：基于几何的可视化方式；基于图标的可视化方式；基于时间序列的可视化方式；基于层次的可视化方式等。本文将着重阐述基于层次的可视化方式。
层次信息是一种常见的信息类型。我们每天接触的文本信息就包含许多层次。层次信息的可视化主要包含节点连接图和树图两种方法。
节点链接图：节点链接图[2]是将层次信息组织成一个树状图，根据层次的类属关系分别形成父类和子类节点，以树状结构连接，节点和连接线分别用来表示信息项和它们之间的关系。节点链接图的优点是能清晰直观地展现层次数据内的关系。缺点是子类分支之间的空白会浪费展示空间。
树图：树图的概念（treemap）由Johnson等在1991年提出[3]。树图依靠一系列的图块的嵌套来展示信息和信息的层。，其优点是能够在有限的空间下展示更多的信息数据。其缺点是难以展示节点的内容细节。
3 可视化技术在搜索引擎结果知识体系化输出的方案设计
本方案的总体功能结构如图1所示，主要由用户交互、网页检索、聚类处理、可视化处理和全文搜索引擎数据库组成。矩形方框处为本方案的核心框架。搜索引擎首先从用户交互界面接收用户在界面中輸入的目标字词，将目标发送到检索模块并从数据库中返回相应的结果集合。聚类处理模块将对返回结果先进行预处理，将预处理结果完成聚类并把聚类结果传递至可视化处理模块，经过可视化处理后通过用户界面返回至用户。接下来将继续阐述本文的重点，即聚类处理模块与可视化处理模块。
3.1 聚类模块设计
聚类模块先对搜索结果信息进行预处理，然后对预处理过后的统一格式的数据集利用聚类算法对搜索结果进行聚类。将相似度较高的搜索结果归为一类并为每一个类定义一个具体的聚类标签，根据聚类后的结果子集使用排序算法依照相关性再排序。因此搜索结果聚类模块的总体设计主要由三部分组成：数据预处理子模块，聚类生成子模块和聚类子集排序模块。
3.1.1 文本预处理
（1）文档分词。分词的过程是将文档中的语句按照语言的相应规则划分为词语或短语的过程。分词结果的质量也影响着后续短语的提取和聚类标签的生成。基于词典或词库的分词过程包括：词典初始化、文本输入、文本结构化处理、分词/粗分、消除歧义与识别未登录词、更新词典和结果保存。
（2）词干解析。词干解析对于处理英文文本的意义要大于处理中文文本的意义。英文单词的衍生词和词的形态变化十分常见。例如play是一个词干，它能衍生出player，plays，played，playing等等不同时态不同人称但意义相同的词。
（3）去除停词。通过文档分词，文档已经被划分为一系列的单词。但是这一过程并没有过滤掉文档的无效信息。一些语气词、虚词和助词的词频很高，但与用户需求匹配度低。有时这些词出现次数较多会影响接下来高频词提取和聚类标签生成的过程。可以在搜索引擎运行前预先将停词表加载到内存中，在分词后使用停用词接口方法判定单词是否在停用词表中。
（4）高频短语提取。提取文档高频短语的目的是高度概述文档并提供有限个聚类标签的候选者。因此，高频短语提取的准确信直接关系到聚类标签生成的效果。针对这些要求，后缀数组是一种高效准确的方法。设一个文档T，长度为N。T的后缀数组s是指将T所有的后缀按照字符顺序排序，而令后缀起始的位置（按排序后的顺序）构成的数组。[4] 3.1.2 聚类处理
我们把频率超过一定阈值的词条定义为高频短语。这可以从预处理结果中获取。通过这些数据再利用向量空间模型对文档建模。通过隐含语义索引技术和矩阵降维可以发现文档之间的主题相关性以及相关主题。根据主题对文档进行聚类，完成对预处理结果的二次处理。
（1）生成聚类标签。通过预处理我们已经得到了文档的高频短语，创建特征词-文档矩阵T，对矩阵T进行奇异值分解（SVD），得到一个正交基向量U。根据该正交基向量与高频短语（候选聚类标签）的匹配结果，确定出最终的聚类标签。
（2）聚类生成。根据VSM建立的文档模型，我们已经可以直接通过k-means方法对文档进行聚类。
（3）聚类内部排序。聚类的标签生成后。可以看见标签下包含着一个文档集。最后根据之前的特征词-文档矩阵计算得到的文档对于聚类标签词的TFIDF值的大小降序排列。还可以结合用户行为统计数据进行加权分析，调整最终排序结果。
3.1.3 可视化处理
本方案中的用户交互界面设计采用辐射图和树图两种方法进行结果的展示。树状结构是输出聚类结果的最好选择。就单次搜索聚类得到的结果而言，可以生成一棵简单的以搜索关键词为父节点，结果聚类标签为子节点的树。对于结果聚类较多的情况可以星射状的树结构完成输出。这对后面映射到树图的结果不会产生很多影响。
可视化模块的另一个关键构件是用户行为统计。对每次聚类结果输出后用户选择的领域方向进行记录。在一段时间后，积累了个体用户对于某一领域的多次搜索记录后，通过不同记录树节点的语义消歧和识别，可以生成一棵用户近期对于某一领域探索的知识树。这棵树为用户提供了一个时间维的视角来审视自己对于某个领域的了解发现过程，真正形成搜索结果的知识体系化输出。
4 结束语
时下主流的搜索引擎工具均是单纯以列表的形式为用户呈现搜索结果。这一显示方式降低了用户寻找目标信息的效率，并且这个问题对于学术研究人员的负面影响更为显著。
本设计方案的主要创新之处在于添加了用户行为统计模块修正树状可视化结构的个性化模块，并且还提供了不同的可视化方式進行聚类结果的呈现，另外，基于用户在同一领域中多次搜索聚类结果生成知识树，为用户提供了审视自己阶段性工作成果的能力。
主要参考文献
[1]赵宇.计算机检索工具的发展与应用[J].中小企业管理与科技，2011（4）：271-272.
[2]G Robertson，S K Card，J D Mackinlay.The Congnitive Coprocessor Architecture for Interactive User Interfaces [C]. Proceedings of the 2nd Annual ACM SIGGRAPH Symposium on User interface Software and Technology，New York，1989.
[3]张昕，袁晓如.树图可视化[J].计算机辅助设计与图形学学报，2012，24（9）：1113-1124.
[4]朱光楠. 基于聚类的搜索可视化呈现系统的设计与实现[D].北京：北京邮电大学，2012.
[5]周登朋. 搜索引擎搜索结果的聚类研究[D].上海：上海交通大学，2007.
[关键词] 搜索引擎；可视化；文本聚类
doi ： 10 . 3969 / j . issn . 1673 - 0194 . 2015 . 13. 128
[中图分类号] TP391 [文献标识码] A [文章编号] 1673 - 0194（2015）13- 0211- 03
1 当下的搜索引擎技术发展现状
搜索引擎成为我们最为常用的信息检索工具已经成为了不争的事实，到2014年底，我国的网民规模已达6.5亿。有超过82%的用户使用百度等常用搜索引擎作为获取信息的主要手段。显而易见，搜索引擎技术的发展对于推动互联网的进步和发展具有重要的意义。然而，目前的搜索引擎还存在着很大的局限性。
其一是结果呈现形式，其二是语义。主流搜索引擎呈现形式以列表为主，其主要工作原理是利用网络爬虫，通过用户输入的关键字，遍历信息集并采集相关条目，根据相关性顺序列表展现。用户根据列表，依次浏览搜索结果的标题和摘要来确定他们所感兴趣的信息。由于语义多义性广泛存在，用户也时常无法准确地表达自身需求，导致歧义的搜索结果混合在一起。用户在浏览搜索结果时需要人为将不感兴趣的结果筛选出来并定位自己感兴趣的信息，大大降低效率。[1]
2 信息可视化技术的发展
可视化技术的概念在20世纪80年代中被提出，而“信息可视化”的概念最初出现在1989年。总的来说，信息可视化技术是可视化技术在非空间数据领域的应用，其核心是一个将数据和数据包含的信息转化为直观的符合人思维习惯的图形的过程。信息可视化技术使用户能够以直观的方式实现对数据和数据间的关系进行观察，进而更全面地发现数据中隐藏的特征、关系和模式。
经过近20年的发展，信息可视化技术已经被细化到多个领域，包括：基于几何的可视化方式；基于图标的可视化方式；基于时间序列的可视化方式；基于层次的可视化方式等。本文将着重阐述基于层次的可视化方式。
层次信息是一种常见的信息类型。我们每天接触的文本信息就包含许多层次。层次信息的可视化主要包含节点连接图和树图两种方法。
节点链接图：节点链接图[2]是将层次信息组织成一个树状图，根据层次的类属关系分别形成父类和子类节点，以树状结构连接，节点和连接线分别用来表示信息项和它们之间的关系。节点链接图的优点是能清晰直观地展现层次数据内的关系。缺点是子类分支之间的空白会浪费展示空间。
树图：树图的概念（treemap）由Johnson等在1991年提出[3]。树图依靠一系列的图块的嵌套来展示信息和信息的层。，其优点是能够在有限的空间下展示更多的信息数据。其缺点是难以展示节点的内容细节。
3 可视化技术在搜索引擎结果知识体系化输出的方案设计
本方案的总体功能结构如图1所示，主要由用户交互、网页检索、聚类处理、可视化处理和全文搜索引擎数据库组成。矩形方框处为本方案的核心框架。搜索引擎首先从用户交互界面接收用户在界面中輸入的目标字词，将目标发送到检索模块并从数据库中返回相应的结果集合。聚类处理模块将对返回结果先进行预处理，将预处理结果完成聚类并把聚类结果传递至可视化处理模块，经过可视化处理后通过用户界面返回至用户。接下来将继续阐述本文的重点，即聚类处理模块与可视化处理模块。
3.1 聚类模块设计
聚类模块先对搜索结果信息进行预处理，然后对预处理过后的统一格式的数据集利用聚类算法对搜索结果进行聚类。将相似度较高的搜索结果归为一类并为每一个类定义一个具体的聚类标签，根据聚类后的结果子集使用排序算法依照相关性再排序。因此搜索结果聚类模块的总体设计主要由三部分组成：数据预处理子模块，聚类生成子模块和聚类子集排序模块。
3.1.1 文本预处理
（1）文档分词。分词的过程是将文档中的语句按照语言的相应规则划分为词语或短语的过程。分词结果的质量也影响着后续短语的提取和聚类标签的生成。基于词典或词库的分词过程包括：词典初始化、文本输入、文本结构化处理、分词/粗分、消除歧义与识别未登录词、更新词典和结果保存。
（2）词干解析。词干解析对于处理英文文本的意义要大于处理中文文本的意义。英文单词的衍生词和词的形态变化十分常见。例如play是一个词干，它能衍生出player，plays，played，playing等等不同时态不同人称但意义相同的词。
（3）去除停词。通过文档分词，文档已经被划分为一系列的单词。但是这一过程并没有过滤掉文档的无效信息。一些语气词、虚词和助词的词频很高，但与用户需求匹配度低。有时这些词出现次数较多会影响接下来高频词提取和聚类标签生成的过程。可以在搜索引擎运行前预先将停词表加载到内存中，在分词后使用停用词接口方法判定单词是否在停用词表中。
（4）高频短语提取。提取文档高频短语的目的是高度概述文档并提供有限个聚类标签的候选者。因此，高频短语提取的准确信直接关系到聚类标签生成的效果。针对这些要求，后缀数组是一种高效准确的方法。设一个文档T，长度为N。T的后缀数组s是指将T所有的后缀按照字符顺序排序，而令后缀起始的位置（按排序后的顺序）构成的数组。[4] 3.1.2 聚类处理
我们把频率超过一定阈值的词条定义为高频短语。这可以从预处理结果中获取。通过这些数据再利用向量空间模型对文档建模。通过隐含语义索引技术和矩阵降维可以发现文档之间的主题相关性以及相关主题。根据主题对文档进行聚类，完成对预处理结果的二次处理。
（1）生成聚类标签。通过预处理我们已经得到了文档的高频短语，创建特征词-文档矩阵T，对矩阵T进行奇异值分解（SVD），得到一个正交基向量U。根据该正交基向量与高频短语（候选聚类标签）的匹配结果，确定出最终的聚类标签。
（2）聚类生成。根据VSM建立的文档模型，我们已经可以直接通过k-means方法对文档进行聚类。
（3）聚类内部排序。聚类的标签生成后。可以看见标签下包含着一个文档集。最后根据之前的特征词-文档矩阵计算得到的文档对于聚类标签词的TFIDF值的大小降序排列。还可以结合用户行为统计数据进行加权分析，调整最终排序结果。
3.1.3 可视化处理
本方案中的用户交互界面设计采用辐射图和树图两种方法进行结果的展示。树状结构是输出聚类结果的最好选择。就单次搜索聚类得到的结果而言，可以生成一棵简单的以搜索关键词为父节点，结果聚类标签为子节点的树。对于结果聚类较多的情况可以星射状的树结构完成输出。这对后面映射到树图的结果不会产生很多影响。
可视化模块的另一个关键构件是用户行为统计。对每次聚类结果输出后用户选择的领域方向进行记录。在一段时间后，积累了个体用户对于某一领域的多次搜索记录后，通过不同记录树节点的语义消歧和识别，可以生成一棵用户近期对于某一领域探索的知识树。这棵树为用户提供了一个时间维的视角来审视自己对于某个领域的了解发现过程，真正形成搜索结果的知识体系化输出。
4 结束语
时下主流的搜索引擎工具均是单纯以列表的形式为用户呈现搜索结果。这一显示方式降低了用户寻找目标信息的效率，并且这个问题对于学术研究人员的负面影响更为显著。
本设计方案的主要创新之处在于添加了用户行为统计模块修正树状可视化结构的个性化模块，并且还提供了不同的可视化方式進行聚类结果的呈现，另外，基于用户在同一领域中多次搜索聚类结果生成知识树，为用户提供了审视自己阶段性工作成果的能力。
主要参考文献
[1]赵宇.计算机检索工具的发展与应用[J].中小企业管理与科技，2011（4）：271-272.
[2]G Robertson，S K Card，J D Mackinlay.The Congnitive Coprocessor Architecture for Interactive User Interfaces [C]. Proceedings of the 2nd Annual ACM SIGGRAPH Symposium on User interface Software and Technology，New York，1989.
[3]张昕，袁晓如.树图可视化[J].计算机辅助设计与图形学学报，2012，24（9）：1113-1124.
[4]朱光楠. 基于聚类的搜索可视化呈现系统的设计与实现[D].北京：北京邮电大学，2012.
[5]周登朋. 搜索引擎搜索结果的聚类研究[D].上海：上海交通大学，2007.