欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2016111203263
申请人: 重庆邮电大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-02-23
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于Spark大数据平台的数据集聚类方法,其特征在于,将数据集转化成Spark平台的分布式数据集RDD,对RDD数据集进行划分,得到最优的数据划分结构,分割得到最优分区;并行获取每个最优分区中所有样本点的邻居样本点编号,并赋予OPTICS算法的核心距离;对每个分区执行OPTICS算法,得到每个分区的簇排序并将其存储;根据每个分区的簇排序,赋予每个样本在分区内的簇号,计算全局簇号转换Map;根据全局簇号转换Map,合并分区并更换簇号,得到聚类结果;

按照最优结构划分并计算距离得到每个分区中每个样本点的邻居样本点,并把邻居样本点的序号存储到样本点后,每个分区进行经典OPTICS通过点排序识别聚类结构算法,对所有样本的可达距离进行排序,每个分区得到簇排序,调用saveAsTextFile函数将簇排序持久化存储,每个分区的簇排序只能进行数据结构层面上观测作用,而为了得到每个样本点的最终簇号,需要输出聚类结果;所以根据每个分区的簇排序,可以依照用户的需求在不同层次结构上得到簇号,然后合并分区,输出聚类的结果;具体包括:(1)根据用户输入的判断距离阈值B,从每个分区的簇排序中按顺序提取样本,首先先设定一个初始类别,如果该样本的可达距离不大于B则属于当前正在判定的类别;如果样本的可达距离大于B且核心距离大于B,则为噪声;如果样本的可达距离大于B且核心距离小于B,则属于下一个新的类别,则另起一个新的类别;

(2)生成全局合并簇号的Map,保留每个分区的边界样本形成盒子边界数组,广播该数组;按每个分区的前边界点和数组序号对应的前一个盒子的后边界点进行循环,如果存在一对样本的距离小于给定B,则加入Map中;

(3)每个分区根据该Map合并簇号,并输出最终的聚类结果,如不符合期望公式,期望公式:已分配簇号的样本数/总样本数>=0.8,则可以返回步骤(1),直到符合期望公式为止。

2.根据权利要求1所述的方法,其特征在于,进一步包括:输入聚类初始半径ε和半径内最小的邻居数MinPts,将输入的数据集转化成Spark平台的分布式数据集RDD,创建一个SparkContext环境对象,然后用SparkContext环境对象的parallelize或textFile函数创建一个可以被并行操作的分布式数据集RDD。

3.根据权利要求1所述的方法,其特征在于,寻找最优的数据划分结构进一步包括,调用RDD的行动函数计算数据集维度差异最大的N个维度,将RDD划分成N个分区,使每个分区能够获取前面的广播变量;每个分区分别根据各自的维度生成树形结构,树的每个节点是一个盒子box;根据维度进行数据集划分。

4.根据权利要求1所述的方法,其特征在于,并行计算分区中每个样本的邻居数并赋予OPTICS算法的核心距离,具体包括:广播盒子数组,生成盒子中样本数组的RDD,每个分区分别获得序号相对应的盒子;每个分区分别根据广播的盒子数组中对应的盒子及其前后盒子计算样本点邻居;根据样本与邻居间的欧几里得距离,得到每个样本对应的核心距离。

5.根据权利要求1所述的方法,其特征在于,计算全局簇号转换Map,具体包括;根据用户的预定距离值B,从每个分区的簇排序中按顺序提取样本,赋予样本一个初始类别,如果该样本的可达距离不大于B则属于当前类别,如果可达距离大于B且核心距离大于B,则为噪声,当可达距离大于B且核心距离小于B,则标记为下一个新的类别;生成全局合并簇号的Map,过滤留下每个分区的边界样本形成盒子的边界数组,广播边界数组,每个分区中样本与其序号对应的前后边界数组里的盒子中样本进行计算合并簇号,如果存在一对样本的距离小于B,则把得到的簇号加入Map中;每个分区根据Map合并簇号,得到每个样本点最终簇号,根据簇号输出聚类结果。

6.根据权利要求3所述的方法,其特征在于,根据维度进行数据集划分具体包括:按照维度将数据集等距离进行平分,形成两个盒子,这两个盒子的样本数组再进行等距离平分,直到盒子的样本数据个数小于设定值或者盒子的前边界值减去后边界值小于2ε,标记每个样本数组所属的盒子,标记每个样本与所属盒子的前后边界的关系。

7.根据权利要求3所述的方法,其特征在于,根据盒子的长度L,每个分区的盒子中数组样本个数最多的盒子中的数组样本数M,盒子的平均数组样本数N,根据公式P=N/M判断倾斜标准P,把每个分区的L和P标准化,标准化后L+P值最大对应的分区为最优分割分区。

8.根据权利要求4所述的方法,其特征在于,根据邻居样本点及与其目标样本点的欧式距离,调用公式:

计算样本P的核心距离

core-distε,MinPts(p),由此获得每个样本的核心距离,其中,if|Nε(p)|<MinPts表示当样本P周围的邻居样本个数小于用户设定阈值个数MinPts时,UNDEFINED表示无定义,MinPts-th smallest distance to Nε(p)表示当样本P周围的邻居样本个数大于等于用户设定阈值个数MinPts时,使得样本点P周围至少有MinPts个邻居样本点的最小邻域半径为核心距离;根据公式 计算样本点O到样本点P的可达距离reachability-distε,MinPts(o,p),由此获得每个样本的可达距离,其中,Max(core-distε,MinPts(p),dist(p,o))表示样本点P的核心距离和样本点P和样本O的欧式距离中最大的一个。