数据挖掘笔记

数据挖掘笔记

习题课

  1. 盒图：五数概括不用判定离群点，盒图要判定离群点
  2. 中位数概括宽度不用+1
  3. OLAP基础操作 专有名词
  4. 15选择（1分）+5填空（2分）+4大题
  5. upd：20-21春学期期末
    • 大题考了用基尼系数做朴素贝叶斯概率、频繁模式挖掘、k近邻聚类、神经网络参数计算（求导大法）。确实都是作业出现过的题型，但是数不好算，聚类和基尼系数要按的计算器太多了。老师最后开始频繁催“算不出来数没关系，写对公式就给绝大部分分；写不出来公式写算法，至少写点东西好给分”。
    • 前几章的计算只考了小题，比如算卡方、选正确的盒图。
    • 小题里有概念题，比如写出三种集成学习算法。
  6. 不挂人但是也不保B+，作业/PJ/期末考三部分占比未知

第一章 引论

数据挖掘/KDD：从大量数据中挖掘有趣模式和知识的过程，通常包括数据清理、数据集成、数据选择、数据变换、模式发现、模式评估、知识表示。

挖掘的对象

  1. 关系数据库：表的汇集，有实体-联系（ER）等数据模型
  2. 数据仓库：从多个数据源收集的信息存储库，存放在一致的模式下，通常驻留在单个站点上。围绕主题组织，从历史的角度提供信息，通常是汇总的。用数据立方体建模。
  3. 事务数据：挖掘频繁项集

数据挖掘功能

  1. 类/概念描述：特征化与区分
  2. 挖掘频繁模式、关联和相关性
  3. 用于预测分析的分类与回归
  4. 聚类分析
  5. 离群点分析

第二章 认识数据

属性

  1. 数据对象用属性描述；属性表示数据对象的一个特征，同义词有属性（数据挖掘、数据库）、特征（机器学习）、变量（统计学）、维（数据仓库）。
  2. 标称属性：意味着“与名称相关”，值是一些符号或事物的名称，是分类的、枚举的、不定量、无序的。只有众数，没有其他数学运算（eg：颜色、编号、职业）。
  3. 二元/布尔属性：01的标称属性。若两种状态有同等价值且权重相同，称为对称的（eg：性别）；否则称为非对称的（eg：病毒阳性），一般将重要结果用1编码。
  4. 序数属性：可能的值之间具有意义的序或秩评定，但是相继值之间的差是未知的（eg：饮料大小杯、成绩等级、职位）。记录不能客观度量的主观质量评估，或通过把数值属性离散化得到。有众数和中位数，没有平均值。
  5. 数值属性：定量的可度量的量。区间标度属性用相等的单位尺度度量，可以做差，但是由于没有真正的零不能做商（eg：华氏温度、日期）；比率标度属性是具有固定零点的数值属性，可以做差和商（eg：开式温标、文档字数、速度）。数值属性都可以求众数、中位数、平均值。
  6. 总结：无序的只有众数、有序的可以求中位数、数值的可以做差和平均值、有零点的可以做商。
  7. 离散属性具有有限或无限可数个值（eg：头发颜色、顾客编号、邮政编码）；不离散的属性是连续属性（可与数值属性互换使用），一般用浮点变量表示。

