上次的无监督学习1笔记中学习了基于基于原型的聚类算法。今天来记录基于层次的聚类算法和基于密度的聚类算法。

一、基于层次的聚类算法
层次聚类法试图在不同层次对数据集进行划分，从而形成树形的聚类结构，数据集的划分可采用“自下向上”的聚合策略，也可以采用“自顶向下”的分拆策略。聚类的层次被表示成树形图。树根拥有所有样本的唯一聚类，叶子是仅有一个样本的聚类。

层次聚类由不同层次的分割聚类组成，层次之间的分割具有嵌套的关系。它不需要输入参数，这是它的一个明显的优点，其缺点是终止条件必须具体指定。
与原型聚类和密度聚类不同，层次聚类试图在不同的“层次”上对样本数据集进行划分，一层一层地进行聚类。
典型的分层聚具体有：Hierarchical Clustering算法、 BIRCH算法等。
1.基本概念：判断两个簇之间的距离

层次聚类法涉及到一个很关键的地方就是判断簇之间的距离。判断的准则叫做链接准则。对于AgglomerativeClustering算法，scikit-learn有以上4种准则在调用层次聚类算法时可选。
计算两个组合数据点间距离常用的方法是：Single Linkage，Complete Linkage和Average Linkage，3种计算方法解析如下：
Single Linkage是将两个簇中最近的两个点间的距离作为这两个组合数据点的距离，该方法易受极端值的影响，两个不相似的点可能由于其中的某个极端的点距离较近而组合在一起。
Complete Linkage与Single Linkage相反，将两个簇中距离最远的两个点间的距离作为这两个簇的距离，Complete Linkage的问题也与Single Linkage相反，两个相似的点可能某个点原先所在的簇中有极端值而无法组合在一起。
Average Linkage的计算方法是计算两个簇中的每个点与其他所有点的距离并将所有距离的均值作为两个组合数据点间的距离，此方法计算量比较大，但结果比前两种方法更合理。

