第8-1节层次聚类法|写给程序员的数据挖掘实践指南-学习笔记

作者: 努力奋斗的durian | 来源:发表于2018-09-06 17:05 被阅读94次

文章原创,最近更新：2018-09-06

1.关于本书
2.关于作者
3.内容简介
4.案例

引言:网上找资料觉得这本书挺通俗易懂的,刚好可以跟《机器学习实战》相关章节结合一起学习。

本案例所涉及到的数据集dog.csv,可在官方网站直接下载.

暂时未写完,后续再补充.

1.关于本书

写给程序员的数据挖掘实践指南:豆瓣评分:7.4分
作者: [美] Ron Zacharski
出版社: 人民邮电出版社
原作名: A Programmer's Guide to Data Mining
译者: 王斌
出版年: 2015-10-24

2.关于作者

Ron Zacharski是一名软件开发工程师，曾在威斯康辛大学获美术学士学位，之后还在明尼苏达大学获得了计算机科学博士学位。博士后期间，他在爱丁堡大学研究语言学。正是基于广博的学识，他不仅在新墨西哥州立大学的计算研究实验室工作，期间还接触过自然语言处理相关的项目，而该实验室曾被《连线》杂志评为机器翻译研究领域翘楚。除此之外，他还曾教授计算机科学、语言学、音乐等课程，是一名博学多才的科技达人。

3.内容简介

本书是写给程序员的一本数据挖掘指南，可以帮助读者动手实践数据挖掘、集体智慧并构建推荐系统。全书共8章，介绍了数据挖掘的基本知识和理论、协同过滤、内容过滤及分类、算法评估、朴素贝叶斯、非结构化文本分类以及聚类等内容。本书采用“在实践中学习”的方式，用生动的图示、大量的表格、简明的公式、实用的Python代码示例，阐释数据挖掘的知识和技能。每章还给出了习题和练习，帮助读者巩固所学的知识。

4.案例分析

4.1 getMedian()

这个函数主要是计算中位数,那么如何计算中位数呢?
确定中位数，必须将总体各单位的标志值按大小顺序排列，最好是编制出变量数列。这里有两种情况：
对于未分组的原始资料，首先必须将标志值按大小排序。设排序的结果为：

则中位数就可以按下面的方式确定：

比如案例中的数据
20.0, 16.0, 18.0, 27.0, 8.0, 25.0, 23.0, 32.0, 21.0, 19.0, 6.0
首先对数据进行大小排序后,结果如下:
6.0, 8.0, 16.0, 18.0, 19.0, 20.0, 21.0, 23.0, 25.0, 27.0, 32.0
数据共有11个,则中位数是第6个数字,即这个数字是20.0

用代码表示以上的过程,如下:

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

测试代码及其结果如下:

alist=[20.0, 16.0, 18.0, 27.0, 8.0, 25.0, 23.0, 32.0, 21.0, 19.0, 6.0]

getMedian(alist)
Out[7]: 20.0

4.2 normalizeColumn()

这个函数主要是计算修正的标准分,标准分的计算过程如下:

对于未分组的原始资料，首先必须将标志值按大小排序,找出中位数.
每个数据的标准差的计算如下：

$\frac{每一数据-中位数}{\frac{\sum |每一数据-中位数|}{数据的个数}}$
用本文所使用的案例进行分析,用狗的高度和重量来进行聚类：

数据标准化对比图
那么这个结果是怎么产生的呢?
首先我们查看一下数据
第1列的数据,即狗的高度:20.0, 16.0, 18.0, 27.0, 8.0, 25.0, 23.0, 32.0, 21.0, 19.0, 6.0
第2列的数据,即狗的重量:45.0, 20.0, 35.0, 120.0, 8.0, 78.0, 70.0, 160.0, 50.0, 65.0, 7.0
Border Collie狗的身高标准差为:

我们用Python的列表结构来存储这些数据，data[0]用来存放所有记录的分类，如data[0][0]是Border Collie，data[0][1]是Boston Terrier。data[1]则是所有记录的高度，data[2]是重量。

特征列的数据都会转换成浮点类型，如data[1][0]是20.0，data[2][0]是45.0等。在读取数据时就需要对其进行标准化。此外，我们接下来会使用“下标”这个术语，如第一条记录Border Collie的下标是0，第二条记录Boston Terrier下标是1等。

需要使用代码将数据分割成这样:

[['Border Collie', 'Boston Terrier', 'Brittany Spaniel', 'Bullmastiff', 'Chihuahua', 'German Shepherd', 'Golden Retriever', 'Great Dane', 'Portuguese Water Dog', 'Standard Poodle', 'Yorkshire Terrier'], 
[20.0, 16.0, 18.0, 27.0, 8.0, 25.0, 23.0, 32.0, 21.0, 19.0, 6.0],
 [45.0, 20.0, 35.0, 120.0, 8.0, 78.0, 70.0, 160.0, 50.0, 65.0, 7.0]]

以下有四种方案可以达到以上要求的效果:
方案1

def filedocument(filename):
    data = []
    data1=[]
    data2=[]
    data3=[]
    data4=[]
    file= open(filename)
    lines = file.readlines()
    file.close()
    for line in lines[1:]:
        cells = line.strip().split(",")
        data.append(cells)
    for i in range(0,len(data)):
        data1.append(data[i][0])
        data2.append(float(data[i][1]))
        data3.append(float(data[i][2]))
    data4.append(data1)
    data4.append(data2)
    data4.append(data3)
    return data4

方案2

def filedocument(filename):
    data=[]
    data1=[]
    data2=[]
    data3=[]
    file= open(filename)
    lines=file.readlines()
    for line in lines[1:]:
        cells= line.strip().split(",")
        data1.append(cells[0])
        data2.append(float(cells[1]))
        data3.append(float(cells[2]))
    data.append(data1)
    data.append(data2)
    data.append(data3)
    return data

方案3

def filedocument(filename):
    file=open(filename)
    lines=file.readlines()
    header=lines[0].strip().split(",")
    data=[[] for i in range(len(header))]
    for line in lines[1:]:
        cells=line.strip().split(",")
        for cell in range(len(cells)):
            if cell ==0: 
                data[cell].append(cells[cell])
            else:
                data[cell].append(float(cells[cell]))
    return data

方案4

def filedocument(filename):
    filename = 'dog.csv'
    file=open(filename)
    lines=file.readlines()
    file.close()
    header=lines[0].strip().split(",")
    cols = len(header)
    data=[[] for i in range(len(header))]
    for line in lines[1:]:
       cells=line.strip().split(",")
       toggle=0
       for cell in range(cols):
           if toggle ==0: 
                data[cell].append(cells[cell])
                toggle=1
           else:
               data[cell].append(float(cells[cell]))
    return data

以上四种方案,测试代码及其结果都一样,具体如下:

filename = 'dog.csv'
print(filedocument(filename))

runfile('C:/Users/Administrator/Desktop/untitled1.py', wdir='C:/Users/Administrator/Desktop')
[['Border Collie', 'Boston Terrier', 'Brittany Spaniel', 'Bullmastiff', 'Chihuahua', 'German Shepherd', 'Golden Retriever', 'Great Dane', 'Portuguese Water Dog', 'Standard Poodle', 'Yorkshire Terrier'], 
[20.0, 16.0, 18.0, 27.0, 8.0, 25.0, 23.0, 32.0, 21.0, 19.0, 6.0], 
[45.0, 20.0, 35.0, 120.0, 8.0, 78.0, 70.0, 160.0, 50.0, 65.0, 7.0]]

本案例采用的是第4种方案.

标准化特征列

依据从文件中读取数据相关代码的基础上,标准化特征列

def filedocument(filename):
    #1.从文件中读取数据
    file=open(filename)
    lines=file.readlines()
    file.close()
    header=lines[0].strip().split(",")
    cols = len(header)
    data=[[] for i in range(len(header))]
    for line in lines[1:]:
       cells=line.strip().split(",")
       toggle=0
       for cell in range(cols):
           if toggle ==0: 
                data[cell].append(cells[cell])
                toggle=1
           else:
               data[cell].append(float(cells[cell]))
     #2.标准化特征列          
    for i in range(1,cols):
       data[i]=normalizeColumn(data[i])
       
    return data

测试代码及其结果如下:

filename = 'dog.csv'
print(filedocument(filename))

[['Border Collie', 'Boston Terrier', 'Brittany Spaniel', 'Bullmastiff', 'Chihuahua', 'German Shepherd', 'Golden Retriever', 'Great Dane', 'Portuguese Water Dog', 'Standard Poodle', 'Yorkshire Terrier'],
[0.0, -0.721311475409836, -0.360655737704918, 1.262295081967213, -2.163934426229508, 0.901639344262295, 0.540983606557377, 2.163934426229508, 0.180327868852459, -0.180327868852459, -2.524590163934426], 
[-0.1455026455026455, -0.8730158730158729, -0.43650793650793646, 2.0370370370370368, -1.222222222222222, 0.8148148148148148, 0.582010582010582, 3.201058201058201, 0.0, 0.43650793650793646, -1.2513227513227512]]

与我们之前计算的结果是一致的,具体如下:

4.4 distance()

这个函数主要计算每个犬种与其它犬种的距离.

还是以下截图的数据,作为案例:

以Border Collie为例，我们需要计算它和其它犬种的距离，保存在Python字典里：

{1: ((0, 1), 1.0244), # Border Collie（下标为0）和Boston Terrier（下标为1）之间的距离为1.0244
2: ((0, 2), 0.463), # Border Collie和Brittany Spaniel（下标为2）之间的距离为0.463
...
10: ((0, 10), 2.756)} # Border Collie和Yorkshire Terrier的距离为2.756

通过手工计算,发现Border Collie最近的分类及距离：这对犬种是(0, 8)，即下标为0的Border Collie和下标为8的Portuguese WD，距离是0.232。

这个距离是怎么计算出来的呢?

注意:我们这里的距离指的是欧几里德距离,具体公式如下:
在欧几里得空间中，点x =(x₁,...,x_n)和 y =(y₁,...,y_n)之间的欧氏距离为

由此可以计算出这对犬种是(0, 8)，即下标为0的Border Collie和下标为8的Portuguese WD的距离是0.232的具体过程,如下:

Border Collie的下标为0,则高度与重量的坐标为(0,-0.1455)
Portuguese WD下标为8,,则高度与重量的坐标为(0.1803,0)

$d(0,8):=\sqrt{(0-0.1803)^{2}+(-0.1455-0)^{2}}\approx 0.232$

因此由此类推,可以得到每个犬种之间的距离,具体可以参见如下截图:
注意:图中高亮了一些最短距离

每种犬种与其它犬种之间的距离

那么如何通过代码对以上过程进行展示呢?具体如下:

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

测试代码及其结果如下:

filename = 'dog.csv'
a=distance(filename,1,2)
print(a)

0.5662258734585477

由此可以知道Boston Terrier和Brittany Spaniel这两种犬种之间的距离是约等于0.566,与我们手工计算的每种犬种与其它犬种之间的距离中的截图结果是一致的.

4.5 queue()

这个函数主要是初始化优先队列

什么又叫优先队列呢？
普通的队列有“先进先出”的规则，比如向队列先后添加Moa、Suzuka、Yui，取出时得到的也是Moa、Suzuka、Yui：

而对于优先队列，每个元素都可以附加一个优先级，从队列中取出时会得到优先级最高的元素。比如说，我们定义年龄越小优先级越高，以下是插入过程：

取出的第一个元素是Yui，因为她的年龄最小：

我们看看Python中如何使用优先队列：

这里需要特别说明,queue是python自带的一个库,不需要安装.

>>> from queue import PriorityQueue           # 加载优先队列类
>>> singersQueue = PriorityQueue()            # 创建对象
>>> singersQueue.put((16, 'Suzuka Nakamoto')) # 插入元素
>>> singersQueue.put((15, 'Moa Kikuchi'))
>>> singersQueue.put((14, 'Yui Mizuno'))
>>> singersQueue.put((17, 'Ayaka Sasaki'))
>>> singersQueue.get() # 获取第一个元素，即最年轻的歌手Yui。
(14, 'Yui Mizuno')
>>> singersQueue.get() # 获取第二个元素
(15, 'Moa Kikuchi')
>>> singersQueue.get() # 获取第三个元素
(16, 'Suzuka Nakamoto')
>>> singersQueue.get() # 获取第四个元素
(17, 'Ayaka Sasaki')

在介绍优先队列时，我用了歌手的年龄举例，如果他们的年龄相等，取出的顺序又是怎样的呢？

可以看到，如果年龄相等，优先队列会根据记录中的第二个元素进行判断，即歌手的姓名，并按字母顺序返回，如Avaka会比Moa优先返回。

在犬种示例中，我们让距离成为第一优先级，下标成为第二优先级。因此，我们插入到优先队列的一条完整记录是这样的：

优先队列记录

既然知道了距离,也知道了优先排队的方法,以及优先队列数据记录展现的形式,那么如何用代码来表示上述犬种的优先排队呢?

继续依据从文件中读取数据以及标准化特征列相关代码的基础上,对犬种进行优先排队.具体如下:

def queue(filename):
    data=filedocument(filename)
    queue = PriorityQueue()
    counter=0
    for i in  range(len(data[0])):
        minDistance=99999
        nearestNeighbor = 0
        neighbors={}
        for j in  range(len(data[0])):
            if i!=j:
                dist=distance(filename,i,j)
                if i <j:
                    Pair=(i,j)
                else:
                    Pair=(j,i)
                neighbors[j]=(Pair,dist)
                if dist < minDistance:
                    minDistance = dist
                    nearestNeighbor = j
                
        if i < nearestNeighbor:
            nearestPair = (i, nearestNeighbor)
        else:
            nearestPair = (nearestNeighbor, i)
            queue.put((minDistance, counter,
                                [[data[0][i]], nearestPair, neighbors]))
        print((minDistance, counter,
                           [[data[0][i]], nearestPair, neighbors]))

测试代码及其结果如下:

filename = 'dog.csv'
a=queue(filename)

(0.23170921460558744, 0, [['Border Collie'], (0, 8), {1: ((0, 1), 1.0244831578726061), 2: ((0, 2), 0.4634184292111748), 3: ((0, 3), 2.5212830741150487), 4: ((0, 4), 2.4170099809294157), 5: ((0, 5), 1.3172559097276118), 6: ((0, 6), 0.9066083822525246), 7: ((0, 7), 3.9852329543899034), 8: ((0, 8), 0.23170921460558744), 9: ((0, 9), 0.6093065384986165), 10: ((0, 10), 2.756155583828758)}])
(0.5662258734585477, 1, [['Boston Terrier'], (1, 2), {0: ((0, 1), 1.0244831578726061), 2: ((1, 2), 0.5662258734585477), 3: ((1, 3), 3.52180392892288), 4: ((1, 4), 1.4842863782160383), 5: ((1, 5), 2.34152552705655), 6: ((1, 6), 1.9262634448032971), 7: ((1, 7), 4.9922663664881854), 8: ((1, 8), 1.255033952393085), 9: ((1, 9), 1.416868332017332), 10: ((1, 10), 1.8425336150695488)}])
(0.4634184292111748, 2, [['Brittany Spaniel'], (0, 2), {0: ((0, 2), 0.4634184292111748), 1: ((1, 2), 0.5662258734585477), 3: ((2, 3), 2.958444540501654), 4: ((2, 4), 1.9670182935759584), 5: ((2, 5), 1.7774131489151734), 6: ((2, 6), 1.3602696349205545), 7: ((2, 7), 4.42780339457414), 8: ((2, 8), 0.6951276438167623), 9: ((2, 9), 0.8914453739980573), 10: ((2, 10), 2.3122576377780506)}])
(1.2743232406392442, 3, [['Bullmastiff'], (3, 5), {0: ((0, 3), 2.5212830741150487), 1: ((1, 3), 3.52180392892288), 2: ((2, 3), 2.958444540501654), 4: ((3, 4), 4.728828561272353), 5: ((3, 5), 1.2743232406392442), 6: ((3, 6), 1.6240049967240762), 7: ((3, 7), 1.4723786121140605), 8: ((3, 8), 2.306550008240866), 9: ((3, 9), 2.154728377283816), 10: ((3, 10), 5.015357411324655)}])
(0.3618278622956078, 4, [['Chihuahua'], (4, 10), {0: ((0, 4), 2.4170099809294157), 1: ((1, 4), 1.4842863782160383), 2: ((2, 4), 1.9670182935759584), 3: ((3, 4), 4.728828561272353), 5: ((4, 5), 3.6806605973096675), 6: ((4, 6), 3.2514362328001205), 7: ((4, 7), 6.1883647684231375), 8: ((4, 8), 2.64374599170132), 9: ((4, 9), 2.5857456785133), 10: ((4, 10), 0.3618278622956078)}])
(0.4292672500331769, 5, [['German Shepherd'], (5, 6), {0: ((0, 5), 1.3172559097276118), 1: ((1, 5), 2.34152552705655), 2: ((2, 5), 1.7774131489151734), 3: ((3, 5), 1.2743232406392442), 4: ((4, 5), 3.6806605973096675), 6: ((5, 6), 0.4292672500331769), 7: ((5, 7), 2.699545586269829), 8: ((5, 8), 1.0882157079364436), 9: ((5, 9), 1.1461976899425346), 10: ((5, 10), 4.000996511500954)}])
(0.4292672500331769, 6, [['Golden Retriever'], (5, 6), {0: ((0, 6), 0.9066083822525246), 1: ((1, 6), 1.9262634448032971), 2: ((2, 6), 1.3602696349205545), 3: ((3, 6), 1.6240049967240762), 4: ((4, 6), 3.2514362328001205), 5: ((5, 6), 0.4292672500331769), 7: ((6, 7), 3.081132875082385), 8: ((6, 8), 0.6846961944627522), 9: ((6, 9), 0.7358405156052383), 10: ((6, 10), 3.571953758580651)}])
(1.4723786121140605, 7, [['Great Dane'], (3, 7), {0: ((0, 7), 3.9852329543899034), 1: ((1, 7), 4.9922663664881854), 2: ((2, 7), 4.42780339457414), 3: ((3, 7), 1.4723786121140605), 4: ((4, 7), 6.1883647684231375), 5: ((5, 7), 2.699545586269829), 6: ((6, 7), 3.081132875082385), 8: ((7, 8), 3.7658290695451373), 9: ((7, 9), 3.6246798304633625), 10: ((7, 10), 6.46575277734129)}])
(0.23170921460558744, 8, [['Portuguese Water Dog'], (0, 8), {0: ((0, 8), 0.23170921460558744), 1: ((1, 8), 1.255033952393085), 2: ((2, 8), 0.6951276438167623), 3: ((3, 8), 2.306550008240866), 4: ((4, 8), 2.64374599170132), 5: ((5, 8), 1.0882157079364436), 6: ((6, 8), 0.6846961944627522), 7: ((7, 8), 3.7658290695451373), 9: ((8, 9), 0.5662258734585477), 10: ((8, 10), 2.9803339061376346)}])
(0.5662258734585477, 9, [['Standard Poodle'], (8, 9), {0: ((0, 9), 0.6093065384986165), 1: ((1, 9), 1.416868332017332), 2: ((2, 9), 0.8914453739980573), 3: ((3, 9), 2.154728377283816), 4: ((4, 9), 2.5857456785133), 5: ((5, 9), 1.1461976899425346), 6: ((6, 9), 0.7358405156052383), 7: ((7, 9), 3.6246798304633625), 8: ((8, 9), 0.5662258734585477), 10: ((9, 10), 2.888656805320768)}])
(0.3618278622956078, 10, [['Yorkshire Terrier'], (4, 10), {0: ((0, 10), 2.756155583828758), 1: ((1, 10), 1.8425336150695488), 2: ((2, 10), 2.3122576377780506), 3: ((3, 10), 5.015357411324655), 4: ((4, 10), 0.3618278622956078), 5: ((5, 10), 4.000996511500954), 6: ((6, 10), 3.571953758580651), 7: ((7, 10), 6.46575277734129), 8: ((8, 10), 2.9803339061376346), 9: ((9, 10), 2.888656805320768)}])

