聚类1——距离计算

文档中心

文章目录

1. 无监督学习
2. 聚类
3. 聚类任务
4. 性能度量
- 4.3 外部指标公式
- 4.4 内部指标公式
5. 距离计算
- 5.4 闵可夫斯基距离
- - 5.4.2 欧式距离
  - 5.4.3 曼哈顿距离/街区距离
  - 5.4.8 切比雪夫距离
- 5.5 标准化欧式距离
- 5.6 马氏距离
- 5.7 余弦距离
- 5.8 汉明距离
- 5.9 杰卡德相似系数与杰卡德距离
- 5.10 相关系数与相关距离

1. 无监督学习

1.1 无监督学习简介

- "英文："Unsupervised Learning- "概念："根据类别未知(没有被标记)的训练样本解决模式识别中的各种问题，称之为"无监督学习"。- "性质："1）在"无监督学习"中，训练样本的标记信息是"未知"的。2）或，训练样本没有标签。- "分类："1）确定型无监督学习代表：自编码、稀疏自编码、降噪自编码2）概率型无监督学习代表：限制玻尔兹曼机- "用途："希望通过"对无标记训练样本的学习"来揭示数据的内在性质及规律，为进一步的数据分析提供基础。- "联系实际："1）缺乏足够的先验知识，因此难以人工标注类别。2）进行人工类别标注的成本太高。我们希望，计算机：1）从庞大的样本集合中选出一些具有代表性的加以标注用于"分类器"的训练。2）先将所有样本自动分为不同的类别，再由"人类"对这些类别进行"标注"。3）在无类别信息情况下，寻找"好的特征"。- "典型例子："聚类

1.2 浅谈无监督与监督

1. "监督学习"- 白话描述：我给计算机猫和狗的图片，然后告诉计算机哪个是猫，哪个是狗。计算机带着"打好的标签"去学习。- 代表算法：决策树，朴素贝叶斯，SVM，k-临近算法2. "无监督学习"- 白话描述：我给计算机猫和狗的图片，但是不告诉计算机哪个是猫，哪个是狗。计算机带着"无标签"样本，自己从数据间不同特征，去学习。- 代表算法：K-Means, EM3. "半监督学习"- 白话描述：我给计算机猫和狗的图片，然后有的图片告诉计算机哪个是猫，哪个是狗，有的却不告诉。（对应现实中，数据标签丢失）。4. "强化学习"- 又叫"人工智能的机器学习"。计算机（智能体），循环（累积），让奖励最大（预期累积奖励最大化）。- 例子：AlphagGo5. "深度学习"- 通过神经网络来实现的，它以人工神经网络为架构，可以做自然语言处理、计算机视觉等。- 代表算法：卷积神经网络（CNN）,多层感知机（MLP）

2. 聚类

2.1 聚类算法的主要方法

- "主要方法："划分方法、层次方法

2.2 划分方法（划分聚类算法）

- "思想：""划分聚类算法"通过优化评价函数把数据集分割为K个部分，它需要K作为输入参数。- "典型的分割聚类算法："1）K-means算法2）K-medoids算法3）CLARANS算法

2.3 层次方法（分层聚类算法）

- "思想："层次聚类由不同层次的分割聚类组成，层次之间的分割具有嵌套的关系。- "典型的分层聚类算法："1）BIRCH算法2）DBSCAN算法3）CURE算法

3. 聚类任务

3.1 文字描述

- "描述："1）"聚类"试图将数据集中的样本划分为若干个"不相交"的子集。2）每个子集称为一个"簇" (cluster)（样本簇亦称为"类"）。3）每个簇可能对应于一些"潜在的概念(类别)"。- "例如："对于上面的样本簇，"人为"的可以命名。如"浅色瓜" "深色瓜"等。- "拓展："1）"聚类"虽属于"无监督学习"，但聚类任务中也可使用"有标记"训练样本（半监督）。2）但样本的类标记与聚类产生的簇有所不同。

