PMkSK:一种空间关键字移动近邻查询并行处理方法

为了提高空间关键字移动k近邻查询处理效率,提出关键字影响集的概念,并设计了一种基于关键字影响集的空间关键字移动近邻查询并行处理方法.该方法包含一种并行查询算法和一种并行验证算法.首先,采用并行查询算法计算近邻结果;然后,确定查询区域,并在区域内查找包含的关键字影响集;最后,在查询者移动时不断通过并行验证算法验证影响集,以实现空间关键字移动近邻查询处理.实验结果表明:这2种算法的时间复杂度分别为O((log D+k)/k)和O(logk),均为现有对应算法的O(1/k),其中D为空间对象数目.在多核系统上,这2种算法的运行时间均比现有算法低一个数量级.基于影响集的并行查询处理方法避免了基于安全区域的移动k近邻查询处理方法中更新代价和更新频率难以同时取得最优的固有缺点,可以高效地处理关键字移动k近邻查询.     

一种采用预排序策略的多核并行skyline算法

为提升大规模多维数据集的skyline计算效率,提出了一种多核并行算法MPSCS(multi-core parallelskyline computation based on sorting).首先按照任意一维对数据集进行预排序,然后划分为多个子集,使用skeleton并行程序设计模型进行并行化处理.与未采用预排序策略的多核并行算法相比,MPSCS算法处理过程简单,具有较好的渐进性、用户友好性和效率.实验结果表明,对规模较大、维数较高的数据集,效率可提高30%～40%,相对加速比可达线性.     

无索引空间数据库的基于最优点的集合最近邻查找算法

针对度量空间中的无索引空间数据库,提出一种基于最优点的集合最近邻查找算法及其改进算法.采用真实数据集与人工生成的数据集对算法进行测试,评估所提出算法的效率.实验结果表明,所提算法的效率优于组最近邻居查询算法,并且对于高维数据空间,所提出的算法有较高的稳定性.由于查询区域中数据点的数量比较少,改进的基于最优点的集合最近邻...     

基于并行的非支配排序遗传Ⅱ算法优化双聚类

双聚类是微阵列基因表达数据分析中很实用的一种数据挖掘技术,它是一种同时对微阵列基因和条件进行聚类的方法,用来挖掘基因子集在条件子集下所体现出来的生物模式。传统的双聚类算法对于庞大的基因表达数据处理效率很弱,考虑在j Metal平台上实现基因表达数据的双聚类的一种新的研究方法及思路。同时考虑加入并行策略,提高算法的效率。在酵母啤酒细胞基因表达集和人类B-细胞两个标准数据集上对两个算法进行实验验证,表明所提出算法比其他多目标双聚类算法呈现出更好的优越性。     

基于类内和类间距离的粗粒度并行AP聚类算法

近邻传播(Affinity Propagation,AP)聚类是基于数据点间消息传递的算法,主要通过数据间的相似度实现聚类.与传统的聚类方法相比,AP聚类无需事先给定聚类数目就可实现聚类,因此具有快速高效的优点,然而在处理高维复杂数据集时存在随着聚类效率提升而准确度不高的问题.为改善AP聚类算法的效率和精度,提出基于类内和类间距离的粗粒度并行AP聚类算法——IOCAP.首先引入粒度思想将初始数据集划分成多个子集;其次对各子集结合类内和类间距离进行相似度矩阵的改进计算,最后基于MapReduce模型实现改进后的并行AP聚类.在真实数据集上的实验表明,IOCAP算法在大数据集上有较好的适应性,能在保持AP聚类效果的同时有效地提升算法精度.     

面向组近邻的Top-k空间偏好查询

空间偏好查询是当前空间查询研究中的一类热点问题,而现有的空间偏好查询不能有效支持面向组用户的位置服务应用.为此,提出一类新型空间偏好查询——面向组近邻的Top-k空间偏好查询(Topk spatial preference query for group nearest neighbor).该查询通过查找特征对象的λ子集组近邻最终为用户返回评分值最高的前k个λ子集.为了高效执行这一查询,给出了两种查询算法:TSPQ-G及TSPQ-G*.其中TSPQ-G*在TSPQ-G的基础上,通过空间剪枝及高效的特征对象索引树遍历策略大幅减少I/O代价,进而有效提高了该查询的执行效率.实验采用多个数据集验证了所提算法在不同参数设置下的有效性.     

数据挖掘中并行离散化数据准备优化

