一种基于近邻规则的缺失数据填补方法

数据缺失是数据挖掘与分析过程中的常见问题,若直接删除含缺失的事例可能导致不可靠的决策。为此,针对缺失数据的填补问题,提出一种基于近邻规则的缺失数据填补方法。根据关联规则的后件数据项进行分类,计算分类后的规则项与缺失项集间的相似度,用最相似的规则项值填补缺失值。实验结果表明,该方法具有较高的填补正确率。     

一种对象完备度优先填补的决策树规则提取算法

不完备信息系统中决策规则的提取是数据挖掘领域的重要研究问题。对不完备信息系统中决策规则的主要获取方法进行分析,以决策属性具有缺失值的不完备决策表为研究对象,提出一种基于数据优先填补的决策树规则提取算法。针对ROUSTIDA算法在数据填补时运算量较大且容易导致决策规则冲突这一问题,算法采用决策属性优先填补的思想,引入对象完备度概念对其进行改进,使用改进的ROUSTIDA算法对不完备决策表进行一次性数据填补预处理,并在限制容差关系下采用属性重要性为启发函数构建决策树,从而获得决策规则。实例表明该方法是有效的,生成的决策规则简单,且具有较高的精确度。     

改进填补法和多权重相似度相结合的推荐算法

针对传统推荐算法中存在的数据稀疏性问题,国内外许多研究人员都提出了相应的推荐算法。然而,在个性化推荐方面,其中大多数并没有取得很好的推荐效果。因此,提出改进填补法和多权重相似度相结合的推荐算法,该算法首先采用改进填补法填充缺失值并对数据降维,接着分别计算社交网络用户信任度和改进的二部图用户关联度,最后采用多权重因子将这两者相似度进行结合。基于此,该算法根据相似度高低获取邻居用户并对目标用户进行商品推荐。实验结果表明,在数据稀疏性以及个性化推荐情况下,该算法的平均绝对误差（MAE）优于其他推荐方法。     

基于不完备数据聚类的缺失数据填补方法

缺失数据的处理是数据挖掘领域进行数据预处理的一个重要问题.传统的缺失数据填补方法大部分是基于概率分布等一些统计假设,对于大数据集的数据挖掘不一定是最适合的方法.受不完备数据分析(ROUSTIDA)未采用传统的概率统计学方法启发,提出基于不完备数据聚类的缺失数据填补方法(MIBOI),针对分类变量不完备数据集定义约束容差集合差异度,直接计算不完备数据对象集合内所有对象的总体相异程度,以不完备数据聚类的结果为基础进行缺失数据的填补.采用UCI机器学习基准数据集进行实验表明,MIBOI对缺失数据的填补是有效可行的.     

基于最小Steiner树的关键词查询方法

在关系数据库中,关键词查询无需用户学习查询语言和数据库模式相关知识,而且有效地扩大了查询范围.采用元组图描述关系数据库中元组关系,可使关键词查询问题转化为元组图的最小Steiner树求解问题.本文提出元组图上基于相似度的边权重计算方法,使边权重能够反映元组与关键词相似度的大小.然后,鉴于最小Steiner树求解问题是NP-完全问题,提出按照贪心策略执行Dijkstra算法的最小Steiner树较优解求解算法.最后,通过实验对算法进行了分析和验证.     

粗关系数据库查询模型

针对粗关系数据库中数据的特性,提出一种不确定性数据的存储方法。基于汉明距离的一种变式,计算元组间距离,构成距离矩阵,根据距离矩阵将相同或相近的元组归类,从而有效地对表中的元组进行索引。借助粗集中的上、下近似,通过计算用户查询的数据与粗关系数据库中数据的相似度,查询出用户所需的数据。结合以上方法构建粗关系数据库查询模型,设计相应的查询算法并应用于实例中。     

不完备区间值决策系统的三支决策模型及增量式规则获取算法

在现实应用中,区间值数据会因为测量、干扰或信息传输等噪声影响导致数据出现缺失值,而且这些数据随着时间推移呈现动态递增趋势,忽略或删除这些数据很有可能导致有用信息的丢失而出现决策误判。为此,针对这一问题,提出面向不完备区间值决策系统的三支决策模型和增量式规则获取算法。首先定义不完备区间值数据的量化相似容差关系,构造出基于不完备区间值决策系统的三支决策模型;其次从两个层级分析对象集动态规则获取策略,提出增量式规则获取算法;最后,通过一组UCI数据集对该算法进行验证。实验结果表明,该算法不仅能减少误划分损失获得更高的划分精度,而且在运行时间上也具有较大优越性。     