2.Hierarchical Clustering使用方法
skearn提供的模块cluster中可以调用：AgglomerativeClustering(n_clusters=2, affinity=“euclidean”, memory, connectivity, compute_full_tree, linkage, pooling_func）
具体参数描述：
n_clusters：一个整数，指定分类簇的数量，默认为2。
affinity：一个字符串或者可调用对象，用于计算距离，默认欧氏距离“euclidean”。
memory：用于缓存输出的结果，默认为不缓存。
connectivity：一个数组或者可调用对象或者None，用于指定连接矩阵。
compute_full_tree：通常当训练了n_clusters后，训练过程就会停止，等于True时会继续训练从而生成一颗完整的树。

具体参数描述：
linkage：一个字符串，用于指定链接算法 ，可选类型为{“ward”, “complete”, “average”, “single”} 。
“single”，单链接single-linkage，采用dmin。
“complete”,全链接complete-linkage，采用dmax。
“average”,均连接average-linkage，采用davg。
“ward，Ward链接，为默认选择方式。

pooling_func：一个可调用对象，它的输入是一组特征的值，输出是一个数。该参数在sklearn 0.20版本中弃用，将在0.22中删除。

AgglomerativeClustering()方法的属性：
abels_：array [n_samples]，每个点的簇标签
n_leaves_：int，分层树中的叶数。
n_components_：int，图表中估计的已连接组件数。
children_：类似数组，形状（n_samples-1,2），每个非叶节点的子节点。 小于n_samples的值对应于作为原始样本的树的叶子。 大于或等于n_samples的节点i是非叶节点并且具有子child_ [i-n_samples]。 或者，在第i次迭代中，子[i] [0]和子[i] [1]被合并以形成节点n_samples + i

2.BIRCH算法
BIRCH算法即平衡迭代削减聚类法，其核心是用一个聚类特征3元组表示一个簇的有关信息，从而使一簇点的表示可用对应的聚类特征，而不必用具体的一组点来表示。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。
3元组包含：数据点个数，数据点特征之和，数据点特征的平方和
分支因子：规定了树的每个节点的样本个数
簇直径：体现一类点的距离范围
BIRCH算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。
BIRCH算法中聚类特征树的构建过程是动态的，可以随时根据新的数据点对树进行重构，适合大规模数据集。

BIRCH算法描述：
第一步是通过扫描数据，建立聚类特征树。
第二步是采用某个算法对聚类特征树的叶节点进行聚类。
BIRCH算法优缺点：
优点就是一次扫描就行进行比较好的聚类。
缺点是要求是球形聚类，因为CF树存储的都是半径类的数据，都是球形才适合。

3.BIRCH算法的计算解析
聚类特征树可以动态构造，不要求所有数据读入内存，可逐个读入。新的数据项总是插入到树中与该数据距离最近的叶子中。如果插入后使得该叶子的直径大于类直径T，则把该叶子节点分裂。其它叶子结点也需要检查是否超过分枝因子来判断其分裂与否，直至该数据插入到叶子中，并且满足不超过类直径，而每个非叶子节点的子女个数不大于分枝因子。算法可通过改变类直径修改特征树大小，控制其占内存容量。
BIRCH算法通过一次扫描就可以进行较好的聚类，因此该算法适于大数据集。I/O花费与数据量成线性关系。
BIRCH算法只适用于数据的分布呈凸形及球形的情况，并且由于BIRCH算法需提供正确的聚类个数和簇直径限制，对不可视的高维数据不可行。

BIRCH算法使用方法：
sklearn中的聚类算法包含在sklearn.cluster模块中，BIRCH算法的具体描述为：
Birch(threshold=0.5, branching_factor=50, n_clusters=3, compute_labels=True, copy=True)
参数说明如下：
threshold：float，表示设定的半径阈值，默认0.5。
branching_factor：int，默认=50，每个节点最大特征树子集群数。
n_clusters：int，默认=3，最终聚类数目。
compute_labels：bool，默认为True，是否为每个拟合计算标签，一般默认。
copy：bool，默认为True，是否复制给定数据。如果设置为False，则将覆盖初始数据

二、基于密度的聚类算法
关于密度聚类算法：
密度聚类的思想不同于K-Means，它是通过聚类的簇是否紧密相连来判断样本点是否属于一个簇，代表性的算法就是DBSCAN，它基于一组邻域参数来判断某处样本是否是紧密。
DBSCAN（Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法）是一种很典型的密度聚类算法，和K-Means，BIRCH这些一般只适用于凸样本集的聚类相比，DBSCAN还适用于非凸样本集。

1.DBSCAN算法：

2.优缺点：
DBSCAN的优点：
可以解决数据分布特殊（非凸， 互相包络，长条形等）的情况。
对于噪声不敏感 ，速度较快，不需要指定簇的个数；可适用于较大的数据集。
在邻域参数给定的情况下结果是确定的，只要数据进入算法的顺序不变，与初始值无关。
缺点：
因为对整个数据集我们使用的是一组邻域参数 ，簇之间密度差距过大时效果不好。
数据集较大的时候很消耗内存。
对于高维数据距离的计算会比较麻烦，造成维数灾难。

3.DBSCAN聚类算法使用方法
利用sklearn库中的sklearn.cluster.DBSCAN方法，完整描述为：
sklearn.cluster.DBSCAN(eps=0.5, min_samples=5, metric=’euclidean’, metric_params=None, algorithm=’auto’, leaf_size=30, p=None, n_jobs=None)
注意：DBSCAN主要参数：
eps：两个样本被看作邻居节点的最大距离。
min_samples：最小簇的样本数。
metric：距离计算方式，euclidean为欧氏距离计算。

其他参数说明
metric 版本0.17中的新功能：度量预先计算以接受预先计算的稀疏矩阵。
metric_params：dict，可选，度量函数的其他关键字参数。版本0.19中的新功能。
algorithm算法：{‘auto’，‘ball_tree’，‘kd_tree’，‘brute’}，可选，NearestNeighbors模块用于计算逐点距离并找到最近邻居的算法。有关详细信息，请参阅NearestNeighbors模块文档。目前在scikit-learn中已经可以使用ball-trees 和 kd-trees来确定邻居点（可以看出找出点的邻域内有几个点是DBSCAN最基本，最多的操作）,但是在默认情况下是不使用他们的，而是使用很消耗内存的距离矩阵。
leaf_size：int，optional（默认值= 30），叶子大小传递给BallTree或cKDTree。这可能会影响构造和查询的速度，以及存储树所需的内存。最佳值取决于问题的性质。
p：float，可选，用于计算点之间距离的Minkowski度量的功效。
n_jobs：int或None，可选（默认=无），要运行的并行作业数。除非在joblib.parallel_backend上下文中，否则表示1。 -1表示使用所有处理器。有关详细信息，请参阅词汇表。腾科

4.聚类算法应用于推荐系统
常用的聚类推荐算法有K-Means、BIRCH、DBSCAN等
推荐系统：类似于基于用户或者项目的协同过滤
我们可以按照用户或者按照物品基于一定的距离度量来进行聚类。如果基于用户聚类，则可以将用户按照一定距离度量方式分成不同的目标人群，将同样目标人群评分高的物品推荐给目标用户。

基于物品聚类的话，则是将用户评分高物品的相似同类物品推荐给用户。

想学习考证，首选腾科