数据挖掘-----算法描述 层次聚类
1. CLara（Cluster Larger Application）是一种基于K-中心点模型设计的算法。
2. 它特别适用于处理规模更大的数据集。
3. CLara通过抽取数据集的多个样本集来进行分析。
4. 然后利用PAM算法从这些样本集中寻找最优的K个中心点。
5. 最终生成最优聚类结果作为输出。
6. 但是需要注意的是，
7. 其准确性受抽样策略的影响较大，
8. 因此在实际应用中应谨慎选择合适的抽样方法以提高聚类效果。
2. CLArANS（基于随机搜索的聚类分析方法），是一种k-中心点算法，在某些方面与CLara相似（similar to CLara），但又有其独特之处（however, there are notable differences）。具体而言，与CLara不同（unlike CLara），在每个步骤中选择一个样本时会遇到一个问题（a challenge arises）。
然而，在每个步骤中选择一个样本时会遇到一个问题。
C = \{c_1,c_2,…,c_k\}
X = \{x_1,x_2,…,x_n\}
层次聚类方法
层次聚类分为两种：
（1） 分层聚类：一种自底向上策略。开始于将每个样本独立作为初始簇，并随后逐步合并这些初始簇形成较大的簇。直至所有样本最终整合到一个大的簇中或根据预设终止条件进行操作。
（2） 分类的层次聚类：自顶向下的策略。
AGNES算法
AGNES算法是一种凝聚式的层次聚类方法。当两个簇C₁和C₂中的最短距离等于所有不同类别对象间欧氏距离的最小值时，则该两组可能被合并。这种策略属于单连接方法，并且每个集群可以由其中的所有样本点来表示。两集群间的相似性则基于各自内部最邻近样本点对的相关性来进行评估。
算法描述：
输入：包含n个对象的数据库，终止条件簇的数目k
输出：k个簇
（1） 将每个对象当成一个初始簇
（2） Repeat
（3） 根据两个簇中最近的数据点找到最近的两个簇
（4） 合并两个簇，生成新的簇的集合
（5） Until达到定义的簇的数目
算法性能：
（1） 简单，但遇到合并点选择困难的情况。
（2） 一旦一组对象被合并，不能撤销
（3） 算法的复杂度为O(n的平方)，不适合大数据集计算DIANA算法
DIANA（Divisive Analysis）算法归类于分裂型层次聚类方法。初始时将所有对象归并至同一个簇中。随后基于一系列标准（例如基于最近邻居的最大欧氏距离），对该簇进行划分。直至满足以下任一终止条件：目标达到指定的簇数量或任意两个相邻簇之间的最小距离超过设定阈值。
DIANA用到如下两个定义：
（1）在同一个聚类（cluster）中的每一对数据点都具有一个欧氏距离（Euclidean distance），而所有这些距离的最大值即为此聚类（cluster）的直径（diameter）。
（2） 平均相异度（平均距离）：
算法描述：
输入：包含n个对象的数据库，终止条件簇的数目k
输出：k个簇，达到终止条件规定簇数目
（1） 将所有对象整个当成一个初始簇
（2） For ( i=1;i!=k;i++) Do Begin
（3） 在所有簇中挑选出具有最大直径的簇；
（4） 从选定的簇中识别出具有最大平均差异度的那个点，并将其归类到splinter组中；其余的则归类到old party中。
（5） Repeat
从old party中选择一个最优点，使其到splinter group各点的距离不小于旧党派内部各点之间的最小距离，并将其纳入到splinter group中。
（7） Until 没有新的old party的点被分配给splinter group；
Splinter group 和old party成为分裂的对象后分为了两支独立的集团，并与其它组织共同组成了新的组织集合
（9） END
算法性能：
该方法存在无法回溯已完成的分拆操作的问题，并且类间无法互换现有对象。若在某一阶段未能恰当选择分组分界线时，则可能导致产生的聚类质量不高。对于数据规模较大的情况不适用。
其他算法
层次聚类方法较为简单，在实际应用中常遇到一个问题即在确定合并与分割临界点时存在挑战。一种值得探索的方向是将层级聚类与其他技术结合使用以实现多阶段聚类效果
（1） BIRCH算法
BIRCH（基于层次方法实现的一种平衡迭代缩减与聚类过程）是一种基于层次结构的数据聚类技术
（2） CURE算法
密度聚类方法
基本思想：若某一区域内的点密度超过设定阈值，则将该区域归入最近预设聚类区。其能识别形状多样的数据群组，并具有抗噪声特性。然而，在处理高维数据时不够灵活且计算开销较大，在实际应用中容易导致大量I/O操作。
DBSCAN算法
基于密度的空间聚类算法DBSCAN通过连接具有相同密度的点来形成数据簇，并能将具备较高密度的数据区域划分为多个数据簇。同时支持在包含噪声的数据空间中识别不同形状和大小的数据集。
基本定义：
（1） 对象的 -临域：给定对象的半径 内的区域。
（2） 关键实体：若一个实体在其-邻域内至少包含指定阈值MinPts所规定的数量的对象，则称该实体为关键实体。
对于任意的对象集合D，在其中某个元素p与另一个元素q之间满足p位于q的邻域内，并且已知q被认定为核心对象的情况下，则称p为从q出发直接密度可达的对象。
（4） 密度可达：假设存在一个对象序列p₁, p₂,…,pₙ, 其中每个pi都属于集合D，并且满足pn等于p。如果对于任意的pi（i=1到n-1），pi+1都是通过MinPts参数计算得到的直接密度可达性，则称点p相对于q而言是基于MinPts参数计算得到的密度可达性。
具有密度联系：假设在对象集合D中存在一个对象o，则p和q基于o通过 关于 和MinPits的密度连接是可实现的。
（6） 噪声：基于密度的一个簇是由所有相互基于密度连接的对象构成的最大区域。那些无法融入任何簇的对象则被称为 outlier 或 noise objects。
算法描述：
输入：包含n个对象的数据库，半径 ，最少数目MinPts
输出：所有生成的簇，到达密度要求
(1) repeat
(2) 从数据库中抽取出一个未处理过的点
(3) If 抽出的点是核心点 then 找出所有从改密度可达的对象，形成一个簇
(4) Else 抽出的点是边缘点（非核心对象），跳出本次循环，寻找下一个点
(5) Until 所有点都被处理
算法性能：
能够识别不同形状的数据簇；然而该方法对于用户指定的关键参数较为敏感；为此OPTICS（Ordering Points to Identify the Clustering Structure）被提出；通过引入核心距离和可达距离概念；从而使得聚类过程对输入参数的变化不那么敏感。