3.2 数学描述

$已知：$
$假定样本集D = \{x_1, x_2, ..., x_m \}, m个样本$

$每个样本x_i = (x_{i1}, x_{i2}, ..., x_{in}), n个特征（n维特征向量）$

$聚类算法：$
$聚类算法将D划分为k个不相交的簇\{C_l | l = 1, 2, ..., k\}$

$\ \ \ \ \ \ \ \ \ \ 数学表达为：C_{i}\bigcap C_{i+1} = \emptyset且D = \bigcup_{l=1}^kC_l$

$结果：$
$\ \ \ \ \ \ \ \ \ \ 用\lambda_j = \{1, 2, ..., k\}表示样本x_j的簇标记，x_j\in C_{\lambda_j}$

$聚类的结果:可用包含m个元素的簇标记向量 λ=(λ_1;λ_2;... ;λ_m) 表示。$

3.3 实际用途

聚类在实际中的十大示例

- 聚类既能作为一个"单独过程"，用于找寻数据内在的分布结构，- 也可作为分类等其他学习任务的"前驱过程".

3.4 拓展

- 除了"聚类任务"，还有1）密度估计（density estimation）2）异常检测（anomaly detection）

4. 性能度量

4.1 介绍

- "别名/英文："有效性指标（validity index）- "作用："1）评估聚类结果的好坏。2）当明确了性能度量，可直接将其作为聚类过程的优化目标。- "聚类性能评估的指标："同一簇的样本尽可能彼此相似 不同簇的样本尽可能不同。即：1）"簇内相似度（intra-cluster similarity）" 要高2）"簇间相似度（inter-cluster similarity）" 要低

4.2 聚类性能度量

- "外部指标（external index）："将聚类结果与某个"参考模型" (reference model) 进行比较。- "内部指标（inrernal index）："直接考察聚类结果而不利用任何参考模型。

4.3 外部指标公式

$已知：$
$数据集D = \{x_1, x_2, ..., x_m\}$
$簇划分C = \{C_1, C_2, ..., C_k\}$
$参考模型的簇划分C^* = \{C^*_1, ..., C^*_s\}$
$\ \ \ \ \ \ \ \ \ \ 令\lambda表示C对应的簇标记向量$
$\ \ \ \ \ \ \ \ \ \ 令\lambda^*表示C^*对应的簇标记向量$

$定义：$
$a = |SS|, SS = \{(x_i, x_j) | λ_i=λ_j,λ^*_i=λ^*_j,i<j\}$

$\ \ \ \ \ \ \ \ \ \ b = |SD|, SD = \{(x_i, x_j) | λ_i=λ_j,λ^*_i\neqλ^*_j,i<j\}$

$\ \ \ \ \ \ \ \ \ \ c = |DS|, DS = \{(x_i, x_j) | λ_i\neqλ_j,λ^*_i=λ^*_j,i<j\}$

$\ \ \ \ \ \ \ \ \ \ d = |DD|, DD = \{(x_i, x_j) | λ_i\neqλ_j,λ^*_i\neqλ^*_j,i<j\}$

$解释 1 ：$
$\ \ \ \ \ \ \ \ \ \ 样本两两配对,每个样本对仅能出现在一个集合中$

$解释 2 ：$
$SS:样本对，在C和C^*中都隶属于相同簇$

$SD:样本对，在C中隶属于相同簇，但在C^*中隶属于不同簇$

$DS:样本对，在C中隶属于不同簇，但在C^*中隶属于相同簇$

$DD:样本对，在C和C^*中都隶属于不同簇$

$结论：$
$\ \ \ \ \ \ \ \ \ \ Jaccard系数：JC = \frac{a}{a+b+c}$

$\ \ \ \ \ \ \ \ \ \ FM指数：FMI =\sqrt{\frac{a}{a+b} *\frac{a}{a+c}}$

