欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

密度聚类算法DBScan

程序员文章站 2022-07-03 11:39:06
...

利用密度聚类DBScan对样本进行分类。
基本思路:
1、读取两组不同数据训练
2、分别对两组数据进行聚类
3、将聚类结果视作一个多维空间的点,计算其到原点的欧氏距离
4、根据ans1和ans2的欧氏距离找到合适的阈值

几个必要概念:
ε-邻域:对于样本集中的xj, 它的ε-邻域为样本集中与它距离小于ε的样本所构成的集合。
核心对象:若xj的ε-邻域中至少包含MinPts个样本,则xj为一个核心对象。
密度直达:若xj位于xi的ε-邻域中,且xi为核心对象,则xj由xi密度直达。
密度可达:若样本序列p1, p2, ……, pn。pi+1由pi密度直达,则p1由pn密度可达。

DBScan思路:
1. 初始化核心对象集合T为空,遍历一遍样本集D中所有的样本,计算每个样本点的ε-邻域中包含样本的个数,如果个数大于等于MinPts,则将该样本点加入到核心对象集合中。初始化聚类簇数k= 0, 初始化未访问样本集和为P = D。
2. 当T集合中存在样本时执行如下步骤:
2.1记录当前未访问集合P_old = P
2.2从T中随机选一个核心对象o,初始化一个队列Q = [o]
2.3P = P-o(从T中删除o)
2.4当Q中存在样本时执行:
2.4.1取出队列中的首个样本q
2.4.2计算q的ε-邻域中包含样本的个数,如果大于等于MinPts,则令S为q的ε-邻域与P的交集,
Q = Q+S, P = P-S
2.5 k = k + 1,生成聚类簇为Ck = P_old - P
2.6 T = T - Ck
3. 划分为C= {C1, C2, ……, Ck}

import numpy as np
import math

##############################
path = 'http_real.txt'
for line in open(path):
    continue
data1 = line.split('    ')
for i in range(len(data1)):
    data1[i] = float(data1[i])
##############################
path2 = 'http_code.txt'
for line in open(path2):
    continue
data2 = line.split('    ')
for i in range(len(data2)):
    data2[i] = float(data2[i])

#计算距离,a,b分别为两个元组
def dist(a, b):
    return abs(a-b)

#算法模型
def DBSCAN(D, e, Minpts):
#    D = data
#    e = 1
#    Minpts = 10
    #初始化核心对象集合T,聚类个数k,聚类集合C, 未访问集合P,
    T = set(); k = 0; C = []; P = set(D)
    for d in D:
        if len([ i for i in D if dist(d, i) <= e]) >= Minpts:
            T.add(d)
    #开始聚类
    while len(T):
        P_old = P
        o = list(T)[np.random.randint(0, len(T))]
        o1 = [] #把元素变为列表
        o1.append(o)
        o = o1
        P = P - set(o)
        Q = []; Q.append(o[0])
        while len(Q):
            q = Q[0]
            Nq = [i for i in D if dist(q, i) <= e]
            if len(Nq) >= Minpts:
                S = P & set(Nq)
                Q += (list(S))
                P = P - S
            Q.remove(q)
        k += 1
        Ck = list(P_old - P)
        T = T - set(Ck)
        C.append(Ck)
    return C

e = 1
Minpts = 50
w = 1600
ans = []
n = len(data1)/w
for i in range(n):
    Euclid = 0
    data = data1[w*i:w*(i+1)]
    C = DBSCAN(data, e, Minpts)
    for j in C:
        Euclid = Euclid + math.pow(len(j),2)
    ans.append(math.sqrt(Euclid))
    print i

ans2 = []
n = len(data2)/w
for i in range(n):
    Euclid = 0
    data = data2[w*i:w*(i+1)]
    C = DBSCAN(data, e, Minpts)
    for j in C:
        Euclid = Euclid + math.pow(len(j),2)
    ans2.append(math.sqrt(Euclid))
    print i