一种面向大数据的分布式密度聚类方法

摘要

一种面向大数据的分布式密度聚类方法，包括如下步骤：步骤一：虚拟化环境、搭建Hadoop平台；步骤二：数据预处理与加载：从数据库中将原始数据表抽取，利用sqoop–query命令截取需要的字段，将预处理后的数据直接抽取到Hdfs中；步骤三：计算距离矩阵；步骤四：计算截止距离与点密度；步骤五：计算点与较高密度点的最小距离；步骤六：临界密度点临界距离以及聚类中心；步骤七：点进行聚类，得到最终的聚类结果；步骤八：剔除离群点。本发明在处理大数据集时快速有效，并具备输入参数对聚类结果的鲁棒性较好的效果。

主权项

一种面向大数据的分布式密度聚类方法，其特征在于：所述聚类方法包括如下步骤：步骤一：虚拟化环境、搭建Hadoop平台；步骤二：数据预处理与加载从数据库中将原始数据表抽取，利用sqoop‑query命令截取需要的字段，将预处理后的数据直接抽取到Hdfs中；步骤三：计算距离矩阵A_i＝{d_i1 … d_in}＝a_i·{a₁ … a_n}＝{|a_i·a₁| … |a_i·a_n|}  (2)其中，a_i代表点的坐标(1≤i≤N)，N为点集合的总数，A_i为距离矩阵的第i行距离向量，R为地球半径，，a_i、a_j为球面上的两点、球面坐标为a_i(x₁，y₁)，B(x₂，y₂)，x₁、x₂∈[‑π，π]，y₁、y₂∈[‑π/2，π/2]；在计算距离矩阵的第i行时，向量A_i中所有的|a_i·a_j|(1≤j≤N)都会用到相同起始点a_i和整个数据集的所有点{a_j|1≤j≤N}；|a_i·a_j|＝R·arccos[cosy₁cosy₂cos(x₁‑x₂)+siny₁siny₂]  (3)步骤四：计算截止距离与点密度4.1)计算截止距离截至距离d_c为距离集合降序排列的20％的位置处的距离即：d_c＝D([N*0.2])；其中，D为计算所得的距离{d_ij|1≤i，j≤N}的降序排列集合，N为点的总数，[]为取整函数；4.2)计算点密度ρ点密度ρ_i为点i与其他所有点的距离小于截止距离d_c的个数；在Map过程中将同一行的元素集中在相同Key中，将每个小于d_ij的元素化成常数‘1’加入到key值为i的value里；Reduce过程中对key值i对应的Values里的元素进行累加就得到各点的密度ρ_i；步骤五：计算点与较高密度点的最小距离δ_iδ_i为i与其高局部密度点的最小距离，计算δ_i的公式如下：δi＝min{d_ij|ρ_i＜ρ_j}，最大Max(ρ_i)点所对应的δ＝Max(d_ij)，包括如下步骤：5.1)对ρ_i进行降序排序，得到对应i的排序后的集合{i}_decrbyp_i；5.2)利用i对应的{j|ρ_i＜ρ_j}，得到i点的δi计算所需要的d的角标集合{ij|ρ_i＜ρ_j}；5.3)计算角标集合中对应d_ij的最小值，由{ij|ρ_i＜ρ_j}，距离集合{d_ij1≤i，j≤N}得到计算δi所需要的{d_ij|ρ_i＜ρ_j}；并且记录当δi＝min{d_ij|ρi＜ρj}成立时所对应的j值；其中，d_ij为点i与点j的距离，ρ_i代表点i与其他所有点的距离小于d_c的个数，ρ_j代表点j与其他所有点的距离小于d_c的个数，N为点的总个数；步骤六：临界密度点临界距离以及聚类中心6.1)临界密度点ρ₀、临界距离δ₀临界密度点ρ₀为{ρ_i}是密度从大到小后的排列的第C个点，临界距离δ₀是集合{δ_i}从大到小后的排列的第C个点，我们对{ρ_i}从小到达的排序，然后取点{ρ_i|i＝C}的点作为ρ₀，对{δ_i}，我们进行从小到达的排序，然后取点{δ_i|i＝C}的点作为δ₀；其中，ρ_i代表点i与其他所有点的距离小于d_c的个数，δ_i为i与其高局部密度点的最小距离，C为固定常数；6.2)判定i是否为聚类中心分别判断i与之对应的ρ_i＞ρ₀，δ_i＞δ₀是否成立，若都成立则点i为聚类中心；判断所有的点后得到聚类中心集合M＝{i|ρ_i＞ρ₀，δ_i＞δ₀}；步骤七：点进行聚类顺序取{(i，j)}的点，判断i是否为聚类中心，如果属于则判断下个点，如果不属于判断(i，j)的j是否属于聚类中心，如果属于则i为j类，如果不属于判断i＝j点对应的j是否属于聚类中心，循环后会得到最终的聚类结果，其中i为点编号，j为当δ_i＝min{d_ij|ρ_i＜ρ_j}成立时所对应的值，{(i，j)}代表(i，j)按照ρ_i从大到小排列。