基于网格索引的数据流子空间概率轮廓查询

在数据流子空间上的连续概率轮廓查询(CPSQS)基础上,提出一种基于网格索引结构的概率轮廓查询算法。采用适合于子空间轮廓计算的网格索引结构,将数据空间划分成若干个格,利用格间的支配关系,减少对象之间的比较次数。同时挖掘全空间与子空间上格的概率上下界关系,设计有效的剪枝策略提高CPSQS算法的性能。理论分析和实验结果表 明,该算法能满足实际应用中用户的个性化查询要求,降低查询响应时间。     

基于iceberg概念格并置集成的闭频繁项集挖掘算法

由于概念格的完备性,在基于概念格的数据挖掘过程中,构造概念格的时间复杂度和空间复杂度一直是影响其应用的主要因素.结合iceberg概念格的半格特性和概念格的集成思想,首先在理论上分析并置集成后的iceberg概念格与由完备概念格裁剪得到的iceberg格同构;然后分析了iceberg概念格集成过程中的映射关系;最终提出一个新颖的基于iceberg概念格并置的闭频繁项集挖掘算法(Icegalamera).此算法避免了完备概念格的计算,并且在构造过程中采用集成和剪枝策略,从而显著提高了挖掘效率.实验证明其产生的闭频繁项集的完备性.使用稠密和稀疏数据集在单站点模式下进行了性能测试,结果表明稀疏数据集上性能优势明显.     

基于搜索引擎的Deep Web数据源发现技术

随着Web数据库的广泛应用,Web正在不断"深化".传统搜索引擎只能检索浅层网络,却不能直接索引到深层网络(Deep Web)的资源.为了有效地利用Deep Web资源,必须要对Deep Web数据进行大规模集成.其中,数据源发现是整合DeepWeb资源的首要工作,能否高效地发现DeepWeb站点是DeepWeb数据获取的关键.提出了一种基于传统搜索引擎的Deep Web数据源发现方法,该方法通过分析返回结果来扩展查询,从而进一步提高了数据源发现的效率.实验证明该方法能得到较好的结果.     

本体自动抽取中的概念相似性分析

本体的自动抽取问题是电子政务信息集成的核心问题之一。在本体的自动抽取过程中,FCA方法用于自动分析概念之间的关系,但它对概念间的同义词关系分析不够。基于这个原因,对FCA方法进行了优化,提出了SFCA算法。算法根据属性在概念中的重要性对属性赋权值,利用属性的权值计算两个概念的相似度,最终确定两个概念是否是同义词关系。通过对算法的实验结果的分析验证其是有效的,并给出了正确性证明。     

基于本体的电子政务信息集成研究

本体的自动抽取问题是电子政务信息集成的核心问题之一。在本体的自动抽取过程中,FCA方法用于自动分析概念之间的关系,但它对概念间的同义词关系分析不够。基于这个原因,对FCA方法进行了优化,提出了SFCA算法。算法根据属性在概念中的重要性对属性赋权值,利用属性的权值计算两个概念的相似度,最终确定两个概念是否是同义词关系。通过对算法的实验结果的分析验证其是有效的,并给出了正确性证明。     

区间概念格的纵向维护原理与算法

区间概念格是唯一能直接反映具备一定数量或比例的内涵中属性的对象集合的格结构。格结构是根据对象-属性的二元关系构造的,形式背景中的属性是时刻变化的,为使概念格能反映属性变化后的数据规律进而提取新的规则,提出了区间概念格的纵向维护算法。算法在分析了区间概念格的概念外延特点及结构特征后,给出了区间概念格在增加属性、删除属性两种情况下的维护算法,进而通过算法分析表明了维护较重构在时间与空间上的高效性,最终用实例表明了维护算法的可行性。     

概念格与关联规则发现

作为数据挖掘核心任务之一的关联规则发现已经得到了广泛的研究。而由二元关系导出的概念格则是一种非常有用的形式化工具。它体现了概念内涵和外延的统一,反映了对象和特征间的联系以及概念间的泛化与例化关系,因此非常适于发现数据中潜在的概念。分析了概念格与关联规则提取之间的关系,根据需要对格结构进行了相应的修改,提出了相应的渐进式生成算法和基于概念格的关联规则提取算法,通过定理和性质对算法进行了说明并对关联规则进行缩减。最后对格结构的复杂性进行了讨论并给出了相应的实验结果。     

概念格的属性渐减原理与算法研究