数据的基本统计描述

  1. 中心趋势度量
    • 均值/mean：算术均值/加权均值（对极端值很敏感）、截尾均值（丢弃高低极端值之后的均值）
    • 中位数/median（对倾斜、非对称数据描述更好）：数据个数为偶数时，中位数不唯一，取中间两个值和它们之间的任意值；对于数值属性，约定取中间两个值的平均值。中位数的近似值。
    • 众数/mode：根据众数个数将数据集合分为单峰的、双峰的、三峰的、多峰的（两个或更多个峰），N峰也称为N模。每个数据值只出现一次，则没有众数。
    • 对于适度倾斜的单峰数值数据，有经验关系：$mean-mode \approx 3(mean-median)$
    • 中列数/midrange：数据集最大和最小值的平均值。
    • 完全对称的单峰频率曲线中，均值、中位数、众数都是相同的中心值。
    • 正倾斜：众数小于中位数。反之则为负倾斜。
  2. 数据散布度量
    • 极差/range：最大值与最小值之差
    • 分位数/quantile：把数据划分成基本上大小相等的连贯集合，有$q-1$个q-分位数，第$k$个q-分位数是值$x$，小于$x$的数据值最多为$k/q$，大于$x$的数据值最多为$(q-k)/q$。2-分位数是中位数，四分位数依次为$Q_1$、$Q_2$、$Q_3$，又常用百分位数。
    • 四分位数极差：$IQR=Q_3-Q_1$，给出被数据的中间一半覆盖的范围。
    • 五数概括：最小观测值、$Q_1$、中位数、$Q_3$、最大观测值。
    • 盒图：端点在四分位数上，长度是IQR，中位数用盒内的线标记，胡须延伸到最大最小观测值。若最大最小观测值距四分位数超过1.5IQR，胡须在距四分位数1.5IQR内最极端的观测值处终止，剩下的情况个别绘出。
    • 方差：到均值距离的平方和的均值，或$(\frac{1}{N}\sum_{i=1}^{n}x_{i}^2)^2-\bar{x}^2$。标准差：方差的平方根，度量关于均值的发散。一个观测一般不会远离均值超过标准差的数倍，最少$(1-\frac{1}{k^2})*100%$的观测值离均值不超过k个标准差。
  3. 基本统计描述的图形显示
    • 分位数图（观察单变量数据分布）：横轴为f值(i-0.5)/N，纵轴为观测值。
    • 分位数-分位数图（观察两个分布之间是否有漂移）：横轴为一个观测值，纵轴为另一个观测值，每个点在两个数据集离对应的分位数相同。若两个观测集数据个数不同，以小的为准，需要在大的观测集里插值。
    • 直方图：标称属性的直方图常被称为条形图。数值属性的直方图横轴为不相交的连续子域（桶/箱），通常是等宽的，纵轴为子域内数据的计数。
    • 散点图（确定两个数值变量之间是否存在联系）：每个值对视为一个代数坐标对，作为一个点画在平面上。左下-右上暗示正相关，左上-右下暗示负相关。

数据可视化

  1. 基于像素的可视化技术：对每一维创建一个窗口。线性填充、空间填充曲线，圆弓分割技术。
  2. 几何投影可视化技术：散点图矩阵（随着维数增加变得不太有效）、平行坐标（视觉上的簇和重叠导致不能有效地显示具有很多记录的数据集）
  3. 基于图符的可视化技术：切尔诺夫脸（容易被用户消化，在表示多重联系的能力方面存在局限性，最多18维，眼睛大小和眉毛的歪斜是重要的）、非对称的切尔诺夫脸（达到36维）、人物线条画（两个维映射到显示轴，其他维映射到人物线条画，数据关于两个显示维相对稠密则结果显示纹理模式）。
  4. 层次可视化技术：世界中的世界（将部分维固定为选定的值，以这个值为原点绘制内世界三维图，在外世界三维图中改变原点位置观察内世界变化）、树图
  5. 可视化复杂对象和关系：标签云（用大小表示次数）、图

度量数据的差异性和相似性

  1. 数据矩阵/二模矩阵：对象-属性结构，n*p。每行对应一个对象，又称数据样本/特征向量。

  2. 相异性矩阵/单模矩阵：对象-对象结构，n*n，存放对象两两之间的邻近度，对称矩阵。对于标称数据，$sim(i,j)=1-d(i,j)$

  3. 标称属性的邻近性度量：$d(i,j)=\frac{p-m}{p}$，m可加权

  4. 二元属性的邻近性度量

    • 对称的二元相异性$d(i,j)=\frac{r+s}{q+r+s+t}$
    • 非对称的二元相异性$d(i,j)=\frac{r+s}{q+r+s}$
    • 非对称的二元相似性$sim(i,j)=\frac{q}{q+r+s}$，称为Jaccard系数。

  5. 数值属性的相异性

    • 先对数据规范化，如变换到$[-1,1]$或$[0,1]$
    • 欧几里得距离，加权的欧几里得距离
    • 曼哈顿距离
    • 度量：满足非负性、同一性、对称性、三角不等式
    • 闵可夫斯基距离/$L_p$范数：各维距离的p次方之和，开p次方，p是不小于1的实数。$L_1$范数为曼哈顿距离，$L_2$范数为欧几里得距离。
    • 上确界距离/$L_{max}$/$L_{∞}$范数/一致范数/切比雪夫距离：各维距离的最大值

  6. 序数属性的邻近性度量：对于第$i$个对象，用对应排位$r_{if}$取代序数属性组$x_{if}$，将每个属性的值域映射到$[0,1]$，$z_{if}=\frac{r_{if}-1}{M_f-1}$，再对$z$使用数值属性的距离度量计算相异性

  7. 混合类型属性的相异性

    • 计算两者均不缺失的所有属性相异性并取平均数
    • 数值属性$d_{ij}^{(f)}=\frac{|x_{if}-x_{jf}|}{max_hx_{hf}-min_hx_{hf}}$
    • 序数属性计算$z$后按数值属性处理
    • 标称属性$d$即为是否相等

  8. 余弦相似性

    • 处理很长的、稀疏的向量，数据往往高度非对称（eg：信息检索、生物学分类）
    • $sim(x,y)=\frac{x*y}{||x||||y||}$，分母为两个向量欧几里得范数（即长度）之积
    • 0代表两个向量正交，余弦值越小向量之间的匹配越大
    • 不遵守度量测度性质，被称为非度量测度
    • 二值属性的余弦相似性可以用共享特征或属性解释，分子是共同具有的属性数，分母是两个向量具有的属性数的几何均值，sim成为公共属性相对拥有的一种度量，$sim(i,j)=\frac{xy}{xx+yy-xy}$，称为Tanimoto系数或Tanimoto距离