$\ \ \ \ \ \ \ \ \ \ Rand指数：RI = \frac{2(a+d)}{m(m-1)}$

$（三个都是 [0, 1] ，值越大，性能度量越大，越好）$

4.4 内部指标公式

$已知：$
$聚类结果的簇划分C = \{C_1,...,C_k\}$

$定义：$
$\ \ \ \ \ \ \ \ \ \ avg(C)=\frac{2}{|C|(|C|-1)}\sum_{1\leq i<j\leq |C|}dist(x_i,x_j)$

$\ \ \ \ \ \ \ \ \ \ diam(C)=max_{1\leq i<j\leq |C|}dist(x_i,x_j)$

$\ \ \ \ \ \ \ \ \ \ d_{min}(C_i,C_j)=min_{x_i\in C_i,x_j\in C_j}dist(x_i,x_j)$

$d_{cen}(C_i,C_j)=dist(u_i,u_j)$

$解释：$
$dist(x_i,x_j):\ \ 用于计算两个样本之间的距离$

$\ \ \ \ \ \ \ \ \ \ u:代表簇的中心点(u=\frac{1}{|C|}\sum_{1\leq i\leq |C|})$

$\ \ \ \ \ \ \ \ \ \ avg(C)对应于簇C内样本间的平均距离$

$\ \ \ \ \ \ \ \ \ \ diam(C)对应于簇C内样本间的最远距离$

$d_{min}(C_i,C_j)对应于簇C_i与C_j最近样本间的距离$

$d_{cen}(C_i,C_j)对应于簇C_i与C_j中心点的距离$

$结论：$
$\ \ \ \ \ \ \ \ \ \ DB指数：DBI=\frac{1}{k}\sum_{i=1}^kmax(\frac{avg(C_i)+avg(C_j)}{d_{cen(u_i,u_j)}}),i\neq j$

$\ \ \ \ \ \ \ \ \ \ Dunn指数：DI=min_{1\leq i\leq k}\{min(\frac{d_{min}(C_i,C_j)}{max_{1\leq l\leq k}diam(C_l)})\},i\neq j$

（DBI越小越好，DI越大越好）

5. 距离计算

5.1 距离度量

英文：
$\ \ \ \ \ \ \ \ \ \ {}$ distance measure

概念：
$\ \ \ \ \ \ \ \ \ \ {}$ 距离度量是数学中的法则，用在某些空间中测量沿曲线的距离和曲线间的角度，包含曲线所在空间的曲率的信息。（就是，能够作为度量的距离）

基本性质：
$\ \ \ \ \ \ \ \ \ \ 非负性：dist(x_i,x_j)\geq 0$

$同一性：dist(x_i,x_j)=0当且仅当x_i=x_j$

$对称性：dist(x_i,x_j)=dist(x_j,x_i)$

$\ \ \ \ \ \ \ \ \ \ 直递性(三角不等式)：dist(x_i,x_j)\leq dist(x_i,x_k)+dist(x_k,x_j)$

5.2 相似度度量

- "英文："similarity measure- "定义："1）相似性度量，即综合评定两个事物之间相近程度的一种度量。2）两个事物越接近，它们的相似性度量也就越大，3）而两个事物越疏远，它们的相似性度量也就越小。4）一般用距离，来代表相似度。- "性质："1）距离越大，相似度越小2）用于"相似度度量"的距离未必一定要满足"距离度量"的所有基本性质- "常用的相似性度量："1）相关系数（衡量变量之间的接近程度）2）相似系数（衡量样品之间接近程度）3）匹配系数（定性数据）4）一致度（定性数据）

5.3 非度量距离

英文：non-metric distance例如："人"和"马"分别与"人马"相似，但"人"和"马"很不相似。可以说明："人"、"马"与"人马"之间的距离都比较小 但"人"与"马"之间的距离很大。结论：以上就是非度量距离

