0. 聚类步骤
为了完成一个聚类任务，必须遵循以下步骤：
- 特征选择：合适的选择特征，尽可能多的包含任务关心的信息，使得信息冗余减少和最小化是主要目标；
- 近邻测度：用于定量测量两个特征向量如何“相似”或“不相似”，这里需要注意让选中的特征都具有相同的近邻性，不能让某个或某些特征占支配地位；
- 聚类准则：依赖于专家的判断，可以通过代价函数或者其他规则表示；
- 聚类算法：用于揭示数据集的聚类结构；
- 结果验证：验证聚类算法结果的正确性，通常使用逼近检验；
- 结果判定：应用领域的专家用其他实验证据和分析判定聚类结果，最后做出正确结论。
很多情况下，还包含“聚类趋向”这一步骤，用于测试有效数据是否拥有聚类结构，比如数据集可能是完全随机的，那么试图聚类就没意义了。
1. 聚类的应用
在许多应用中，聚类是主要工具，四个基本方向：
- 减少数据：通过将数据分成几组可判别的聚类，并且每类当作独立实体来分析处理。例如，数据传输中，为每一个聚类定义一个描述符，然后传输相应于聚类描述符的编码号代替传输数据样本，从而压缩数据；
- 假说生成：推导出数据性质的一些假说，然后使用其他数据集验证这些假说；
- 假说检验：使用聚类分析来验证指定假说的有效性；
- 基于分组的预测：对现有数据集进行聚类分析，形成模式的特征，并用特征表示聚类，接下来，如果给出一个未知模式，则可以决定它最可能属于哪一类，并用相应聚类的特征表示。
2. 特征类型
特征的可能取值通常有离散的和连续的两种。如果特征取值是有限离散的，且只有2个元素，那么该特征被称为二值的或者二分的。特征的不同分类是基于相关有意义的值，如：
- 标称的：性别特征，男性为1，女性为0。对于这些值来说，任何定量比较都是无意义的，其只是一个类似于字典索引的数值；
- 顺序的：成绩特征，“优秀”，“很好”，“好”，“不好”对应4，3，2，1。对于这些值，顺序是有意义的，然而两个值之间的差值是无意义的。
- 区间尺度的：对于一个具体的特征，如果两个值之间的差异是有意义的，而比率是无意义的，那么它属于区间尺度的特征，如温度的测量。比如伦敦和巴黎的温度分别是5度和10度，说巴黎比伦敦高5度是有意义的，而巴黎温度比伦敦高2倍是无意义的；
- 比率尺度的：如果两个具体特征值之间的比率是有意义的，那么就是比率尺度的特征。比如重量，一个人重100kg比另一个50kg的人重两倍是有意义的。
特征分类排序为标称的、顺序的、区间尺度的以及比率尺度的，可以看出后面特征拥有它前面的所有属性。例如一个区间尺度的特征有标量的和顺序的特征的所有属性。
聚类的定义可以分成两种：
- 硬聚类：将数据集划分成完全分离的几个类别，其中两两类别之间无重叠样本，且每个类别都有样本。即一个样本有且只属于一个类别；
- 模糊聚类：通过引入一个membership函数，其值为当前样本属于当前类别的概率。也就是说，每个样本可以属于所有类别，只是程度问题，接近1表示该样本属于该类的程度高，反之相反。所以如果两个样本在同一个类别上的membership函数值都接近1，则可以认为这两个样本是相似的。因为(sum_{j=1}^mu_j(x_i)=1,i=1,2,...N)，即一个样本属于所有类的和为1，假如membership的输出值只能是0和1，那么可以认为这时候每个样本只能属于一个类别，且此时的membership函数可以称为characteristic函数。
3.近邻测度
测度，就是计算不同对象之间的相似性，主要分相似性测度和不相似性测度。
不相似性测度（dissimilarity measure，DM）：假设d是一个函数,基于数据集X,有：
其中(R)是实数集合，如：
(exists d_0in R:-infty<d_0leq d(x,y)< +infty,forall x,yin X quad(3.1))
(d(x,x)=d_0,forall xin Xquad(3.2))
且
(d(x,y)=d(y,x),forall x,y in X)
如果另外有
(d(x,y)=d_0,当且仅当x=y quad(3.4))
且
(d(x,z)leq d(x,y)+d(y,z),forall x,y,z in X quad(3.5))
则d被称为度量DM，式子3.5也称为三角不等式。当X中任意两个向量相等时，式子3.4表示得到这两个向量之间的最小可能的不相似值(d_0)
相似性测量（similarity measure，SM）：，定义函数：
(s:X imes X
ightarrow R)
其中：
(exists s_0in R:-infty<s(x,y)leq s_0<+infty,forall x,y in X)
(s(x,x)=s_0,forall xin X)
且
(s(x,y)=s(y,x),forall x,y,in X)
如果另外有
(s(x,y)=s_0,有且仅当x=y)
且
(s(x,y)s(y,z)leq[s(x,y)+s(y,z)]s(x,z),forall x,y,zin X)
则称s为度量SM
其中欧氏距离本身是一个不相似性测度，其又满足(3,4)和(3.5)，所以欧式距离也是一个不相似性度量。不过因为不是所有的聚类算法都是基于向量间的近邻测度，所以需要将测度算法进行扩展，比如训练集X子集之间的测度，设U是包括X子集的一个集合，即(D_isubset X，i=1,...k)且(U={D_1,...D_k}),则在U上的近邻测度是一个函数：
如上述不相似性测度和相似性测度，用(D_i,D_j)代替x和y，用U代替X。通常根据两个集合(D_i,D_j)中元素的近邻测度来定义两个集合之间的近邻测度。
直观的说，前面定义证明DM和SM是对立的，且，
- 如果d是度量DM，(d(x,y)>0,forall x,yin X)那么(s=a/d,a>0)是度量SM；(d_{max}-d)也是度量SM；
- 如果d是有限集上的DM，那么(-ln(d_{max}+k-d))和(kd/(1+)d)也是度量DM，其中k是任意正常数；
- 如果s是(s_0=1-sigma)的度量SM，其中(sigma)是小的正数，那么(1/(1-s))也是度量SM.
对于集合(D_i,D_j)之间的相似测度和不相似测度也成立。
3.1点与点之间
3.1.1 实向量
A. 不相似测度
加权(l_p)度量DM，即:
加权(l_2)度量DM进一步推广为:
其中(B)是正定对称矩阵，Mahalanobis距离是该公式的一个特例。
特定(l_p)度量DM是实际中遇到的加权(l_1)或Manhattan范数：
加权(l_infty)范数：
(l_1)和(l_infty)可以分别认为是对范数(l_2)的过高估计和过低估计，即(d_infty(x,y)leq d_2(x,y)leq d_1(x,y))。当(l=1)时，所有的(l_p)范数重合。
基于这些DM，定义的相应SM为(s_p(x,y)=b_{max}-d_p(x,y))
一些附加的DM如下：
其中(b_j,a_j)分别是数据集X上N个特征维度向量上第(j)个特征维度上的最大和最小值。容易证明(d_G(x,y))是度量DM，注意到这里的值不仅仅依赖于x和y，也依赖于整个数据集X,所以，如果样本x，y来自于数据集X，而数据集Y中也有相同的样本x，y，那么两边计算时不同的。另一个DM是：
B. 相似测度
实际应用中，最常用的实向量的相似性测度为：
内积：(s_{inner}(x,y)=x^Ty=sum_{i=1}^lx_iy_i),在大多数情况下，当样本x和y都被归一化了，可使用内积（他们的长度都相同）；相应的内积不相似性测度是(d_{inner}(x,y)=b_{max}-s_{inner}(x,y))
与内积最相关的是余弦相似测度：
这个测度是旋转不变的，不过不是线性变换
pearson相关系数：
其中(x_d=[x_1-overline{x},...,x_l-overline{x}]^T,y_d=[y_1-overline{y},...,y_l-overline{y}]^T)，其中(overline{x}=frac{1}{l}sum_{i=1}^lx_i,overline{y}=frac{1}{l}sum_{i=1}^ly_i)。通常称(x_d,y_d)为差分向量。显然(r_{pearson}(x,y))在-1和+1之间取值；相关的不相似性测度定义为：
取值范围是[0,1],这个测度用于分析遗传表达数据。
另一个通用的SM是Tanimoto测度，Tanimoto测度也被称为Tanimoto距离，其可用于实向量测量，也可以用于离散值向量测量，定义：
对分母中(x^Ty)项的加减等一些运算后：
也就是Tanimoto测度与“x和y之间的欧式距离平方除以x和y之间的内积”成反比。比例系数是它们的相关性，当X的向量都被归一化为相同长度时，方程：
这种情况下，(s_T)和(a^2/x^Ty)成反比，因此，x和y越相关，(s_T)的值越大。
另一个相似性测度也是有用的：
当(x=y)时，(s_c(x,y))取最大值1；当(x=-y)时，(s_c(x,y))取最小值0.
3.1.2 离散值向量
对于样本x，假设其特征维度为l，且每个维度上的取值属于有限集(F={0,1,...k-1}),其中k是正整数，则可以得知一共有(k^l)个样本，当l=2的时候，就是一个正常的以xoy坐标系中点取整数的网格。
考虑(x,yin F^l)，且令：
是一个(k imes k)矩阵，其中元素(a_{ij})是<第一个向量有i符号，第二个向量有j符号>的相应元素的数量，(i,jin F).这个矩阵被称为相依表，例如，如果l=6，k=3，且(x=[0,1,2,1,2,1]^T),(y=[1,0,2,1,0,1]^T)那么矩阵(A(x,y))等于
a_ij=sum([1 for xi,yi in zip(x,y) if xi==i and yi==j])
自己实现的一个较为快速的方法：
def contingency_table_vec(x,y,k=None):
'''
performance:
>>> timeit contingency_table_vec(np.arange(1000),np.arange(1000),1000)
1 loop, best of 3: 1.61 s per loop
>>> timeit contingency_table_vec(np.arange(2000),np.arange(2000),2000)
1 loop, best of 3: 9.99 s per loop
'''
assert k != None, 'k should not be None'
@numba.jit(nopython=True)
def _inner(x,i,y,j):
xBool = (x==i)
yBool = (y==j)
ans = (xBool &yBool).sum()
return ans
#return ((x==i)&(y==j)).sum() # the sentence maybe faster
@numba.jit(nopython=True,parallel=True)
def _contingency_table_vec(x,y,table,k=None):
for i in range(k):
for j in range(k):
table[i,j]=_inner(x,i,y,j)
return table
table = np.zeros([k,k])
table = _contingency_table_vec(x,y,table,k)
return table
容易验证$$sum_{i=0}^{k-1}sum_{j=0}^{k-1}a_{ij}=l$$,两个离散值向量之间的大多数近邻测度可以用矩阵(A(x,y))的元素组合表示。
A. 不相似测度
汉明（Hamming）距离：汉明距离被定义为两个向量不同位置的数量，使用矩阵A，可以定义汉明距离(d_H(x,y))为：
也就是A的非对角线的所有元素的总和，这表明x和y不同的位置。当k=2时，向量x时二值向量，且汉明距离变为：
这种情况下，(xin F_1^l),其中(F_1={-1,1})，x称为双极向量，汉明距离为：
相应的(d_H)相似性测度为(s_H(x,y)=b_{max}-d_H(x,y))
(l_1)距离：在连续值向量情况下，(l_1)距离定义为：
而在二值向量时，(l_1)的距离和汉明距离一致。
B. 相似测度
广泛应用于离散值向量的相似性测度是Tanimoto测度，来自集合的比较。假如X和Y是两个集合，且(n_X,n_Y,n_{Xcap Y})分别是X，Y，(Xcap Y)集合的势（元素的数量）。则两个集合X和Y之间的Tanimoto测度定义为：
即，两个集合之间的Tanimoto测度是相同元素数量与所有不同元素数量的比率（如目标检测领域中的IOU）
对于两个离散值向量x和y的Tanimoto测度，除了((x_i,y_i))都为0的坐标对，考虑所有x和y的坐标对。定义(n_x=sum_{i=1}^{k-1}sum_{j=0}^{k-1}a_{ij}),(n_y=sum_{i=0}^{k-1}sum_{j=1}^{k-1}a_{ij}),其中(a_{ij})是(A(x,y))矩阵的元素。(n_x)表示非零左边的数量，(n_y)也是。测度定义为：
一些函数只考虑两个向量相同，而且不为0的位置的数量的相似性函数：
- (frac{sum_{i=1}^{k-1}a_{ii}}{l})；(frac{sum_{i=1}^{k-1}a_{ii}}{l-a_{00}})
而另外一些函数考虑所有向量相同的位置的数量的相似性函数:
- (frac{sum_{i=0}^{k-1}a_{ii}}{l})
3.1.3 混合值向量
当样本特征值不全是实数或离散值时，则存在混合的情况，简单的处理方法就是采用实数向量的近邻测度。一个好的近邻测度方法就是(l_1)距离。或者使用其他方法将实值转化为离散值特征。如直方图的形式。
一种处理混合值向量的相似性函数，考虑两个l维混合值向量x,y,那么他俩之间的相似性函数定义为:
其中(s_i(x,y))是x和y的第i个坐标的相似度。且(w_i)对应于第i个坐标的加权系数。特别的，如果x，y的第i个坐标至少有一个未定义，则(w_i=0)。如果第i个坐标是二值变量，且它对所有向量都是0，则(w_i=0)，在所有其他情况下，(w_i=1)。最后，如果所有(w_i)都等于0，则(s(x,y))未定义。如果两个向量的第i个坐标是二值的，则：
如果两个向量的第i个坐标对应着标称或有序变量，并且(x_i,y_i)有同样的值，则(s_i(x,y)=1)，否则(s_i(x,y)=0).最后，如果第i个坐标对应于区间尺度或比率尺度变量，则：
其中(r_i)是第i个坐标值区间的长度，可以发现，对于区间或比率变量，当(x_i,y_i)一致时，(s_i(x,y))取最大值，另一方面，如果(x_i,y_i)之间的绝对差值等于(r_i)，那么(s_i(x,y)=0).对于(|x_i-y_i|)等于任何其他的情况，(s_i(x,y))位于[0,1]之间。
模糊测度
考虑两个实值向量x，y，其特征(x_i,y_i)属于区间[0,1]。这里与以前所述不同在于，(x_i)的值不是测度的输出，其与1越接近，则(x)拥有第i个特征的可能性越大，当值为0.5的时候，就无法分清楚到底有没有第i个特征了。并且假设这里(x_i)只能取值0和1。对于两个相等的二进制变量a和b，有
不过有趣的是：
- 两个二进制变量之间的and，or运算可以看成是最小，最大操作，而二进制a的not可以看成是1-a。这样在[0,1]区间的两个实值变量(x_i,y_i)的相似度可以定义为：
当l大于3时，也就是一个样本的特征空间(H_l)是一个超立方体，在这种情况下，样本x和(H_l)中心越接近，不确定的概率越大。而越接近顶点，不确定因素越小。基于上面的式子，在[0,1]中取值的两个变量之间的相似性，可以定义两个向量之间的相似性测度。样本x和y之间的通用相似性测度定义为：
容易验证(s_F)的最大值和最小值分别为(l^{1/q},0.5l^{1/q})。当(q
ightarrow +infty)时，(s_F(x,y)=max_{1leq ileq l}s(x_i,y_i));当(q=1)时，(s_F(x,y)=sum_{i=1}^ls(x_i,y_i))
通过计算可以发现，向量的相似度策略不但依赖于向量本身，也依赖于向量所处超立方体的位置，越接近中心，相似性越小；越接近顶点，相似性越大。
数据缺失
在实际中，很多时候一些特征向量的值是缺失的，这里简单的介绍下常用的方法：
- 如果当前特征向量特征丢失严重，或者丢失特征的向量个数相对特征向量总数很小时，可直接丢弃该特征向量；
- 计算该特征向量相对的平均值，用于代替缺失的特征；
- 对于样本x和y的所有元素对(x_i,y_i)，定义(b_i)为：
(b_i=0,当x_i,y_i都有效)；(b_i=1,其他情况)
然后样本x和y之间的近邻定义为：
其中(phi(x_i,y_i))表示两个标量之间的近邻性，(l)表示特征维度长度。当涉及到不相似性测度时，通常选择(phi(x_i,y_i)=|x_i-y_i|)。假设(d(x,y))的值区间为[a,b]。这样不管两个样本中有多少特征值是缺失的，这个定义都能保证x和y之间的近邻测度覆盖所有[a,b]
- 对于数据集X的特征维度上，计算每个维度的平均近邻，当计算不同样本之间的相似度时，如果两个元素之间有效，则按之前计算，如果无效，则用当前维度的平均近似代替，如：
(X={x_1,x_2,x_3,x_4,x_5}),其中(x_1=[0,0]^T),(x_2=[1,*]^T),(x_3=[0,*]^T),(x_4=[2,2]^T),(x_5=[3,1]^T).因为其中第二维有缺失值，且当且有三个值([0,2,1])，其平均值为(frac{|0-2|+|0-1|+|2-1|}{3}=4/3)，则(x_1,x_2)之间的距离为(d(x_1,x_2)=|0-1|+4/3=7/3)
3.2 点与集合之间
在许多聚类方法中，需要根据样本x与类别C之间的近邻性来将样本x归为类别C中。有两种通用方法定义(d(x,C))：
- 最大近邻函数：$$d_{max}^{ps}(x,C)=max_{yin C}d(x,y)$$
- 最小近邻函数：$$d_{min}^{ps}(x,C)=min_{yin C}d(x,y)$$
- 平均近邻函数：$$d_{avg}^{ps}(x,C)=frac{1}{n_C}sum_{yin C}d(x,y)$$
其中(n_C)是C的势。在上述的定义中，(d(x,y))可以是两点之间的任意近邻测度。
第二种方法，将C设置一个表达，C和x之间的近邻性用x和C的表达之间的近邻性测量：点表达适合致密聚类；超平面表达适合线性聚类；超球面适合超球面聚类。
点表达
选用平均向量作为表达点：$$m_p=frac{1}{n_C}sum_{yin C}y$$
当处理连续空间时，这是最常用的旋转，而处理离散空间时，这就不能很好的工作了，因为很有可能表达点在空间外面，这时候可以使用C的均值中心(m_c):$$sum_{yin C}d(m_c,y)leq sum_{yin C}d(z,y),forall zin C$$
其中(d)是两点之间的不相似性测度。当涉及到相似性测度时，不等式符号反过来；另一个常用的点表达是中值中心，通常在两点之间近邻测度不能度量时使用，中值中心(m_{med}in C)定义为：$$med(d(m_{med},y)|yin C)leq med(d(z,y)|yin C),forall zin C$$
其中d是两点之间的不相似性测度。med(T)是集合T的最小数量，最小数量大于等于([(q+1)/2])的T数量，其中T是q个标量的集合。确定med(T)的算法是将T中的元素按升序排序，并挑出其中的([(q+1)/2])个元素。
超平面表达
线性聚类，或一般情况下的超平面，经常在计算机视觉中遇到，这种类型的聚类是不能用单个点精确的表达的。在这座情况下，使用线作为聚类的表达。超平面H的一般方程为：
其中(x=[x_1,...x_l]^T),并且(a=[a_1,...a_l]^T)是H的权向量，点x与H的距离定义为：
在两点间的欧式距离中，使用简单的几何参数，得到：$$d(x,H)=frac{|a^Tx+a_0|}{||a||}$$
其中(||a||=sqrt{sum_{j=1}^la_j^2})
超球面表达
另一种类型的聚类是圆形（高维是超球面），在计算机视觉中经常遇到这样的类型，这样的聚类，理想的表达是圆（超球面）。超球面Q的一般方程为：$$(x-c)^T(x-c)=r^2$$
其中c是超球面的中心，r是超球面的半径，从点x到Q的距离定义为：
3.3 集合与集合之间
一些聚类算法是建立在两个不同集合之间的近邻测度的。如果(D_i,D_j)是两个样本集合，最通用的近邻函数是：
- 最大近邻函数：$$d_{max}^{ss}(D_i,D_j)=max_{xin D_i,yin D_j}d(x,y)$$
容易看出，如果(d(x,y))是不相似性测度，则(d_{max}^{ss})却不是测度，因为它不满足一些条件，(d_{max}^{ss})完全是由最不相似的向量对（x，y）决定的，另一方面，如果(d(x,y))是相似性测度，(d_{max}^{ss})是测度但不是度量。在这种情况下，(d_{max}^{ss})完全由最相似的向量对决定。- 最小近邻函数：$$d_{min}^{ss}(D_i,D_j)=min_{xin D_i,yin D_j}d(x,y)$$
当(d(x,y))是相似性测度时，(d_{min}^{ss})不是测度，在这种情况下，(d_{min}^{ss})完全由最不相似的向量对决定；另一方面如果(d(x,y))是不相似性测度，则(d_{min}^{ss})是测度但不是度量，这种情况下，(d_{min}^{ss})完全由最相似的向量对决定。- 平均近邻函数：$$d_{avg}^{ss}(D_i,D_j)=frac{1}{n_{D_i}n_{D_j}}sum_{xin D_i}sum_{yin D_j}d(x,y)$$
容易得知，即使(d(x,y))是测度，(d_{avg}^{ss})也不是测度，这种情况下，(D_i,D_j)的所有向量都参与(d_{avg}^{ss})的计算。- 中值近邻函数：$$d_{mean}^{ss}(D_i,D_j)=d(m_{d_i},m_{D_j})$$
其中(m_{D_i})可以是均值点，均值中心，或(D_i)的中值。很明显这个函数是基于(D_i,D_j)的表达之间的近邻函数，如果(d(x,y))是测度，则平均近邻函数也是测度。- 基于均值的近邻函数：$$d_e^{ss}(D_i,D_j)=sqrt{frac{n_{D_i}n_{D_j}}{n_{D_i}+n_{D_j}}}d(m_{D_i},m_{D_j})$$
可以看出，这也是基于点表达来进行集合的近邻测度