第九章聚类

作者: 无赖宵小 | 来源:发表于2018-10-22 17:10 被阅读7次

聚类

通过物品特征来计算距离，并自动分类到不同的群集或组中。

层次聚类算法

对于层次聚类算法，我们不需要预先指定分类的数量，这个算方法会将每条数据都当作是一个分类，每次迭代的时候合并距离最近的两个分类，直到剩下一个分类为止。
聚类的结果：顶层有一个大分类，这个分类下有两个子分类，每个子分类下又有两个子分类，依次内推，层级聚类也因此得名。

在合并的时候，我们会计算两个分类之间的距离，可以采用不同的方法，如下图 A、B、C 三个分类，我们可以采取：

单链聚类

在单链聚类中，分类之间的距离由两个分类相距最近的两个元素决定。如上图中分类 A 和分类 B 的距离由 A1 和 B1 的距离决定，因为这个距离小于 A1 到 B2、A2 到 B1 的距离，这样一来我们会将 A 和 B 进行合并。

全链聚类

在全链聚类中，分类之间的距离由两个分类相距最远的两个元素决定。因此上图中分类 A 和 B 的距离是 A2 到 B2 的距离，最后会将分类 B 和 C 进行合并。

平均链接聚类

在平均链接聚类中，分类之间的距离由分类之间两两元素的平均距离决定。因此上图中会将分类 B 和 C 进行合并。

例：用狗的高度和重量来进行聚类

计算欧几里得距离：

计算过程
第一步：找到最近的两个元素，进行聚类

第二部：在找到距离最近你的两个元素，进行聚类：

第三步：重复上面的步骤

算法实现层次聚类

from queue import PriorityQueue
import math
"""
层次聚类示例代码
"""

