一种基于CD-Tree的高效聚类算法

基于网格的聚类算法可以高效处理低维的海量数据.然而,对于维数较高的数据集,生成的单元数过多导致算法的效率较低.CD-Tree是一种只保存非空单元的索引结构,基于CD-Tree设计了新的基于网格的聚类算法,利用CD-Tree的优点提高了传统的基于网格的聚类算法的效率.此外,该算法聚类时只需访问稠密单元,设计了优化策略,在聚类之前剪枝掉非稠密单元,进一步提高了算法的效率.实验表明,与传统的聚类算法相比,基于CD-Tree的聚类算法有更好的可伸缩性.     

一种基于磁盘的大数据集快速异常检测算法

异常点检测是数据挖掘的一个重要研究方向，基于Cell的异常点检测算法生成的Cell（单元）数与维数成指数增长．当生成的单元数增多及数据量增大时，基于Cell的算法不能有效工作．分析发现这些单元中存在很多无用的空单元．本文采用CD-Tree结构对非空单元进行索引，并采用聚簇技术，将每个单元中的数据点存放在同一个磁盘页链中．实验表明，采用CD-Tree以及聚簇技术设计的异常点检测磁盘算法的效率，以及所能处理的数据集维数较原基于Cell的磁盘算法都有显著的提高．     

ISAD:一种新的基于属性距离和的孤立点检测算法

孤立点是数据对象在某些属性(维)上波动形成的.由此,本文提出了关键属性的概念,用于描述影响数据稳定性的属性.在真实数据集中,只有一部分属性是能够决定某数据是否是孤立点的关键属性.由此,本文提出了关键属性隶属度的定义及其求解算法,并在此基础上提出了一种新的基于属性距离和的孤立点检测算法.实验结果表明,该算法较基于单元的算法在效率及雏数可扩展方面均有显著提高.     

数据挖掘中GridLOF算法的研究与改进

通常那些与数据集的一般行为或模型不一致的数据对象,可能包含某些重要的隐藏信息.在分析了基于单元网格的局部孤立因子的孤立点挖掘算法(GridLOF)的基础上,做出了相应的改进,提出了基于相邻网格密度因子的孤立点挖掘算法.     

一种支持快速相似检索的多维索引结构

