密度聚类算法DBScan

利用密度聚类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