基于局部聚类的轨迹数据流偏倚采样

移动对象轨迹数据管理是移动计算领域的研究热点。通过采样技术构造数据流摘要是普通采用的方法之一。传统的均匀采样往往容易丢失某些关键变化数据。利用轨迹数据流的局部连续性特征,提出一种基于滑动窗口的偏倚采样算法。算法将滑动窗口通过聚类划分成若干大小不一的基本窗口,并针对每个基本窗口给定一个采样率,对窗口内数据进行偏倚采样,从而形成数据流摘要。算法利用了轨迹数据的内在特征,因此具有较高的采样质量。最后,基于实际数据对算法进行了实验,结果证明了算法的有效性。     

面向不确定数据流的近似ER-Topk查询处理

随着移动互联网的快速发展以及信息技术的普遍应用,在许多应用中都产生了海量、不确定性数据,包括金融、军事、位置服务、医疗以及气象等。然而,传统的确定性数据管理方法很难管理不确定数据,亟需开发新型数据管理方法。可能世界模型被广泛用于为不确定数据建模,通过该模型可以衍生出诸多确定性的可能世界实例。不确定性数据流是指高速到达的海量不确定元组序列,因而不确定数据流管理比不确定性静态数据管理更具挑战性。面向于不确定数据流的ER-Topk查询是一个典型问题,但是处理复杂度高。提出一种近似算法来处理该查询,具有较小的空间复杂度;同时,还通过搜索策略优化来进一步提升查询处理效率。实验结果验证了所提方法的有效性和高效性。     

基于滑动窗口密度聚类的数据流偏倚采样算法

对于移动计算领域的移动对象轨迹数据流的管理,最普遍采用的技术手段是采样技术,而传统的均匀采样易丢失一些关键的变化数据,造成信息丢失现象.针对这一问题,提出一种基于概率密度聚类的数据流偏倚采样算法.该算法在滑动窗口模型下,充分利用了轨迹数据流自身的分布特性,结合偏倚采样算法思想克服了均匀采样的数据丢失问题.算法首先采用基于数据存在密度的聚类技术将滑动窗口划分为强簇、弱簇和过度簇,然后针对不同的簇给予不同的采样率,进行偏倚采样,进而得到最终的数据流摘要.经过实际数据集的实验检测,证明算法较好地保证了采样质量,并具有较快的数据处理能力.     

基于查询采样的高维数据混合索引

为了改进高维数据库查询的效率,通常需要根据数据分布来选择合适的索引策略.然而,经典的分布模型难以解决实际应用中图像、视频等高维数据复杂的分布估计问题.提出一种基于查询采样进行数据分布估计的方法,并在此基础上提出了一种支持最近邻查询的混合索引,即针对多媒体数据分布的不均匀性,自适应地对不同分布的数据使用不同的索引结构,建立统一的索引结构.为了实现混合索引,采用构造性方法:首先通过聚类分解分割数据并建立树状索引;然后使用查询采样算法,对数据实际分布进行估计;最后根据数据分布的特性,把稀疏数据从树状索引中剪裁出来,进行基于顺序扫描策略的索引,而分布比较密集的数据仍然保留在树状索引中.在4个真实的图像数据集上进行了充分的实验,结果显示,该索引方法明显优于iDistance,M-Tree等度量空间索引,在维数达到336时,查询效率仍高于顺序扫描.实验结果显示,该查询采样算法在采样数据量仅为N~(1/2)(N为数据量)的情况下即可获得满足索引需要的分布估计结果.     

基于E2LSH的轨迹KNN查询算法

目前海量时空轨迹数据近邻查询算法中存在计算时间复杂度较高的问题,因此提出了一种结合领域POI数据和E2LSH算法的轨迹KNN查询算法。首先利用GeoHash技术对地理空间进行编码,然后结合POI数据实现向量空间的初步降维,进而根据停留时间构建每条轨迹的向量,采用局部敏感哈希函数运算结果建立轨迹索引,最后对查询返回的相似轨迹集合分别进行距离计算,经过排序得到距离最近的K个查询结果。对于增量的轨迹数据,利用E2LSH算法计算哈希值,直接添加轨迹索引,从而避免了复杂的计算过程以及对现有轨迹索引的影响。基于合成数据及真实数据集的实验结果表明,该方法在海量时空轨迹数据的近邻查询中,虽然牺牲了一定的准确率,但有效提升了算法效率,并能够高效简便地处理增量的时空轨迹数据。     

