lec2 中学习的是如何把一个多边形切割开来；而这节课学习的就是，如何把一堆点给包起来 就像你在地上撒了一把钉子，然后用一根橡皮筋把它们围起来，拉紧之后那个形状就是 “凸包”。 所以，构造凸包的这个过程，我们还是从暴力解法开始 朴素暴力解法 我们可以假定一个结论：将点集 S 中的所有点遍历一遍，然后将这些三角形中包住的点都删除；最后剩余的这些没有被包围的点，一定是凸包的顶点。(作为三角形顶点或位于三角形边上的点不被删除) 那么我们就可以 #算法步骤（CH1）： 遍历 SSS 中所有可能的三元组 (x,y,z)(x, y, z)(x,y,z)：一共...

# 聚类（Clustering) # 一、聚类的概念 聚类是一种 无监督学习方法 目标是：将相似的数据点分在同一个 “簇”（cluster）中 没有预先的标签，完全基于数据之间的 “相似性” 划分 # 二、聚类的用途 文档分组、客户画像、基因数据分析、股票走势分群等 聚类可以帮助我们发现数据中的 “自然结构” # 三、相似性度量方法 用于计算两个数据点之间的 “相似程度”（或 “距离”）： 距离类型 定义 说明 曼哈顿距离（L1） ( d(i,j) = ∑\sum∑ x_i - x_j ) 抗异常值 欧几里得距离（L2） ( d(i,j)...

# 聚类（Clustering) # 一、聚类的概念 聚类是一种 无监督学习方法 目标是：将相似的数据点分在同一个 “簇”（cluster）中 没有预先的标签，完全基于数据之间的 “相似性” 划分 # 二、聚类的用途 文档分组、客户画像、基因数据分析、股票走势分群等 聚类可以帮助我们发现数据中的 “自然结构” # 三、相似性度量方法 用于计算两个数据点之间的 “相似程度”（或 “距离”）： 距离类型 定义 说明 曼哈顿距离（L1） ( d(i,j) = ∑\sum∑ x_i - x_j ) 抗异常值 欧几里得距离（L2） ( d(i,j)...

# 聚类（Clustering) # 一、聚类的概念 聚类是一种 无监督学习方法 目标是：将相似的数据点分在同一个 “簇”（cluster）中 没有预先的标签，完全基于数据之间的 “相似性” 划分 # 二、聚类的用途 文档分组、客户画像、基因数据分析、股票走势分群等 聚类可以帮助我们发现数据中的 “自然结构” # 三、相似性度量方法 用于计算两个数据点之间的 “相似程度”（或 “距离”）： 距离类型 定义 说明 曼哈顿距离（L1） ( d(i,j) = ∑\sum∑ x_i - x_j ) 抗异常值 欧几里得距离（L2） ( d(i,j)...

# week1 不考？ # 2. week2 # 2.1 数据类型 Nominal 定类数据 只有数据类型，没有其他的 比如 ID number，性别 Ordinal 定序数据 在 Nominal 的基础上可以进行排序 例如辣度，电影评分等 Interval 定距数据 在 Ordinal 的基础上，可以对数据进行加减计算 例如温度，年份等， Ratio 定比数据 有了乘除的操作，有绝对 0 的定义 例如质量，长度等 # 2.2...

5.31 5270 lec2 5045 lec1 6.1 5270 lec 3 5310 期末 1 6.2 5270 lec 4 5045 lec 2 6.3 5270 lec 5 5310 期末 2 6.4 5045 lec2 5992 期末 2 6.5 5045 lec 3 5310 期末 3 6.6 5992 期末 3 5045 lec 4 6.7 5310 期末 4 5992 期末 4 6.8 5310 期末 5 5992 期末 5 6.9 5310 5992 最后一轮复习 6.12 5270 lec 6 5045

这一节我们讲的是对比轨迹的相似度 # 相似性度量 # Hausdorff 距离 hausdorff 距离是获取比如 P 和 Q 两个点集的最远的最近点，比如 P->Q，就是从 P 中选择随机一点 p，获取他到 Q 的最近距离，然后在所有 p 点中距离最大的点就是 P->Q 的 Hausdorff 距离。 而两个点集的 Hausdorff 距离就是 P->Q,Q->P 两者中的 max 值 Hausdorff 可以让我们知道两个点集的轨迹相似度，但是他并不能衡量顺序以及其他的，比如两个点集的点完全一样，但是顺序完全不同，Hausdorff...

# 数据结构知识 # 最小生成树 视频链接 他的作用即将一个带权连通无向图转换成一个树形结构，并且权值最低。 常用的算法有 Kruskal 算法和 Prim 算法 Prim 算法是从第一个点开始，然后每连通一条边，都将已经连通的点当作一个整体去找下一个链接当前整体的权值最小的边，去连接那个点。不能存在图。适用于点较少的图 Kruskal 算法是先把每个点都画出来，然后寻找权值最小的边相连，不能存在环 适用于边较少的图 # 英文单词对照 对角线： diagonal 角 corners 相邻的：adjacent 随机增量算法：Randomized Incremental Algorithm 转换...

# 为什么要用 因为如类似于最小生成树这样的问题，当量级上去了，时间复杂度也会以非常夸张的形式提升，所以有些时候，我们宁可牺牲一点选择近似的方式，但是时间复杂度会快非常多 # 两种近似方法 # 启发式 启发式方法在实际中很好用，比如用 AI、贪心、局部优化等等。但问题是 —— 你无法证明这个方法一定能给出好结果，有时候甚至什么都算不出来 # 近似算法 而我们要讲的，是有保证的近似算法。这些算法有一个好处 —— 无论多难的题，它至少不会比最好的答案差太多，比如最多差 2 倍。 但同时 如果我们只能证明他最多差 100 倍，那么这也就说明可能存在差 100...