层次聚类对新能源汽车大数据的分析与应用技术

1.层次聚类原理和步骤

层次聚类算法，是通过将数据组织为若干组并形成一个相应的树来进行聚类的。根据层次是自底向上还是自顶向下形成，层次聚类算法可以进一步分为凝聚的聚类算法和分裂的聚类算法，如图4-6所示。一个完全层次聚类的质量由于无法对已经做的合并或分解进行调整而受到影响。但是层次聚类算法没有使用准则函数，它所含的对数据结构的假设更少，所以它的通用性更强。

在实际应用中一般有两种层次聚类方法：

①凝聚的层次聚类：这种自底向上的策略首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被达到要求。大部分的层次聚类方法都属于一类，它们在簇间的相似度的定义有点不一样。

图4-6 凝聚的层次聚类和分裂的层次聚类处理过程

②分裂的层次聚类：像这样的自顶向下的策略与凝聚的层次聚类有些不一样。它首先将所有对象放在一个簇中，然后慢慢地细分为越来越小的簇，直到每个对象自行形成一簇，或者直到满足其他的一个终结条件，例如满足了某个期望的簇数目，又或者两个最近的簇之间的距离达到了某一个阈值。

图4-6描述了一个凝聚的层次聚类方法AGENES和一个分裂的层次聚类方法DIANA在一个包括5个对象的数据的集合{a，b，c，d，e}上的处理过程。初始时，AGENES将每个样本点自为一簇，之后这样的簇依照某一种准则逐渐合并，例如簇C₁中的某个样本点和簇C₂中的一个样本点相隔的距离是所有不同类簇的样本点间欧几里得距离最近的，则认为簇C₁和簇C₂是相似可合并的。这就是一类单链接的方法，即每一个簇能够被簇中其他所有的对象所代表，两簇之间的相似度是由这里的两个不同簇中的距离最相近的数据点对的相似度来定义的。聚类的合并进程往复地进行直到其他的对象合并形成了一个簇。而DIANA方法的运行过程中，初始时DIANA将所有样本点归为同一类簇，然后根据某种准则进行逐渐分裂，例如类簇C中两个样本点A和B之间的距离是类簇C中所有样本点间距离最远的一对，那么样本点A和B将分裂成两个簇C₁和C₂，并且先前类簇C中其他样本点根据与A和B之间的距离，分别纳入到簇C₁和C₂中。例如，类簇C中样本点O与样本点A的欧几里得距离为2，与样本点B的欧几里得距离为4，因为Distance（A，O）＜Distance（B，O），那么O将纳入类簇C₁中。

其中，AGENES算法的核心步骤是：

● 输入：K—目标类簇数；D—样本点集合；

● 输出：K个类簇集合。

● 方法：

①将D中每个样本点当作其类簇。

②循环③到④直到类簇数=K为止。

③找到分属两个不同类簇，且距离最近的样本点对。

④将两个类簇合并。

而DIANA算法的核心步骤是：

输入：K—目标类簇数；D—样本点集合；

输出：K个类簇集合。

方法：

①将D中所有样本点归并成类簇。

②循环③到④直到类簇数=K为止。

③在同类簇中找到距离最远的样本点对。

④以该样本点对为代表，将原类簇中的样本点重新分属到新类簇。

2.层次聚类特点

①在凝聚的层次聚类方法和分裂的层次聚类的所有方法中，都需要用户提供所希望得到的聚类的单个数量和阈值作为聚类分析的终止条件，但是对于复杂的数据来说这是很难事先判定的。尽管层次聚类的方法实现很简单，但是偶尔会遇见合并或分裂点的抉择困难。这样的抉择是特别关键的，因为只要其中的两个对象被合并或者分裂，接下来的处理将只能在新生成的簇中完成。已形成的处理就不能被撤销，两个聚类之间也不能交换对象。如果在某个阶段没有选择合并或分裂的决策，就非常可能会导致质量不高的聚类结果。而且这种聚类方法不具有特别好的可伸缩性，因为它们合并或分裂的决策需要经过检测和估算大量的对象或簇。

②层次聚类算法由于要使用距离矩阵，因此它的时间和空间复杂性都很高，几乎不能在大数据集上使用。层次聚类算法只处理符合某静态模型的簇，忽略了不同簇间的信息以及簇间的互连性（互连性指的是簇间距离较近数据对的多少）和近似度（近似度指的是簇间对数据对的相似度）。