《机器学习》周志华note3

聚类

  • 大纲
    《机器学习》周志华note3
    k-means,DBSCAN算法最为常用

聚类的概述

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

相似性计算

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

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

《机器学习》周志华note3

  • 欧式距离
  • 曼哈顿距离
  • 闵可夫斯基距离
    《机器学习》周志华note3
    《机器学习》周志华note3
    《机器学习》周志华note3
    《机器学习》周志华note3
    《机器学习》周志华note3
    《机器学习》周志华note3
    《机器学习》周志华note3
    《机器学习》周志华note3
    《机器学习》周志华note3
    《机器学习》周志华note3
    《机器学习》周志华note3
    青年 中年 老年 本科以下 本科 研究生 低 中 高
    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

《机器学习》周志华note3

  • 如何计算
    《机器学习》周志华note3
    《机器学习》周志华note3
    《机器学习》周志华note3
    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个簇中心,按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心,从而确定新的簇心,一直迭代,直到簇心的移动距离小于某个给定的值。
    《机器学习》周志华note3
    计算矩阵
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()

《机器学习》周志华note3
《机器学习》周志华note3

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算法

  • 基本思想:选取有代表性的样本(而不是均值)来表示整个簇,即:选取最靠近中心点的那个样本来代表整个簇,以降低聚类算法对离群点的敏感度。
    《机器学习》周志华note3
    《机器学习》周志华note3
    《机器学习》周志华note3

层次方法

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

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

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

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

  • until达到定义的簇的数目。
    《机器学习》周志华note3
    《机器学习》周志华note3
    《机器学习》周志华note3

DBSCAN算法

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

《机器学习》周志华note3
将点分为:核心点、边界点、噪声或背景点
《机器学习》周志华note3
《机器学习》周志华note3
《机器学习》周志华note3
《机器学习》周志华note3
DBSCAN运行效果好时的效果:
《机器学习》周志华note3

  • 时间复杂度
    《机器学习》周志华note3
  • 空间复杂度
    《机器学习》周志华note3
  • 如何选取合适的EPS和MinPts
    《机器学习》周志华note3
  • 优点:基于密度定义,相对抗噪声,能处理任意形状和大小的簇
  • 缺点:当簇的密度变化太大时,会有麻烦;对于高维问题,密度定义是个麻烦的问题。
# -*- 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('', '')
上一篇:机器学习(聚类七)——层次聚类的优化算法


下一篇:打造Flowportal绿色版(实现系统*迁移)