第三章 数据预处理

概述

  1. 数据质量的三个要素：准确性、完整性、一致性

  2. 影响数据质量的要素：时效性、可解释性、可信性

  3. 主要步骤：数据清理、数据集成、数据归约、数据变换

数据清理

  1. 缺失值
  2. 噪声数据：分箱、回归、离群点分析
  3. 偏差检测，数据变换两步的迭代过程
  4. 数据清洗工具，数据审计工具，数据迁移工具，ETL工具

数据集成

  1. 实体识别问题：使用元数据
  2. 冗余和相关分析
    • 标称数据的卡方检验：相依表中$o_{ij}$为联合事件观测频度，$e_{ij}$为期望频度，可用$e_{ij}=\frac{count(A=a_i)count(B=b_j)}{n}$计算，卡方=$\sum_{i=1}^c\sum_{j=1}^r\frac{(o_{ij}-e_{ij})^2}{e_{ij}}$，对卡方贡献越大的单元实际计数与期望计数越不符。卡方检验假设A和B是独立的，具有自由度$(r-1)(c-1)$，自由度和置信水平决定拒绝假设的值
    • 数值数据的相关系数/Pearson积矩系数：$r_{A,B}=\frac{\sum_{i=1}^n(a_i-\bar A)(b_i-\bar B)}{n\sigma_A\sigma_B}=\frac{\sum_{i=1}^n(a_ib_i)-n\bar A\bar B}{n\sigma_A\sigma_B}$；r越接近1，正相关越强；越接近-1，负相关越强；r为0，A和B独立。相关性不蕴涵因果关系
    • 数值数据的协方差：$Cov(A,B)=E((A-\bar A)(B-\bar B))=\frac{\sum_{i=1}^n(a_i-\bar A)(b_i-\bar B)}{n}=E(A*B)-\bar A\bar B=r_{A,B}\sigma_A\sigma_B$；协方差为正表示正相关，协方差为负表示负相关；A和B独立时协方差一定为0，但A和B不独立协方差也可能为0，只有当数据满足多元正态分布等限制条件时协方差为0才充分说明数据独立。方差是属性和自身的协方差
  3. 元组重复
  4. 数据值冲突的检测与处理

