9.1 试证明 : $ p \geq1 $ 时，闵可夫斯基距离满足距离度量的四条基本性质； $ 0\leq p < 1 $ 时，闵可夫斯基距离不满足直递性，但满足非负性、同一性、对称性；P 趋向无穷大时，闵可夫斯基距离等于对应分量的最大绝对距离，即 $ \lim_{p \rightarrow +\infty}{(\sum_{u=1}^n\left| x_{iu} -x_{ju} \right|^p)^{\frac{1}{p}}}=\max_u\left| x_{iu}-x_{ju} \right| $.
答：
非负性、同一性、对称性很显然，关键是直递性了，关于直递性就是闵可夫斯基不等式的证明，具体参考：闵可夫斯基不等式。
9.2 同一样本空间中的集合 X 与 Z 之间的距离可通过"豪斯多夫距离" (Hausdorff distance)计算：$ dist_H(X,Z)=\max(dish_h(X,Z),dist_h(Z,X)) $ ,其中 $ dist_h(X,Z)=\max_{x\in X}\min_{z\in Z}\Vert x-z\Vert_2 $ .试证明:豪斯多夫距离满足距离度量的四条基本性质.
答：
- 非负：$ dist_h(X,Z)=\max_{x\in X}\min_{z\in Z}\Vert x-z\Vert_2\geq0 $ ，所以 $ dist_H(X,Z)\geq0 $ ；
- 同一性： 若 $ X\ne Z $ ，不失一般性，假设 $ x_i\ne z_i $ ，其他的样本都完全相同，那么对于 $ x_j,j=1, 2,..i-1, i,...,n $ 都有 $ z_j $ 使得 $ \min_{z\in Z}\Vert x_j-z\Vert_2=0 $ ，而对于 $ x_i $ ，由于没有相同的样本，所以 $ \min_{z\in Z}\Vert x_i-z\Vert_2>0\Rightarrow \max_{x\in X}\min_{z\in Z}\Vert x-z\Vert_2>0 $ 。原命题得证；
- 对称性：$ dist_H(X,Z)=\max(dish_h(X,Z),dist_h(Z,X))=\max(dist_h(Z,X)，dish_h(X,Z))=dist_H(Z,X) $
- 直递性：太难了。不会。
答：
不能，因为 k 均值本身是 NP 问题，且 9.24 是非凸的（具体证明不太懂.），容易陷入局部最优是 k 均值的一个缺点吧， 所以在使用 k 均值时常常多次随机初始化中心点，然后挑选结果最好的一个。
答：
代码在：9.4，暂时先不分析初始化点和结果了。
答：
- 连接性： 由于任意 $ x^{'} \in D $ 都由 $ x $ 密度可达，于是任意 $ x_i,x_j\in D $ 都可通过 $ x $ 密度相连；
- 最大性：$ x_i \in D\Rightarrow x_i $ 由 $ x $ 密度可达， $ x_j $ 由 $ x_i $ 密度可达 $ \Rightarrow x_j $ 由 $ x $ 密度可达 $ \Rightarrow x_j \in D $ 。
答：
个人理解，不一定正确。使用最小距离合并聚类簇时，最终聚类结果趋于不同类别之间的“空隙”会更大； 而最大距离约等于最小距离加上两个类别的离散程度，这里离散程度可理解为方差，方差越大，两个类别的最大距离越大， 所以使用最大距离时，会尽量使得类别的方差尽量小，最终聚类结果也趋于类内更集中。
其实类似于线性判别分析中类内方差尽量小，类间距离尽量大。
答：
- 原型聚类：输出线性分类边界的聚类算法显然都是凸聚类，这样的算法有：K均值，LVQ；而曲线分类边界的也显然是非凸聚类， 高斯混合聚类，在簇间方差不同时，其决策边界为弧线，所以高混合聚类为非凸聚类；
- 密度聚类：DBSCAN，如下图情况，显然当领域参数符合一定条件时，会生成两个簇，其中外簇会包括内簇，所以DBSCAN显然也是非凸聚类；
- 层次聚类：AGENS，这个暂时没想明白怎么分析。从书中给出的示例，是凸聚类。
答：
参考线性判别分析的优化目标：同类协方差尽量小，异类中心之间距离尽量大。
答：
样本 $ x_i,x_j $ 的距离为：$ d(x_i,x_j)=\frac{\sum_{n=1}^{N}\delta^n_{ij}d^n_{ij}}{\sum_{n=1}^{N}\delta^n_{ij}} $ ， 其中当 $ x_{in},x_{jn} $ 缺失时，$ \delta^n_{ij}=0 $ ，其他为1；
- 当前属性 $ n $ 为数值类型时， $ d^n_{ij} =\frac{\left| x_{in}-x_{jn} \right|}{\max(X)-\min(X)} $ ；
- 当属性 $ n $ 为类别型或二元型时，$ x_{in}=x_{jn} $ 时， $ d_{ij}^n=1 $ ，否则为 0 ；
- 当前属性 $ n $ 为序数型时，即 $ x_{in}\in[1, 2,...,M_n] $ ，先将其归一化， $ z_{in} = \frac {x_{in}-1}{M_n -1} $ ，然后将 $ z_{in} $ 作为数值属性来处理。
这里的计算其实很简单，就是把连续属性归一化；而离散属性有序时则归一化话再按照连续属性处理，无序时则相等为 1 ，不等为 0.
参考：《数据挖掘概念与技术》.韩家炜，2.4节.
答：
《X-meas: Extending K-means with Efficient Estimation of the Number of Clusters》给出了一个自动确定 k 值的方法，代码有时间再写.