聚类

• 大纲
  
  k-means，DBSCAN算法最为常用

聚类的概述

• 聚类是将数据集划分为若干组相似对象组成的多个组或簇的过程，使得同一组对象间的相似度最大化，不同组中对象间的相似度最小化。
• 簇是相似数据的集合。
• 聚类分析是一种无监督分类算法。数据集中的数据没有预定义的类别标号，无训练集和训练的过程。
• 聚类分析的作用：1、作为一个独立的工具来或得数据集中数据的分布情况；2、作为其他数据挖掘算法的预处理步骤。
• 聚类分析在数据挖掘中的作用：1、作为一个独立的工具来或得数据集中数据的分布情况：首先对数据集进行聚类，或得所有簇，然后，根据每个簇中样本的数目获得数据及总每类数据的大体分布情况。2、作为其他数据挖掘算法的预处理步骤：首先对数据进行聚类（粗聚类），然后，分别对每个簇进行特征提取和细分类，可以提高精度。
• 聚类的应用：空间数据分析：图像处理、万维网：WEB日志数据聚类、金融领域：用户交易数据聚类分析
• 常用的聚类分析方法：
  1、划分法：以距离作为数据集中不同数据间的相似性度量，k-means
  2、层次法：对给定的数据集进行层次分解，自顶向下法，自底向上法
  3、密度法：DBSCAN、谱聚类

相似性计算

• 在聚类分析中，样本件的相似性通常采用样本之间的距离表示。距离越大，越不相似。
• 样本之间的距离是在样本的描述属性上进行计算的：连续型、二值离散型、多值离散型、混合类型……

连续型属性的相似性计算方法

• 欧式距离
• 曼哈顿距离
• 闵可夫斯基距离
  
  
  
  
  
  
  
  
  
  
  
  青年 中年 老年 本科以下 本科 研究生 低 中 高
  x1 1 0 0 0 0 1 0 0 1
  x2 1 0 0 0 1 0 1 0 0

jc1-2=4/5=0.8

• 如何计算
  
  
  
  x 青年 中年 老年 本科以下 本科 研究生 低 中 高
  x1 0.5 1 0 0 0 0 1 0 0 1
  x2 0.9 1 0 0 0 1 0 1 0 0

距离 0.4 0 0 0 0 1 1 1 0 1
为0的不用考虑
d1-2 = (4.4)/(6)=0.7333

kmeans原理

划分方法

• 给定n个样本的数据集，以及要生成的簇的数目k，划分方法将样本组织为k个划分（k≤n）
• 划分准则：同一个簇中的样本尽可能接近或相似
• 以样本间的距离作为相似性度量
• 典型划分方法：k-means，k-medoids
• 算法思想：初始随机给定k个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心，一直迭代，直到簇心的移动距离小于某个给定的值。
  
  计算矩阵

import numpy as np

a = np.array([[3,4],[3,6],[7,3],[4,7],[3,8],[8,5],[4,5],[4,1],[7,4],[5,5]])

lines = ""
for i in a:
    for j in a:
        distance = np.sqrt(np.sum((i-j)**2))
        # lines += str(distance)+","
        lines += "%.2f"%distance+","
    lines += "\n"
file = open("result.csv",mode="w",encoding="utf-8")
file.write(lines)
file.close()

import numpy as np
import matplotlib.pyplot as plt
#获取数据集
def loadDataSet(filename):
    return np.loadtxt(filename,delimiter=',')

#取出k个中心点
def initCenters(dataset,k):
    """
    返回k个中心点
    :param dataset: 数据集
    :param k:中心点的个数
    :return:
    """
    centerIndex =  np.random.choice(len(dataset),k,replace=False)
    # print(chenterIndex)
    return dataset[centerIndex]

#计算距离公式
def distance(x,y):
    return np.sqrt(sum((x-y)**2))

#kmeans核心算法
def kmeans(dataset,k):
    """
    返回k个簇
    :param dataset:
    :param k:
    :return:
    """
    #初始化中心点
    centers = initCenters(dataset,k)  #随机的
    # centers = np.array([[4,5],[5,5]],dtype = np.float)  #指定
    n,m = dataset.shape
    #用于存储每个样本属于哪个簇
    clusters = np.full(n,np.nan)
    #迭代  flag->标志
    flag = True
    while flag:
        flag = False
        #计算所有点到簇中心点的距离
        for i in range(n):   #n是样本个数
            minDist,clustersIndex = 99999999,0
            for j in range(len(centers)):  #中心点的个数
                dist = distance(dataset[i],centers[j])   #某一点至中心点的距离
                if dist < minDist:
                    #为样本分簇
                    minDist = dist
                    clustersIndex = j
            if clusters[i] != clustersIndex:
                clusters[i] = clustersIndex  # 为这个簇
                flag = True
        # print(centers)
        # print(clusters)
        #更新簇中心
        for i in range(k):
            subdataset = dataset[np.where(clusters==i)]
            centers[i] = np.mean(subdataset,axis = 0)
    return clusters,centers