数据归约

  1. 维归约：小波变换、主成分分析、属性子集选择、属性创建
  2. 数量归约：参数方法（回归、对数-线性模型）、非参数方法（直方图、聚类、抽样、数据立方体聚集）
  3. 数据压缩：有损的、无损的
  4. 离散小波变换（DWT）
    • 将数据向量X变换成不同的数值小波系数向量X’，变换后数据可以截短，仅存放一部分最强的小波系数，消除噪声
    • 有损压缩，比DFT更准确，空间局部性好，对稀疏或倾斜数据和具有有序属性的数据效果好
    • 层次金字塔算法：每次迭代数据减半，先后使用光滑和加权差分函数，得到两个长度为L/2的数据集，分别代表光滑后的版本或低频版本和它的高频内容
    • 有若干族DWT，小波名后的数是小波的消失瞬间
    • 将矩阵乘法用于输入数据，所用的矩阵必须是标准正交的
    • 处理多维数据，首先将变换用于第一个维，然后第二个，复杂度关于立方体中单元的个数是线性的
  5. 主成分分析/PCA
    • 搜索k个最能代表数据的n维正交向量，k<=n
    • 对输入数据规范化，计算k个标准正交向量（主成分），对主成分按重要性或强度降序排列，主成分本质上充当新坐标系，通过去掉较弱的成分（方差较小的那些）来规约数据
    • 可用于有序和无序的属性，可以处理稀疏和倾斜数据，可以用做多元回归和聚类分析的输入
    • 多于二维的多维数据可以通过将问题归约为二维问题来处理
    • 小波变换更适合高维数据，PCA能够更好处理稀疏数据
  6. 属性子集选择
    • 删除不相关或冗余属性，目标是找出最小属性集，使数据类的概率分布尽可能接近原分布
    • 压缩搜索空间的启发式算法：贪心，取局部最优解
    • 确定”最好/差的“属性：统计显著性检验/信息增益度量
    • 具体技术：逐步向前选择、逐步向后删除、逐步向前选择和逐步向后删除的组合、决策树归纳
  7. 回归和对数线性模型
    • 参数化数据归约
    • 线性回归（最小二乘法求解回归系数）、多元回归
    • 对数线性模型：近似离散的多维概率分布，基于维组合的一个较小子集估计多维空间中每个点的概率
    • 都可以用于稀疏数据。回归对倾斜数据可望更好，对数线性模型对高维数据伸缩性好，可达10维
  8. 直方图
    • 等宽直方图，等频/等深直方图
    • 对于近似稀疏和稠密数据，以及高倾斜和均匀的数据，都是非常有效的
    • 多维直方图可以表现属性间的依赖，能有效近似多达5个属性的数据
    • 对于存放具有高频率的离群点，单值桶是有用的
  9. 聚类
    • 直径：簇中两个对象的最大距离
    • 形心距离：簇中每个对象到簇形心（平均对象/空间中的平均点）的平均距离
    • 数据归约中用簇代表替换实际数据，对于能够组织成不同的簇的数据较为有用
  10. 抽样
    • s个样本的无放回简单随机抽样（SRSWOR）
    • s个样本的有放回简单随机抽样（SRSWR）
    • 簇抽样：每次抽取一个簇
    • 分层抽样：数据倾斜时可以帮助确保样本的代表性
    • 得到样本的花费正比例于样本集的大小s，而不是数据集的大小N，因此复杂度亚线性于数据大小，仅根据数据的维数n线性增加
    • 常用来估计聚集查询的回答，通过简单的增加样本大小可以进一步求精
  11. 数据立方体聚集
    • 每个属性都可能存在概念分层，允许在多个抽象层进行数据分析
    • 数据立方体提供对与计算的汇总数据进行快速访问，适合联机数据分析和数据挖掘
    • 在最低抽象层创建的立方体称为基本方体，应当对应于感兴趣的个体实体
    • 最高抽象层的立方体称为顶点方体
    • 不同层创建的数据立方体称为方体，数据立方体可以看作方体的格
    • 回答询问时使用与给定任务相关的最小可用方体

数据变换与数据离散化

  1. 光滑：去掉数据中的噪声，包括分箱、回归和聚类
  2. 属性构造/特征构造：由给定属性创造新属性
  3. 聚集：一般用来维多个抽象层的数据分析构造数据立方体
  4. 规范化/标准化：把属性数据按比例缩放到特定小区间
    • 最小-最大规范化：$v_i’=\frac{v_i-min_A}{max_A-min_A}(max_A’-min_A’)+min_A’$，保持原始数据之间的联系，但新输入落在原始数据值域外可能越界
    • z分数规范化/z-score规范化/零均值规范化：$v_i’=\frac{v_i-\bar A}{\sigma_A}$，实际最大最小值未知或离群点左右了最小-最大规范化时是有用的。标准差可用均值绝对偏差$s_A$替换，对离群点更鲁棒
    • 小数定标规范化：通过移动属性A的小数点位置进行规范化，$v_i’=\frac{v_i}{10^j}$，j是使得$max(|v_i’|)<1$的最小整数
    • 有必要保留规范化参数，以便将来的数据可以用一致的方式规范化
  5. 离散化：将数值属性原始值用区间标签或概念标签替换
    • 监督的离散化和非监督的离散化：是否使用类信息
    • 自顶向下离散化/分裂，自底向上离散化/合并
    • 分箱离散化：等宽/等频分箱，用箱均值/中位数替换箱中的每个值，是非监督的离散化技术，对用户指定的箱个数和离群点很敏感
    • 直方图离散化：非监督，可以递归地用于每个分区，自动产生多级概念分层，用预设概念层数或最小区间长度控制递归过程
    • 聚类
    • 决策树：监督的离散化，选择最小化熵的值作为划分点
    • 相关分析离散化：监督的离散化，ChiMerge，自底向上递归找出具有最小卡方值的相邻区间并合并（对于精确的离散化，相对类频率在一个区间内应当完全一致）
  6. 由标称数据产生概念分层：利用模式和属性值计数信息