基于相似度融合和动态预测的兴趣点推荐算法

现有的兴趣点推荐算法大都存在两个问题：第一,算法中利用用户签到的历史数据,而忽略了用户的评论和标签等信息,不能很好地解决冷启动问题。第二,部分算法在计算相似度时仅使用用户的签到评分,而由于POI签到矩阵的高稀疏性,会导致推荐结果不准确。鉴于上述问题,提出了利用潜在的狄利克雷分配（Latent Dirichlet Allocation,LDA）主题模型挖掘用户的兴趣话题,融合签到数据进行相似度度量,很好地解决了冷启动问题。在推荐生成阶段提出了一种动态预测法,动态填补缺失的访问概率,进一步缓解数据稀疏,提高推荐质量。在真实数据集上的实验结果表明,基于相似度融合和动态预测的兴趣点推荐算法有效解决了数据稀疏性和冷启动问题,推荐性能优于传统的推荐算法。     

时空大数据的缺失数据流关联修复仿真

传统方法对缺失数据进行修复,通常存在填补效果较差、所需时间较长和填补准确度较低等问题。提出一种针对时空大数据的缺失数据流关联修复方法。方法首先利用数据流之间的关联规则创建条件函数依赖,然后对数据流之间的关联相似度进行计算,并通过该相似度结果进一步计算缺失数据的加权值,完成对缺失数据和相应的临界点之间融合情况的检测。最后选择最佳置信度方法决定缺失数据的修复顺序,以实现对时空大数据缺失数据流的修复。经过仿真证明,提出的方法对缺失数据流检测准确,且修复效果好,经过修复的数据流与原始时空大数据十分接近。     

工业过程数据中缺失值处理方法的研究

针对工业生产中过程数据的缺失问题,首次提出了运用多重填补方法处理工业过程的缺失数据.阐述了常用的缺失数据处理方法,指出各方法的优缺点.在此基础上,通过建立回归模型,针对多变量工业数据中缺失值较少和较多时的两种情况,分别用删除含缺失值的个案,简单填补和多重填补(MI)3种方法对数据进行处理,利用处理后的新数据集进行数据挖掘,预测目标变量的值,并对预测结果进行分析比较.实验结果表明,多重填补方法的处理效果最好,为工业数据的缺失值处理提供了有用的策略.     

基于关系数据库的关键词查找排序策略

基于关系数据库的关键词查找技术像使用搜索引擎一样获取数据库中相关的数据.针对RDBMS上具体书目索引数据库的关键词查找高效性问题,提出了对返回结果集的一种排序策略.以查询序列与结果元组树之间的相似值作为排序依据,参照传统信息检索系统上关键词查找结果集排序的相似值计算公式,提出数据库上查询序列与结果元组树之间的相似值公式,并分析与重新定义了相关影响因子的标准化函数表达式.通过在简单数据库上的分析验证了该改进是合理的.     

Incremental Evaluation of Sliding-Window Queries over Data Streams

Two research efforts have been conducted to realize sliding-window queries in data stream management systems, namely, query revaluation and incremental evaluation. In the query reevaluation method, two consecutive windows are processed independently of each other. On the other hand, in the incremental evaluation method, the query answer for a window is obtained incrementally from the answer of the preceding window. In this paper, we focus on the incremental evaluation method. Two approaches have been adopted for the incremental evaluation of sliding-window queries, namely, the input-triggered approach and the negative tuples approach. In the input-triggered approach, only the newly inserted tuples flow in the query pipeline and tuple expiration is based on the timestamps of the newly inserted tuples. On the other hand, in the negative tuples approach, tuple expiration is separated from tuple insertion where a tuple flows in the pipeline for every inserted or expired tuple. The negative tuples approach avoids the unpredictable output delays that result from the input-triggered approach. However, negative tuples double the number of tuples through the query pipeline, thus reducing the pipeline bandwidth. Based on a detailed study of the incremental evaluation pipeline, we classify the incremental query operators into two classes according to whether an operator can avoid the processing of negative tuples or not. Based on this classification, we present several optimization techniques over the negative tuples approach that aim to reduce the overhead of processing negative tuples while avoiding the output delay of the query answer. A detailed experimental study, based on a prototype system implementation, shows the performance gains over the input-triggered approach of the negative tuples approach when accompanied with the proposed optimizations     

