聚类
将数据组织成多个类以确保：
- 高的类内相似度
- 低的类间相似度
硬聚类与软聚类
硬聚类
每个对象必定属于一个类别。
硬聚类更为常见，且更为容易实施
软聚类
一个对象可以属于多个类别
距离度量
定义
给定对象O1和O2，其距离为一个实数，记为D(O1, O2)
性质
对称性：$D(A,B)=D(B,A)$
自相似为0：$D(A,A)=0$
重叠：$D(A,B)=0 \Leftrightarrow A=B$
三角不等式：$D(A,B)\le D(A,C)+D(B,C)$
常用方式
对于向量，一般采取余弦距离。
\[cos(x,y)=\frac{x\cdot y}{\mid x\mid \cdot \mid y\mid}\]对于集合，一般采取杰卡德距离。
\[Jaccard(A,B)=\frac{A\bigcap B}{A\bigcup B}\]对于点，一般采取欧拉距离
\[\sqrt{\sum_{i=1}^n(X_i^{(a)}-X_i^{(b)})^2}\]常用聚类算法
划分方法
将有n个数据的数据集划分为K个类别。
K-means
每个簇根据其质心来标识，即
\[\vec{\mu} (c)=\frac{1}{\mid c\mid}\sum_{\vec{x}\in c}\vec{x}\]算法过程：
- 初始选定k个点作为簇的质心
- 对每个点，分配到离质心最近的簇。
- 在所有点被分配后，对每个簇调整质心
- 调整质心后，重新对每个点分配位置
重复2和3直到收敛。
k的选择：尝试不同的k，观察k上升时到质心平均距离的变化。当到达合适的k时，平均距离下降骤减。
优点：
- 效率高，复杂度为$O(tkn)$，t为迭代次数。一般情况下，t、k远小于n
- 容易形成可接受的局部最优
缺点：
- 中心距离需要可计算
- 需要提前设定K
- 对异常值和离群点敏感
- 不适合发现非凸形状的簇