基于数据流的近似查询计算及其应用研究

通过分析基于实化聚集视图的查询重写方法，将相关的查询计算理论与数据流的查询相结合，针对数据流的特征，给出了一种具有广泛应用前景的基于数据流的近似查询计算方案。     

二阶段近似KNN离群挖掘算法与应用

针对高维大数据集，提出了二阶段近似最近邻离群挖掘算法（TPOM），在聚类的基础上，通过加速最近邻查询和改善剪枝效率，提高了循环嵌套KNN算法的离群检测效率。应用分析表明，该算法对于实际数据集有良好的适用性和可扩展性，具有近似线性的时间复杂度。     

基于K-均值聚类的小样本集KNN分类算法

KNN及其改进算法进行分类时,如样本集中、样本过少或各类样本的密度差异较大,都将会影响最后的分类精度。提出一种基于聚类技术的小样本集KNN分类算法。通过聚类和剪理,形成各类的样本密度接近的新的样本集,并利用该新样本集对类标号未知数据对象进行类别标识。通过使用标准数据集的测试,发现该算法能够提高KNN的分类精度,取得了较满意的结果。     

不确定性对象的反向最近邻查询

多数不确定性对象的反向近邻查询不能明确回答某个不确定性对象是否为查询对象的反向最近邻,针对该问题,提出概率反向最近邻查询的概念,设计不确定性对象的概率反向最近邻查询的索引结构,给出一种基于该结构的不确定性对象的反向最近邻查询算法。     

基于Voronoi划分的位置数据KNN查询处理方法

K最近邻(KNN)查询是空间数据查询研究的重要内容。目前的KNN查询方法在处理大规模的位置数据时,存在着更新和查找失衡的问题,导致查询效率较低。因此,提出基于Voronoi划分的位置数据KNN查询处理方法。首先,创建了一个二级空间索引结构——VRI,包含VHash和VR树两部分。一级索引结构VHash表示Voronoi图的直邻;二级索引结构VR树,按照各Voronoi单元所在的最小矩形区域的重叠面积,自下而上地生成对应的R树。其次,基于VRI索引结构提出了位置数据的KNN查询算法及动态维护算法,在KNN查询方法中,采用VR树进行定位,VHash查找K近邻,能够有效地对查询点定位,查找速度快。再次,针对数据更新的情况,索引结构也能够及时更新,在更新的时间段内,对于位置数据随时间变化的KNN查询,提出了利用记录表进行有效查询的方法。最后,实验表明,提出的基于Voronoi划分的空间索引结构和其对应的KNN查询算法均具有较好的性能和适应性。     

结合属性值贡献度与平均相似度的KNN改进算法

与传统的K-近邻算法不同,提出了一种结合属性值贡献度与平均相似度的KNN改进算法。首先考虑测试样本与相似样本点间的平均相似度,其次考虑不同类别中的相似样本点的个数,最后还考虑与相似样本相同的属性值对类别的贡献度。在蘑菇数据集上进行实验结果表明,改进后的KNN分类算法的准确率比传统的K-近邻分类算法的准确率更高。     

基于Storm的流数据KNN分类算法的研究与实现

KNN算法是一种简单、有效且易于实现的分类算法,可用于类域较大的分类。近年来对KNN算法的研究偏向于静态大数据集,不过,在越来越多的情况下要用KNN算法在线实时处理流数据。考虑到流式数据流量大,连续且快速,不易存储和恢复等特性,以及流处理系统Storm对流数据处理具有实时性、可靠性的特点,提出了基于Storm的流数据KNN分类算法,该算法首先对整个样本集进行划分,形成多个片集,然后计算出待分类向量在各片集上的[K]近邻,最后再将所有片集[K]近邻归约得出整体[K]近邻,实现待分类向量的分类。实验结果表明,基于Storm的流数据KNN分类算法能够满足大数据背景下对流数据分类的高吞吐量、可扩展性、实时性和准确性的要求。     

