# 聚类（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...

这一节我们讲的是对比轨迹的相似度 # 相似性度量 # 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...

# 📌 数学推导目标 我们希望算出： 对一个固定的查询点 qqq，在所有 n!n!n! 条线段插入顺序下，它的查询路径（走 DAG 的节点数）平均是多少？ # 🧱 定义记号 XiX_iXi​：第 iii 条线段插入时，是否导致查询路径中新增了一个节点。 是：Xi=1X_i = 1Xi​=1，否：Xi=0X_i = 0Xi​=0 那么 ∑i=1nXi\sum_{i=1}^n X_i∑i=1n​Xi​ 表示：最终查询路径长度 我们关心的是期望值：E[∑Xi]\mathbb{E}\left[\sum X_i\right]E[∑Xi​] # 🎯...

# 1. 平面点定位问题 首先代入日常生活，就如同我们使用地图软件一般，我们点击某个点的时候，我们需要快速判断出我们点的是哪个区间的点。 自然而然的可以想到的就是暴力法，即每次搜索点的时候都通过线性扫描扫描所有的点，但是这样的效率太低了，每次都需要 O (n) 的时间复杂度，所以接下来我们考虑别的方式 # 1.1 垂直切分法（Vertical Slab Decomposition） 如图所示，我们可以按照每个点所在的 y 轴进行切分，然后根据二分查找，第一次找出点所在的 slab。 然后，找出在哪个 slab...

# 🎯 1. 背景与目标 # 📌 应用场景 轨迹数据广泛存在于以下应用中： GPS 路径（车辆、手机用户行驶轨迹） 雷达 / 卫星跟踪（如台风移动路径） 动物迁徙轨迹（如候鸟、鲸鱼） 运动轨迹数据（如跑步者、球员移动） 这些轨迹数据常常由很多点组成，呈折线状。 # 🧠 分析目标： 从这些轨迹中提取有意义的行为模式，例如： 找出聚集区域（多个个体集中活动）； 分析路径形状（如迁徙路线）； 进行预测分析（如风暴路径预测）。 # ❓ 要解决的两个核心问题 相似性问题： 给定两条轨迹，如何判断它们的相似程度？ 哪些方法能更准确刻画...