def getMedian(alist):
    """计算中位数"""
    tmp = list(alist)
    tmp.sort()
    alen = len(tmp)
    if (alen % 2) == 1:
        return tmp[alen // 2]
    else:
        return (tmp[alen // 2] + tmp[(alen // 2) - 1]) / 2

def normalizeColumn(column):
    """计算修正的标准分"""
    median = getMedian(column)
    asd = sum([abs(x - median) for x in column]) / len(column)
    result = [(x - median) / asd for x in column]
    return result

class hClusterer:
    """该聚类器默认数据的第一列是标签，其它列是数值型的特征。"""

    def __init__(self, filename):
        file = open(filename)
        self.data = {}
        self.counter = 0
        self.queue = PriorityQueue()
        lines = file.readlines()
        file.close()
        header = lines[0].split(',')
        self.cols = len(header)
        self.data = [[] for i in range(len(header))]
        for line in lines[1:]:
            cells = line.split(',')
            toggle = 0
            for cell in range(self.cols):
                if toggle == 0:
                    self.data[cell].append(cells[cell])
                    toggle = 1
                else:
                    self.data[cell].append(float(cells[cell]))
        # 标准化特征列（即跳过第一列）
        for i in range(1, self.cols):
            self.data[i] = normalizeColumn(self.data[i])

        ###
        ### 数据已经读入内存并做了标准化，对于每一条记录，将执行以下步骤：
        ### 1. 计算该分类和其他分类的距离，如当前分类的下标是1，
        ### 它和下标为2及下标为3的分类之间的距离用以下形式表示：
        ### {2: ((1, 2), 1.23), 3: ((1, 3), 2.3)... }
        ### 2. 找出距离最近的分类；
        ### 3. 将该分类插入到优先队列中。
        ###

        # 插入队列
        rows = len(self.data[0])

        for i in range(rows):
            for i in range(rows):
                minDistance = 99999
                nearestNeighbor = 0
                neighbors = {}
                for j in range(rows):
                    if i != j:
                        dist = self.distance(i, j)
                        if i < j:
                            pair = (i,j)
                        else:
                            pair = (j,i)
                        neighbors[j] = (pair, dist)
                        if dist < minDistance:
                            minDistance = dist
                            nearestNeighbor = j
                            nearestNum = j
            # 记录这两个分类的配对信息
            if i < nearestNeighbor:
                nearestPair = (i, nearestNeighbor)
            else:
                nearestPair = (nearestNeighbor, i)
            # 插入优先队列
            self.queue.put((minDistance, self.counter,
            [[self.data[0][i]], nearestPair, neighbors]))
            self.counter += 1

    def distance(self, i, j):
        sumSquares = 0
        for k in range(1, self.cols):
            sumSquares += (self.data[k][i] - self.data[k][j])**2
        return math.sqrt(sumSquares)

    def cluster(self):
        done = False
        while not done:
            topOne = self.queue.get()
            nearestPair = topOne[2][1]
            if not self.queue.empty():
                nextOne = self.queue.get()
                nearPair = nextOne[2][1]
                tmp = []

                ## 我从队列中取出了两个元素：topOne和nextOne，
                ## 检查这两个分类是否是一对，如果不是就继续从优先队列中取出元素，
                ## 直至找到topOne的配对分类为止。
                while nearPair != nearestPair:
                    tmp.append((nextOne[0], self.counter, nextOne[2]))
                    self.counter += 1
                    nextOne = self.queue.get()
                    nearPair = nextOne[2][1]
                ## 将不处理的元素退回给优先队列
                for item in tmp:
                    self.queue.put(item)
                if len(topOne[2][0]) == 1:
                    item1 = topOne[2][0][0]
                else:
                    item1 = topOne[2][0]
                if len(nextOne[2][0]) == 1:
                    item2 = nextOne[2][0][0]
                else:
                    item2 = nextOne[2][0]
                ## curCluster即合并后的分类
                curCluster = (item1, item2)

                ## 对于这个新的分类需要做两件事情：首先找到离它最近的分类，然后合并距离字典。
                ## 如果item1和元素23的距离是2，item2和元素23的距离是4，我们取较小的那个距离，即单链聚类。
                minDistance = 99999
                nearestPair = ()
                nearestNeighbor = ''
                merged = {}
                nNeighbors = nextOne[2][2]

                for (key, value) in topOne[2][2].items():
                    if key in nNeighbors:
                        if nNeighbors[key][1] < value[1]:
                            dist = nNeighbors[key]
                        else:
                            dist = value
                        if dist[1] < minDistance:
                            minDistance = dist[1]
                            nearestPair = dist[0]
                            nearestNeighbor = key
                        merged[key] = dist
                if merged == {}:
                    return curCluster
                else:
                    self.queue.put( (minDistance, self.counter, [curCluster, nearestPair, merged]))
                    self.counter += 1

    def printDendrogram(T, sep=3):
        """打印二叉树状图。树的每个节点是一个二元组。这个方法摘自：
        http://code.activestate.com/recipes/139422-dendrogram-drawing/"""

        def isPair(T):
            return type(T) == tuple and len(T) == 2

        def maxHeight(T):
            if isPair(T):
                h = max(maxHeight(T[0]), maxHeight(T[1]))
            else:
                h = len(str(T))
            return h + sep

        activeLevels = {}

        def traverse(T, h, isFirst):
            if isPair(T):
                traverse(T[0], h-sep, 1)
                s = [' ']*(h-sep)
                s.append('|')
            else:
                s = list(str(T))
                s.append(' ')
            while len(s) < h:
                s.append('-')
            if (isFirst >= 0):
                s.append('+')
                if isFirst:
                    activeLevels[h] = 1
                else:
                    del activeLevels[h]
                A = list(activeLevels)
                A.sort()
                for L in A:
                    if len(s) < L:
                        while len(s) < L:
                            s.append(' ')
                        s.append('|')
                print (''.join(s))

                if isPair(T):
                    traverse(T[1], h-sep, 0)
            traverse(T, maxHeight(T), -1)

        filename = '/Users/raz/Dropbox/guide/data/dogs.csv'

        hg = hClusterer(filename)
        cluster = hg.cluster()
        printDendrogram(cluster)

k-means 聚类算法

使用 k-means 算法时需要指定分类的数量，这也是算法名称中“k”的由来。

k-means 聚类过程

1、随机选取 k 个元素作为中心点；
2、根据距离将各个点分配给中心点；
3、计算新的中心点；
4、重复2、3，直至满足条件。

例：将一下点分成两个类：

第一步：随机选取中心点
(1, 4) 作为分类 1 的中心点，(4, 2) 作为分类 2 的中心点；

第二步：将各点分配给中心点（使用曼哈顿距离）

聚类结果：

第三步：更新中心点
通过计算平均值来更新中心点，如 x 轴的均值是：( 1 + 1 + 2 ) / 3 = 4 / 3 = 1.33
y 轴是：( 2 + 4 + 3) / 3 = 9 / 3 = 3
因此分类 1 的中心点是( 1.33, 3 )，计算得分类 2 的中心点是( 4, 2.4 )

第四步重复第二、第三步，直到中心点不发生变化
得到分类 1 的中心点是( 1.2, 2.75 )，计算得分类 2 的中心点是( 4.5, 2.5 )

误差平方和（SSE）

可以使用误差平方和（或称离散程度）来评判聚类结果的好坏，它的计算方法是：计算每个点到中心点的距离平方和。

第一个求和符号是遍历所有的分类，比如 i = 1 时计算第一个分类，i = 2 计算第二个分类，直到计算第 k 个分类；
第二个求和符号是遍历分类中所有的点；
dist 指代距离计算公式（如曼哈顿距离、欧几里距离）；
计算数据点 x 和中心点 c_j 之间的距离，平方后相加。

算法实现

import math
import random

"""
K-means算法
"""
 
def getMedian(alist):
    """计算中位数"""
    tmp = list(alist)
    tmp.sort()
    alen = len(tmp)
    if (alen % 2) == 1:
        return tmp[alen // 2]
    else:
        return (tmp[alen // 2] + tmp[(alen // 2) - 1]) / 2

def normalizeColumn(column):
    """计算修正的标准分"""
    median = getMedian(column)
    asd = sum([abs(x - median) for x in column]) / len(column)
    result = [(x - median) / asd for x in column]
    return result

class kClusterer:
    """kMeans聚类算法，第一列是分类，其余列是数值型特征"""

    def __init__(self, filename, k):
        """k是分类的数量，该函数完成以下功能：
        1. 读取filename的文件内容
        2. 按列存储到self.data变量中
        3. 计算修正的标准分
        4. 随机选取起始点
        5. 将各个点分配给中心点
        """
        file = open(filename)
        self.data = {}
        self.k = k
        self.counter = 0
        self.iterationNumber = 0
        # 用于跟踪本次迭代有多少点的分类发生了变动
        self.pointsChanged = 0
        # 误差平方和
        self.sse = 0
        #
        # 读取文件
        #
        lines = file.readlines()
        file.close()
        header = lines[0].split(',')
        self.cols = len(header)
        self.data = [[] for i in range(len(header))]
        # 按列存储数据，如self.data[0]是第一列的数据，
        # self.data[0][10]是第一列第十行的数据。
        for line in lines[1:]:
            cells = line.split(',')
            toggle = 0
            for cell in range(self.cols):
                if toggle == 0:
                    self.data[cell].append(cells[cell])
                    toggle = 1
                else:
                    self.data[cell].append(float(cells[cell]))

        self.datasize = len(self.data[1])
        self.memberOf = [-1 for x in range(len(self.data[1]))]
        #
        # 标准化
        #
        for i in range(1, self.cols):
            self.data[i] = normalizeColumn(self.data[i])

        # 随机选取起始点
        random.seed()
        self.centroids = [[self.data[i][r] for i in range(1, len(self.data))] for r in random.sample(range(len(self.data[0])), self.k)]
        self.assignPointsToCluster()

    def updateCentroids(self):
        """根据分配结果重新确定聚类中心点"""
        members = [self.memberOf.count(i) for i in range(len(self.centroids))]
        self.centroids = [[sum([self.data[k][i] for i in range(len(self.data[0])) if self.memberOf[i] == centroid])/members[centroid] for k in range(1, len(self.data))] for centroid in range(len(self.centroids))]

    def assignPointToCluster(self, i):
        """根据距离计算所属中心点"""
        min = 999999
        clusterNum = -1
        for centroid in range(self.k):
            dist = self.euclideanDistance(i, centroid)
            if dist < min:
                min = dist
                clusterNum = centroid
        # 跟踪变动的点
        if clusterNum != self.memberOf[i]:
            self.pointsChanged += 1
        # 计算距离平方和
        self.sse += min**2
        return clusterNum

    def assignPointsToCluster(self):
        """分配所有的点"""
        self.pointsChanged = 0
        self.sse = 0
        self.memberOf = [self.assignPointToCluster(i) for i in range(len(self.data[1]))]

    def euclideanDistance(self, i, j):
        """计算欧几里得距离"""
        sumSquares = 0
        for k in range(1, self.cols):
            sumSquares += (self.data[k][i] - self.centroids[j][k-1])**2
        return math.sqrt(sumSquares)

    def kCluster(self):
        """开始进行聚类，重复以下步骤：
        1. 更新中心点
        2. 重新分配
        直至变动的点少于1%。
        """

        done = False
        while not done:
            self.iterationNumber += 1
            self.updateCentroids()
            self.assignPointsToCluster()
            #
            # 如果变动的点少于1%则停止迭代
            #
            if float(self.pointsChanged) / len(self.memberOf) < 0.01:
                done = True
        print("Final SSE: %f" % self.sse)

    def showMembers(self):
        """输出结果"""
        for centroid in range(len(self.centroids)):
            print ("\n\nClass %i\n========" % centroid)
            for name in [self.data[0][i] for i in range(len(self.data[0])) if self.memberOf[i] == centroid]:
                    print (name)

# 对犬种数据进行聚类，令k=3
# 请自行修改文件路径
km = kClusterer('../../data/dogs.csv', 3)
km.kCluster()
km.showMembers()

k-means++

k-means 是 50 年代发明的算法，它的实现并不复杂，但它有一个明显的缺点，在算法一开始需要随机选取 k 个起始点，有时选取的点产生最佳结果，而有时会让结果变得很差。k-means++ 则改进了起始点的选取，其余的和 k-means 一致。

k-means++ 选取起始点的过程：

1、随机选取一个点；
2、重复一下步骤，直到选完 k 个点：
i.计算每个数据点（dp）到各个中心点距离（D），选取最小的值，记为 D(dp)；
ii.根据 D(dp) 的概率来随机选取一个点作为中心点。

起始点选取总结：

第一个点还是随机的，但后续的点就会尽量选择离现有中心点更远的点。

算法实现

第一步

将：

self.centroids = [[self.data[i][r] for i in range(1, len(self.data))] for r in random.sample(range(len(self.data[0])), self.k)]

修改为：

self.selectInitialCentroids()

第二步实现 selectInitialCentroids

def distanceToClosestCentroid(self, point, centroidList):
    result = self.eDistance(point, centroidList[0])
    for centroid in centroidList[1:]:
        distance = self.eDistance(point, centroid)
        if distance < result:
            result = distance
    return result

def selectInitialCentroids(self):
    """实现k-means++算法中的起始点选取过程"""
    centroids = []
    total = 0
    # 首先随机选取一个点
    current = random.choice(range(len(self.data[0])))
    centroids.append(current)
    # 开始选取剩余的点
    for i in range(0, self.k - 1):
        # 计算每个点到最近的中心点的距离
        weights = [self.distanceToClosestCentroid(x, centroids) for x in range(len(self.data[0]))]
        total = sum(weights)
        # 转换为权重
        weights = [x / total for x in weights]
        # 开始随机选取
        num = random.random()
        total = 0
        x = -1
        # 模拟轮盘游戏
        while total < num:
            x += 1
            total += weights[x]
        entroids.append(x)
    self.centroids = [[self.data[i][r] for i in range(1, len(self.data))] for r in centroids]

# -*- coding:utf-8 -*-

'''
Created on 2018年11月29日

@author: KingSley
'''

import math
import random 

"""
K-means++ 算法
"""

def getMedian(alist):
    """计算中位数"""
    tmp = list(alist)
    tmp.sort()
    alen = len(tmp)
    if (alen % 2) == 1:
        return tmp[alen // 2]
    else:
        return (tmp[alen // 2] + tmp[(alen // 2) - 1]) / 2
    
def normalizeColumn(column):
    """计算修正的标准分"""
    median = getMedian(column)
    asd = sum([abs(x - median) for x in column]) / len(column)
    result = [(x - median) / asd for x in column]
    return result

class kClusterer:
    """
    K-means 聚类算法，第一列是分类，其余列是数值型特征
    """
    
    def __init__(self, filename, k):
        """
        k 是分类的数量，该函数完成以下功能：
        1. 读取 filename 的文件内容
        2. 按列存储到 self.data 变量中
        3. 计算修正的标准分
        4. 随机选取起始点
        5. 将各个点分配给中心点
        """
        file = open(filename)
        self.data = {}
        self.k = k
        self.counter = 0
        self.iterationNumber = 0
        # 用于跟踪本次迭代有多少点的分类发生了变动
        self.pointsChanged = 0
        # 误差平方和
        self.sse = 0
        # 读取文件
        lines = file.readlines()
        file.close()
        header = lines[0].split(',')
        self.cols = len(header)
        self.data = [[] for i in range(len(header))]
        # 按列存储数据，如 self.data[0] 是第一列的数据
        # self.data[0][10] 是第一列第十行的数据
        for line in lines[1:]:
            cells = line.split(',')
            toggle = 0
            for cell in range(self.cols):
                if toggle == 0:
                    self.data[cell].append(cells[cell])
                    toggle = 1
                else:
                    self.data[cell].append(float(cells[cell]))
                    
        self.datasize = len(self.data[1])
        self.memberOf = [-1 for x in range(len(self.data[1]))]
        # 标准化
        for i in range(1, self.cols):
            self.data[i] = normalizeColumn(self.data[i])
        # 随机选取起始点
        random.seed()
        self.selectInitialCentroids()
        self.assignPointsToCluster()

    def showData(self):
        for i in range(len(self.data[0])):
            print("%20s   %8.4f  %8.4f" %
                (self.data[0][i], self.data[1][i], self.data[2][i]))

    def distanceToClosestCentroid(self, point, centroidList):
        result = self.eDistance(point, centroidList[0])
        for centroid in centroidList[1:]:
            distance = self.eDistance(point, centroid)
            if distance < result:
                result = distance
        return result
    
    def selectInitialCentroids(self):
        """实现 k-means++ 算法中的起始点选取过程"""
        centroids = []
        total = 0
        # 首先随机选取一个点
        current = random.choice(range(len(self.data[0])))
        centroids.append(current)
        # 开始选取剩余的点
        for i in range(0, self.k - 1):
            # 计算每个点到最近的中心点的距离
            weights = [self.distanceToClosestCentroid(x, centroids) 
                       for x in range(len(self.data[0]))]
            total = sum(weights)
            # 转换为权重
            weights = [x / total for x in weights]
            # 开始随机选取
            num = random.random()
            total = 0
            x = -1
            # 模拟轮盘游戏
            while total < num:
                x += 1
                total += weights[x]
            centroids.append(x)
        self.centroids = [[self.data[i][r]  for i in range(1, len(self.data))]
                            for r in centroids]
        
    def updateCentroids(self):
        """根据分配结果重新确定聚类中心点"""
        members = [self.memberOf.count(i) for i in range(len(self.centroids))]
        
        self.centroids = [[sum([self.data[k][i]
                            for i in range(len(self.data[0]))
                            if self.memberOf[i] == centroid])/members[centroid]
                           for k in range(1, len(self.data))]
                          for centroid in range(len(self.centroids))] 
        
    def assignPointToCluster(self, i):
        """根据距离计算所属中心点"""
        min = 999999
        clusterNum = -1
        for centroid in range(self.k):
            dist = self.euclideanDistance(i, centroid)
            if dist < min:
                min = dist
                clusterNum = centroid
        # 跟踪变动的点
        if clusterNum != self.memberOf[i]:
            self.pointsChanged += 1
        # 计算距离平方和
        self.sse += min**2
        return clusterNum
    
    def assignPointsToCluster(self):
        """分配所有的点"""
        self.pointsChanged = 0
        self.sse = 0
        self.memberOf = [self.assignPointToCluster(i)
                         for i in range(len(self.data[1]))]
    
    def eDistance(self, i, j):
        """点 i 到质心 j 的距离计算"""
        sumSquares = 0
        for k in range(1, self.cols):
            sumSquares += (self.data[k][i] - self.data[k][j])**2
        return math.sqrt(sumSquares)
    
    def euclideanDistance(self, i, j):
        """计算欧几里得距离"""
        sumSquares = 0
        for k in range(1, self.cols):
            sumSquares += (self.data[k][i] - self.centroids[j][k-1])**2
        return math.sqrt(sumSquares)
    
    def kCluster(self):
        """ 开始进行聚类，重复以下步骤：
        1. 更新中心点
        2. 重新分配
        直至变动的点少于 1%
        """
        done = False
 
        while not done:
            self.iterationNumber += 1
            self.updateCentroids()
            self.assignPointsToCluster()
            
            # 如果变动的点少于 1% 则停止迭代
            
            if float(self.pointsChanged) / len(self.memberOf) <  0.01:
                done = True
        print("Final SSE: %f" % self.sse)
        
    def showMembers(self):
        """输出结果"""
        for centroid in range(len(self.centroids)):
            print ("\n\nClass %i\n========" % centroid)
            for name in [self.data[0][i]  for i in range(len(self.data[0]))
                        if self.memberOf[i] == centroid]:
                print (name)

### 对犬种数据进行聚类，令 k = 3
km = kClusterer('dogs.csv', 3)
km.kCluster()
km.showMembers()

参考原文作者：Ron Zacharski CC BY-NC 3.0] https://github.com/egrcc/guidetodatamining

参考原文原文 http://guidetodatamining.com/

参考译文来自 @egrcc 的 https://github.com/egrcc/guidetodatamining

第九章聚类

聚类

层次聚类算法

单链聚类

全链聚类

平均链接聚类

例：用狗的高度和重量来进行聚类

算法实现层次聚类

k-means 聚类算法

例：将一下点分成两个类：

误差平方和（SSE）

算法实现

k-means++

k-means++ 选取起始点的过程：

起始点选取总结：

算法实现

第一步

第二步实现 selectInitialCentroids

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据挖掘

第九章 聚类

聚类

层次聚类算法

单链聚类

全链聚类

平均链接聚类

例：用狗的高度和重量来进行聚类

算法实现层次聚类

k-means 聚类算法

例：将一下点分成两个类：

误差平方和（SSE）

算法实现

k-means++

k-means++ 选取起始点的过程：

起始点选取总结：

算法实现

第一步

第二步实现 selectInitialCentroids

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据挖掘

第九章聚类