# 数据仓库与数据挖掘 ## 中英文对照 | eng | abbr | chn | | --------------------------------------- | --------- | ---------------------------- | | Data Warehouse | DW | 数据仓库 | | Data Base | DB | 数据库 | | Data Mining | DM | 数据挖掘 | | Knowledge Discovery in Database | KDD | 数据库中的知识发现 | | Decision Support System | DSS | 决策支持系统 | | System Development Life Cycle | SDLC | 应用需求驱动 | | Data Driven Development Life Cycle | CLDS | 数据中心驱动 | | On-Line Analytical Processing | OLAP | 联机分析处理 | | On-Line Transcation Processing | OLTP | 联机交易处理 | | Relational/Multidimensional/Hybird OLAP | R/M/HOLAP | 关系型/多维/混合联机分析处理 | | Attribute-Oriented Induction | AOI | 面向属性的归纳方法 | | Associaction Rule Mining | ARM | 关联规则挖掘 | | K Nearest Neighborhood | KNN | K近邻算法 | | Concept Learning System | CLS | 概念学习系统 | | Classification and Regression Tree | CART | 分类回归输 | | AGglomerative NESting | AGNES | 凝聚的层次聚类 | | DIvisive ANAlysis | DIANA | 分类的层次聚类 | ## 1 数据仓库与数据挖掘概述 数据挖掘的定义：数据挖掘是从大量的数据中挖掘出隐含的，未知的，用户可能感兴趣的和对决策有潜在价值的知识和规则 数据挖掘出现的背景：数据膨胀，知识匮乏；数据背后可能蕴含有能够帮助更好分析事物与做出决策的知识 数据仓库内的数据可能来源于数据库，但数据仓库和数据库存在本质的不同 数据挖掘的数据源必须是真实的，大量的，含噪声的 数据挖掘的常用模式 * 关联分析（描述） 反映一个事件与其他事件依赖或关联的知识 * 聚类分析（描述） 最大化类内相似性，最小化类间相似性 * 分类（预测） 反映同类事物共同性质的特征型只是和不同事物之间的差异型特征知识 * 孤立点分析（预测） 对差异和极端特例的描述 聚类与分类的比较 | | 聚类 | 分类 | | ------------------ | -------------------------------------- | ------------------------------------ | | 监督与否 | 无监督学习，没有预先设定的类 | 有监督学习，有预先设定的类，有训练集 | | 建立模型或训练与否 | 否，仅是为了发现实体与属性间的函数关系 | 是，目的是为了预测分类 | ## 2 数据仓库 数据仓库是为构建**分析型数据处理环境**而出现的一种数据存储和组织技术 数据仓库之父：Willian H.Inmon 数据仓库的作用： * 存储经过加工处理的用于决策的数据 * 查询和决策分析的依据 数据仓库的特征： * 面向主题 数据仓库的中数据组织的**基本原则**，都是围绕某一主题组织展开的 （关系型数据库内的数据通常是面向日常操作和**事务处理**而组织的） * 集成的 数据仓库是通过集成多个异种数据源来构造的 数据进入数据仓库前需要完成数据清理和数据集成，主要是消除冲突： * 不一致 * 同名异义 * 异名同义 * 单位不统一 * 随时间而变化的 数据仓库不同于操作数据库，其一般只进行数据的初始装载和数据查询，不会进行数据库更新（update）操作 通常是定期加载一段数据，并不是是说数据仓库中的数据永恒不变（在某个时间点保持不变） * 不容易丢失的 数据仓库从历史的角度提供信息 数据仓库中的每一个关键结构**都隐式或显式地包含时间信息，时间维在数据仓库中非常重要** 应用数据库通常进行事务型处理，而数据仓库进行**分析型处理** 数据仓库是一种存储技术，数据挖掘是一种分析技术。数据仓库能够很好地集成数据，为数据挖掘提供了一个绝佳的平台（但并不意味着数据仓库是数据挖掘的必要条件） 数据仓库基于多维数据模型，也就是**数据立方体**，虽说是立方体，但事实上是一个n维的结构，每一个维度表示一个数据范畴 概念分层：定义一个映射序列，将低维概念映射到更一般的高层概念，比如表示location，就可以从city->province/state->country->continent。这是对**单个维**上的操作 概念分层为不同级别上的数据汇总提供了良好的基础 方体的格：给定一个维的集合，在不同汇总级别上给出的数据立方体称为方体的格（本质上一个切片/切块的操作） 每个方体的格都在不同的汇总级别或不同的数据子集显示数据 0-D方体存放最高层的汇总，称作顶点方体，存放最底层汇总的方体，称为基本方体  数据仓库用**概念包图**表示概念模型，其包括： * 维度 分析所需的数据范畴维度 * 级别 确定各个维度的详细类别``name(count)``，需要分别指出各类别的数量 * 度量（指标与事实） 用于进行分析的数值化信息  数据仓库的逻辑模型通常由下列模型表示： * 基本概念 多维数据模型围绕中心主题组织，该主题用事实表表示 事实表包括事实与维关键字（->维表） 每一个维都有一个维表与事实表关联 * 星型模型 **一个事实表在中心**，周围围绕连接着维表 可能**产生冗余**  * 雪花模型 在星座模型的基础上进一步**规范化维表到一些附属表**里 增加复杂性，降低性能，通常不采用  * 星座模型 多主题的数据仓库系统采用 数据仓库通常采用分布式/集中式存储去存储数据 数据仓库设计与传统数据库设计的不同 | | 数据仓库 | 数据库 | | -------- | ------------------------------------------------------------ | ------------------------------ | | 处理类型 | 面向主题的分析型数据处理环境，从基本主题开始，不断发展新主题 | 面向业务 | | 需求 | 通常需求不确定，比较灵活 | 确定的应用处理需求 | | 设计目标 | 建立数据分析环境，支持用户快速分析查询 | 高效完成事务处理操作，增删改查 | | 数据来源 | 通常来自与OLTP系统，经过转换，重组，综合 | 企业的业务流程中产生的数据 | | 设计方法 | 以数据驱动为中心，需求驱动辅助结合 | 应用需求驱动 | ## 4 联机分析处理（OLAP） E.F.Codd 提出了OLAP的概念 OLAP可以理解成多维数据分级工具的集合 OLTP是传统的关系型数据的主要应用，主要是实时的增删改查，为了完成日常事务需求 OLAP是数据仓库的主要应用，可以完成复杂的分析操作，提供直观的查询分析结果 OLAP所用的数据通常都来自于OLTP系统，但需要经过数据清理和集成 OLAP特性： * 快速性 * 可分析性 * 多维性 **多维性是OLAP的最关键属性** * 信息性 OLAP的分析方法： * 切片 * 广义切片：n维中确定1个维度，降为n-1维 * 狭义切片：n维中确定n-2个维度，降为2位 * 切块 * 广义切块：n维中选定1个维度的取值区间，**没有降维** * 狭义切块：n为中选定一个三维子集 * 旋转 * 维度交换 * 钻取 * 下钻：从汇总数据深入到细节数据进行观察或增加新维 * 上钻：将某一维度上的低层次细节数据概括到高层次的汇总数据 * 二者的操作实际上都依赖于**概念分层** OLAP的数据组织： * Relational OLAP 利用关系型数据库存储和管理基本数据 具有良好的可扩展性 * Multidimensional OLAP 利用多维数据库来存储和管理基本数据 索引快速 * Hybrid OLAP 常用的维度使用MOLAP，不常用的使用ROLAP 充分利用ROLAP的可伸缩性和MOLAP的快速计算 | | MOLAP | ROLAP | | ---------------- | ----- | ----- | | 数据存取速度 | 快 | 慢 | | 维度变化的适应性 | 差 | 好 | ## 5 数据预处理 脏数据： 1. 杂乱性 2. 重复性 3. 不完整性 4. 噪声数据 数据预处理的方法： 1. 数据清理 2. 数据集成 3. 数据变换 4. 数据归约 数据清洗： 1. 空缺值 1. 忽略该元组 2. 人工填写空缺值 3. 使用属性的平均值填充空缺值 4. 使用与给定元组属同一类的所有样本的平均值 5. 使用一个全局变量填充空缺值（Unknown） 6. 使用最可能的值填充空缺值 2. 噪声数据 1. 分箱 1. 排序数据，分到等深（每个箱的个数相同）/等宽（箱子的区间相同）的箱中 2. 按平均值/中值/边界值平滑 2. 聚类 3. 计算机和人工检查结合 4. 回归 4. 不一致数据 数据集成： 1. 模式匹配 整合不同数据源中的元数据 2. 数据冗余 可以通过计算两两相关系数发现 $\begin{align}r_{A,B}=\frac{\sum(A-\overline A)(B-\overline B)}{(n-1)\sigma_A \sigma_B}\end{align}$ 3. 数据值冲突 数据变换： 1. 平滑处理 从数据中消除噪声 分箱 2. 聚类操作 对数据进行综合 汇总分类 3. 规范化 将数据转换到较小的区间内 1. 最大-最小规范化 $\begin{align}v'=\frac{v-min_A}{max_A-min_A}\cdot (new\_max_A-new\_min_a)+new\_min_A \end{align}$ 2. z-score规范化 $\begin{align}v'=\frac{v-mean_A}{standard\_dev_A}\end{align}$ 3. 小数定标规范化 数据归约： * 在不影响最终挖掘结果的前提下，尽可能缩小所挖掘数据的规模 * 用于数据规约的时间不应当超过或抵消在归约后的数据集上挖掘节省的时间 数据归约的常用策略： 1. 数据立方体聚集 降维操作 2. 维归约 检测并删除不相关，弱相关或是冗余的属性维 方法：属性自己选择 1. 逐步向前选择（每次选最好的加入空集合） 2. 逐步向后删除（每次选最差的移出集合） 3. 向前选择和向后删除相结合 4. 判定树归纳 3. 数据离散化 1. **分箱** 利用各个分箱的均值和中值替代每个分箱内的值 2. **基于熵的离散化** 3. **通过自然划分分段，3-4-5划分** 4. 聚类 ## 6 概念描述：特征规划与比较 从数据分析的角度，数据挖掘可分为两类： 1. 描述式数据挖掘 2. 预测式数据挖掘 数据概化是将大的任务相关的数据集从较低的概念层抽象到较高的概念层的过程 数据概化的方法 1. 数据立方体（OLAP）方式 降维分析 只能够处理非数值类型（离散类型）的维度 缺乏智能分析，无法自动确定分析中该用到哪些维，以及该概化到哪个层次 2. 面向属性的归纳方法（AOI） 通过考察任务相关的数据中每个属性的不同值的个数，进行概化（属性删除或概化） 通过合并相等的，概化的广义元组，并累计计数，进行聚集操作 * 属性删除的基本原则： 若一个属性有大量不同数值，且没有定义概化操作符或其较高层次的概念可以借由其他属性表示，则将其删除 * 属性概化的基本原则 若一个属性有大量不同数值，且存在定义的概化操作符，则对其进行概化操作 * 判定属性大量不同数值的原则 1. 属性概化阈值控制 若属性不同值的个数大于阈值，则进行删除或概化 2. 概化关系阈值控制 若概化操作以后的不同广义元组的个数超过该阈值则进一步概化，否则不再概化 * 面向属性归纳的结果表示 1. 表格，图表表示法 2. 定量描述规则 t权计算方式： $\begin{align} t-weight_a=\frac{count(q_a)}{\sum_{i=1}{N}(q_i)} \end{align}$ 一般来说通过这样的式子表示 $\forall X, targt\_class(X) \Rightarrow \text condition_{1}(X)\left[t: w_{1}\right] \vee \ldots \vee \text { condition}_{n}(X)\left[t: w_{n}\right]$ 属性相关分析是指，对于给定的类，如果某属性或维的值可用于区分该类或其他类，则该属性被认为是任务高度相关的，我们就是要去过滤掉不相关或弱相关的属性，而只保留最关键（强相关）的属性 属性相关分析的方法： 1. 基于信息增益的属性选择过程 决策树归纳学习算法ID3 运用了**熵**的概念作为启发式函数 $\begin{align}I\left(s_{1}, s_{2}, \ldots, s_{m}\right)=-\sum_{i=1}^{m} \frac{s_{i}}{s} \log _{2} \frac{s_{i}}{s}\end{align}$ 重点掌握计算： 1. 根据训练集，求得初始不确定度$I(S)$ 2. 分别计算知道属性$I$之后的不确定度$E(I)$，做差可得到信息增益$G(I)$，选择最大的，作为决策属性 3. 分别在各个子树上进行决策 挖掘类比较： 与基于汇总的方法相比，需要两个数据集，一个是目标数据集，一个是对比数据集 属性概化需要在所有比较类上同步进行 比较概念描述的步骤： 1. 数据收集，分为目标数据集和对比数据集 2. 属性相关分析，如果属性个数过多，需要进行属性相关分析 3. 同步概化，根据需要同步概化两个数据集 4. 挖掘结果表示 比较概念结果的表示： 1. 图，表，可视化图形 2. 基于规则的表述 d权 常见的统计度量指标： 中心趋势：均值，中位数，众数（模） 离散趋势：四分位数，方差，标准差 ## 7 关联规则挖掘 关联规则挖掘发现的是大量数据中**项集之间**的关联或相关联系 关联规则挖掘的主要对象是交易型数据库，购物篮分析是关联规则挖掘的最初形式 关联规则通常用如下形式表示 $A \Rightarrow B [support=2\%, confidence=60\%]$ $support$支持度，表示总体数据记录中，同时包含有项集$A$与项集$B$的记录数占比 $confidence$置信度，表示在所有包含有项集$A$的数据记录中，同时包含有项集$B$的记录数占比 置信度表示规则可信度，置信度过小，则该规则不具有关联性或关联性弱，无意义 支持度表示模式在总体数据中的出现频率，支持度过小则该规则适用性差，适用面窄 同时具有较高置信度和支持度（较高的概念并不唯一，其来自于数据挖掘过程中的用户定义）的关联规则被称为**强关联规则** 关联规则的分类： * 基于关联规则中变量的不同类别 * 布尔型：离散的，可枚举的，种类化的 * 数值型：可比的，可加的 * 基于关联规则中数据的不同抽象层次 * 单层关联规则：所有变量均不考虑层次关系 * 多层关联规则：考虑变量与变量之间可能存在的层次关系 * 同层关联规则：挖掘同层次之间的关联规则，如：相机$\Rightarrow$手机 * 层间关联规则：挖掘不同层次（通常尤其指父层次与子层次之间）之间的关联规则，如：相机$\Rightarrow$索尼相机 * 基于关联规则中涉及的不同数据维数 * 单维关联规则：只涉及到一个属性维度，如：均是购买商品维度 * 多维关联规则：设计多个属性维度，如：用户购买的商品与其在超市内的滞留时间的关系 关联规则挖掘（Apriori算法）： * 核心：找出所有满足最小支持度的频繁项集 * 原理 * 任何一个频繁项集的子集必定是频繁项集 * 任何非频繁项集的超集都为非频繁项集 * 步骤 * Apriori算法利用**逐层迭代**来计算数据库中的频繁项集。 * 第$i$次迭代计算出所有频繁$i$项集。每一次迭代有两个步骤：产生候选集；计算和选择候选集得到频繁$i$项集 * 在频繁$i-1$项集的基础上，做连接运算，得到候选$i$项集 * 连接运算的操作：对频繁$i-1$项集的所有属性集中取出$i$个属性 * 计算候选$i$项集的支持度，保留满足最小支持度的项集，就得到频繁$i$项集 强关联规则 * 当得到最大频繁项集后，进行置信度计算，最终得到 * 多层关联规则： * 在多个抽象层间挖掘关联规则 * 多层关联规则挖掘的度量方法仍可以沿用"支持度-置信度框架" * 有两种设置支持度的策略： | $\quad$ | 一致支持度 | 递减支持度 | | ----- | ---------- | ---------- | | 介绍 | 对于所有层使用一致的最小支持度，在每一层挖掘时，使用相同的最小支持度阈值 | 每个抽象层均有其最小支持度阈值，在较低层使用递减的最小支持度 | | 优势 | 简单易行，只需要设置一个最小支持度阈值即可 | 能够较好匹配多层的挖掘过程，能够自适应设置支持度阈值，不容易丢失或带来无关的关联规则 | | 缺陷 | 支持度太高会导致较低抽象层中丢失规则，太低则会导致较高抽象层中出现无关规则（与多层关联规则的相性不合） | 每层均需要设置，比较繁重 | * 搜索策略 * 逐层独立 * 层交叉单项过滤 * 层交叉k-项集过滤 * 多维关联规则： * 若将数据库的每个属性或数据仓库的每个维看作一个谓词，可挖掘得到多维关联规则 * 针对数值属性，在进行关联规则挖掘前应该首先进行离散化 * 然后，再沿用“支持度—置信度”原则，完成关联规则的发掘 ## 8 分类数据挖掘 分类可用于**预测**。从历史数据纪录中自动推导出对给定数据的推广描述，从而能对未来数据进行**类预测** 分类方法： * 基于距离的分类方法 * 决策树分类方法 * 贝叶斯分类方法 数据分类的基本过程： * 准备数据 完成[数据的预处理](#5-数据预处理) * 数据清理 * 相关性分析（删除不相关和冗余属性） * 数据变换 * 建立分类模型 通过某种分类算法对训练集进行训练，得到分类模型。监督学习过程，数据集必须带有类标号 * 使用模型进行分类 将数据分为训练集与测试集，用测试集去衡量训练分类的效果  * 评估训练模型 * 预测的准确性 * 建立模型的速度/运行模型的速度 * 对噪声与空缺值的鲁棒性 * 面对大量数据的可伸缩性 * 模型的可理解性 * 规则的优越性 * ... * 基于距离的分类算法 * 常见的距离度量 * 欧几里德距离 * 曼哈顿距离 * （加权）明斯克夫斯基距离（是欧几里德距离和曼哈顿距离的概化） * k-近邻算法（KNN） * 通过测量不同特征值之间的距离（通常为欧几里德距离）的方法进行分类 * 直接找出与目标最接近的$k$个样本，目标就归属于这$k$个样本中出现最频繁的类 * k值的大小需要通过大量的实验来选择：过小预测比较准确，但容易发生过拟合；过大则可以减少估计误差，但容易产生近似误差 * 决策树分类算法 * 基本的决策树生成算法是一个**贪心算法**，采用**自上而下、分而治之的递归**方式来构造。决策树上的各个分支是在对数据不断分组的过程中**逐渐生长**出来的 * **测试属性的选择是构建决策树的关键环节**，不同的决策树算法在此使用的技术都不尽相同 * 在决策树算法中，所有属性均为符号值，即离散值，因此必须对数据进行**离散化操作** * CLS * 最早期的算法，提出了决策树学习算法的理论依据与框架， * 但并没有对测试节点的选择策略给出标准和依据（**选择节点属性**是决策树学习算法中重要的研究课题） * ID3 * 基于信息熵，提出了一种解决属性选择问题的一种思路 * 始终选择**具有最大信息增益的属性**作为当前划分节点 * 基本思想：以信息熵为度量，用于决策树节点的属性选择，**每次优先选取信息量最多的属性**，亦即能使熵值变为最小的属性，以构造一棵熵值下降（不确定性降低）最快的决策树，到叶子节点处的熵值为0 * 优点： * 算法简单，易于理解 * 缺点 * 偏向分割属性中取值多的一个（因为可以带来最大的信息熵降低） * 只能处理离散属性，无法处理数值属性（必须进行离散化） * 无法对未知的分割属性进行操作 * 不包含树剪枝，容易受到噪声和波动的影响 * C4.5 * 对ID3的几个缺点都进行了改进与优化 | 11ID3缺点 | C4.5改进 | | -------------------------- | ---------------------------------- | | 偏向分割属性中取值多的一个 | 引入增益比例 | | 只能处理离散分隔分割 | 引入基于熵的离散化 | | 无法对位置分割属性处理 | 利用平均值或概率法补全分割属性取值 | | 无树剪枝 | K阶交叉验证 | * CART * 采用基于最小距离的基尼指数估计函数 * 生成**二叉树**（ID3和C4.5都不一定是二叉树） * 基尼系数 * $\begin{align}Gini(D)=1-\sum_{i=1}^{m}{p_i}^2\end{align}$ * 取值越小，表达的不确定性越小 * CART分类树必须是二叉结构 * 计算某个属性有几个二叉结构: 属性值为$n$,有$\begin{align}\frac{2^n-2}{2}\end{align}$种划分方法 * 决策树剪枝 * 先剪枝 * 事先设定树的最大生长高度 * 后剪枝 * 找出完全生长的树并替换 * 贝叶斯分类算法 * 贝叶斯分类的核心思想是根据$A$，$B$分别的先验概率以及$P(B|A)$的后验概率去求$P(A|B)$的后验概率（或相反） * 通俗的说：假如一个人正在吃屎，而我们已经知道"傻子吃屎的概率"，那我们就可以通过贝叶斯概率公式去求出来"吃屎的是傻子的概率"，同时，我们还可能去求出来"吃屎的是天才的概率"，以此类推，就可以把这个正在吃屎的人划归到最可能的那一类人中 * 若事件$A_1,A_2,A_3...A_n$构成互斥的$n$个事件，且其中的任意一个是事件$B$必要条件 * 则我们就可以反向求出在$B$发生的情况下$$A_i$发生的概率，可以理解为$A_i$对$B$所提供的贡献 * $\begin{align}P(A_i|B)=\frac{P(A_i)P(B|A_i)}{P(B)}=\frac{P(A_i)P(B|A_i)}{\sum_{i=1}^{n}P(A_i)P(B|A_i)}\end{align}$ * 基本贝叶斯分类器是基于各属性相互独立这一假设来进行分类计算的。即，若给定一个数据样本类别，其样本属性的取值应是相互独立的，但现实中很少满足，因为变量之间的相互依赖非常常见。可以通过**贝叶斯信念网络或决策树**去客服 * 例：办公室新来了一个雇员小王，小王是好人还是坏人，大家都在猜测。按人们的主观意识，**一个人是好人还是坏人的概率均为0.5**，**坏人总是要做坏事，好人总是做好事，偶尔也会做一件坏事。一般好人做好事的概率是0.9，坏人做好事的概率是0.2**。一天，小王做了一件好事，则小王是好人的概率有多大，小王究竟为好人还是坏人？ $\begin{align} &P(good\_ppl|do\_good)& \\ &=\frac{P(good\_ppl) P(do\_good|good\_ppl)}{P(good\_ppl)P(do\_good|good\_ppl)+P(bad\_ppl) P(do\_good|bad\_ppl)} &\\ &=\frac{0.5 \times 0.9}{0.5 \times 0.9+0.5 \times 0.2}&\\ &=0.82& \end{align}$ $\begin{align} &P(bad\_ppl|do\_good)& \\ &=\frac{P(bad\_ppl) P(do\_good|bad\_ppl)}{P(good\_ppl)P(do\_good|good\_ppl)+P(bad\_ppl) P(do\_good|bad\_ppl)} &\\ &=\frac{0.5 \times 0.2}{0.5 \times 0.9+0.5 \times 0.2}&\\ &=0.18& \end{align}$ 显然$P(good\_ppl|do\_good)>P(bad\_ppl|do\_good)$，小王是好人的概率更大一些 * 又例： 试求样本：$X=(age="<30", income="medium", student="yes", credit-rating="fair")$的分类，即其是否会买电脑 结论：买电脑的概率大于不买电脑的概率 ## 9 聚类分析 聚类是指对组的数目或者组的结构不用做任何假设的一种发现项目（或者变量）的自然分组方法 聚类分析使用无监督的学习（观察式学习） 聚类分析的原则： * 同一个组内的数据对象具有较高的相似度 * 而不同组中的数据对象是不相似的 聚类分析中相似性的度量： 1. Q型聚类，行聚类，找到**样本之间的关系**并聚类 2. R型聚类，列聚类，找到**变量之间的关系**并聚类 间隔尺度变量（数值型）的测度： 可比可加 标准化后按类/维度计算明可夫斯基距离即可 特例：比例数值变量：可以按照区间标度变量正常处理，但不佳，最好可以采用对数变换log对比例数值变量处理后再当作区间标度变量正常处理 有序尺度变量的测度： 只可比 可以使用对有序尺度变量进行量化$\begin{align}z_{if}=\frac{r_{if}-1}{M_f-1}\end{align}$ 名义尺度变量的测度： 恒定二元尺度变量的相异度计算$\begin{align}d(i,j)=\frac{cnt_{1,0}+cnt_{0,1}}{tot}\end{align}$ 非恒定二元尺度变量的相异度计算$\begin{align}d(i,j)=\frac{cnt_{1,0}+cnt_{0,1}}{tot-cnt_{0,0}}\end{align}$。**负匹配在非恒定二元尺度变量中被认为不重要** 多元名义尺度变量的$\begin{align}d(i,j)=\frac{tot-cnt_{diff}}{tot}\end{align}$ 混合数据类型：    R型聚类： 相似系数：测度变量之间的亲疏程度    类的定义： 1. 任意元素之间距离小于等于阈值$\forall i,j\in S, d_{ij}\leq h$ 2. 集合内任意元素之间的平均距离小于阈值$\forall i,j\in S, \frac{\sum d_{ij}}{k-1}\leq h$ 3. 集合内存在某两个元素之间的距离小于阈值$\exists i,j\in S, d_{ij}\leq h$ 类间距离： 1. 最近/小/短距离 2. 最远距离 3. 平均距离 4. 中间距离 5. 重心距离 基于划分的聚类方法 1. k-均值聚类算法 取各个聚类子集内的数据样本均值作为聚类的代表点 不适合离散型属性，但对于连续型属性具有较好的聚类效果  缺点： * 局部最优而非全局最优 * 用户必须事先给出簇的数目，划分方向，更新分区与停止准则 * 不适合发现大小很不相同或凹状的簇 * 簇必须有定义平均值，不适用于带有类属性的数据 * 对噪声和异常点非常敏感 通常选择误差平方和最小作为收敛准则函数 $\begin{align}E=\sum_{i=1}^{k} \sum_{p \in C_{i}}\left|p-m_{i}\right|^{2}\end{align}$ 2. k-中心点聚类算法 取最接近各个聚类子集内的数据样本均值的点作为聚类的代表点（与k-means不同，其必须是一个实际存在的点）  特点： * 相比于k-means更加健壮，但其时空开销代价更高 基于层次的聚类方法 1. 凝聚层次方法（AGENES） 自底而上，逐步合并相近的对象或组，直到停止 从每个对象都是一个簇开始，每次合并最相近的两个簇，直到达到定义的簇的数目 特点： * 已合并的结果不能撤销 * 时空开销较大 2. 分裂层次方法（DIANA） 自顶而下，逐步分裂，直到停止 簇的直径：一个簇中$max(d_{ij})$ 平均相异度：簇内平均距离$\frac{\sum d_{ij}}{n-1}$ 每次选择直径最大的簇C，找出C内与其他点的平均相异度最大的点p加入分裂簇D，并在C中继续查找更接近D而非C的点，加入D；重复迭代，直到C，D均无变化。这样就将原簇分裂成了两个簇，如此迭代，直到达到定义的簇的数目 基于密度的聚类方法 * 只要一个区域中点的密度（对象或数据点的数目）超过某个阈值，就将其加到与之相近的聚类中去 * DBSCAN通过检查数据集中每个对象的ε-邻域来寻找聚类。 * 如果一个点p的ε-邻域包含多于MinPts个对象，则创建一个p作为核心对象的新簇。 * 然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象，这个过程可能涉及一些密度可达簇的合并。 * 当没有新的点可以被添加到任何簇时，该过程结束。 *