A. 数据挖掘干货总结（四）--聚类算法
本文共计2680字，预计阅读时长七分钟
聚类算法
一 、 本质
将数据划分到不同的类里，使相似的数据在同一类里，不相似的数据在不同类里
二 、 分类算法用来解决什么问题
文本聚类、图像聚类和商品聚类，便于发现规律，以解决数据稀疏问题
三 、 聚类算法基础知识
1. 层次聚类 vs 非层次聚类
– 不同类之间有无包含关系
2. 硬聚类 vs 软聚类
– 硬聚类：每个对象只属于一个类
– 软聚类：每个对象以某个概率属于每个类
3. 用向量表示对象
– 每个对象用一个向量表示，可以视为高维空间的一个点
– 所有对象形成数据空间（矩阵）
– 相似度计算：Cosine、点积、质心距离
4. 用矩阵列出对象之间的距离、相似度
5. 用字典保存上述矩阵（节省空间）
D={(1,1):0,(1,2):2,(1,3):6...(5,5):0}
6. 评价方法
– 内部评价法（Internal Evalution）：
• 没有外部标准，非监督式
• 同类是否相似，跨类是否相异
DB值越小聚类效果越好，反之，越不好
– 外部评价法（External Evalution）：
• 准确度（accuracy）: (C11+C22) / (C11 + C12 + C21 + C22)
• 精度（Precision）: C11 / (C11 + C21 )
• 召回（Recall）: C11 / (C11 + C12 )
• F值（F-measure）：
β表示对精度P的重视程度，越大越重视，默认设置为1，即变成了F值，F较高时则能说明聚类效果较好。
四 、 有哪些聚类算法
主要分为 层次化聚类算法 ， 划分式聚类算法 ， 基于密度的聚类算法 ， 基于网格的聚类算法 ， 基于模型的聚类算法等 。
4.1 层次化聚类算法
又称树聚类算法，透过一种层次架构方式，反复将数据进行分裂或聚合。典型的有BIRCH算法，CURE算法，CHAMELEON算法，Sequence data rough clustering算法,Between groups average算法,Furthest neighbor算法,Neares neighbor算法等。
凝聚型层次聚类 ：
先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。
算法流程：
1. 将每个对象看作一类，计算两两之间的最小距离；
2. 将距离最小的两个类合并成一个新类；
3. 重新计算新类与所有类之间的距离；
4. 重复2、3，直到所有类最后合并成一类。
特点：
1. 算法简单
2. 层次用于概念聚类（生成概念、文档层次树）
3. 聚类对象的两种表示法都适用
4. 处理大小不同的簇
5. 簇选取步骤在树状图生成之后
4.2 划分式聚类算法
预先指定聚类数目或聚类中心，反复迭代逐步降低目标函数误差值直至收敛，得到最终结果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering，CLARANS等
经典K-means：
算法流程：
1. 随机地选择k个对象，每个对象初始地代表了一个簇的中心；
2. 对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；
3. 重新计算每个簇的平均值，更新为新的簇中心；
4. 不断重复2、3，直到准则函数收敛。
特点：
1.K的选择
2.中心点的选择
– 随机
– 多轮随机：选择最小的WCSS
3.优点
– 算法简单、有效
– 时间复杂度：O(nkt)
4.缺点
– 不适于处理球面数据
– 密度、大小不同的聚类，受K的限制，难于发现自然的聚类
4.3 基于模型的聚类算法
为每簇假定了一个模型，寻找数据对给定模型的最佳拟合，同一”类“的数据属于同一种概率分布，即假设数据是根据潜在的概率分布生成的。主要有基于统计学模型的方法和基于神经网络模型的方法，尤其以基于概率模型的方法居多。一个基于模型的算法可能通过构建反应数据点空间分布的密度函数来定位聚类。基于模型的聚类试图优化给定的数据和某些数据模型之间的适应性。
SOM 神经网络算法 ：
该算法假设在输入对象中存在一些拓扑结构或顺序，可以实现从输入空间(n维)到输出平面(2维)的降维映射，其映射具有拓扑特征保持性质,与实际的大脑处理有很强的理论联系。
SOM网络包含输入层和输出层。输入层对应一个高维的输入向量，输出层由一系列组织在2维网格上的有序节点构成，输入节点与输出节点通过权重向量连接。学习过程中，找到与之距离最短的输出层单元，即获胜单元，对其更新。同时，将邻近区域的权值更新，使输出节点保持输入向量的拓扑特征。
算法流程：
1. 网络初始化，对输出层每个节点权重赋初值；
2. 将输入样本中随机选取输入向量，找到与输入向量距离最小的权重向量；
3. 定义获胜单元，在获胜单元的邻近区域调整权重使其向输入向量靠拢；
4. 提供新样本、进行训练；
5. 收缩邻域半径、减小学习率、重复，直到小于允许值，输出聚类结果。
4.4 基于密度聚类算法
只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类，擅于解决不规则形状的聚类问题，广泛应用于空间信息处理,SGC,GCHL，DBSCAN算法、OPTICS算法、DENCLUE算法。
DBSCAN：
对于集中区域效果较好，为了发现任意形状的簇，这类方法将簇看做是数据空间中被低密度区域分割开的稠密对象区域；一种基于高密度连通区域的基于密度的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据中发现任意形状的簇。
4.5 基于网格的聚类算法
基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构（即量化空间）上进行。这种方法的主要优点是它的处理 速度很快，其处理速度独立于数据对象的数目，只与量化空间中每一维的单元数目有关。但这种算法效率的提高是以聚类结果的精确性为代价的。经常与基于密度的算法结合使用。代表算法有STING算法、CLIQUE算法、WAVE-CLUSTER算法等。
B. 用于数据挖掘的聚类算法有哪些，各有何优势
聚类方法的分类，主要分为层次化聚类算法，划分式聚类算法，基于密度的聚类算法，基于网格的聚类算法，基于模型的聚类算法等。
而衡量聚类算法优劣的标准主要是这几个方面：处理大的数据集的能力；处理任意形状，包括有间隙的嵌套的数据的能力；算法处理的结果与数据输入的顺序是否相关，也就是说算法是否独立于数据输入顺序；处理数据噪声的能力；是否需要预先知道聚类个数，是否需要用户给出领域知识；算法处理有很多属性数据的能力，也就是对数据维数是否敏感。
.聚类算法主要有两种算法，一种是自下而上法（bottom-up），一种是自上而下法（top-down）。这两种路径本质上各有优势，主要看实际应用的时候要根据数据适用于哪一种，Hierarchical methods中比较新的算法有BIRCH主要是在数据体量很大的时候使用；ROCK优势在于异常数据抗干扰性强……
关于数据挖掘的相关学习，推荐CDA数据师的相关课程，课程以项目调动学员数据挖掘实用能力的场景式教学为主，在讲师设计的业务场景下由讲师不断提出业务问题，再由学员循序渐进思考并操作解决问题的过程中，帮助学员掌握真正过硬的解决业务问题的数据挖掘能力。这种教学方式能够引发学员的独立思考及主观能动性，学员掌握的技能知识可以快速转化为自身能够灵活应用的技能，在面对不同场景时能够自由发挥。点击预约免费试听课。
C. 层次聚类分析案例（三）
之前的笔记：
聚类介绍： 点这里
层次聚类分析案例（一）
层次聚类分析案例（二）
获取全基因组表达数据的能力是一项计算复杂度非常高的任务。由于人脑的局限性，是无法解决这个问题。但是，通过将基因分类进数量较少的类别后再进行分析，就能将基因数据加工到更易理解的水平。
聚类的目标是将一组基因进行划分，使相似的基因落入同一个簇，同时不相似的基因落入不同的簇。这里需要考虑的关键问题是如何定义相似性，以及处理已分类基因。这里我们使用两种基因类型的感光性来探索基因聚类问题。
准备工作
为了进行层次聚类，我们使用从实验鼠身上采集的数据集。
第1步：收集和描述数据
该任务使用名为GSE4051_data和GSE4051_design的数据集。该数据集以标准格式存储在名为GSE4051_data.csv和GSE4051_design.csv的CSV格式的文件中。数据获取路径： 在这里
GSE4051_data数据集包含29949行数据和39个变量。数值型变量如下：
GSE4051_design数据集包含39行数据和4个变量。数值型变量是：sidNum
非数值型变量是：sidChar；devStage；gType；
具体实施步骤以下为实现细节。
第2步：探索数据
RColorBrewer包是一个R包，可从 http://colorbrewer2.org 获取，它提供地图和其他图形的彩色模板。
pvclust包用来实现非确定性的层次聚类分析。在层次聚类中，每个簇通过多尺度有放回抽样计算p值。一个簇的p值在0～1之间。p值有两种类型：近似无偏（approximately unbiased，AU）和有放回概率（bootstrap probability，BP）值。AU p值通过多尺度有放回采样方法计算，经典的有放回采样方法用来计算BP p值。AU p值相比BP p值存在优效性偏见。
xtable包可以生成LaTeX格式的表格。使用xtable可以将特定的R对象转换成xtables。这些xtables能够以LaTeX或HTML的格式输出。
plyr包被用来进行分置合并（split-apply-combine，SAC）过程。它将一个大的问题切分成易处理的小块，在每个小块上进行操作，然后将所有小块合并起来。
载入以下包：
让我们探索并理解变量间的关系。从导入名为GSE4051_data.csv的CSV文件开始。我们将该文件数据存储到GSE4051_data数据框中：
接下来，输出GSE4051_data数据框的信息。str（）函数返回GSE4051_data的结构信息。它简略显示了GSE4051_data数据框的内部结构。max.level指明了为了显示网状结构的最大等级。
结果如下：
下面，我们导入名为GSE4051_design.csv的CSV文件，将其数据保存到GSE4051_design数据框中：
输出GSE4051_design数据框的内部结构。
结果如下：
第3步：转换数据
为了便于后续的可视化阶段，需要对每一行数据进行拉伸操作。这是由于在目前的要求下，不同基因表达之间存在绝对值的差距，因此需要对每一行数据进行拉伸。
中心化变量和创建z值是两个常见的数据分析方法。scale函数中心化并拉伸数值型矩阵的列。
变换矩阵。传入GSE4051_data数据框用t（）函数进行数据框变换。
接下来，我们输出GSE4051_data数据框的信息。通过设置give.attr=FALSE，次级结构的属性不会被显示。
结果如下：
round（）函数用于舍入到最接近的整数。语法形式只有1种：Y = round(X)，这里的X可以是数，向量，矩阵，输出对应。
head（）函数返回一个向量、矩阵、表、数据框或函数的头部。GSE4051_data和trans_GSE4051_data数据框被当作对象传入。rowMeans（）函数计算每列的平均值。data.frame（）函数创建数据框耦合变量集合，并且共享许多指标的性质：
结果如下：
第4步：训练模型
接下来是训练模型。第一步是计算距离矩阵。dist（）函数用来计算并返回距离矩阵，可以使用特定的距离度量方法来计算数据矩阵中各行间的距离。这里可使用的距离度量方法有欧式距离、最大距离、曼哈顿距离、堪培拉距离、二进制距离，或闵可夫斯基距离。这里使用欧式距离。欧式距离计算两个向量间的距离公式为sqrt（sum（（x_i-y_i）^2））。转换后的trans_GSE4051_data数据框被用来计算距离。结果存储在pair_dist_GSE4051_data数据框中。
接下来，使用interaction（）函数计算并返回gType、devStage变量间相互作用的无序因子。无序因子的结果连同GSE4051_design数据框一同被传入with（）函数。该函数计算产生一个新的因子代表gType、devStage变量的相互作用：
summary（）函数用来生成GSE4051_design$group数据框的结果总结：
结果如下：
下面，使用多种不同的联合类型计算层次聚类。
使用hclust（）函数对n个不同对象进行聚类分析。第一个阶段，每个对象被指派给自己的簇。算法在每个阶段迭代聚合两个最相似的簇。持续该过程直到只剩一个单独的簇。hclust（）函数要求我们以距离矩阵的形式提供数据。pair_dist_GSE4051_data数据框被传入。
在第一个例子中使用single聚类方法：
结果如下：
在第二个例子中使用complete聚集方法。
调用pr.hc.complete的结果是显示所使用的聚集方法、距离计算方法和对象数量：
结果如下：
在第三个例子中使用average聚类方法：
调用pr.hc.complete的结果是显示所使用的聚集方法、距离计算方法和对象数量：
结果如下：
在第四个例子中使用ward聚类方法：
pr.hc.ward的调用结果是显示所使用的聚集方法、距离计算方法和对象数量：
结果如下：
plot（）函数是绘制R对象的通用函数。
第一次调用plot（）函数，传递pr.hc.single数据框作为输入对象：
结果如下：
第二次调用plot（）函数，传入pr.hc.complete数据框作为输入对象：
结果如下：
第三次调用plot（）函数，传入pr.hc.average数据框作为输入对象：
结果如下：
第四次调用plot（）函数，传入pr.hc.ward数据框作为输入对象：
结果如下：
第5步：绘制模型
plot（）函数是绘制R对象的通用函数。这里，plot（）函数用来绘制系统树图。
rect.hclust（）函数强调不同的簇，并在系统树图的枝干上绘制长方形。系统树图首先在某个等级上被剪切，之后在选定的枝干上绘制长方形。
RColorBrewer使用从 http://colorbrewer2.org 获得的包来选择绘制R图像的颜色模板。
颜色分为三组：
最重要的一个RColorBrewer函数是brewer.pal（）。通过向该函数传入颜色的数量和配色的名字，可以从display.brewer.all（）函数中选择一个配色方案。
在第一个例子中，pr.hc.single作为一个对象传入plot（）函数：
结果如下：
下面创建热度图，使用single聚集方法。heatmap（）函数默认使用euclidean聚集方法：
结果如下：
在第二例子中，pr.hc.complete作为对象传入plot（）函数：
结果如下：
下面使用complete聚集方法创建热度图：
结果如下：
在第三个例子中，pr.hc.average作为对象传入plot（）函数：
结果如下：
下面创建average聚集方法的热度图：
结果如下：
在第四个例子中，pr.hc.ward作为对象传入plot（）函数：
结果如下：
下面绘制ward聚集方法的热度图：
结果如下：