Bayesian networks for supporting query processing over incomplete autonomous databases

As the information available to naïve users through autonomous data sources continues to increase, mediators become important to ensure that the wealth of information available is tapped effectively. A key challenge that these information mediators need to handle is the varying levels of incompleteness in the underlying databases in terms of missing attribute values. Existing approaches such as QPIAD aim to mine and use Approximate Functional Dependencies (AFDs) to predict and retrieve relevant incomplete tuples. These approaches make independence assumptions about missing values—which critically hobbles their performance when there are tuples containing missing values for multiple correlated attributes. In this paper, we present a principled probabilistic alternative that views an incomplete tuple as defining a distribution over the complete tuples that it stands for. We learn this distribution in terms of Bayesian networks. Our approach involves mining/“learning” Bayesian networks from a sample of the database, and using it to do both imputation (predict a missing value) and query rewriting (retrieve relevant results with incompleteness on the query-constrained attributes, when the data sources are autonomous). We present empirical studies to demonstrate that (i) at higher levels of incompleteness, when multiple attribute values are missing, Bayesian networks do provide a significantly higher classification accuracy and (ii) the relevant possible answers retrieved by the queries reformulated using Bayesian networks provide higher precision and recall than AFDs while keeping query processing costs manageable.     

Efficient histogram-based range query estimation for dirty data

In recent years, data quality issues have attracted wide attentions. Data quality problems are mainly caused by dirty data. Currently, many methods for dirty data management have been proposed, and one of them is entity-based relational database in which one tuple represents an entity. The traditional query optimizations are not suitable for the new entity-based model. Then new query optimizations need to be developed. In this paper, we propose a new query selectivity estimation strategy based on histogram, and focus on solving the overestimation which traditional methods lead to. We prove our approaches are unbiased. The experimental results on both real and synthetic data sets show that our approaches can give good estimates with low error.     

采用元组聚类的增量式数据分区方法

数据分区是提升数据库可扩展能力的有效方法。在事务查询密集的系统中,合理的分区策略可减少分布式事务查询数量,并提高事务查询响应速度。提出了一种基于元组聚类的增量式分区方法,通过将元组聚簇和采用分区感知的数据筛选策略来降低算法的复杂度。首先依据时间窗口模型聚类元组,并构建簇节点图,然后利用分区感知策略对图进行删减,最后采用图划分算法对图进行子图划分来得到分区。与现有方法相比,该方法减少了分区响应时间,保证了较少的分布式事务数量,并提高了分区事务查询速度。     

基于维度分组降维的高维数据近似k近邻查询

针对现有的高维空间近似k近邻查询算法在数据降维时不考虑维度间关联关系的问题,首次提出了基于维度间关联规则进行维度分组降维的方法.该方法通过将相关联维度分成一组进行降维来减少数据信息的损失,同时针对Hash降维后产生的数据偏移问题,设置了符号位并基于符号位的特性对结果进行精炼;为提高维度间关联规则挖掘的效率,提出了一种新的基于UFP-tree的频繁项集挖掘算法.通过将数据映射成二进制编码来进行查询,有效地提高了近似k近邻查询效率,同时基于信息熵筛选编码函数,提高了编码质量;在查询结果精炼的过程,基于信息熵对候选集数据的编码位进行权重的动态设定,通过比较动态加权汉明距离和符号位碰撞次数返回最终近似k近邻结果.理论和实验研究表明,所提方法能够较好地处理高维空间中近似k近邻查询问题.     

基于元组存在性的概率数据模型研究

随着信息与通讯技术的快速发展,数据管理正面临着越来越多的挑战,其中之一就是数据的不确定性。提出一种基于元组存在性的概率数据模型相似文献   

数据流查询计划的并行迁移策略

数据流中的查询计划需要不断进行适应性优化,针对该特征提出一种查询计划的并行迁移策略。该策略能确保在输出过程中不丢。失元组或产生冗余元组,维持正确的元组输出时序。实验结果证明,该策略可以使查询计划平滑过渡,避免迁移过程出现无元组输出的空自期,在系统资源紧张和数据流流速过大时,维持较少的中间元组数和较大输出速率。