基于内容的图像检索是一种典型的相似检索问题,对于尺度空间上的图像相似匹配问题,一般认为距离计算费用很高.因此,需要建立有效的索引结构,以减少每个查询中的距离计算次数.为此,基于数据空间的"优化划分",并且使用"代表点",以层次结构方式划分数据,提出了一种新的基于距离的相似索引结构opt-树及其变种(-树.为了更有效地支持基于内容的图像检索,在(-树索引结构中采用了"(-最优化划分"和"(-对称冗余存储"策略,以提高相似检索的效率.详细讨论了这种索引结构的建立与检索等问题,并给出了相应的算法.实验结果显示了这种索引技术的有效性.     

基于引力的孤立点检测算法

提出一种基于引力的孤立点检测算法.通过综合考虑数据对象周围的密度及数据对象之间的距离等因素对孤立点定义的影响来挖掘出数据集中隐含的孤立点.给出了与该算法相关的概念与技术,详细介绍了该算法,并用实际数据进行了实验.实验表明:该算法对数据集的维度具有很好的扩展性,能有效地识别孤立点,同时能反映出数据对象在数据集中的孤立程度.     

基于单元的孤立点检测算法改进及应用

研究基于单元的孤立点检测算法,给出数据空间的单元格划分及数据对象分配算法。针对该算法中阈值M设置的不足,对算法进行改进并应用于纳税行为的分析。与其他孤立点检测算法对比的结果表明,该算法不仅能有效挖掘纳税行为中的孤立点,还能确定孤立点的位置,有利于对纳税行为的分析。     

移动对象反向最近邻查询技术研究

提出一种基于自调节网格索引的反向最近邻查询(RNNQ)算法,将空间划分为大小相等的网格单元,每个单元作为一个桶存储移动对象,采用基于桶内对象数目和网格几何特征的剪枝策略减少反向最近邻查询所需访问的节点。查询点周围单元桶内对象过多时进行二次网格划分,减小节点访问代价。实验结果表明,该算法具有良好的查询性能,优于基于TPR树索引的RNNQ算法。     

一种基于受限网络的移动对象索引结构

为了提高受限网络中移动对象索引效率和满足近邻查询需求,基于FNR-Tree索引结构和Geohash编码算法,提出一种能够满足近邻查询的移动对象索引结构RNR(restricted network R-Tree).通过添加哈希表、链表等辅助索引结构来提升索引结构操作效率,融合Geohash编码和相关算法来使得索引结构能高效满足近邻查询的需求.通过将指定区域按一定规则划分,可使得索引结构具备在不规则范围查询的能力.使用旧金山市地理数据和移动对象数据对索引结构性能进行了测试,结果表明RNR具有较高索引结构操作效率,并且能够高效地提供窗口查询和近邻查询的功能.     

面向移动对象的高效组最近邻居查询方法

组最近邻居查询是移动对象数据库重要的查询类型之一。本文提出了一种基于网格索引结构的剪枝搜索策略,将空间区域划分为网格,通过对象点的网格单元标识减少组最近邻居查询所需要的节点访问代价。用步长迭代法得到查询对象集的质心,提出了一种移动对象组最近邻居查询MOGNN算法,采用更精确的裁剪搜索空间准则,减少了查询所需要访问的节点数目。实验结果与分析表明,基于网格索引的MOGNN查询算法具有良好的查询性能。     

基于索引偏移的MapReduce聚类负载均衡策略

MapReduce作为一种分布式编程模型,被广泛应用于大规模和高维度数据集的处理中。其采用原始Hash函数 划分 数据,当数据分布不均匀时,常会出现数据倾斜的问题。基于MapReduce的聚类算法,需要多次迭代且不清楚各阶段Reduce的输入数据分布,因此现有的解决数据倾斜的方法并不适用。为解决数据划分的不均衡问题,提出一种当存在数据倾斜时更改剩余分区索引的策略。该方法在Map运行的过程中统计将要分给各reducer的数据量,由JobTrackcr监控全局的分区信息并根据数据倾斜模型动态修改原分区函数;在接下来的分区过程中,Partitioner把即将导致倾斜的分区索引到其余负载较轻的reducer上,使各节点的负载达到均衡。基于Zipf分布数据集和真实数据集,将所提算法与现有的解决数据倾斜的方法进行对比,结果证明,所提策略解决了MapReduce聚类中的数据倾斜问题,且在稳定性与执行时间上优于Hash和基于采样的动态分区法。     

一种优化的基于网格的聚类算法

聚类是数据挖掘领域中一个重要的研究课题．与其它算法相比，基于网格的聚类算法可以高效处理低维的海量数据．然而，由于划分的单元数与数据的维数呈指数增长，因此对于维数较高的数据集，生成的单元数过多，导致算法的效率较低．本文基于CD—Tree设计了新的基于网格的聚类算法，该算法的效率远高于传统的基于网格聚类算法的效率．此外，本文设计了一种剪枝优化策略，以提高算法的效率．实验表明，与传统的聚类算法相比，基于CD-Tree的聚类算法在数据集的大小及维度的可伸缩性方面均有显著提高．     

基于B＋-tree索引的多元时间序列相似查询

为提高多元时间序列相似查询执行效率,采用了基于距离索引结构的相似查询算法。利用主成分分析方法对多元时间序列数据降维并在此基础上进行聚类,以聚类质心为参考点,将各类变换到一维空间,利用B＋-tree结构进行索引查询,找到与查询序列最相似的k个MTS序列。实验表明查询效率和准确性都有比较大的提高。     

利用子空间划分的局部离群数据挖掘算法

目前大多数局部离群数据挖掘算法需人为事先设置参数或阈值,且难以应用到高维数据集.给出一种新的局部离群数据挖掘算法PSO-SPLOF,该算法首先将数据集划分为互不相交的子空间,利用偏斜度判断子空间划分的优劣,并采用微粒群算法搜索最优划分子空间集;其次针对每个最优划分子空间,计算其数据对象的局部离群因子SPLOF值,并用SPLOF值来度量数据对象的局部偏离程度.最后采用离散化的天体光谱数据作为数据集,实验验证了PSO-SPLOF算法具有受人为因素影响小、伸缩性强和运算效率高等优点.     

基于Kd树改进的高效K-means聚类算法

针对经典的K-means算法在多维数据聚类效率上还有待提高的问题,本文提出一种称为CK-means的改进聚类算法。该算法在k-means算法的基础上,通过引入Kd树空间数据结构,初始聚类中心从多维数据某一维的区间等间隔集中选取,以及在数据对象分配过程中采用剪枝策略来提高算法的运行效率。实验结果表明,CK-means聚类算法较经典的k-means聚类算法运行效率更高。     

基于MapReduce改进离散型萤火虫算法和多重分形的属性约简方法

针对大数据环境下属性约简问题,提出基于MapReduce改进离散型萤火虫算法(IDGSO)和多重分形(MFD)的属性约简方法.首先,通过对萤火虫个体的移动方式进行离散化改进,引入迁徙策略和高斯变异策略,避免陷入局部最优,并提出改进离散型萤火虫算法.然后,将IDGSO结合MFD应用于属性约简中.最后,针对大数据环境下属性约简问题,采用MapReduce编程模式,实现对IDGSO和MFD的并行化.在UCI数据集和实际气象数据集上的实验表明,文中算法约简性能较优,运行效率较快,具有较好的有效性和可行性.     

基于模块密度优化的标签传播社区发现算法

基于标签传播的社区发现算法(LPA)以其简单高效得到了广泛的研究,然而当社区结构模糊时,LPA得到的是一个单一的社区,这是无意义的.模块化标签传播算法(LPAm)则倾向于将网络划分为度数相近的社区且存在解极限问题.为此提出基于模块密度的标签传播(LPAd)算法,该算法通过对模块密度优化进行标签标记和传播,以避免过大社区的形成,且生成的社区满足Radicchi等人提出的弱社区定义.多个真实数据集和人工网络数据的实验结果表明,本文算法在不改变算法复杂度的情况下提高了所发现社区的质量,与现有的若干基于标签传播的社区发现算法相比,取得了改进的效果.     

使用均值距离与关联性标记的并行OPTICS算法

针对大数据环境下传统并行密度聚类算法中存在的数据划分不合理,聚类结果准确度不高,结果受参数影响较大以及并行效率低等问题,提出一种MapReduce下使用均值距离与关联性标记的并行OPTICS算法——POMDRM-MR。算法使用一种基于维度稀疏度的减少边界点划分策略（DS-PRBP）,划分数据集;针对各个分区,提出标记点排序识别簇算法（MOPTICS）,构建数据点与核心点之间的关联性,并标记数据点迭代次数,在距离度量中,使用领域均值距离策略（FMD）,计算数据点的领域均值距离,代替可达距离排序,输出关联性标记序列;最后结合重排序序列提取簇算法（REC）,对输出序列进行二次排序并提取簇,提高算法局部聚类的准确性和稳定性;在合并全局簇时,算法提出边界密度筛选策略（BD-FLC）,计算筛选密度相近局部簇;又基于n叉树的并集型合并与MapReduce模型,提出并行局部簇合并算法（MCNT-MR）,加快局部簇收敛,并行合并局部簇,提升全局簇合并效率。对照实验表明,POMDRM-MR算法聚类效果更佳,且在大规模数据集下算法的并行化性能更好。     

云计算下保持边界域划分的知识约简算法研究

知识约简是数据挖掘应用中知识获取的重要步骤。经典的知识约简算法是一次性将小数据集装入内存中进行知识约简,而传统的并行知识约简仅仅利用任务并行来提高约简算法效率,都无法处理海量数据。通过分析经典的知识约简算法,构建了不可辨识的对象对,提出了保持边界域划分的知识约简算法,并探讨了保持边界域划分的知识约简算法之间的关系。深入剖析了知识约简算法中数据和任务同时并行的可行性,提出了云计算环境下保持边界域划分的知识约简算法框架模型,在Hadoop平台上构建了云计算环境并进行了相关实验。实验结果表明该知识约简算法可以处理海量数据集。