数据挖掘 笔记三

12月主要研读了《数据挖掘概念与技术》中的第十章、第六章、第八章以及第十一章，并详细介绍了K-Means聚类算法的实现过程。

一、《数据挖掘概念与技术》

第十章（2、3、4、5小节）

阐述了聚类分析的多种方法：包括划分法、分层法、基于密度的方法以及网格化的方法。

1.划分方法

（1）k-均值：一种基于形心的技术

该聚类方法并不总是能够收敛至全局最优解，并通常会陷入到局部最优解的状态中。其最终结果可能受初始簇中心选取的影响较大。为了获得较好的聚类效果，在实际应用中建议采用不同的初始簇中心多次运行该算法以获取较优的结果。该算法的时间复杂度为O(nkt)，其中n表示对象总数目、k表示簇的数量、t表示迭代次数。通常情况下k远小于n且t也远小于n.因此，在处理大数据集时该算法整体表现是相对可扩展且高效的。然而该方法不适用于识别非凸形状的簇结构或者规模差异较大的数据集类别。同时该算法对于噪声数据以及异常点较为敏感，在实际应用中需特别注意避免出现此类情况会影响聚类效果的程度。</

（2）k-中心点：一种基于代表对象的技术

当数据中存在噪声和异常值时，在选择聚类中心时采用k-中心点方法相较于k-均值方法更具鲁棒性。其原因在于中心点受极端值的影响较小。然而，在每次迭代过程中该算法的时间复杂度为O(k(n−k)²)，因此当n和k较大时计算开销显著高于k-means方法。

这些方法都需要用户预先设定一个参数k。对于小规模的数据集而言，该算法表现出色；然而，在处理大规模数据时存在一定的局限性。此时可以采用一种名为CLARA（Clustering LARge Applications,大型应用聚类）的抽样聚类算法。基于从原始数据集中随机抽取的一个子集进行计算。通过PAM算法在样本上计算出最佳中心点位置，并据此扩展至整个数据空间以获得最终结果。值得注意的是，在某些特殊情况下可能会出现性能问题：当抽样得到的最佳中心点与真实最优中心点存在较大差距时，在这种情况下CLARA可能无法有效找到合适的聚类结果；而如果某个对象属于这k个理想中的核心点之一，并且在采样过程中未被选中，则可能会导致无法正确识别该对象所属的核心簇。

2.层次方法

层次聚类方法将数据对象组成层次结构或簇的“树”。

（1）凝聚的与分裂的层次聚类

层次聚类中的凝聚法通过自底向上的方式实施；而层次聚类中的分裂法则采用自顶向下的策略

（2）算法方法的距离度量

距离有最小距离、最大距离、平均距离、均值距离。

（3）BIRCH:使用聚类特征树的多阶段聚类

基于层次结构的平衡迭代缩减与分类技术（BIRCH）是一种专为处理大规模数值数据而设计的方法学框架。该系统结合了层次分类法在微观阶段的应用以及基于迭代划分等方法在宏观阶段的应用。通过这种方式，BIRCH成功地解决了凝聚式簇算法中所面临的主要两个问题：一是系统的可扩展性问题；二是无法撤销先前处理结果所带来的操作不便。

（4）Chameleon：使用动态建模的多阶段层次聚类

Chameleon是一种层次型聚类方法，在计算每一对簇之间的相似度时采用了动态建模策略。在评价各簇间相似性时主要基于以下两个方面：一是各簇内部样本间的连接程度；二是各簇间的相互紧密程度。

（5）概率层次聚类

基于概率的分层聚类方法主要目标在于利用概率模型来衡量不同簇之间的关系，并非传统的层次聚类算法所能取代

3.基于密度的方法

（1）DBSCAN：一种基于高密度连通区域的基于密度聚类

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种适用于处理噪声数据的基于密度的空间聚类方法。该算法通过识别具有密集邻域的对象群来实现数据聚类，并将这些核心对象与其领域关联起来以形成密集区域作为数据簇