一种改进的KNN文本分类

在文本分类中,文本特征空间维数巨大以及训练样本分布不均衡等问题影响分类性能。针对这个问题,提出一种改进的KNN分类方法。利用隐含语义分析方法对特征样本空间进行降维处理;利用基于样本密度的改进的KNN分类器进行分类。实验结果表明提出的方法能够收到较好的分类效果。     

基于KNN图的空间离群点挖掘算法

空间数据集中离群数据与正常数据之间的非空间属性值相差较大。针对该情况,提出一种基于K-最邻近(KNN)图的空间离群点挖掘算法。该算法通过所有对象的K近邻关系构造KNN图,将相邻对象非空间属性值的差作为2个对象点间的边权值,利用裁边策略去掉权值较高的边,从而识别出空间离群点和离群区域。实验结果表明,该算法的时间性能优于POD算法。     

基于熵权的K最临近算法改进

维度灾难直接影响到K最临近算法（KNN）的效率和准确率,将信息论中的信息熵理论与KNN算法结合起来,用信息熵理论进行属性约简,并根据特征属性与分类的相关度来确定各属性的权限,从而建立相关度与权重的内在联系。仿真实验表明,与传统的KNN相比,基于熵权的KNN改进方法在保持分类效率的情况下,使分类器的准确率得到了极大的提高。     

一种事件驱动的数据流查询模型

分析数据流上事件的语义和特点,建立了事件驱动的数据流模型EQM.提出一种具有事件监控,事件定义和事件驱动功能的语言EQL,讨论了事件监控和事件驱动查询的优化算法以及相关的效率问题和实时性.实验表明,该模型在解决数据流上事件相关问题比现有的数据流模型和处理方法有着更好的性能.     

面向路网连通关系的车辆轨迹数据查询技术研究

定位及通信技术的发展使获取和传输移动车辆的轨迹信息成为可能。从车辆轨迹数据中可以提取出大量的交通信息,这些信息是对交通状况的一个直接和全面的反映。但由于轨迹数据固有的网络特性及时空特性,使针对此类数据的查询成为一个难点,其中关键技术包括建立用于车辆轨迹数据的索引结构及其对应的轨迹数据查询语言。在比较现有轨迹数据索引结构的基础上,对轨迹数据查询语言的分类及其与索引结构之间的调用关系进行了初步的探讨,提出了面向连通关系的查询语言（connectivity-oriented query language, CQL）的定义、分类及实现方法,并简要讨论了车辆轨迹数据查询原型系统的结构和实现方法。     

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

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

一种支持流数据的查询语言

流数据的查询应用十分广泛,而标准SQL语言不支持这类查询功能,因此有必要对标准SQL语言进行扩展,以满足流数据的查询应用需求。支持流数据的查询语言StreamSQL在标准SQL语言的基础上增加了对流数据对象的处理机制,通过引入滑动窗口的概念,以支持流数据与关系表的相互转换操作,同时提供用户自定义函数功能,弥补了SQL在流数据处理方面的不足。     

基于聚类算法的KNN文本分类算法研究

KNN算法是一种在人工智能领域如专家系统、数据挖掘、模式识别等方面广泛应用的算法。该算法简单有效,易于实现。但是KNN算法在决定测试样本的类别时,是把所求的该测试样本的K个最近邻是等同看待的,即不考虑这Ｋ个最近邻能表达所属类别的程度。由于训练样本的分布是不均匀的,每个样本对分类的贡献也就不一样,因此有必要有区别的对待训练样本集合中的每个样本。利用聚类算法,求出训练样本集合中每个训练样本的隶属度,利用隶属度来区别对待测试样本的K个最近邻。通过实验证明,改进后的KNN算法较好的精确性。