5.4 闵可夫斯基距离

5.4.1 闵可夫斯基距离公式

$英文：$
$\ \ \ \ \ \ \ \ \ \ {}$ Minkowski Distance

$公式：$
$\ \ \ \ \ \ \ \ \ \ dist_{mk}(x_i,x_j)=(\sum_{u=1}^n|x_{iu}-x_{ju}|^p)^\frac{1}{p}$

$定义：$
$x_i=(x_{i1};x_{i2};...;x_{in})$
$x_j=(x_{j1};x_{j2};...;x_{jn})$

$易证：$
$\ \ \ \ \ \ \ \ \ \ 有绝对值，满足距离度量的非负性$
$\ \ \ \ \ \ \ \ \ \ 有绝对值，减数与被减数可以交换，满足同一行$
$\ \ \ \ \ \ \ \ \ \ 同理，有第二条，满足对称性$
$\ \ \ \ \ \ \ \ \ \ 当p\geq1时，满足直递性$
$\ \ \ \ \ \ \ \ \ \ 当0\leq p<1时，不满足直递性，其余三性满足$

$求证 1 : p 趋向无穷大时，闵可夫斯基距离等于对应分量的最大绝对距离：$
$（即，\lim_{p\to +\infty} (\sum_{u=1}^n|x_{iu}-x_{ju}|^p)^\frac{1}{p}=max_u|x_{iu}-x_{ju}|）$
$证明：$
$假设，a=max_u|x_{iu}-x_{ju}|，当p趋向无穷大时成立$

$\ \ \ \ \ \ \ \ \ \ \ 得，lim_{p\to +\infty} (\sum_{u=1}^n|x_{iu}-x_{ju}|^p)^\frac{1}{p}\geq\lim_{p\to +\infty}(a^p)^\frac{1}{p}=a$

$\ \ \ \ \ \ \ \ \ \ \ 又因为，lim_{p\to +\infty} (\sum_{u=1}^n|x_{iu}-x_{ju}|^p)^\frac{1}{p}\leq\lim_{p\to +\infty}(na^p)^\frac{1}{p}=a$

$\ \ \ \ \ \ \ \ \ \ \ 所以，\lim_{p\to +\infty} (\sum_{u=1}^n|x_{iu}-x_{ju}|^p)^\frac{1}{p}=max_u|x_{iu}-x_{ju}|$

$\ \ \ \ \ \ \ \ \ \ \ （同理，p\to -\infty时，同样满足）$

$求证2:闵可夫斯基距离（p\geq 1）满足直递性：$
$(即，dist_{mk}(x_i,x_j)\leq dist_{mk}(x_i,x_k)+dist_{mk}(x_k,x_j))$
$证明 :$
$\ \ \ \ \ \ \ \ \ \ 已知，p\geq1$

$\ \ \ \ \ \ \ \ \ \ 已知，\lim_{p\to +\infty} (\sum_{u=1}^n|x_{iu}-x_{ju}|^p)^\frac{1}{p}=max_u|x_{iu}-x_{ju}|$

$\ \ \ \ \ \ \ \ \ \ 所以，不等式两边取极值:$

$\ \ \ \ \ \ \ \ \ \ 得，$

$dist_{mk}(x_i,x_j)=max_{u1}|x_{iu1}-x_{ju1}|$

$dist_{mk}(x_i,x_k)+dist_{mk}(x_k,x_j))=max_{u2}|x_{iu2}-x_{ku2}|+max_{u3}|x_{ku3}-x_{ju3}|$

$令u_1=n,u_2=u_3=u$

$\ \ \ \ \ \ \ \ \ \ 得，$

$dist_{mk}(x_i,x_j)=|x_{in}-x_{jn}|$

$dist_{mk}(x_i,x_k)+dist_{mk}(x_k,x_j))=|x_{iu}-x_{ku}|+|x_{ju}-x_{ku}|$