（2）OPTICS：通过点排序识别聚类结构

该聚类分析方法（OPTICS）能够有效改进传统聚类分析中的单一全局参数问题。该算法不会显式生成密度数据集簇（data density clusters），而是通过输出簇排序（cluster ordering）来实现。这种排序结果相当于基于不同参数设置得出的密度基群（density-based clusters）结构。

（3）DENCLUE：基于密度函数分布的聚类

DENCLUE使用高斯核估计基于给定的待聚类的对象集密度。

4.基于网格的方法

（1）STING:统计信息网络

STING(Statistical Information Grid,统计信息网格)是一种以网格为基础的多层次聚类技术，在处理输入数据时将其空间区域划分为矩形单元。通过多层次递归划分的方法对空间进行组织管理，并形成了一个层次化的空间划分体系：在这一体系中,每个高层单元都被划分为多个低一层级的子单元,从而形成了从粗粒度到细粒度的不同分辨率层级

（2）CLIQUE：一种类似于Apriori的子空间聚类方法

CLIQUE（Clustering In QUEst）是一种基于格网的基本聚类方法，在基于密度的簇识别方面具有重要价值。CLIQUE通过将每个维度划分为互不重叠的区间来分割数据对象的空间区域，并进而将整个嵌入空间划分为一个个单元。它通过设定一个密度阈值来区分密集型单元与稀疏型单元：当该单元对应对象的数量超过该密度阈值时，则被认定为密集型单元。

第六章

发现频繁项集及其联系与重要程度：涵盖基本概念框架、主要挖掘算法及其性能优化策略

频繁模式是频繁的出现在数据集中的模式（如项集、子序列或子结构）。

1.基本概念

支撑程度和信心水平是规则兴趣度的两个重要指标。它们分别体现了所述规则的实用性和可靠性。在一般情况下,关联规则被认为具有吸引力,如果它满足最小支持阈值和最小置信阈值

2.频繁项集挖掘方法

Apriori方法是一种用于布尔型关联规则挖掘的创新性算法。该方法基于数据中的频繁项集及其属性，在逐层筛选过程中构建候选集合。该算法预设属性：所有包含在频繁项集中的非空子集必定也是频繁的。

（2）由频繁项集产生关联规则

优化Apriori算法性能：采用散列技术和缩减事务长度等方法

3.模式评估方法

（1）强规则不一定是有趣的

（2）从关联分析到相关分析

（3）模式评估度量比较

应采用模式评估指标以拓展支持-置信框架，并引导出更具吸引力的关联规则；这些规则将有助于生成更有价值的相关结论。其中一种指标具有零不变性——即其值不受非目标项集的影响。以下为几种主要的模式评估指标：提升率（Lift）、卡方检验（χ²）、完全置信率（Confidence）、最大置信率（Max Confidence）、Kulczynski指数以及余弦相似性；其中后四种指标均具备零不变性特性。建议将Kulczynski指数与不均衡比率结合使用以增强对项集间关联性的识别能力

第八章

各类分类技术涵盖基础理论框架及其核心要素分析；其中包含基于决策树的方法、贝叶斯统计模型以及规则驱动型分类算法等具体内容；对于模式识别标准及筛选策略有专门探讨；同时针对优化策略与性能提升措施展开深入研究

1.基本概念

（1）

数据分析的核心目标是数值预测问题。在这一过程中所构建的模型能够预估连续值函数或有序序列而非仅仅分类标签。这种模型被统称为预测器。回归分析作为统计学中应用最广泛的数值预测方法之一。而分类与数值预测构成了数据处理中的两大核心问题类型。

（2）分类的一般方法

数据分类可分为两个主要阶段：第一阶段是建立分类模型的学习过程；第二阶段是利用该模型对输入的数据进行类别预测。

2.决策树归纳

