非监督学习之聚类算法（3）--基于密度

基于划分的方法是用对象之间的距离进行聚类，这样的方法只能发现球状的簇，而在发现任意形状的簇上遇到了困难，因此有人提出了基于密度的另一类聚类方法，其主要思想是：只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类。也就是说，对给定类中的每个数据点，在一个给定范围的区域中必须至少包含某个数目的点。这样的方法可以用来过滤“噪声”孤立点数据，发现任意形状的簇。

DBSCAN算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法）是一种基于密度的空间聚类算法。它对于集中区域效果较好，为了发现任意形状的簇，这类方法将簇看做是数据空间中被低密度区域分割开的稠密对象区域（将具有足够高密度的区域划分为簇），该算法可在具有噪声的空间数据中发现任意形状的簇。

1、执行步骤

step 1：制定合适的r和M。r-邻域，指给定半径r内的区域。核心点，指如果一个点的r-邻域内包含最小M个点则称该点为核心点。
step 2：随机访问一个样本点P，N是P的邻域点集合。遍历访问N中每一个未访问过的点，得到该点Q的邻域点集合NN，如果NN中样本点的数量大于等于M则将NN中的点加入N集合中。
step 3：如果所有的样本点都被访问过，结束。

2、优缺点

（1）优点

• 不需要知道簇的数量
• 能够有效处理噪声点
• 能够发现任意形状的簇

（2）缺点

• 计算复杂度大，当数据量增多时对内存需求大
• 当空间聚类的密度不均匀，聚类间距离相差很大时，聚类质量较差
• 对给定的参数敏感，参数的选择只能靠经验确定

3、代码实现

# coding=utf-8
'''
DBSCAN算法
'''
import numpy as np
import pandas as pd
import math
import matplotlib.pyplot as plt
from sklearn import datasets
import random

#==============================================
# 计算距离
#==============================================

def euclidean_dist(p, q):
    ''' 
    欧式距离(L2范数)
    INPUT  -> 长度一致的向量1、向量2
    '''
    p = np.mat(p)
    q = np.mat(q)
    return math.sqrt(np.sum(np.power(p-q, 2)))

#==============================================
# visitlist数据结构
#==============================================

class visitlist:
    ''' 
    visitlist类用于记录访问列表
    unvisitedlist记录未访问过的点
    visitedlist记录已访问过的点
    unvisitednum记录访问过的点数量
    '''
    def __init__(self, count=0):
        self.unvisitedlist=[i for i in range(count)]
        self.visitedlist=list()
        self.unvisitednum=count

    def visit(self, pointId):
        self.visitedlist.append(pointId)
        self.unvisitedlist.remove(pointId)
        self.unvisitednum -= 1

#==============================================
# 算法核心部分
#==============================================

def DBSCAN(dataSet, r, M):
    '''
    DBSCAN算法
    INPUT  -> 数据集、r-领域、簇最小数量M
    '''
    # 标记所有对象为unvisited
    vPoints = visitlist(count=len(dataSet))
    # 聚类结果
    output = []

    while(vPoints.unvisitednum > 0):
        # 随机选择一个未访问的点p访问
        p = random.choice(vPoints.unvisitedlist)
        vPoints.visit(p)

        # N是p的邻域点列表
        N = [i for i in range(len(dataSet)) if euclidean_dist(dataSet[i], dataSet[p])<= r]
        if len(N) >= M:
            for q in N:
                if q in vPoints.unvisitedlist:
                    vPoints.visit(q)

                    # NN是q的邻域点列表
                    NN = [i for i in range(len(dataSet)) if euclidean_dist(dataSet[i], dataSet[q]) <= r]
                    if len(NN) >= M:
                        for i in NN:
                            if i not in N:
                                N.append(i)

        Cluster = [dataSet[i] for i in N]
        # 过滤掉噪声
        if len(Cluster) > M:
            output.append(Cluster)

    return output

#========================================================
#  主程序
#========================================================

if __name__ == '__main__':
    X1, Y1 = datasets.make_circles(n_samples=500, factor=0.6, noise=0.05, random_state=1)
    X2, Y2 = datasets.make_blobs(n_samples=200, n_features=2, centers=[[1.5,1.5]], cluster_std=[[0.1]], random_state=5)
    points = np.concatenate((X1, X2))
    
    output = DBSCAN(dataSet=points, r=0.12, M=5)
    print(len(output))
   
    C1 = np.array(output[0])
    C2 = np.array(output[1])
    C3 = np.array(output[2])
    
    plt.figure(figsize=(12, 9), dpi=80)
    plt.scatter(C1[:,0], C1[:,1], marker='.')
    plt.scatter(C2[:,0], C2[:,1], marker='X')
    plt.scatter(C3[:,0], C3[:,1], marker='o')
    plt.show()

利用KD树进行优化
KD树（K-Dimensional Tree），是一种分割k维数据空间的数据结构，是二叉搜索树在多维条件下的推广。主要应用于多维空间关键数据的搜索。
参考代码