1.聚类

将相似的样本划分为一类，分析各类间的差异。

样本的属性有定性和定量两种：

如果变量只有数值型数据：可选用K-means，DBSCAN,分层聚类等。

如果变量只有分类型数据：可选用K-modes，Kmodes是Kmeans的一种变种算法，将原本Kmeans使用的欧式距离替换为字符间的汉明距离。

如果变量有数值和分类型混合的数据：可用K-prototype，度量具有混合属性的方法是：数值属性采用K-means方法得到P1，分类属性采用Kmodes方法得到P2，D=P1+a*P2,a是权重，如果分类属性重要增大a,否则减小a。

2.算法原理

2.1 K-means

对于数据集，给定一个分类数K，划分法将数据集划分为K个组，每一个分组就代表一个分类。

大部分划分方法是基于距离的，以K-means算法为例，其大致原理是：

1.首先确定分类的数量K

2. 从数据集中随机的选择K个样本点作为初始类中心（质心）

3. 计算数据集中每一个样本点与初始类中心的距离，离那一个类中心近就划分给那个类中

4.重新计算K个类的类中心（质心），新的质心是该组所有样本的各属性的平均值，即means

5.如果新的类中与旧的类中心的距离小于设定的阈值，可以认为我们进行的聚类达到预期的结果，算法终止。

6.如果新的类中心和旧中心的距离很大，继续迭代3~5步骤。

2.2 Kmodes算法

Kmodes算法原理与Kmeans原理一样，计算的距离的方法不同。Kmodes计算的是字符间的距离。

距离的计算：假设有两个点：A，B，A=（a1,a2,a3,...an）,B=(b1,b2,b3,...bn)

欧式距离： $d(A,B)=\sqrt{\sum_{i=1}^n (a_{i} -b_{i})^2 }$ (i=1,2,3,4..n)

汉明距离（也叫海明威距离）：通过比较两个向量每一位是否相同，若不同则汉明距离加1，这样得到汉明距离，向量相似度越高，得到的汉明距离越小。

余弦距离： $\cos \theta =\frac{\sum\nolimits_{1}^n (a_{i} \times b_{i} )}{\sqrt{\sum\nolimits_{1}^n}a_{i}^2 \times \sqrt{\sum\nolimits_{1}^nb_{i}^2 } }$ 两个向量间的余弦相似度。夹角越小，余弦值越接近1.

2.3 K-prototype算法

K-prototype算法提出了混合属性簇的原型，其原型就是数值属性原型用属性中所有属性取值的均值，分类属性原型是分类属性中取值频率最高的属性。合起来就是原型。

K-prototype的目标函数（损失函数）：

K-prototype聚类的准则就是使用一个合适的损失函数去度量数值型和分类型变量对原型的距离。假设X={X1,X2,....X3}为n个样本集合，Xi={X1,X2,...Xm}为样本i的m个属性。k为聚类个数。而这个损失函数可以定义为： $E=\sum\nolimits_{l=1}^k\sum\nolimits_{i=1}^ny_{il} d(X_{i},Q_{l} )$

其中 $Q_{l} =[q_{l1},q_{l2},...q_{lm}](一个样本有每个属性)$ ，它表示类别 l 的一个原型，也就是类别 l 的中心（质心）， $y_{il}$ 为切分矩阵Y的元素，其实就是在类别l中有么有这个样本，有则为1，没有为0。d是相似性度量，经常定义为平方欧式距离。 $E_{l} =\sum\nolimits_{i=1}^n y_{il} d(X_{i} ,Q_{l} )$ 为把X分为类别l的总损失。

当 $q_{lj} =\frac{1}{nl} \sum\nolimits_{i=1}^ny_{il}x_{ij} ,j=1,2,...m$ 时， $E_{l}$ 达到最小化，

其中 $n_{l} =\sum\nolimits_{i=1}^n y_{il}$ 为类别l中的样本个数。上面是对于数值型变量，当X中含有分类变量时，可以把相似度改为：

$d(X_{i} ,Q_{l})=\sum\nolimits_{i=1}^r(x_{ij}^r-q_{lj}^r)^2 +\gamma l\sum\nolimits_{j=1}^c\delta (x_{ij}^c ,q_{lj}^c)$ r,c分别为数值属性和分类属性的个数， $\gamma l$ 是类别l中分类属性的权重。

将d(Xi,Ql)带入El中： $E_{l} =\sum\nolimits_{i=1}^ny_{il} \sum\nolimits_{i=1}^r(x_{ij}^r-q_{lj}^r)^2 +\gamma l\sum\nolimits_{i=1}^ny_{il} \sum\nolimits_{j=1}^c\delta (x_{ij}^c ,q_{lj}^c) =E_{l}^r+E_{l}^c$ 这样 $E_{l}^r$ 就代表类别l的样本中所有数值属性的总损失， $E_{l}^c$ 代表所有分类属性的总损失。

根据变量属性选择聚类算法(K-means,Kmodes,K-prototype