聚类算法和分类算法

常用的分类算法包括：
决策树分类法
朴素的贝叶斯分类算法(native Bayesian classifier)
基于支持向量机(SVM)的分类器
神经网络法
k-最近邻法(k-nearest neighbor，kNN)
模糊分类法

下文出处
常见的聚类算法包括：
①基于划分的聚类算法
k-means： 是一种典型的划分聚类算法，它用一个聚类的中心来代表一个簇，即在迭代过程中选择的聚点不一定是聚类中的一个点，该算法只能处理数值型数据
k-modes： K-Means算法的扩展，采用简单匹配方法来度量分类型数据的相似度
k-prototypes： 结合了K-Means和K-Modes两种算法，能够处理混合型数据
k-medoids： 在迭代过程中选择簇中的某点作为聚点，PAM是典型的k-medoids算法
CLARA： CLARA算法在PAM的基础上采用了抽样技术，能够处理大规模数据
CLARANS： CLARANS算法融合了PAM和CLARA两者的优点，是第一个用于空间数据库的聚类算法
Focused CLARAN： 采用了空间索引技术提高了CLARANS算法的效率
PCM： 模糊集合理论引入聚类分析中并提出了PCM模糊聚类算法

②基于层次聚类算法：
CURE： 采用抽样技术先对数据集D随机抽取样本，再采用分区技术对样本进行分区，然后对每个分区局部聚类，最后对局部聚类进行全局聚类
ROCK： 也采用了随机抽样技术，该算法在计算两个对象的相似度时，同时考虑了周围对象的影响
CHEMALOEN（变色龙算法）： 首先由数据集构造成一个K-最近邻图Gk ,再通过一个图的划分算法将图Gk 划分成大量的子图,每个子图代表一个初始子簇,最后用一个凝聚的层次聚类算法反复合并子簇，找到真正的结果簇
SBAC： SBAC算法则在计算对象间相似度时，考虑了属性特征对于体现对象本质的重要程度，对于更能体现对象本质的属性赋予较高的权值
BIRCH： BIRCH算法利用树结构对数据集进行处理，叶结点存储一个聚类，用中心和半径表示，顺序处理每一个对象，并把它划分到距离最近的结点，该算法也可以作为其他聚类算法的预处理过程
BUBBLE： BUBBLE算法则把BIRCH算法的中心和半径概念推广到普通的距离空间
BUBBLE-FM： BUBBLE-FM算法通过减少距离的计算次数，提高了BUBBLE算法的效率

③基于密度聚类算法：
DBSCAN： DBSCAN算法是一种典型的基于密度的聚类算法，该算法采用空间索引技术来搜索对象的邻域，引入了“核心对象”和“密度可达”等概念，从核心对象出发，把所有密度可达的对象组成一个簇
GDBSCAN： 算法通过泛化DBSCAN算法中邻域的概念，以适应空间对象的特点
DBLASD：
OPTICS： OPTICS算法结合了聚类的自动性和交互性，先生成聚类的次序，可以对不同的聚类设置不同的参数，来得到用户满意的结果
FDC： FDC算法通过构造k-d tree把整个数据空间划分成若干个矩形空间，当空间维数较少时可以大大提高DBSCAN的效率

④基于网格的聚类算法：
STING： 利用网格单元保存数据统计信息，从而实现多分辨率的聚类
WaveCluster： 在聚类分析中引入了小波变换的原理，主要应用于信号处理领域。（备注：小波算法在信号处理，图形图像，加密解密等领域有重要应用，是一种比较高深的东西）
CLIQUE： 是一种结合了网格和密度的聚类算法
OPTIGRID：

⑤基于神经网络的聚类算法：
自组织神经网络SOM： 该方法的基本思想是–由外界输入不同的样本到人工的自组织映射网络中，一开始时，输入样本引起输出兴奋细胞的位置各不相同，但自组织后会形成一些细胞群，它们分别代表了输入样本，反映了输入样本的特征

⑥基于统计学的聚类算法：
COBWeb： COBWeb是一个通用的概念聚类方法，它用分类树的形式表现层次聚类
CLASSIT：
AutoClass： 是以概率混合模型为基础，利用属性的概率分布来描述聚类，该方法能够处理混合型的数据，但要求各属性相互独立