在海量数据挖掘中,针对元数据的离散化数据准备处理能有效提高数据挖掘效率.本文提出了一种并行比较并获得最优离散化的数据准备算法(AOA),针对不同数据集,先进行数据集的特性检测以获得数据集分布特性,按照分布特性进行数据集的异常值检测和剔除,并行完成与分布特性适配的离散化方法处理,通过比较不同离散化方法的熵、方差指数、稳定性参数的最小欧氏距离,根据三个参数自动化比选,获得最优离散化的预处理成果.仿真表明,对不同样本数据库进行关联规则挖掘结果中,比较四种固定的离散化数据预处理方法,在使用AOA数据准备算法并行比选出最优的离散化来数据预处理后,在不同最小支持度阈值情况下,挖掘得到关联规则数都更少,因此效率得到提高.     

一种并行的加速K-近邻分类方法

文章针对传统K-近邻分类方法学习效率低下的问题,提出一种基于并行计算的加速K-近邻分类方法(K-nearest neighbor classification method based on parallel computing,PKNN),即并行K-近邻分类.该方法首先将所需要分类的样本划分为不同的工作子集,然后在每个子集上进行并行的K-近邻分类.由于划分后每个工作子集的规模均远小于整个数据集的规模,因此降低了分类算法的复杂度,可有效处理大规模数据的分类问题.实验结果表明,PK-NN方法能提高分类效率.     

基于重用技术的相互Skyline查询算法

提出了一种新的Skyline查询,即相互Skyline查询(MSQ).给定一个对象集合P和一个查询对象q,MSQ返回一个对象集合,它的每个对象既在q的动态Skyline中,同时也在q的可逆Skyline中.基于传统的R-tree索引、重用堆信息技术以及启发式的修剪策略,显著降低了I/O成本,改进了基于BBS算法和BBRS算法实现的MSQ算法.几个真实数据集的实验表明提出的算法有效而高效,比一般MSQ算法快几个数量级.     

面向生产调度规则挖掘的关键属性提取技术

针对生产调度规则提取工作对数据集属性约简的客观需求,提出了一种关键属性提取技术.首先,分析了生产数据的特点,并依据重要性和关联性,将生产数据的属性划分为多个集合;然后,在此基础上利用模糊熵与聚类准确度建立重要性目标函数,用于发现重要属性.最后,利用关联性分析查找重要属性的关联属性,将相关属性进行合并,形成重要复合属性,以进一步增强属性提取效果.为了验证该技术的有效性,将利用该技术所获取的数据子集与通过随机法所得到的数据子集进行了对比,分析比较了各数据子集的相容性和规则提取准确性.结果表明,提取属性后所形成的数据子集具有较低不相容度,浓缩了原始数据集的调度规则知识,可显著提升多种生产调度规则挖掘算法的准确度与效率.该技术非常适用于生产调度规则挖掘数据预处理阶段的关键属性提取工作.     

一种新的基于FP_Growth的频繁项目集并行挖掘算法

频繁项目集挖掘用于发现项目之间的关联规则.为了高效求解面向大数据的频繁项目集,本文提出一种新的基于FP_Growth的频繁项目集并行挖掘算法NPFP_Growth(New Parallel algorithm based on FP_Growth),该算法对频繁模式树的存储结构进行改进,基于Map/Reduce并行计算模型,利用HDFS实现数据存储,在各自计算节点上构造局部频繁模式树,求解该局部频繁模式树中每个分支的最长全局频繁项目集;对于全局非频繁项目集,计算其支持数,发送至相应计算节点进行支持度统计,从而以较为简单的算法实现频繁项目集并行挖掘.实验表明,NPFP_Growth算法具有较高的计算效率和良好的可伸缩性.     

面向测试用例生成的集合进化算法实现

基于集合进化优化方法,实现新的测试用例生成方法.实现的算法中,一个个体包含多个测试用例,一次运行该算法能够生成满足测试需求的测试用例集.实验结果表明,将实现的方法用于具体程序能够生成覆盖所有分支的测试用例集.     

面向三维城市地理信息系统的体相交分析方法的实现与应用

提出一种应用于三维城市地理信息系统的空间分析方法:体相交分析。该方法先后输入两个体数据集, 经过分析计算, 输出一个关系集合, 集合中的每一条关系代表第一个输入数据集 中的一个体对象与第二个输入数据集中的一个或多个体对象之间存在的相交关系。基于 OO3D 数据模型, 实现了一种稳定、快速 的体相交分析算法,并将其应用到一个三维城市地理信息系统项目(TG-U-3D) 之中。在该项目中, 体相交分析用于辅助检测城市地下空间规划过程中的用地冲突, 以及查询某一城市设施所位于或者穿越的地层。     