第四章 数据仓库与联机分析处理

基本概念

  1. 主要特征：面向主题的、集成的、时变的、非易失的
  2. 使用更新驱动而非查询驱动方法
  3. 操作数据库与数据仓库分离，OLTP和OLAP分离
  4. OLAP系统面向市场（而非面向顾客），管理大量历史数据（而非当前数据），采用星形或雪花模型和面向主题的数据库设计（而非ER模型和面向应用的数据库设计），常常跨越数据库模式的多个版本，存放在多个存储介质上，大部分是只读操作
  5. 三层体系结构：底层是仓库数据库服务器，中间层是OLAP服务器，顶层是前端客户层
  6. 数据仓库模型：企业仓库，数据集市和虚拟仓库
  7. 数据提取、变换和装入
  8. 元数据库：关于数据的数据，应当持久存放和管理（即存放在磁盘上）

数据立方体与OLAP

  1. 数据立方体由维和事实定义，是n维的
  2. 数据立方体称作方体。给定维的集合，可以对给定诸维的每个子集产生一个方体，结果形成方体的格，称作数据立方体。存放最低层汇总的方体称作基本方体，最高层汇总的方体称作顶点方体。
  3. 多维数据模型
    • 星形模式：一个事实表+一组维表
    • 雪花模式：在星形模式的基础上将某些维表规范化
    • 星系模式/事实星座：多个事实表共享维表
    • 数据仓库通常使用事实星座模式，数据集市流行采用星形或雪花模式
  4. 概念分层
    • 模式分层：形成数据库模式中属性的全序或偏序的概念分层
    • 集合分组分层：将给定维或属性的值离散化或分组
  5. 度量的分类和计算
    • 数据立方体度量是一个数值函数，可以对数据立方体空间的每个点求值，通过对给定点的各维-值对聚集数据，计算该点的度量值
    • 度量分类：分布的（可以划分计算，eg：sum、count、min）、代数的（可以由多个划分计算的结果得到，eg：avg、min_N)、整体的（描述子聚集所需的存储没有常数界，eg：median、mode、rank）
  6. 典型的OLAP操作
    • 上卷（roll-up）/上钻（drill-up）：通过沿一个维的概念分层向上攀升，泛化
    • 下钻（drill-down）：通过沿一个维的概念分层向下或引入附加的维，特殊化
    • 切片（slice）：在一个维进行选择
    • 切块（dice）：在两个或多个维进行选择
    • 转轴（pivot）/旋转（rotate）：转动数据视角
    • 钻过（drill-across）：执行涉及多个事实表的查询
    • 钻透（drill-through）：使用关系SQL机制钻透到后端关系表
  7. 星网模型：由从中心点发出的射线组成，其中每一条射线代表一个维的概念分层，概念分层上的每个”抽象级“称为一个足迹，代表 OLAP操作可用的粒度

数据仓库的设计与使用

  1. 商务分析框架：自顶向下视图、数据源视图、数据仓库视图、商务查询视图
  2. 开发方法：瀑布式方法、螺旋式方法
  3. 数据仓库应用：信息处理、分析处理、数据挖掘
  4. 多维数据挖掘/探索式多维数据挖掘/联机分析挖掘/OLAM

数据仓库的实现

  1. compute cube：在操作指定的维的所有子集上计算聚集
  2. 维灾难：n维方体总数=$\prod_{i=1}^n(L_i+1)$
  3. 不物化、完全物化、部分物化
  4. 冰山立方体：只存放聚集值大于某个最小支持度阈值的立方体单元
  5. 外壳立方体
  6. 位图索引，连接索引，复合连接索引，位图连接索引
  7. 关系OLAP（ROLAP）服务器：伸缩性好，映射到关系操作；多维OLAP（MOLAP）服务器：适用稠密子立方体，映射到数组结构；混合OLAP（HOLAP）服务器；特殊的SQL服务器

