什么是聚类分析？
数据聚类问题的示例
根据销售额对零售店进行分组是聚类分析的一个简单用例。假设一家咖啡馆在城市里有八个分店。下表显示了卡布奇诺和冰咖啡的每日销售情况。
下图显示了相同的数据，其中每个分店的卡布奇诺和冰咖啡的销售额分别绘制在 X 轴和 Y 轴上。在这个示例中，由于数据点有限，因此很容易在图表上绘制两个自然存在的咖啡店聚类，然后手动对其进行可视化。
但是，当涉及到数千个数据点时，需要使用聚类分析算法将数据点划分为不同的聚类。
聚类分析有哪些应用？
聚类分析通常以两种主要方式使用：
- 作为解决与数据分组相关的问题的独立工具。
- 作为各种机器学习算法的预处理步骤。
作为独立工具的聚类分析
- 营销：在营销中，聚类分析可用于根据客户的购买模式或兴趣将客户划分为不同的数据分组。这些分组被称为客户角色。然后，组织针对不同的客户群使用不同的营销策略。
- 金融风险分析：金融机构使用各种聚类分析算法，根据客户的银行余额和债务将其客户分为不同的风险类别。在批准贷款、保险或信用卡时，这些聚类被用来帮助决策。
- 房地产：基建专家根据房屋的规模、位置和市场价值使用聚类对房屋进行分组。这些信息用于评估城市不同地区的房地产潜力。
聚类分析作为机器学习的预处理步骤
聚类分析通常用作各种机器学习算法的预处理步骤。
分类算法对大量数据集运行聚类分析，以过滤掉属于明显组的数据。然后，可以在精简的非明显数据点上使用高级数据分类技术。随着数据集变小，计算时间也大大缩短。同样的方法可以反过来使用，即使用聚类分析算法来滤除噪声或离群值数据。
在运行监督学习算法之前，可以先对输入数据进行聚类分析，以找出数据中的自然聚类。
主要的聚类分析算法有哪些？
聚类分析算法通常属于以下类别：
- 基于分区的算法
- 分层算法
- 基于密度的算法
- 基于网格的算法
- 基于模型的算法
- 基于约束的算法
- 离群值分析算法
每种算法本身都很复杂，可能适合某些分析，而不适合其他分析。
基于分区的聚类分析算法
在此方法中，算法从几个初始聚类开始。然后，它以迭代方式将数据点重新定位到不同的聚类，直到实现最佳分区。K-均值聚类算法是最流行的一种聚类算法。
下面的 K-均值聚类示例显示了其工作原理。
第 1 步：决定聚类
确定聚类数，算法为 “K”，例如 K=3。该算法会将上述 12 个数据点划分为 3 个聚类。数字 K 可以是任何值。视情况而定，聚类的正确性可能会有所不同。还有一些算法方法可用于确定 K 的最佳值。
第 2 步：选择数据点
当 K=3 时，将任意三个数据点作为初始均值。在本例中，点 C、D 和 E 被选为初始均值。请注意，K-均值算法可以将任何点作为初始均值。
第 3 步：计算距离
计算从数据集中的每个点到每个初始聚类均值的距离。随机选择了三个聚类均值 C、D 和 E。对于样本中的每个数据点，计算其与这三个均值的距离。两点（X1、Y1）和（X2、Y2）之间的欧氏距离如下所示：
在第 3 步之后，表格将显示每个数据点与初始均值 C、D 和 E 的距离。
根据数据点的最小距离将数据点添加到聚类中。例如，点 A 与初始均值 C 的距离最小。这意味着 A 位于聚类中，均值为 C。完成第一步后，将获得聚类。
第 4 步：迭代 — 计算新均值
现在可以很容易地看到初始聚类。下一步是计算三个新的聚类均值。为此，获取特定聚类中的每个数据点，并计算平均值。
“C” 聚类的新聚类均值 = (5+2+6+1+4+3+6/7、21+11+22+10+23+14+12/7) = (3.85、16.14)，我们称之为点 X。
“D” 聚类的新聚类均值 = (1+2+5/3, 6+8+4/3) = (2.66, 6)，我们称之为点 Y。
“E” 聚类的新聚类均值 = (4+5/2、10+11/2) = (4.5、10.5)。我们称之为点 Z。
第 5 步：迭代 — 计算每个数据点与新均值的距离
重复第 3 步，找出所有数据点与新计算的聚类均值 X、Y 和 Z 之间的距离。在此次新迭代中，很容易看出数据点 C、D、I 和 L 的最小距离已更改。它们现在属于一个新的聚类，如下所示。
然后，由于某些数据点改变了自己的聚类，K-均值迭代需要继续。
第 6 步：迭代 — 计算新均值和新聚类
由于数据点 C、D、I、L 改变了它们的聚类，因此需要像第 4 步一样计算新的聚类均值。为此，获取特定聚类中的每个数据点，并计算平均值。然后像在第 5 步中一样，计算从每个数据点到新聚类均值的距离。根据距离，将数据点分配给与其具有最小距离的聚类。
K-均值算法何时完成？
K-均值是一种迭代分区算法：
- 决定一开始要使用的聚类数 (K)。在上面的例子中，K=3。
- 随机分配 K 个数据点作为初始聚类均值。
- 重复以下步骤，直到没有数据点更改其聚类。
- 计算从数据点到聚类均值的平均距离。
- 将数据点分配给距离最小的聚类。
- 检查是否有任何数据点更改了其聚类。
在新的迭代中，如果每个数据点都保留在其先前的聚类中，则 K-均值算法将终止。这意味着已经获得了局部最佳解决方案。
基于 K-中心点分区的聚类算法
K-中心点算法是另一种基于分区的聚类算法。K-中心点算法选择中心点作为聚类的代表对象。k-中心点算法试图找到与特定聚类中所有其他数据点都相差最小的数据点。在差异最小化之前，K-中心点算法会迭代划分数据集。K-均值算法通常使用平方误差距离（欧氏距离），而 K-中心点算法通常使用绝对值距离（如曼哈顿距离）来测量两个数据点之间的差异。
K-中心点算法的标准实现是围绕中心点的分区 (PAM) 算法。以下是中心点周围分区 (PAM) 算法的基本步骤。
- 为 K 选择一个值，其中 K 是数据点将被划分为的聚类数。
- 随机选择 K 个数据点作为中心点。
- 对于数据集中的每个数据点（Xi、Yi），测量该点与上面选择的中心点之间的差异。常用的差异度度量标准是曼哈顿距离：
- | Xi — Ci| + | Yi-Cj|，其中 (Ci, Cj) 代表中心点。
- 每个数据点（Xi、Yi）都分配给相异性最小的聚类。
- 对于上述每个聚类，计算总成本，即该聚类中每个数据点的差异之和。
- 现在，随机选择一个非中间点作为新的中间点，然后重复第 3-5 步。
- 当聚类中没有任何变化时停止。
K 均值和 K-中心点算法的比较
尽管 K-均值算法很简单，但是当数据具有大量噪声和离群值时，它并不能产生好的结果。在这种情况下，K-中心点方法更稳固。但是，像 PAM 这样的 K-中心点算法仅在数据集较小时才有用。当数据集大小增加时，K-中心点算法的计算时间将呈指数增长。
除法算法
顾名思义，分割算法在一开始就将所有数据点分配到一个聚类中。然后，它将聚类划分为多个最不相似的聚类。然后，算法递归地划分这些聚类，直到获得最佳解。除法算法也称为自上而下的聚类方法。
聚集算法
这些算法首先将每个数据点分配给不同的聚类。然后，算法递归地加入最相似的聚类，直到获得最佳解。聚集算法也被称为自下而上的聚类方法。
聚集聚类算法示例
以下是五个数据点的距离矩阵。点之间的距离可以根据欧氏距离或曼哈顿距离或任何其他距离公式来计算。距离矩阵始终是对称矩阵，因为点 X 和 Y 之间的距离与 Y 和 X 之间的距离相同。基于此距离矩阵，这是聚集（自下而上）聚类算法的示例。
第 1 步：在距离矩阵中，找到距离最小的两个点。在上面的例子中，它是点 3 和 5。它们之间的距离为 2。将它们放入单个聚类中。
第 2 步：移除点 3 和 5 并将其替换为聚类 “35”，然后创建一个新的距离矩阵。为此，需要计算所有数据点与聚类 “35” 之间的距离。有多种方法可以确定此距离。
在此示例中，使用了以下方法来测量距离：
点 X 与聚类 “35” 的距离 = 最小值（距离 (X, 3)、距离 (X,5)）。基于此方法的更新距离矩阵为：
第 3 步：重复第 2 步，直到将所有数据点分组到一个聚类中。在当前示例中，需要六次迭代。下图显示了聚类的形成。这种表示被称为树状图。在此表示法中，Y 轴表示两个数据点之间的距离。例如，点 3 和 5 之间的距离为 2。
第 4 步：如上所示，将所有数据点聚类后，决定需要保留多少个聚类。这是一个艰难的决定，因为每个分层聚类算法最终都会产生一个聚类。在分层聚类算法对数据进行分区后，有几种方法可用于确定聚类的最佳数量。
基于密度的聚类算法
这些算法基于聚类总是比周围数据空间更密集的想法。基于密度的算法从单个数据点开始，然后探索其邻域的数据点。初始点邻域中的点包含在单个聚类中。邻域的定义因算法的实现而异。基于密度的噪声应用程序空间聚类 (DBSCAN) 是此类别中流行的聚类算法。
基于网格的聚类算法
基于网格的聚类算法与基于密度的聚类算法类似。数据空间被划分为几个较小的单元，称为格网。每个数据点都分配给一个特定的格网像元。然后，该算法计算每个格网的密度。密度低于阈值的格网将被清除。接下来，该算法从相邻的密集格网组中形成聚类。统计信息网格 (STING) 和任务聚类 (CLIQUE) 是两种流行的基于网格的算法。
除了上面讨论的算法外，聚类分析还包括一组基于模型的聚类、基于约束的聚类和离群值分析算法。
聚类分析算法的优缺点
| 算法 | 优点 | 缺点 |
|---|---|---|
| 基于分区的聚类分析算法 |
|
|
| 分层聚类分析算法 |
|
|
| 基于密度的聚类分析算法 |
|
|
| 基于网格的聚类分析算法 |
|
|