一种基于B+树的RFID抗冲突算法

针对二进制树形算法冲突集合分裂速度慢、标签分裂不均匀问题,提出一种基于B+树的RFID抗冲突算法.本算法将冲突集合分裂成一个3阶的B+树,即将每次发生冲突的集合分裂成3个子集,从而加快冲突集合的分裂速度,冲突集合相当于B+树的中间节点,每个子集分别对应于一个关键码,叶子节点或只包含一个标签或为一个空集合.为了防止集合分裂的不均匀,引入合适的hash函数,使集合均匀分裂.仿真实验表明,B+算法减少了标签冲突的发生,缩短了标签识别延时,提高了识别性能.     

基于有向无环图的函数依赖一致性数据生成

针对函数依赖一致性数据生成问题,采用有向无环图作为函数依赖集合的描述模型,提出一种单函数依赖一致性数据生成算法 （TGSFD）;并通过属性排序解决多函数依赖一致性数据生成问题;为了利用流水线技术提高数据生成效率,提出最小独立属性子集概念,并给出了属性集划分算法. 实验表明本文提出的TGSFD和属性排序算法能够保证生成的数据满足函数依赖一致性,属性集划分和流水线技术可以有效提高数据生成效率.      

随机蚕食快速Inc-SVDD算法及其应用

针对SVDD处理大数据样本时存在时间复杂度较大的问题,提出一种随机蚕食快速增量式支持向量域数据描述(RGInc-SVDD)算法.RGInc-SVDD首先利用随机抽样定理将样本训练集分割为多个子集,然后将其中一子集用于建模Inc-SVDDi分类器,最后利用迭代蚕食算法合并增长Inc-SVDDi分类器,以生成整个训练集的SVDD分类器.RGInc-SVDD算法使得SVDD的时间复杂度从O(N3)降到O(N2r/Gn2).实验结果验证了RGInc-SVDD算法的正确性和有效性.     

一种面向图集合的相似性搜索技术

目前图相似性的研究工作主要集中在子图的匹配,而没有充分关注图集合之间的匹配.针对这一问题,提出了一种基于过滤-求精框架的GSSS算法;提出了一种图集合距离定义,设计了Number,Size,Complete edge和Lower bound过滤器减小搜索空间,优化了图集合距离的计算;设计并优化了一种增量式的多层倒排索引,提高了查询效率,适应数据集的动态变化.真实数据集上的大量实验验证了GSSS算法的有效性和高效性.     

利用多级社区中心标签实现大规模图上距离查询

距离查询是图数据挖掘应用中的最基本的操作之一,但是目前的现存查询算法均无法高效处理大规模图数据.针对这个问题,提出建立多级社区中心的标签机制,即首先在原图中将结点按社区划分为多个集合,然后再将各集合中的中心结点建成带权查询子图,经过多次递归操作,最终为各结点建立一个基于社区中心的树状结构标签集,该标签集可以实现利用较短的创建时间和较小的存储代价大幅度提高距离查询的效率.从实验结果可以看出,该方法综合效率明显优于现存的高效算法.     

多路平衡型矩阵Bloom Filter

海量数据的高效表示和查找成为目前存储系统面临的重要挑战.针对存储系统中大规模动态数据集的表示和查找效率问题,提出一种多路平衡型矩阵Bloom Filter结构(M-BMBF)及其插入和查询算法.M-BMBF根据数据集合大小建立一个r×m矩阵型Bloom Filter,设计多个定位哈希函数将该矩阵Bloom Filter分为多组(多路)以实现平衡插入和高效查询操作.为减缓Bloom Filter中比特的消耗速度,使用一种"最长位匹配"填充算法,新元素的插入将从多路备选Bloom Filter中选择新置为1比特个数最少的Bloom Filter中进行.实验结果表明,相较典型拆分Bloom Filter,M-BMBF能在维持算法消耗时间为常量的基础上,有效节省存储空间,降低误判率.     

考虑标记间依赖关系的多标记分类算法

提出了一种考虑标记间依赖关系的多标记分类算法.首先依据RAk EL算法将标记集合划分为若干子集,然后在子集内部应用概率分类器链算法训练分类器.这样不仅充分考虑了标记间的依赖关系,而且对标记进行分组,从而提高了分类的性能.在5个数据集上与其他经典算法进行了对比实验,结果表明本文所提算法可显著提高分类性能.