聚类算法 |
您所在的位置：网站首页 › 怎么看微信版本号是多少 › 聚类算法 |
聚类算法
最近的组会经常会听到这个名词，所以趁着今天有空，所以准备了解下这个算法。 先从百度 百科开始切入： DBSCAN(Density-Based Spatial Clustering of Applications with Noise)是一个比较有代表性的基于密度的聚类算法。与划分和层次聚类方法不同，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。 上面的解释中有【簇】的概念，先攻破它！ 簇：将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合，这些对象与同一个簇中的对象彼此相似，与其他簇中的对象相异。 【题外话】现在理解，认为簇就是一些样本的集合比如说{[1,2,3],[0,2,3],[2,3,4]}。 descan是一种基于密度的聚类方法，下面我们研究下具体操作。 形式化定义DBSCAN中的几个定义： Ε邻域：将某 对象半径为Ε内的区域称为该对象的Ε邻域； 核心对象：如果给定对象Ε邻域内的样本点数大于等于MinPts，则称该对象为核心对象； 【题外话】MinPts这是一个参数，这个参数的用途以后看懂了再说。看到了，MInPts 是最小包含点数(minPts) 直接密度可达：对于样本集合D，如果样本点q在p的Ε邻域内，并且p为核心对象，那么对象q从对象p直接密度可达。 密度可达：对于样本集合D，给定一串样本点p1,p2….pn，p= p1,q= pn,假如对象pi从pi-1直接密度可达，那么对象q从对象p密度可达。 密度相连：存在样本集合D中的一点o， 如果对象o到对象p和对象q都是密度可达的，那么p和q密度相联。 可以发现，密度可达是直接密度可达的传递闭包，并且这种关系是非对称的。密度相连是对称关系。DBSCAN目的是找到密度相连对象的最大集合。 Eg: 假设半径Ε=3，MinPts=3，点p的E邻域中有点{m,p,p1,p2,o}, 点m的E邻域中有点{m,q,p,m1,m2},点q的E邻域中有点{q,m},点o的E邻域中有点{o,p,s},点s的E邻域中有点{o,s,s1}. 那么核心对象有p,m,o,s(q不是核心对象，因为它对应的E邻域中点数量等于2，小于MinPts=3)； 点m从点p直接密度可达，因为m在p的E邻域内，并且p为核心对象； 点q从点p密度可达，因为点q从点m直接密度可达，并且点m从点p直接密度可达； 点q到点s密度相连，因为点q从点p密度可达，并且s从点p密度可达 算法的执行步骤DBScan需要二个参数： 扫描半径 (eps)和最小包含点数(minPts)。 任选一个未被访问的点开始，找出与其距离在eps之内(包括eps)的所有附近点。 如果 附近点的数量 ≥ minPts，则当前点与其附近点形成一个簇，并且出发点被标记为已访问(visited)。 然后递归，以相同的方法处理该簇内所有未访问的点，从而对簇进行扩展。如果 附近点的数量 < minPts，则该点暂时被标记作为噪声点。如果簇充分地被扩展，即簇内的所有点被标记为已访问，然后用同样的算法去处理未被访问的点。 下面分析下怎么写代码先定义数据类型，首先数据的类型为：[x,y]，其中，x，y分别i表示两个坐标。 然后，为了方便计算，我们将其拓展为以下数据结构： 接下来，涉及到一个很重要的东西，就是距离的计算，我们要计算样本间的欧氏距离，从而得到某点是否在有效半径中。 def Euclid_distance(x,y): #中学，学过的两点间距离公式length=x.shape[0]sum=0for i in range(length):sum=sum+(x[i]-y[i])*(x[i]-y[i])return np.sqrt(sum)# 开平方有了距离函数，差不多可以根据百度百科的伪代码，进行主函数的编写了。 def DBSCAN(D,Eps,MinPts):# （数据集，半径，最小数）C=-1# 初始化 簇的编号while len(D)!= 0:# 判断一下样本中是否还有未访问的节点。print(len(D))# 输出下剩余节点数for p in D :# 下面开始遍历下每一个节点if p[VISITED]==1:# 其实没必要了，因为已经过滤过一遍了continue# 如果是已经访问的节点，那麽跳过本次循环p[VISITED]=1 #将i标记为已访问N = getNeighbours (D,p, Eps);if len(N) =80:#防止 超过最大栈循环。return#（当前节点，候选集，聚类，半径，最小数）p[CLUSTER]=C # 将节点p设置为这个簇，因为这个是验证过的for p_ex in N:p_ex[VISITED] = 1# 将节点标记为已经访问N_ex= getNeighbours(D,p_ex, Eps);# 获得相关节点的边缘节点if p_ex[CLUSTER] ==0:p_ex[CLUSTER]=C # 将p_ex 加入簇CExpandCluster(p_ex,N_ex,C,Eps,MinPts,deep+1)#增加一次栈深def getNeighbours(D,p,Eps):neighbours_set=[]# 先划分一个方形区域，作为候选集，然后在进行欧氏距离的计算，这样效率会更高min_x,min_y,max_x,max_y=p[0]-Eps,p[1]-Eps,p[0]+Eps,p[1]+Eps# 可是这样比较，计算复杂度也不低啊,或许会好一点吧D=getUnvisited(D)# 只在乎没有被访问的点。for j in D:if j[0]max_x or j[1]max_y :continue# 由于有四个数据，我们只需要前两个if Euclid_distance(p[:-2], j[:-2]) |
Visited表示是否被访问，Cluster表示所属于的簇。【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |