第9章 聚类

  • 9.1 试证明:时,闵可夫斯基距离满足距离度量的四条基本性质;时,闵可夫斯拈距离不满足直递性,但满足非负性、同一性、对称性;p趋向无穷大时,闵可夫斯基距离等于对应分量的最大绝对距离,即

非负性:

绝对值总是非负的:

幂函数在上显然满足非负性,因此闵可夫斯基距离满足非负性。

同一性:

幂函数在上单调递增,在0处取值为0。

时,,于是

时,由于幂函数的单调递增,可以确定,于是

对称性:

绝对值满足对程性:,于是就有:

直递性:

闵可夫斯基距离直递性证明也就是闵可夫斯基不等式的证明

当p=1时,根据三角不等式,不等式显然成立

当p>1时,根据三角不等式,

,则,根据赫尔德不等式

将这两个式子相加后除以右侧的公共部分,又观察到,就有

由于,于是就可以得到闵可夫斯基不等式。

当p<1时,按照证伪的原则,只需要找到一个反例就可以证明不满足直通性了。对于(0,0)和(1,1),他们之间的距离,但是(0,1)到它们的距离是1,显然不满足于直通性。

切比雪夫距离:

证明p趋向无穷大时,得到切比雪夫距离,等价于证明

不妨假设

得证。

  • 9.2 同一样本空间中的集合 X 与 Z 之间的距离可通过“豪斯多夫距离” (Hausdorff distance) 计算:

​ 其中 ​ 试证明:豪斯多夫距离满足距离度量的四条基本性质。

非负性:

2范数的值总是非负的:

显然,在非负值域中找到的最大值和最小值也是非负的。

同一性:

对于任意,取,总是可以让,因此,所以

,根据max函数性质,有,这说明对于X的每一个对象,总是能够在Z中找到一样的对象,也就是,同理,所以X=Z。

对称性:

函数就是一个对称函数,所有就有

直递性:

这个难度有些过分了,我连抄答案的兴趣也没有。

  • 9.4 试编程实现 K 均值算法设置三组不同的K值、三组不同初始中心点,在西瓜数据集4.0上进行实验比较,并讨论什么样的初始中心有利于取得好结果。

KMeans算法过程为:

输入: 样本集;聚类簇数k。

过程:

  1. 从D中随机选择k个样本作为初始均值向量
    1. repeat
      1. for j = 1, 2, … , m do
        1. 计算样本与各均值向量的距离:
        2. 根据距离最近的均值向量确定的簇标记:
        3. 将样本划入相应的簇:
      2. end for
      3. for i = 1, 2, … , k do
        1. 计算新均值向量:
        2. if then
          1. 将当前均值向量更新为
        3. else
          1. 保持当前均值向量不变
        4. end if
      4. end for
    2. until 当前均值向最均未更新

    输出:簇划分

在西瓜数据集4.0上运行聚类:

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import ConvexHull
from k_means import KMeans
# Read data
data = pd.read_csv('data4.0.csv')
X = np.asarray(data[['密度', '含糖率']])
# Clustering
for k in range(2, 5):
    print('k=%d时\n' % k)
    for i in range(1, 4):
        print('第%d次聚类:' % i)
        model = KMeans()
        model.fit(X, k, visual=True)

K=2时的三次聚类结果:

png

K=3时的三次聚类结果:

png

K=4时的三次聚类结果:

png

  • 9.5 基于DBSCAN的概念定义,若尤为核心对象,由工密度可达的所有样本构成的集合为X。试证明:X满足连接性(9.39)与最大性(9.40)。

连接性:按照DBSCAN算法,对于每一个簇,算法从其中一个核心对象开始,通过密度置达关系不断添加对象。因此,对于,簇中第一个核心对象必然与满足密度可达,因此密度相连。

最大性:密度可达,那么存在样本序列,其中密度直达,按照DBSCAN算法,序列中的所有对象对被添加进簇中,因此有

第10章 降维与度量学习

  • 10.1 编程实现k近邻分类器,在西瓜数据3.0a上比较其分类边界与决策树分类边界之异同。
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.colors as colors
import graphviz as gv
from k_nearest import KNearest
from decision_tree import DecisionTree
# Read data
data = pd.read_csv('data3.0.csv')
X = np.asarray(data[['密度', '含糖率']])
y = np.asarray(data['好瓜'])

使用不同的K值执行K邻近算法:

# Plot data
for k in range(1, 6):
    model = KNearest(k, X, y)
    cmap = colors.LinearSegmentedColormap.from_list('watermelon', ['red', 'green'])
    xx, yy = np.meshgrid(np.arange(0.2, 0.8, 0.01), np.arange(0.0, 0.5, 0.01))
    Z = np.asarray([model.predict(v) for v in np.c_[xx.ravel(), yy.ravel()]]) == '是'
    Z = Z.reshape(xx.shape)
    plt.contourf(xx, yy, Z, cmap=cmap, alpha=0.3, antialiased=True)
    plt.scatter(X[:, 0], X[:, 1], c=(y == '是'), cmap=cmap)
    plt.xlabel('密度')
    plt.ylabel('含糖率')
    plt.title('k=%d' % k)
    plt.show()

png

使用决策树算法进行分类:

model = DecisionTree()
model.fit(X, y)
cmap = colors.LinearSegmentedColormap.from_list('watermelon', ['red', 'green'])
xx, yy = np.meshgrid(np.arange(0.2, 0.8, 0.01), np.arange(0.0, 0.5, 0.01))
Z = np.asarray([model.predict(v) for v in np.c_[xx.ravel(), yy.ravel()]]) == '是'
Z = Z.reshape(xx.shape)
plt.contourf(xx, yy, Z, cmap=cmap, alpha=0.3, antialiased=True)
plt.scatter(X[:, 0], X[:, 1], c=(y == '是'), cmap=cmap)
plt.xlabel('密度')
plt.ylabel('含糖率')
plt.show()

png

  • 10.6 试使用MATLAB中的PCA函数对Yale人脸数据集进行降维,并观察前20个特征向星所对应的图像。
from os import listdir
from os.path import isfile, join
from sklearn.decomposition import PCA
import matplotlib.pyplot as plt
import matplotlib.image as mpimg
import numpy as np

导入数据,进行PCA降维

# Read data
images = np.asarray([mpimg.imread(join('yalefaces/', file)) for file in listdir('yalefaces')])
shape = np.shape(images)
images = images.reshape([shape[0], -1])
# PCA
pca = PCA(n_components=20)
pca.fit_transform(images);

显示特征向量所对应的图像

for comp in pca.components_:
    plt.imshow(comp.reshape(shape[1:]), cmap='gray')
    plt.axis('off')
    plt.show()

png

第11章 特征选择与稀疏学习

  • 11.1 试编程实现Relief算法,并考察其在西瓜数据集3.0上的运行结果。

Relief算法的核心是相关统计量的计算:

对每个示例,Relief先在的同类样本中寻找其最近邻,,称为“猜中近邻”(near-hit),再从的异类样本中寻找其最近邻,称为“猜错近邻” (near-miss)。若属性j为离散型,则,否则为1;若属性j为连续型,则,注意已规范化到[0,1] 区间。

import pandas as pd
import numpy as np


def diff(a, b):
    if type(a) is str:
        return a != b
    if type(a) is float:
        return abs(a - b)
    if type(a) is np.ndarray:
        result = np.zeros([len(a)])
        for i in range(0, len(a)):
            result[i] = diff(a[i], b[i])
        return result
    raise ValueError("Unsupported type '%s'" % type(a))


def distance(a, b):
    d = 0
    for i in range(0, len(a)):
        d += diff(a[i], b[i]) ** 2
    return d


def relief(X, y):
    # Get tje number of attributes
    attr_count = len(X[0])
    # Get the number of samples
    sample_count = len(X)
    # Calculate distance in hit matrix and miss matrix
    hit_mat = np.zeros([sample_count, sample_count])
    miss_mat = np.zeros([sample_count, sample_count])
    for i in range(0, sample_count):
        miss_mat[i][i] = hit_mat[i][i] = np.inf
        for j in range(i+1, sample_count):
            if y[i] == y[j]:
                miss_mat[i][j] = miss_mat[j][i] = np.inf
                hit_mat[i][j] = hit_mat[j][i] = distance(X[i], X[j])
            else:
                hit_mat[i][j] = hit_mat[j][i] = np.inf
                miss_mat[i][j] = miss_mat[j][i] = distance(X[i], X[j])
    # Find nearest hit
    nearest_hit = np.argmin(hit_mat, axis=0)
    # Find nearest miss
    nearest_miss = np.argmin(miss_mat, axis=0)
    # Calculate correlation
    corr = np.zeros([attr_count])
    for i in range(0, attr_count):
        corr[i] = np.sum(-diff(X[nearest_hit, i], X[:, i])**2 + diff(X[nearest_miss, i], X[:, i])**2)
    return corr


data = pd.read_csv('data3.0.csv')
X = np.asarray(data[['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '密度', '含糖率']])
y = np.asarray(data['好瓜'])
print(relief(X, y))

运行结果为:

[-6.        4.       -2.        9.        7.       -4.       -0.121618
  0.340496]
  • 11.3 Relief算法是分别考察每个属性的重要性试设计一个能考虑每一对属性重要性的改进算法。

对于属性对(i,j)的相关统计量为:

其中,

  • 11.8 试给出求解范数最小化问题中的闭式解(11.14)的详细推导过程。

按照分量展开得到

不难发现,的各个分量互相独立,所以只需要求出每个分量最优值即可,将优化目标函数改写成分段函数的形式去掉绝对值,于是得到初中数学问题

在R上的最小值点是在R上的最小值点是。因此,当时,目标函数最小值点为;当时,目标函数最小值点为;当以上情况都不满足,那么根据二次函数的性质,目标函数的最小值点为0。

第12章 计算学习理论

  • 12.1 试证明Jensen不等式(12.4)。

证明的方法有很多种,其中最简单的证明方法是有限形式的证明。

  • 12.2 试证明引理12.1。

引理12.1由Hoeffding不等式推出

证明(12.15)

证明(12.16)

根据Hoeffding不等式的对称性

证明(12.17)

  • 12.3 试证明推论12.1。
  • 12.4 试证明:空间中线性超平面构成的假设空间的VC维是d+1。

证明这个结论需要线性代数的知识

首先证明

首先构造一个大小为d+1的数据集,考虑,那么这是一个大小的矩阵

显然,X是可逆矩阵,如果想要打散数据集,那么对于任意

都能找到对应的w满足,还可以让方程更加严格一点:,可以求出

然后证明

等价于证明,对于任意个样本,由于向量数目多于向量维度,那么样本构成的向量组必然是线性相关的

对于非零对应的,令,接下来要证明这种情况是不存在的:

如果,那么

因此,线性分类器无法实现上述分类,证明完毕。

  • 12.5 试计算决策树桩假设空间的VC维。

决策树桩可以视为线性分类器的一种特殊情况,决策树桩要求超平面必须和空间中的某个坐标垂直或者不做划分。

证明对于空间内的两个不同的样本,至少存在一个属性不相等。那么,决策树桩既可以不进行划分将它们标记为或者,也可以根据属性i进行划分将它们标记为或者

证明对于空间内的三个不同样本D,对于每一个属性i,三个样本的再属性i上顺序关系可以是或者,显然无法实现划分,所以不存在属性划分能够打散数目为3的样本集。

  • 12.6 试证明:决策树分类器的假设空间VC维可以为无穷大。

对于任意数量为m并且互不相同的样本,总是可以创建一棵决策树,使得每个叶节点对应一个样本,决策树可以给每个叶节点分配任意的分类,样本分类的结果可以有种,因此决策树分类器的假设空间VC维可以为无穷大。

  • 12.7 试证明:最近邻分类器的假设空间VC维为无穷大。

最近邻分类器的模型由训练集样本决定,我们可以通过构建训练样本来构建一个分类器。对于任意数量为m的样本集合D中的每一个样本,样本和最近的其他样本的距离为,在样本附近放置1个训练样本满足,按照算法,最近的训练样本的决定$x_i2^m$种,因此最近邻分类器的假设空间VC维为无穷大。

  • 12.8 试证明常数函数c的Rademacher复杂度为0。

对于常数函数,假设空间为

  • 12.9 给定函数空间,试证明Rademacher复杂度

按照定义上确界的性质

参考文献

  1. proof of Minkowski inequality
  2. Chebyshev Distance is Limit of P-Product Metric
  3. Proof that Yau-Hausdorff distance is a metric
  4. The supremum and infimum
  5. The VC Dimension
  6. Jensen’s inequality

相关资源

  1. K Means算法实现:k_means.py
  2. K Nearest算法实现:k_nearest.py
  3. 西瓜数据集3.0:data3.0.csv
  4. 西瓜数据集4.0:data4.0.csv