$x_{in}-x_{jn}|=|(x_{in}-x_{ku})-(x_{jn}-x_{ku})|$

$令|x_{iu}-x_{ku}|=a,|x_{ju}-x_{ku}|=b。a,b都为正$

$\ \ \ \ \ \ \ \ \ \ |a-b|与a+b$

$\ \ \ \ \ \ \ \ \ \ 最终：dist_{mk}(x_i,x_j)\leq dist_{mk}(x_i,x_k)+dist_{mk}(x_k,x_j))$

5.4.2 欧式距离

$英文：$
$\ \ \ \ \ \ \ \ \ \ {}$ Euclidean distance

$定义：$
$\ \ \ \ \ \ \ \ \ \ p=2，闵可夫斯基距离即欧氏距离$

$公式：$
$\ \ \ \ \ \ \ \ \ \ dist_{ed}(x_i,x_j)=||x_i-x_j||_2=\sqrt{\sum_{u=1}^n(x_{iu}-x_{ju})^2}$

$a(x_1,y_1)与b(x_2,y_2)之间的欧式距离：$
$\ \ \ \ \ \ \ \ \ \ dist_{ed}(a,b)=||a-b||_2=\sqrt{{(x_1-x_2)^2}+(y_1-y_2)^2}$

5.4.3 曼哈顿距离/街区距离

$英文：$
$\ \ \ \ \ \ \ \ \ \ {}$ Manhattan distance/city block distance

$定义：$
$\ \ \ \ \ \ \ \ \ \ p=1，闵可夫斯基距离即曼哈顿距离$

$公式：$
$\ \ \ \ \ \ \ \ \ \ dist_{man}(x_i,x_j)=||x_i-x_j||_1=\sum_{u=1}^n|x_{iu}-x_{ju}|$

$a(x_1,y_1)与b(x_2,y_2)之间的曼哈顿距离：$
$dist_{man}(a,b)=||a-b||_1=|x_1-x_2|+|y_1-y_2|$

5.4.4 闵可夫斯基距离可用于有序属性

1. "连续属性/数值属性"与"离散属性/列名属性"- 前者在定义域上有无穷多个可能的取值- 后者在定义域上是有限个取值2. "有序属性（ordinal attribute）"与"无序属性（nonordinal attribute）"- 能直接在属性值上计算距离,，这样的属性称为"有序属性"- 不能直接在属性值上计算距离，称为"无序属性" 3. "闵可夫斯基距离可用于有序属性"

5.4.5 对无序属性采用VDM

$英文：$
$\ \ \ \ \ \ \ \ \ \ {}$ Value Difference Metric

$定义：$
$m_{u,a}:表示属性u上取值为a的样本数$

$m_{u,a,i}:表示在第i个样本簇中在属性u上取值为a的样本数$

$\ \ \ \ \ \ \ \ \ \ k:样本簇数$

$\ \ \ \ \ \ \ \ \ \ 则，（无序）属性u上两个离散值a与b之间的VDM距离为：$

$公式：$
$\ \ \ \ \ \ \ \ \ \ VDM_p(a,b)=\sum_{i=1}^k|\frac{m_{u,a,i}}{m_{u,a}}-\frac{m_{u,b,i}}{m_{u,b}}|^p$

5.4.6 将闵可夫斯基距离和 VDM 结合即可处理混合属性

$定义：$
$假定有n_c个有序属性$
$则有n-n_c个无序属性$
$\ \ \ \ \ \ \ \ \ \ 不失一般性，令有序属性排列在无序属性之前$

$公式：$
$\ \ \ \ \ \ \ \ \ \ MinkovDM_p(x_i,x_j)=(\sum_{u=1}^{n_c}|x_{iu}-x_{ju}|^p+\sum_{u=n_c+1}^nVDM(x_{iu},x_{ju}))^\frac{1}{p}$

5.4.7 加权距离

$英文：$
$\ \ \ \ \ \ \ \ \ \ {}$ weighted distance