f散度的多种常见特例： Kullback-Liebler散度、Jensen-Shannon散度、 Pearson-X2散度和Hellinger距离。４种特例中只有 Ｈｅｌｌｉｎｇｅｒ距离同时满 足非负性、对称性和三角公式３个条件，这也是本算法在ｆ散 度的诸多特例中选择 Ｈｅｌｌｉｎｇｅｒ距离作为度量方法的原因。 当f(t)=1-根号t时，f散度称为Hellinger距离。如果f(x)=xlogx，那就是KL散度。如果是f(x)=-logx，那就表示reverse KL散度
相似度用距离来定义
聚类分析中如何度量两个对象之间的相似性呢？一般有两种方法，一种是对所有对象作特征投影，另一种则是距离计算。前者主要从直观的图像上反应对象之间的相似度关系，而后者则是通过衡量对象之间的差异度来反应对象之间的相似度关系。

距离计算是最为常见的相似度度量方法，通常的对象a,b之间的相似度为Sim(a,b),对象a,b的测量距离为d(a,b)，则一般采取Sim(a,b) = 1/(1+d(a,b))得到相似度。

注意，散度跟距离不一样，没有距离的对称性或是三角不等式的要求。

概率分布之间的距离，顾名思义，度量两组样本分布之间的距离 。

• KL
  KL散度是是两个概率分布P和Q 差别的非对称性的度量。越小越相似。KL散度的值为非负数。有时会将KL散度称为KL距离，但它并不满足距离的性质：1. KL散度不是对称的:KL(A,B) ≠ KL(B,A) 2. KL散度不满足三角不等式: KL(A,B)>KL(A,C)+KL(C,B)
• JS
  JS散度度量了两个概率分布的相似度，基于KL散度的变体，解决了KL散度非对称的问题。一般地，JS散度是对称的，其取值是0到1之间。完全相同时为0。

KL散度和JS散度度量的时候有一个问题：如果两个分配P,Q离得很远，完全没有重叠的时候，那么KL散度值是没有意义的，而JS散度值是一个常数。这在学习算法中是比较致命的，这就意味这一点的梯度为0，梯度消失了。

• 皮尔逊相关系数(pearsoncorrelation)
  它度量的是两个向量之间的相似度。它相对于欧氏距离的一个优势是：它对用户评级的量级并不敏感。比如：一个狂躁者对所有物品的评分都是5分，而另一个忧郁着对所有物品的评分都是1分，它会认为这两个向量是相等的。在Numpy中，它的计算是由函数corrcoef进行的。

• pearson X2
  卡方检验经常用来检验某一种观测分布是不是符合某一类典型的理论分布（如二项分布，正态分布等)。观察频数与期望频数越接近，两者之间的差异越小，χ2值越小；如果两个分布完全一致，χ2值为0

• cosine
  余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上。

与欧几里德距离类似，基于余弦相似度的计算方法也是把用户的喜好作为n-维坐标系中的一个点，通过连接这个点与坐标系的原点构成一条直线（向量），两个用户之间的相似度值就是两条直线（向量）间夹角的余弦值。因为连接代表用户评分的点与原点的直线都会相交于原点，夹角越小代表两个用户越相似，夹角越大代表两个用户的相似度越小。同时在三角系数中，角的余弦值是在[-1, 1]之间的，0度角的余弦值是1，180角的余弦值是-1。

余弦相似度衡量的是空间向量的夹角，更加的是体现在方向上的差异，而不是位置。如果保持A点的位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦相似度cosθ是保持不变的，因为夹角不变，而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦相似度的不同之处。

调整余弦相似度 —— Adjusted Cosine Similarity
在余弦相似度的介绍中说到：余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感。因此没法衡量每个维数值的差异，会导致这样一个情况：比如用户对内容评分，5分制，X和Y两个用户对两个内容的评分分别为(1,2)和(4,5)，使用余弦相似度得出的结果是0.98，两者极为相似，但从评分上看X似乎不喜欢这2个内容，而Y比较喜欢，余弦相似度对数值的不敏感导致了结果的误差，需要修正这种不合理性，就出现了调整余弦相似度，即所有维度上的数值都减去一个均值，比如X和Y的评分均值都是3，那么调整后为(-2,-1)和(1,2)，再用余弦相似度计算，得到-0.8，相似度为负值并且差异不小，但显然更加符合现实。