去年写的算法,纯python实现,现在贴上来。(运行效率真的捉急。。。。)
遍历的时候插入了过多的循环导致运行效率有点捉急。可得好好补补算法了。还有就是太菜了= =
关于这个算法的介绍有很多这里上 WIKI 的
先上结果
大致流程
- 先根据给定的半径 r 确定中心点,也就是这类点在半径r内包含的点数量 n 大于我们的要求(n>=minPionts)
- 然后遍历所有的中心点,将 互相可通达 的中心点与其包括的点分为一组
- 全部分完组之后,没有被纳入任何一组的点就是离群点啦!
导入相关依赖
import numpy as np import matplotlib.pyplot as plt from sklearn import datasets
求点跟点之间距离(欧氏距离)
def cuircl(pointA,pointB): distance = np.sqrt(np.sum(np.power(pointA - pointB,2))) return distance
求临时簇,即确定所有的中心点,非中心点
def firstCluster(dataSets,r,include): cluster = [] m = np.shape(dataSets)[0] ungrouped = np.array([i for i in range (m)]) for i in range (m): tempCluster = [] #第一位存储中心点簇 tempCluster.append(i) for j in range (m): if (cuircl(dataSets[i,:],dataSets[j,:]) < r and i != j ): tempCluster.append(j) tempCluster = np.mat(np.array(tempCluster)) if (np.size(tempCluster)) >= include: cluster.append(np.array(tempCluster).flatten()) #返回的是List center=[] n = np.shape(cluster)[0] for k in range (n): center.append(cluster[k][0]) #其他的就是非中心点啦 ungrouped = np.delete(ungrouped,center) #ungrouped为非中心点 return cluster,center,ungrouped
将所有中心点遍历并进行聚集
def clusterGrouped(tempcluster,centers): m = np.shape(tempcluster)[0] group = [] #对应点是否遍历过 position = np.ones(m) unvisited = [] #未遍历点 unvisited.extend(centers) #所有点均遍历完毕 for i in range (len(position)): coreNeihbor = [] result = [] #删除第一个 #刨去自己的邻居结点,这一段就类似于深度遍历 if position[i]: #将邻结点填入 coreNeihbor.extend(list(tempcluster[i][:])) position[i] = 0 temp = coreNeihbor #按照深度遍历遍历完所有可达点 #遍历完所有的邻居结点 while len(coreNeihbor) > 0 : #选择当前点 present = coreNeihbor[0] for j in range(len(position)): #如果没有访问过 if position[j] == 1: same = [] #求所有的可达点 if (present in tempcluster[j]): cluster = tempcluster[j].tolist() diff = [] for x in cluster: if x not in temp: #确保没有重复点 diff.append(x) temp.extend(diff) position[j] = 0 # 删掉当前点 del coreNeihbor[0] result.extend(temp) group.append(list(set(result))) i +=1 return group
核心算法完毕!
生成同心圆类型的随机数据进行测试
#生成非凸数据 factor表示内外圈距离比 X,Y1 = datasets.make_circles(n_samples = 1500, factor = .4, noise = .07) #参数选择,0.1为圆半径,6为判定中心点所要求的点个数,生成分类结果 tempcluster,center,ungrouped = firstCluster(X,0.1,6) group = clusterGrouped(tempcluster,center) #以下是分类后对数据进行进一步处理 num = len(group) voice = list(ungrouped) Y = [] for i in range (num): Y.append(X[group[i]]) flat = [] for i in range(num): flat.extend(group[i]) diff = [x for x in voice if x not in flat] Y.append(X[diff]) Y = np.mat(np.array(Y))
绘图~
color = ['red','blue','green','black','pink','orange'] for i in range(num): plt.scatter(Y[0,i][:,0],Y[0,i][:,1],c=color[i]) plt.scatter(Y[0,-1][:,0],Y[0,-1][:,1],c = 'purple') plt.show()
结果:
紫色点就是离散点
Be First to Comment