$意义：$
$\ \ \ \ \ \ \ \ \ \ 当样本空间中不属性的重要性不同时，可使用" 加权距离"$

$例子 :$
$\ \ \ \ \ \ \ \ \ \ 加权闵可夫斯基距离：dist_{wmk}(x_i,x_j)=(w1*|x_{i1}-x_{j1}|^p+...+w_n*|x_{in}-x_{jn}|^p)^\frac{1}{p}$

$注意：$
$\ \ \ \ \ \ \ \ \ \ 1） w_i\geq0(i=1,2,...,n)表征不同属性的重要性$

$\ \ \ \ \ \ \ \ \ \ 2）一般\sum_{i=1}^nw_i=1$

5.4.8 切比雪夫距离

$英文：$
$\ \ \ \ \ \ \ \ \ \ {}$ Chebyshev Distance

$定义：$
$\ \ \ \ \ \ \ \ \ \ p=\infin，闵可夫斯基距离即切比雪夫距离$

$公式：$
$\ \ \ \ \ \ \ \ \ \ dist_{cd}(x_i,x_j)=\lim_{p\to \infty}(\sum_{u=1}^n|x_{iu}-x_{ju}|^p)^{\frac{1}{p}}$

$由上面的求证 1 ：$
$dist_{cd}(x_i,x_j)=max(|x_{iu}-x_{ju}|)$

$a(x_1,y_1)与b(x_2,y_2)之间的切比雪夫距离：$
$dist_{cd}(x_i,x_j)=max(|x_1-x_2|,|y_1-y_2|)$

5.5 标准化欧式距离

概念

- "英文："Standardized Euclidean Distance- "特点："1）针对欧式距离的缺点————数据的单位可能不一样。例如：x1(5kg,10cm),x2(5kg,15cm)2）欧式距离等高线是圆，而标准化欧式距离等高线是椭圆。3）标准化后，数据的单位就是统一的（单位：标准差或均方差）。- "标准化公式："标准化后的值=（标准化前的值-分量的均值）/分量的标准差(也叫均方差)注：1. 均方差 = 标准差2. 标准差^2 = 方差3. 如何计算标准差？例如：2，3，4，5，6，81）计算平均值：(2 + 3 + 4 + 5+ 6 + 8)/6 = 30 /6 = 52）计算方差：(2 – 5)^2 = (-3)^2= 9(3 – 5)^2 = (-2)^2= 4(4 – 5)^2 = (-1)^2= 0(5 – 5)^2 = 0^2= 0(6 – 5)^2 = 1^2= 1(8 – 5)^2 = 3^2= 93）计算平均方差：(9 + 4 + 0 + 0+ 1 + 9)/6 = 24/6 = 44）计算标准差：√4 = 2

公式
$dist_{sed}(x_i,x_j)=\sqrt{\sum_{u=1}^n(\frac{x_{iu}-x_{ju}}{\sigma_u})^2}$
代码示例

from scipy.spatial import distanceimport numpy as np# 标准差sigma = np.array([[2,1],[1,2]])q = [0, 0]x_1 = [175, 60]x_2 = [165, 65]# Calculate standardized Euclidean distancesd_1 = distance.seuclidean(q, x_1, np.diag(sigma))d_2 = distance.seuclidean(q, x_2, np.diag(sigma))print(d_1)print(d_2)

130.8147545195113125.39936203984453

5.6 马氏距离

概念

- "别名："马哈距离- "英文："Mahalanobis Distance- "特点："1）基于统计的距离2）把标准差换为：协方差矩阵的逆矩阵3）协方差矩阵：多维随机变量的协方差矩阵

公式

$dist_{maha}(x_i,x_j)=\sqrt{\sum_{u=1}^n(\frac{x_{iu}-x_{ju}}{\sum^{-1}})^2}$

例子