渐进式算法是概念格构造的一类重要算法,但大多关注于形式背景中对象或属性增加的情况.而当形式背景的属性减少时,已有的算法则需要重新构造概念格,较为费时.针对这一情况,研究了属性消减后从原概念格渐进式产生新概念格的理论和算法,并且算法时间复杂度较低.首先分析了原概念格和新概念格中节点间的映射关系以及从原概念格到新概念格中边(节点间的前驱-后继关系)的变化规律.在此基础上,提出了自顶向下和自底向上两种渐进式的概念格属性渐减算法.算法能够对原有概念格直接进行修改来得到新的概念格,避免了从形式背景重新构造概念格,时间复杂度降低为O(‖ L ‖·G ‖·‖M ‖).实验及分析表明,当属性减少时,能比传统算法节省大量的运行时间.     

网络表格间的快照关系发现

近年来,互联网上涌现出大量结构化的表格数据,网络表格的价值不仅在于数据本身,还在于数据之间的关系。只有探测出表格之间潜在的关系,方能更好地利用这些结构化数据。因此提出发现网络表格间的快照关系,并给出发现快照关系的框架以及检测与给定表之间满足某种匹配关系的快照表的算法,快照表可用于优化查询以及在大数据环境下实时地返回部分查询结果。提出了基于实体和属性重合度的评分方法,并引入实体新鲜度的概念,使得算法在快照关系的发现过程中更多地关注能提供新鲜实体的表;与此同时,基于Bayes模型的表格内容增强算法能更加准确地判断属性列上值的一致性,从而提高快照关系发现的准确率。大量实验表明,该评分模型能发现高质量的快照表,且在快照的查询精度和召回率上表现出色。     

基于本体的Deep Web查询接口集成

Deep Web中的海量信息只能通过查询接口访问获得,为了能够同时访问同一领域多个Web数据库,需要对多个Web数据库的查询接口进行集成.因此,引入本体技术,提出基于本体的Deep Web查询接口集成方法.Deep Web查询接口集成主要完成两个方面的工作:模式匹配与模式融合.模式匹配采用本体的"Bridge(桥接)"效应建立不同接口模式间的属性映射关系,以准确发现不同接口属性间的语义关联.模式融合根据模式匹配的结果,合并DeepWeb数据库查询接口集合中表示同一语义的属性,并尽可能地保持该领域查询接口的结构特征和属性顺序,以获得集成查询接口.通过实验分析,基于本体的DeepWeb查询接口集成方法不仅简化了模式匹配的复杂过程,而且很大程度上提高了模式集成的精度.因此,基于本体的Deep Web查询接口集成方法是高效可行的.     

面向多表连接查询优化的基数估计方法

基数估计是实现数据库多表连接（JOIN）查询优化的重要手段之一。对数据量较大的数据表进行基数估计时常用数据抽样来获得较小的样本,从而估计各种查询负载下所需的数据基数。在单表上利用数据抽样来完成基数估计的方法已经得到广泛研究,但在多个数据表的抽样样本总体存储预算存在限制时,目前仍缺乏有效的多表间样本数划分方法使得整体基数估计达到较优。为此,提出一种面向多表JOIN查询优化的基数估计方法,针对一组给定的含有复杂多JOIN操作的查询负载,为其合理分配数据库中每个表的抽样率,从而在满足样本大小总和限制的同时使得基数估计准确率达到最高。将上述过程抽象为一个抽样率分配搜索问题,在数据库数据抽样问题中引入贝叶斯优化搜索算法,利用该算法快速搜索出不同表之间抽样样本大小的分配比例,使得有限时间内获得的样本分配方案对应的基数估计准确率最高,从而达到查询优化的目的。在TPC-H数据集上的实验结果表明,在相同时间内确定多JOIN操作查询负载下基数估计准确率最高的抽样比例方案时,相比随机搜索算法,贝叶斯优化算法所得方案对应的基数估计误差率降低54.8%~60.2%。     

Deep Web adaptive crawling based on minimum executable pattern

The key to Deep Web Crawling is to submit valid input values to a query form and retrieve Deep Web content efficiently. In the literature, related work focus only on generic text boxes or entire query forms, causing the problem of “data islands” or inferior validity of query submission. This paper proposes the concept of Minimum Executable Pattern (MEP), a minimal combination of elements in a query form that can conduct a successful query, and then presents a MEPGeneration method and a MEP-based Deep Web adaptive crawling method. The query form is parsed and partitioned into MEP set, and then local-optimal queries are generated by choosing a MEP in the MEP set and a keyword vector of the MEP. Furthermore, the crawler can make a decision on its termination to balance the trade-off between high coverage of the content and resource consumption. The adoption of MEP is expected to improve the validity of query submission, and adaptive selection of multiple MEPs shows good effect for overcoming the problem of “data islands”. We present a set of experiments to validate the effectiveness of the proposed method. Experimental results show that our method outperforms the state of art methods in terms of query capability and applicability, and on average, it achieves good coverage by issuing only a few hundred queries.     