def figureShow(dataset,k,clusters,centers):
    n,m = dataset.shape
    if m>2:
        print("维度大于2")
        return 1
    #markers
    #根据簇不同 marker不同
    markers = [".",",","o","v","^","<",">"]
    colors = ["g","r","y","b"]
    for i in range(n):
        clustersIndex = clusters[i].astype(np.int)
        plt.scatter(dataset[i][0],dataset[i][1],color = colors[clustersIndex],marker = "o")

    #绘制质心
    for j in range(k):
        plt.scatter(centers[j][0],centers[j][1],marker = "^")
    plt.show()

if __name__ == "__main__":
    dataset = loadDataSet("testSet.txt")
    # print(initCenters(dataset,2))
    # print(kmeans(dataset,2))
    clusters,centers = kmeans(dataset,3)
    figureShow(dataset,3,clusters,centers)

k-medoids算法

• 基本思想：选取有代表性的样本（而不是均值）来表示整个簇，即：选取最靠近中心点的那个样本来代表整个簇，以降低聚类算法对离群点的敏感度。
  
  
  

层次方法

• 自底向上方法：开始时，将每个样本作为单独的一个组，然后，依次合并相近的样本或组，直至所有样本或组被合并为一个组或者达到终止条件为止。agnes算法

• 自顶向下方法：开始时，将所有样本置于一个簇中，然后，执行迭代，在迭代的每一步中，一个簇被分裂为多个更小的簇，直至每个样本分别在一个单独的簇中或者达到终止条件为止。diana算法
  
  
  输入：包含n个样本的数据集，终止条件簇的数据k。
  输出：k个簇，达到终止条件规定的簇的数目。

• 初始时，将每个样本当成一个簇

• repeat，根据不同簇中最近样本间的距离找到最近的两个簇，合并这两个簇，生成新的簇的集合。

• until达到定义的簇的数目。
  
  
  

DBSCAN算法

基于密度的聚类，他聚类方法大都是基于对象之间的距离进行聚类，聚类结果是球状的簇。
基于密度的聚类是寻找被低密度区域分离的高密度区域。

将点分为：核心点、边界点、噪声或背景点




DBSCAN运行效果好时的效果：

• 时间复杂度
  
• 空间复杂度
  
• 如何选取合适的EPS和MinPts
  
• 优点：基于密度定义，相对抗噪声，能处理任意形状和大小的簇
• 缺点：当簇的密度变化太大时，会有麻烦；对于高维问题，密度定义是个麻烦的问题。

# -*- coding: utf-8 -*-
# @Time    : 2020/12/29 20:25
# @Author  : LUYX
import numpy as np
import matplotlib.pyplot as plt
import math
import random
from sklearn import datasets

#定义一个类 用于记录样本的状态信息


#距离计算公式
def distance(x,y):
    return np.sqrt(np.sum((x-y)**2))

def dbscan(dataset,minPts,eps):
    """
    :param dataset: 数据集
    :param minPts: 最少点数
    :param eps: 半径
    :return: 返回的是样本的簇的集合
    """
    n,m = dataset.shape
    #定义一个容器 用于存储样本的分类
    clusters = np.full((n,1),-1)
    #簇的类别
    k = -1
    for i in range(n):
        if clusters[i] != -1:
            continue
        #取出样本点
        p = dataset[i]
        #获取领域内的所有样本点
        subdataset = [j for j in range(n) if distance(dataset[j],p)<=eps]
        if len(subdataset) <= minPts:
            continue
        #建立簇的标记
        k += 1
        clusters[i] = k
        for j in subdataset:
            clusters[j] = k
            if j > i:
                sub = [item for item in range(n) if distance(dataset[j],dataset[item])<=eps]
                if len(sub)>=minPts:
                    # subdataset.extend(sub)
                    # subdataset = list(set(subdataset))
                    for t in sub:
                        if t not in subdataset:
                            subdataset.append(t)
    # print(clusters)
    return clusters

X1, Y1 = datasets.make_circles(n_samples=2000,factor=0.6,noise=0.05,random_state=1)
X2, Y2 = datasets.make_blobs(n_samples=500,n_features=2,centers=[[1.5,1.5]],cluster_std=[[0.1]],random_state=5)

X = np.concatenate((X1,X2))

C1 = dbscan(X,10,0.1)
print(C1)
plt.scatter(X[:,0],X[:,1],c=C1,marker='.')
plt.show()

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import DBSCAN
from scipy.spatial.distance import pdist

data_path = '.csv'

# 读取文件
data_frame = pd.read_csv(data_path, encoding='gbk')

# dbscsn
def dbscsn_cluster(x_label, y_label):
    clu = DBSCAN(eps=0.05,min_samples=1)

    X_value = data_frame[[x_label, y_label]].values
    print(type(X_value))

    clu.fit(X_value)

    print('样本所属簇编号：', clu.labels_)

    # 可视化
    plt.rcParams['font.sans-serif'] = ['SimHei']
    plt.rcParams['axes.unicode_minus'] = False

    # 以簇编号作为颜色区分依据
    plt.scatter(data_frame[x_label], data_frame[y_label], c=clu.labels_)

    plt.title('DBSCAN聚类结果')
    plt.xlabel(x_label)
    plt.ylabel(y_label)
    plt.show()

if __name__ == '__main__':
    dbscsn_cluster('', '')