比如，有两个样本，每个样本两个特征值（二维）（可以看成：身高，体重）x_1 = [175, 60]x_2 = [165, 65]设协方差矩阵为：SIGMA = [[2, 1], [1, 2]]取逆：（二阶：行列式取倒*[主对调，副取反]）inv(SIGMA) = 1/3*[[2, -1], [-1, 2]]d_1 = sqrt([175, 60]*inv(SIGMA)*inv([175, 60])) = 125.76432986608987d_1 = sqrt([165, 65]*inv(SIGMA)*inv([165, 65])) = 117.54431788336971

代码

from scipy.spatial import distanceimport numpy as npfrom numpy.linalg import inv # 求逆矩阵#逆协方差矩阵SIGMA = np.array([[2,1],[1,2]])q = [0, 0]x_1 = [175, 60]x_2 = [165, 65]# mahalanobisd_1 = distance.mahalanobis(q, x_1, inv(SIGMA))d_2 = distance.mahalanobis(q, x_2, inv(SIGMA))print(d_1)print(d_2)

125.76432986608987117.54431788336971

5.7 余弦距离

概念

- "英文："Cosine Distance- "定义："⽤向量空间中两个向量夹⾓的余弦值作为衡量两个个体间差异的⼤⼩的度量。- "特点："1）余弦距离不是距离，只是相似性(余弦相似度)。2）总体来说，欧⽒距离体现数值上的绝对差异，⽽余弦距离体现⽅向上的相对差异。3）取值范围[-1,1]。越趋于1（夹角越趋于0）代表越相似，趋于-1相反。- "余弦相似度公式："cos(x_1,x_2) = （两个向量的内积）/（x_1向量的内积*x_2向量的内积）注：向量内积：比如：x(1,2,3), y(2,3,4)向量x与向量y的内积为：1*2+2*3+3*4 = 20

公式

两个变量形式：
在这里插入图片描述
n维代数形式:

$cos(x_i,x_j)=\frac{\sum_{u=1}^nx_{iu}*x_{ju}}{\sqrt{\sum_{u=1}^n(x_{iu})^2}*\sqrt{\sum_{u=1}^n(x_{ju})^2}}$

向量形式：

$cos(X,Y)=\frac{X\times Y}{\sqrt{X \times X}*\sqrt{Y \times Y}}$

例子

"文本相似度"第一步，分词句子A：这只/皮靴/号码/大了。那只/号码/合适。句子B：这只/皮靴/号码/不/小，那只/更/合适。第二步，列出所有的词这只，皮靴，号码，大了。那只，合适，不，小，很第三步，计算词频句子A：这只1，皮靴1，号码2，大了1。那只1，合适1，不0，小0，更0句子B：这只1，皮靴1，号码1，大了0。那只1，合适1，不1，小1，更1第四步，写出词频向量句子A：(1，1，2，1，1，1，0，0，0)句子B：(1，1，1，0，1，1，1，1，1)第五步：余弦相似度（余弦距离）cos(A,B) = (1+1+2+1+1)/(sqrt(1+1+4+1+1+1)*sqrt(1+1+1+1+1+1+1+1)) = 6/3*sqrt(8)) = 0.707

5.8 汉明距离

概念

- "由来："1）汉明距离是以理查德·卫斯里·汉明的名字命名的。2）汉明距离是使用在数据传输差错控制编码里面的。- "定义："1）它表示两个（相同长度）字符串对应位置的不同字符的数量2）换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。- "举例："1011101 与 1001001 之间的汉明距离是 2。2143896 与 2233796 之间的汉明距离是 3。"toned" 与 "roses" 之间的汉明距离是 3。

公式

$dist_{ham}(x,y) = \sum x_i\bigoplus y_i$

最小汉明距离

1. 在一个码组集合中，任意两个编码之间汉明距离的最小值称为这个码组的最小汉明距离。2. 最小汉明距离越大，码组越具有抗干扰能力。