基于带有标记类别的训练样本数据集进行归纳的学习过程所建立起来的结构即为决策树。它具有与流程图相似的空间布局特征，并且其内部节点（非叶子节点）对应于特定属性上的判断标准。每一个分支则代表着该判断结果所带来的后续路径；相应的叶子结点（或终端结点）则存储着对应的类别标签。

3.贝叶斯分类方法

该分类方法属于统计学范畴。该方法假设某一属性值在特定类别中与其他属性无关。这一假设旨在简化计算过程，并在此基础上被称作‘简单’。P(H|X)可表示为条件X下事件H发生的后验概率。P（H）则表示事件H发生的先验概率。

4.基于规则的分类

规则可以被视为一种高效的信息表达方式。在机器学习领域中，基于规则的分类器采用一系列条件-结果（IF-THEN）规则来进行数据分类。通过决策树结构识别分类规则：为每一条从根节点延伸至叶子节点的路径生成相应的条件集合。在路径上应用所有分裂条件，并将这些条件组合成逻辑与（AND）关系作为前件。将叶子节点对应的类别作为结果部分（THEN），即后件。该算法直接从训练数据中提取条件-结果（IF-THEN）模式，无需构建完整的决策树结构。该方法是挖掘分类知识最常用的一种策略：它通过逐步学习这些模式来构建分类系统，在每次迭代中仅处理一条新的训练样本，并确保当前生成模式能够准确描述目标类中的多个样本。同时希望这些模式不会涵盖其他类别中的样本点。

5.模型评估与选择

混淆矩阵是一种用于评估分类器性能的有效工具。对于二类区分问题而言，它展示了真实阳性数（TP）、真实阴性数（TN）、虚假阳性数（FP）以及虚假阴性数（FN）。在衡量分类器预测能力方面常用的指标包括准确率（ACC）、灵敏度（Recall）/召回率以及特异性（SPE），此外还有精确率（Precision）、F1分数以及Fβ分数等度量指标。需要注意的是，在目标类别样本数量较少的情况下，默认依赖于准确率作为评价指标可能会导致误导结果。为了构建和评估分类器性能，通常将标记数据集划分为训练集与测试集两部分进行学习与验证过程。常用的数据划分方法有简单随机抽样法、“保持”比例抽样法、“按比例”交叉验证法以及自助采样法等多种方式可以选择使用以确保数据分布的一致性和有效性。此外，在模型选择过程中还应结合显著性检验与ROC曲线分析这两个重要工具来进行深入分析与比较研究以提高模型泛化能力

6.提高分类准确率的技术

组合方法可以通过基于学习的方式优化总体准确率，并整合一系列基础分类器模型。装袋法、提升法以及随机森林等技术广泛应用于集成学习中。当目标类别样本数量过少时会引发类别不平衡问题。针对该问题可采取抽样技术、欠抽样策略以及阈值调节等方式来改善分类性能。此外还有结合多种技术的混合方法可用

二、kMeans算法实现

该算法在实现上较为简便，然而其存在收敛至局部极小值的风险，在处理大规模数据时效率较低。特别适用于处理数值型数据。

kMeans算法伪代码：

生成k个点用于确定初始质心位置（通常采用随机方法确定这些初始位置点，并且这些位置点不会在现有数据样本中出现，在整个数据样本范围内部）

当任意一个点的簇分配结果发生改变时

对数据集中的每个数据点

对每个质心

计算质心与数据点之间的距离

将数据点分配到距其最近的簇

对每一个簇，计算簇中所有点的均值并将均值作为质心

k-means算法的收敛结果导致聚类效果欠佳；其归因于该方法收敛至局部最小值而非全局最小值的问题。该方法能够有效规避这一挑战。

二分kMeans（bisectingK-means）伪代码：

将所有点看成一个簇

当簇数目小于K时

对每一个簇

计算总误差（误差就是每个点到质心的距离平方）

在给定的簇上面进行kMeans（k=2）

计算将该簇一分为二之后的总误差

选择使得总误差最小的那个簇进行划分操作