聚类算法

聚类算法

好像就要求了KNN啊

距离度量

欧氏距离

d(x,y)=∑i(xi−yi)2d(x,y)=\sqrt{\sum_i(x_i-y_i)^2}

欧几里得度量 (EucIidean Metric) （也称欧氏距离）是一个通常采用的距离定又指在 m 维空间中两个点之间的真实距离，或者向量的自然长度（即该点到原点的距离）。在二维和三维空间中的欧氏距离就是两点之间的实际距离。

曼哈顿距离 (Manhattan distance)

d(x,y)=∑i∣xi−yi∣d(x,y)=\sum_i|x_i-y_i|

要从一个十字路囗开车想象你在城市道路里到另外一个十字路口骘驶距离是两点间的直线距离吗？显然不是除非你能穿越大楼。实际骘驶距离就是这个"曼哈顿距离”。而这也是曼哈顿距离名称的来源，曼哈顿距离也称为城市街区距离（ City Block distance)。

切比雪夫距离 (Chebyshev distance)

d(x,y)=maxi∣xi−yi∣d(x,y)=max_i|x_i-y_i|

二个点之间的距离定义是其各坐标数值差绝对值的最大值。国际象棋棋盘上二个位置间的切比雪夫距离是指王要从一个位置移至另一个位置需要走的步数。由于王可以往斜前或斜后方向移动一格，因此可以较有效率的到达目的的格子。上图是棋盘上所有位置距 f6位置的切比雪夫距离

闵可夫斯基距离（ Minkowski distance)

d(x,y)=(∑i∣xi−yi∣p)1pd(x,y)=(\sum_i|x_i-y_i|^p)^\frac{1}{p}

p 取 1 或 2 时的闵氏距离是最为常用的
P = 2 即为欧氏距离，P = 1 时则为曼哈顿距离
当 p 取无穷时的极限情况下，可以得到切比雪夫距离

汉明距离 (Hamming distance)

d(x,y)=1N∑i1xi≠xid(x,y)=\frac{1}{N}\sum_i1_{x_i\neq x_i}

汉明距离是使用在数据传输差错控制编码里面的，汉明距离是一个概念，它表示两个（相同长度）字对应位不同的数量，我们以表示两个字之间的汉明距离。对两个字符串进行异或运算，并统计结果为 1 的个数，那么这个数就是汉明距离。
image-20240104153121511

余弦相似度

假定A和 B 是两个n维向量，A是[A1,A2,…,An][A_1,A_2,\dots,A_n]，B是 [B1,B2,…,Bn][B_1,B_2,\dots,B_n] ，则A和B的夹角的余弦等于：

cos(θ)=A⋅B∥A∥∥B∥=∑i=1nAi×Bi∑i=1n(Ai)2×∑i=1n(Bi)2cos(\theta)=\frac{A·B}{\|A\|\|B\|}=\frac{\sum_{i=1}^{n}A_i\times B_i}{\sqrt{\sum_{i=1}^n(A_i)^2}\times \sqrt{\sum_{i=1}^n(B_i)^2}}

两个向量有相同的指向时，余弦相似度的值为 1 ；两个向量夹角为 90°90°时，余弦相似度的值为 0 ；两个向量指向完全相反的方向时，余弦相似度的值为-1 。

KNN算法

k 近邻法 (k-Nearest Neighbor,KNN) 是一种比较成熟也是最简单的机器学习算法，可用于基本的分类与回归方法。

如果一个样本在正空间中与 k 个实例最为相似（即特征空间中最邻近 )，那么这K个实例中大多数属于哪个类别，则该样本也属于这个类别。
分类问题：对新样本，据其 k 个最近邻的训练样本类别，采用“多数投票”原则进行预测
回归问题：对新样本，通常计算K个最近邻居的属性值的平均值作为预测值。

K近邻的三要素：K值选择、距离度量和决策规则

KNN的训练过程：

  1. 选择K值
    确定K的值（即最近邻居的数量）。K值的选择会影响算法的结果。常见的方法包括交叉验证来选择一个合适的K值。

  2. 距离度量

    选择一种方式来测量数据点之间的距离。常见的距离度量方法有欧氏距离、曼哈顿距离等

  3. 对新数据进行分类

    当有一个新的数据点需要分类时，算法会计算这个点与训练数据集中所有点的距离。然后选择距离这个新点最近的K个点。

  4. 投票和预测

    • 对于分类问题，算法会查看这K个点的类别，并进行投票，最多票的类别就是新数据点的预测类别。
    • 对于回归问题，算法通常会计算这K个点的平均值或中位数，并将其作为新数据点的预测值。

结束