最小汉明距离——具体分析

代码

def hammingDistance(s1, s2):    if len(s1) != len(s2): raise ValueError("unequal length")    return sum(el1 != el2 for el1,el2 in zip(s1,s2))if __name__ == '__main__':    d = hammingDistance("110110110110","110111111110")    print(d)

运行结果：2

5.9 杰卡德相似系数与杰卡德距离

概念

- "英文："Jaccard similarity coefficient- "定义："1）两个集合A和B交集元素的个数在A、B并集所占的比例。2）比值，称为两个集合的杰卡德系数。- "特点："1）jaccard 值越大说明相似度度越高。

回顾

"外部指标公式："上面我写的性能度量的外部指标公式，有jaccard系数

杰卡德相似系数公式

$∣J(A,B)=\frac{|A\bigcap B|}{|A\bigcup B|}$

杰卡德距离

$J_{\sigma}(A,B)=1-J(A,B)$

5.10 相关系数与相关距离

相关系数

- "特点："1）相关系数是衡量两个特征列之间相关程度的一种方法，取值范围[-1,1]2）相关系数的绝对值越大，表明特征列X和Y的相关程度越高。3）当取值为1时表明正线性相关，-1时表明负线性相关。

相关系数公式

$\rho_{XY}=\frac{Cov(X,Y)}{\sqrt{D(X)}*\sqrt{D(Y)}}$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\frac{E((X-EX)(Y-EY))}{\sqrt{D(X)}*\sqrt{D(Y)}}$

$E(x)=\frac{1}{n}\sum_{i=1}^nx_i$
$D(x)=\frac{1}{n}\sum_{i=1}^n(x_i-E(x))^2$
$Cov(x,y)=\frac{1}{n}\sum_{i=1}^n(x_i-E(x))(y_i-E(y))$
$C o v (X, Y) = E (X Y) - E (X) E (Y)$
Cov是协方差

相关距离公式

$YD_{XY}=1-\rho_{XY}$

例子

X = (1.1, 1.9. 3) Y = (5.0, 10.4, 14.6)E(X) = (1.1+1.9+3)/3 = 2E(Y) = (5.0+10.4+14.6)/3 = 10E(XY) = (1.1*5.0+1.9*10.4+3*14.6)/3 = 23.02D(X) = (1/3)[(1.1-2)^2+(1.9-2)^2+(3-2)^2] = 0.607D(Y) = (1/3)[(5.0-10)^2+(10.4-10)^2+(14.6-10)^2] = 15.44Cov(X,Y) = E(XY) - E(X)E(Y) = 3.02相关系数 = 3.02/9.37 = 0.322相关距离 = 1 - 0.322 = 0.678

聚类1——距离计算

文章目录

1. 无监督学习

2. 聚类

3. 聚类任务

4. 性能度量

4.3 外部指标公式

4.4 内部指标公式

5. 距离计算

5.4 闵可夫斯基距离

5.4.2 欧式距离

5.4.3 曼哈顿距离/街区距离

5.4.8 切比雪夫距离

5.5 标准化欧式距离

5.6 马氏距离

5.7 余弦距离

5.8 汉明距离

5.9 杰卡德相似系数与杰卡德距离

5.10 相关系数与相关距离

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

标签

聚类1——距离计算

文章目录

1. 无监督学习

2. 聚类

3. 聚类任务

4. 性能度量

4.3 外部指标公式

4.4 内部指标公式

5. 距离计算

5.4 闵可夫斯基距离

5.4.2 欧式距离

5.4.3 曼哈顿距离/街区距离

5.4.8 切比雪夫距离

5.5 标准化欧式距离

5.6 马氏距离

5.7 余弦距离

5.8 汉明距离

5.9 杰卡德相似系数与杰卡德距离

5.10 相关系数与相关距离

相关问题

公告

DeepSeek全套部署资料免费下载

免费可商用字体批量下载

标签