数据泛化：面向属性的归纳

  1. 属性删除：某个属性有大量不同值但没有泛化操作符，或较高层概念用其他属性表示
  2. 属性泛化：某个属性有大量不同值且存在泛化操作符
  3. 属性泛化控制：属性泛化阈值控制、广义关系阈值控制
  4. 面向属性归纳：关系查询-收集初始关系上的统计量-导出主关系P
  5. 类比较：数据收集-维相关分析-同步泛化-导出比较的表示

第五章 数据立方体技术

基本概念

  1. 基本方体的单元是基本单元，非基本方体的单元是聚集单元
  2. 祖先和后代单元，父母和子女单元
  3. 闭覆盖：一个单元c是闭单元，如果不存在后代d与c有相同的度量值；闭立方体是只由闭单元组成的数据立方体
  4. 立方体外壳，外壳片段
  5. 优化技术：散列、排序、分组、同时聚集和缓存中间结果、由最小的子女聚集、先验剪枝

数据立方体计算方法

  1. 多路数组聚集（MultiWay）：扫描顺序决定保持二维平面在块内存中的最小内存需求量；适合维的基数乘积适中且数据不是太稀疏的情况，但是不能先验剪枝
  2. BUC：自顶向下，容易受维的次序和倾斜数据的影响，理想情况下应先处理最有区分能力的维，应当以维的基数减序处理
  3. Star-Cubing
    • 共享维剪枝
    • 方体树，星树
    • 计算完全立方体，稠密时接近MultiWay，比BUC快；稀疏时比MultiWay快很多，大部分情况下比BUC快
    • 计算冰山立方体，比BUC快
  4. 计算外壳片段：倒排索引，Frag-Shells
  5. 点查询，子立方体查询

高级查询

  1. 抽样立方体
    • 置信区间$\bar x ±t_c\sigma_{\bar x}$，$t_c$与置信水平相关，$\sigma_{\bar x}=\frac{s}{\sqrt l}$是均值的估计标准误差，自由度为$l-1$，$l$为样本数
    • 提升小样本置信度：方体内查询扩展、方体间查询扩展
  2. 排序立方体

多维数据分析

  1. 预测立方体
  2. 多特征立方体：多粒度上多个依赖的聚集的复杂查询
  3. 基于异常的、发现驱动的立方体空间探查
    • SelfExp，InExp，PathExp
    • 给定单元的值和它的期望值之间的差称为残差，残差越大越异常，要对残差定标

第六章 挖掘频繁模式、关联和相关性：基本概念和方法

基本概念

  1. 频繁模式：频繁出现在数据集中的模式，如频繁项集、频繁序列模式
  2. 有趣的关联规则：满足最小支持度阈值和最小置信度阈值
  3. 支持度support(A->B)=P(A$\cup$B)
  4. 置信度confidence(A->B)=P(B|A)=support(A$\cup$B)/support(A)
  5. 闭频繁项集：不存在频繁项集X的真超集Y，使得Y与X在D中支持度相同
  6. 极大频繁项集：不存在频繁项集X的超集Y，使得Y在D中是频繁的

频繁项集挖掘方法

  1. Apriori（先验）算法

    • 先验性质，属于反单调性
    • 连接步，剪枝步
    • 由频繁项集枚举子集，产生关联规则
    • 优化方法：散列技术、事务压缩、划分、抽样、动态项集计数

  2. FP-growth（频繁模式增长）算法

    • 导出频繁项的集合，构造FP树
    • 从表后端的后缀模式开始构造条件模式基

  3. 使用垂直数据格式挖掘频繁项集

    • 不需要扫描数据库来确定k+1项集的支持度

    • 差集技术：数据集稠密和包含长模式时，可以显著降低总开销

  4. 挖掘闭模式和极大模式

    • 项合并
    • 子项集剪枝
    • 项跳过