DeepWeb信息集成系统中查询转换

随着Internet信息的迅速增长,许多Web信息已经被各种各样的可搜索在线数据库所深化,并被隐藏在Web查询接口下面。传统的搜索引擎由于技术原因不能索引这些信息——DeepWeb信息。由于DeepWeb惟一“入口点”是查询接口,为使查询接口自动产生有意义有查询,给出了DeepWeb信息集成系统框架,提出了基于数据类型的搜索驱动的用户查询转换方法,基于此设计并实现了一个针对中文DeepWeb信息集成原型系统。通过在实际DeepWeb站点上的实验证明了此方法是非常有效的。     

基于属性相关度的Web数据库大小估算方法

提出了一种基于词频统计的方法以估算Web数据库的规模.通过分析Web数据库查询接口中属性之间的相关度来获取某个属性上的一组随机样本;并对该属性分别提交由前k位高频词形成的试探查询以估算Web数据库中记录的总数.通过在几个真实的Web数据库上进行实验验证,说明该方法可以准确地估算出Web数据库的大小.     

主题分布在Deep Web数据库选择中的应用

随着越来越多的信息隐藏在Deep Web中,针对用户查询找出最相关的Web数据库成为亟待解决的问题。提出了一种基于Web数据库主题分布的方法用于Deep Web数据集成中的Web数据库选择。获取主题覆盖度形式的Web数据库内容描述,而后利用选定的Web数据库获取查询主题,最终由查询主题和主题分布矩阵来选择Web数据库。在真实Web数据库上的实验结果表明,该方法既取得了较高的查询召回率,也可有效降低数据库内容描述建立的代价。     

Regularized query classification using search click information

Hundreds of millions of users each day submit queries to the Web search engine. The user queries are typically very short which makes query understanding a challenging problem. In this paper, we propose a novel approach for query representation and classification. By submitting the query to a web search engine, the query can be represented as a set of terms found on the web pages returned by search engine. In this way, each query can be considered as a point in high-dimensional space and standard classification algorithms such as regression can be applied. However, traditional regression is too flexible in situations with large numbers of highly correlated predictor variables. It may suffer from the overfitting problem. By using search click information, the semantic relationship between queries can be incorporated into the learning system as a regularizer. Specifically, from all the functions which minimize the empirical loss on the labeled queries, we select the one which best preserves the semantic relationship between queries. We present experimental evidence suggesting that the regularized regression algorithm is able to use search click information effectively for query classification.     

频繁项集在Deep Web数据源聚类中的应用

在Deep Web页面的背后隐藏着海量的可以通过结构化的查询接口进行访问的数据源。将这些数据源按所属领域进行组织划分,是DeepWeb数据集成中的一个关键步骤。已有的划分方法主要是基于查询接口模式和提交查询返回结果,存在查询接口特征难以完全抽取和提交数据库查询效率不高等问题。提出了一种结合网页文本信息,基于频繁项集的聚类方法,根据数据源查询接口所在页面的标题、关键词和提示文本,将数据源按照领域进行聚类,有效解决了传统方法中依赖查询接口特征以及文本模型的高维性问题。实验结果表明该方法是可行的,具有较高的效率。     

Deep Web查询接口研究

Deep Web查询接口是Web数据库的接口,其对于Deep Web数据库集成至关重要。本文根据网页表单的结构特征定义查询接口;针对非提交查询法,给出界定Deep Web查询接口的一些规则;提出提交查询法,根据链接属性的特点进行判断,找到包含查询接口的页面;采用决策树C4.5算法进行分类,并用Java语言实现Deep Web查询接口系统。     

基于最优查询的多领域deep Web爬虫*

Deep Web信息通过在网页搜索接口提交查询词获得。通用搜索引擎使用超链接爬取网页,无法索引deep Web数据。为解决此问题,介绍一种基于最优查询的deep Web爬虫,通过从聚类网页中生成最优查询,自动提交查询,最后索引查询结果。实验表明系统能自动、高效地完成多领域deep Web数据爬取。     

Strategy for mining association rules for web pages based on formal concept analysis

To avoid returning irrelevant web pages for search engine results, technologies that match user queries to web pages have been widely developed. In this study, web pages for search engine results are classified as low-adjacence (each web page includes all query keywords) or high-adjacence (each web page includes some of the query keywords) sets. To match user queries with web pages using formal concept analysis (FCA), a concept lattice of the low-adjacence set is defined and the non-redundancy association rules defined by Zaki for the concept lattice are extended. OR- and AND-RULEs between non-query and query keywords are proposed and an algorithm and mining method for these rules are proposed for the concept lattice. The time complexity of the algorithm is polynomial. An example illustrates the basic steps of the algorithm. Experimental and real application results demonstrate that the algorithm is effective.