• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

canopy聚类算法

ml admin 10个月前 (02-24) 580次浏览 0个评论 扫描二维码

在 k 均值聚类,初始随机选取 k 个点作为中心点的方式在遇到离群点则得到的效果不好,当然你会说我们会尝试多次选取较好的初始数据,
canopy 可以解决上述初始点的选取问题,但是其自身的 t1 t2 选取也是一个头疼的问题,作者说要进行调参的方式,通过交叉验证来确定最优参数。。。黑线。。。


canopy 核心思想:
1、给我一组存放在数组里面的数据 D

2、给我两个距离阈值 T1,T2,且 T1>T2

3、随机取 D 中的一个数据 d 作为中心,并将 d 从 D 中移除

4、计算 D 中所有点到 d 的距离 distance

5、将所有 distance<T1 的点都归如到 d 为中心的 canopy1 类中(注意哦,小于 T2 的也是小于 T1 的,所以也是归入到 canopy1 中的哦)

6、将所有 distance<T2 的点,都从 D 中移除。(这一步很关键的,你回去看上面那个图,就明白了)

7:重复步骤 4 到 6,直到 D 为空,形成多个 canopy 类

# -*- coding: utf-8 -*-
# @Author: Alan Lau
# @Date: 2017-09-05 22:56:16
# @Last Modified by:   Alan Lau
# @Last Modified time: 2017-09-05 22:56:16

import math
import random
import numpy as np
from datetime import datetime
from pprint import pprint as p
import matplotlib.pyplot as plt

# 随机生成 500 个二维[0,1)平面点
dataset = np.random.rand(500, 2)


class Canopy:
    def __init__(self, dataset):
        self.dataset = dataset
        self.t1 = 0
        self.t2 = 0

    # 设置初始阈值
    def setThreshold(self, t1, t2):
        if t1 > t2:
            self.t1 = t1
            self.t2 = t2
        else:
            print('t1 needs to be larger than t2!')

    # 使用欧式距离进行距离的计算
    def euclideanDistance(self, vec1, vec2):
        return math.sqrt(((vec1 - vec2)**2).sum())

    # 根据当前 dataset 的长度随机选择一个下标
    def getRandIndex(self):
        return random.randint(0, len(self.dataset) - 1)

    def clustering(self):
        if self.t1 == 0:
            print('Please set the threshold.')
        else:
            canopies = []  # 用于存放最终归类结果
            while len(self.dataset) != 0:
                rand_index = self.getRandIndex()
                current_center = self.dataset[rand_index]  # 随机获取一个中心点,定为 P 点
                current_center_list = []  # 初始化 P 点的 canopy 类容器
                delete_list = []  # 初始化 P 点的删除容器
                self.dataset = np.delete(
                    self.dataset, rand_index, 0)  # 删除随机选择的中心点 P
                for datum_j in range(len(self.dataset)):
                    datum = self.dataset[datum_j]
                    distance = self.euclideanDistance(
                        current_center, datum)  # 计算选取的中心点 P 到每个点之间的距离
                    if distance < self.t1:
                        # 若距离小于 t1,则将点归入 P 点的 canopy 类
                        current_center_list.append(datum)
                    if distance < self.t2:
                        delete_list.append(datum_j)  # 若小于 t2 则归入删除容器
                # 根据删除容器的下标,将元素从数据集中删除
                self.dataset = np.delete(self.dataset, delete_list, 0)
                canopies.append((current_center, current_center_list))
        return canopies


def showCanopy(canopies, dataset, t1, t2):
    fig = plt.figure()
    sc = fig.add_subplot(111)
    colors = ['brown', 'green', 'blue', 'y', 'r', 'tan', 'dodgerblue', 'deeppink', 'orangered', 'peru', 'blue', 'y', 'r',
              'gold', 'dimgray', 'darkorange', 'peru', 'blue', 'y', 'r', 'cyan', 'tan', 'orchid', 'peru', 'blue', 'y', 'r', 'sienna']
    markers = ['*', 'h', 'H', '+', 'o', '1', '2', '3', ',', 'v', 'H', '+', '1', '2', '^',
               '<', '>', '.', '4', 'H', '+', '1', '2', 's', 'p', 'x', 'D', 'd', '|', '_']
    for i in range(len(canopies)):
        canopy = canopies[i]
        center = canopy[0]
        components = canopy[1]
        sc.plot(center[0], center[1], marker=markers[i],
                color=colors[i], markersize=30)
        t1_circle = plt.Circle(
            xy=(center[0], center[1]), radius=t1, color='dodgerblue', fill=False)
        t2_circle = plt.Circle(
            xy=(center[0], center[1]), radius=t2, color='skyblue', alpha=0.2)
        sc.add_artist(t1_circle)
        sc.add_artist(t2_circle)
        for component in components:
            sc.plot(component[0], component[1],
                    marker=markers[i], color=colors[i], markersize=1.5)
    maxvalue = np.amax(dataset)
    minvalue = np.amin(dataset)
    plt.xlim(minvalue - t1, maxvalue + t1)
    plt.ylim(minvalue - t1, maxvalue + t1)
    plt.show()


def main():
    t1 = 0.6
    t2 = 0.4
    gc = Canopy(dataset)
    gc.setThreshold(t1, t2)
    canopies = gc.clustering()
    print('Get %s initial centers.' % len(canopies))
    showCanopy(canopies, dataset, t1, t2)


if __name__ == '__main__':
    t_s = datetime.now()
    main()
    t_e = datetime.now()
    usedtime = t_e - t_s
    print('[%s]' % usedtime)

Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明canopy 聚类算法
喜欢 (0)
admin
关于作者:

您必须 登录 才能发表评论!