模式评估方法

  1. 提升度：$lift(A,B)=\frac{P(A\cup B)}{P(A)P(B)}=\frac{P(B|A)}{P(B)}=\frac{conf(A->B)}{sup(B)}$，小于1为负相关，大于1为正相关，等于1为独立
  2. 全置信度：min{P(A|B),P(B|A)}
  3. 最大置信度：max{P(A|B),P(B|A)}
  4. Kulczynski（Kulc）度量：0.5(P(A|B)+P(B|A))
  5. 余弦度量：$\sqrt{P(A|B)+P(B|A)}$
  6. 不平衡比：$IR(A,B)=\frac{|sup(A)-sup(B)|}{sup(A)+sup(B)-sup(A\cup B)}$
  7. 全置信度、最大置信度、Kulc和余弦是零不变的，推荐Kulc和IR配合使用

第七章 高级模式挖掘

多层、多维空间中的模式挖掘

  1. 挖掘多层关联规则
  2. 检查多层关联规则的冗余性：根据规则的祖先，它的支持度和置信度都接近于期望值
  3. 挖掘多维关联规则
  4. 挖掘量化关联规则
  5. 挖掘稀有模式和负模式
    • 稀有模式支持度远低于用户指定的最小支持度阈值
    • 负相关：X和Y都是频繁的，但很少一起出现
    • 直接用sup定义的强负相关并不是零不变的
    • 零不变的强负相关定义：Kulc度量小于负模式阈值

基于约束的频繁模式挖掘

  1. 用模式剪枝约束对模式空间剪枝
    • 反单调的
    • 单调的
    • 简洁的
    • 可转变的
    • 不可转变的
  2. 用数据剪枝约束对数据空间剪枝
    • 数据简洁
    • 数据反单调

挖掘高维数据和巨型模式

  1. 通过模式融合挖掘巨型模式
    • 核模式（核后代）、核比率
    • 鲁棒
    • 模式距离
    • 池初始化-迭代的模式融合

挖掘压缩或近似模式

  1. 通过模式聚类挖掘压缩模式：模式距离
  2. 提取感知冗余的top-k模式
    • 显著性度量S
    • S(p,q)联合显著性，S(p|q)=S(p,q)-S(q)相对显著性
    • 冗余性R(p,q)=S(p)+S(q)-S(p,q)，所以S(p|q)=S(p)-R(p,q)
    • 可以用模式间的距离近似冗余度

模式探索与应用

  1. 频繁模式的语义注解：互信息
  2. 模式挖掘的应用

第八章 分类：基本概念

决策树归纳

  1. 属性选择度量
    • 信息增益：信息需求$Info(D)=-\sum_{i=1}^mp_ilog_2(p_i)$，$p_i$用$|C_{i,D}|/|D|$估计；$Info_A(D)=\sum_{j=1}^v\frac{|D_j|}{D}*Info(D_j)$，$Info_A(D)$越小，分区纯度越高；信息增益$Gain(A)=Info(D)-Info_A(D)$
    • 增益率：分裂信息$SplitInfo_A(D)=-\sum_{j=1}^v\frac{|D_j|}{D}*log_2(\frac{|D_j|}{|D|})$，增益率$GRianRate(A)=\frac{Gain(A)}{SplitInfo_A(D)}$
    • 基尼系数：$Gini(D)=1-\sum_{i=1}^mp_i^2$度量数据分区或训练元组集D的不纯度；考虑二元划分裂时，计算每个结果分区不纯度加权和；对连续值属性，最大化不纯度降低
    • 基于最小描述长度原理的属性
  2. 树剪枝：先剪枝，后剪枝（代价复杂度剪枝算法，应用剪枝集）
  3. 可伸缩性与决策树归纳：雨林（在每个结点维护每个属性的AVC-集），树构造的自助乐观算法（BOAT）
  4. 决策树归纳的可视化挖掘：基于感知的分类（PBC）

贝叶斯分类方法

  1. 贝叶斯定理
    • 后验概率P(H|X)
    • P(H|X)=P(X|H)P(H)/P(X)
  2. 朴素贝叶斯分类
    • 预测X属于在X条件下有最高后验概率的类
    • 等价于最大化P(X|Ci)P(Ci)
    • 若P(Ci)未知则假定等概率，否则用Ci/D估计
    • 类条件独立的朴素假定：P(X|Ci)=P(x1|Ci)P(x2|Ci)……P(xn|Ci)
    • 连续值属性的概率用高斯分布定义
    • 拉普拉斯校准/拉普拉斯估计法