4.6 cluster()

这个函数的主要作用是最近距离聚类,直到剩余一个元素为止.

可参照如下截图的数据进行聚类.

什么叫聚类呢?
第一步：我们找到距离最近的两个元素，对他们进行聚类：

第二步：再找出距离最近的两个元素，进行聚类：

第三步：继续重复上面的步骤：

第四步：继续查找距离最近的元素，发现Border Collie已经属于一

这叫树状图，可以用来表示聚类。

你能在下图的基础上继续完成聚类吗？

哈哈,做对了没有.具体结果如下:

通过以上的小案例,是否已经找到了聚类的方法呢?对以上过程总结如下:

我们从优先队列中取出两个元素，对它们进行合并。如合并Border Collie和Portuguese WD后，会形成一个新的分类：

['Border Collie', 'Portuguese WD']

然后我们需要计算新的分类和其它分类之间的距离，方法是对取出的两个分类的距离字典进行合并。如第一个分类的距离字段是distanceDict1，第二个分类的是distanceDict2，新的距离字段是newDistanceDict：

初始化newDistanceDict
对于distanceDict1的每一个键值对:
    如果这个键在distanceDict2中存在:
        如果这个键在distanceDict1中的距离要比在distanceDict2中的距离小:
            将distanceDict1中的距离存入newDistanceDict
        否则:
            将distanceDict2中的距离存入newDistanceDict

第8-1节层次聚类法|写给程序员的数据挖掘实践指南-学习笔记

1.关于本书

2.关于作者

3.内容简介

4.案例分析

4.1 getMedian()

4.2 normalizeColumn()

标准化特征列

4.4 distance()

4.5 queue()

4.6 cluster()

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读