基于规则的分类

  1. 规则：规则前件/前提IF，规则结论THEN
  2. 覆盖率$coverage(R)=n_{covers}/|D|$
  3. 准确率$accuracy(R)=n_{correct}/n_{covers}$
  4. 规模序：优先最苛刻的规则，即前件规模最大、激活具有最多属性测试的被触发的规则
  5. 规则序：预定规则的优先次序
  6. 由决策树提取规则：规则是互斥的和穷举的
  7. 使用顺序覆盖算法的规则归纳
    • 贪心的深度优先策略
    • 用于规则学习的称为正元组pos，其余称为负元组neg
    • 信息增益$FOIL-Gain=pos’*(log_2\frac{pos’}{pos’+neg’}-log_2\frac{pos}{pos+neg})$；似然率统计量$Likelihood-Ratio=2\sum_{i=1}^mf_ilog(\frac{f_i}{e_i})$，似然率越高正确预测数与随机猜测差越显著
    • 规则剪枝$FOIL-Prune(R)=\frac{pos-neg}{pos+neg}$

模型评估与选择

  1. 混淆矩阵——真阳性：TP；真阴性：TN；假阳性：FP；假阴性：FN
  2. 准确率/总体识别率：$accuracy=\frac{TP+TN}{P+N}$
  3. 错误率：1-accuracy
  4. 灵敏性/召回率：$sensitivity=\frac{TP}{P}=\frac{TP}{TP+FN}=recall$
  5. 特效性：$specificity=\frac{TN}{N}$
  6. 精度：$precision=\frac{TP}{TP+FP}$
  7. $F_x$分数：$F_x=\frac{(1+x^2)precisionrecall}{x^2*precision+recall}$，x为1时称为F度量/F分数
  8. 保持方法和随机二次抽样
  9. 交叉验证
    • k-折交叉验证：初始数据随机划分成k个互不相交的子集D，训练和检验进行k次，每次留下一个D检验
    • 留一：每次只给检验集留出一个样本
    • 分层交叉验证
    • 建议用分层10-折交叉验证估计准确率
  10. 自助法：有放回，.632，$Acc(M)=\sum_{i=1}^k(0.632Acc(M_i)_{test-set}+0.368Acc(M_i)train-set)$
  11. 统计显著性：t-test，显著水平sig，置信界z=sig/2
    • $t=\frac{\bar {err}(M_1)-\bar {err}(M_2)}{\sqrt{var(M_1-M_2)/k}}$，var为模型差的方差，若有两个检验集，方差估计为$\sqrt{var(M_1)/k_1+var(M_2)/k_2}$
  12. 成本效益
  13. ROC曲线
    • 真正例率TPR=TP/P
    • 假正例率TFR=FP/N
    • 概率从高到低排序，真正例TP增加，假正例FP增加
    • 用当前混淆矩阵计算(FPR,TPR)并将点绘在图中
    • ROC曲线越接近随机猜测，模型准确率越低

提高分类准确率的技术

  1. 组合分类方法
  2. 装袋：有放回抽样，多数表决
  3. 提升和AdaBoost：给不正确分类的元组加权，不同分类器的表决权重也取决于错误率
  4. 随机森林
  5. 提高类不平衡数据的分类准确率：过抽样、欠抽样、阈值移动、组合技术

第九章 分类：高级方法

贝叶斯信念网络

  1. 计算梯度
  2. 沿梯度方向前进一小步
  3. 重新规格化权重

用后向传播分类

  1. 多层前馈神经网络
  2. 后向传播：初始化权重，向前传播输入，向后传播误差
  3. 可增强可解释性

支持向量机

  1. 对线性和非线性数据进行分类
  2. SVM搜索最大边缘超平面（MMH）
  3. 支持向量：最难分类的元组，给出最多支持信息

使用频繁模式分类

惰性学习法（近邻学习）

  1. 距离最近的k个中取最多
  2. 训练元组趋于无穷，k=1，错误率不超过贝叶斯错误率的2倍；k趋于无穷，错误率趋向于贝叶斯错误率
  3. 基于案例的推理

其他分类方法

  1. 遗传算法
  2. 粗糙集算法
  3. 模糊集算法
  4. 多类分类
  5. 半监督分类
  6. 主动学习
  7. 迁移学习

第十章 聚类分析：基本概念和方法

  1. 划分方法：k-均值，k-中心点
  2. 层次方法
  3. 基于密度的方法
  4. 基于网格的方法
  5. 簇的形心、半径、直径
  6. 聚类评估
数据挖掘
孙若诗

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！