数据挖掘速通笔记

发表于 2022-11-20 更新于 2023-01-28 分类于笔记本文字数： 11k 阅读时长 ≈ 10 分钟

前言

本学期开的最不明所以的课，第一节课作业竟然是写深度学习算法的原理。

第一天就让我学深度学习，nmd就不能按书上作业来吗

但是垃圾老师归垃圾老师，数据挖掘还是蛮有价值的。虽然我没有那么多数据…?

我那1T的pixiv图数据库不是吗？

恩，还是有必要学的

但是为什么有种这学科就像一个统计学家学了一点点计算机就过来发paper的感觉…

数据挖掘绪论

知识发现KDD

数据挖掘是知识发现KDD（Knowledge Discovery in Database）的一个步骤，知识发现的阶梯处理模型如下

数据抽取目的是根据数据挖掘的任务从数据库中抽取相应的数据。
数据预处理需要检查数据完整性一致性，有以下目标
- 消除噪声
- 推导计算缺值数据
- 去重
- 转换数据类型，以便符号归纳or投喂神经网络
数据挖掘阶段需要使用数据挖掘算法，从数据中提取出用户所需要的知识。数据挖掘算法的选取有两个考虑的因素：一是不同数据有不同的特点，选择最适合的算法能够有效/快速的提取出知识；二是用户的不同要求。知识分描述型和预测型两类，有的用户更偏向获取容易理解的知识，有的用户只在乎预测的正确率。
知识评估阶段需要对数据挖掘阶段发现的模式进行评估，有以下目标
- 去掉无关和冗余的模式
- 对于不满足用户需求的模式，需要重新再来一遍流程
- 对模式进行可视化

知识表示模式与方法

广义知识(Generalization)挖掘

广义知识是指能够概括/泛化/抽象大批量的数据，目的是发现普遍性、更高层次概念的中观和宏观知识。

被挖掘出的广义知识可以结合可视化技术展示给用户，也可以作为其他应用的基础知识。

C++20 Concept

概念描述(Concept Description)方法

概念描述是对某类对象的内涵特征进行概括，分为特征性(Characterization)描述和区别性(Discrimination)描述。前者描述某类对象的共同特征，后者描述不同类对象之间的区别。

多维数据分析方法

将某一维或某几维的数据汇总分析，比如可以按时间维度分析日数据，周数据，月数据，年数据的波动情况。可以发掘出波动的周期等知识。

多层次概念描述问题

概念通常是具有层次的，比如location是“北京工业大学”，那么可以通过背景知识(Background Knowledge)归纳出“北京市”、“中国”、“亚洲”等不同层次的更高级概念。概念分层（Concept Hierarchy）技术就是将低层概念映射集到高层概念集的方法。更高层次的数据综合和分析是决策的基础

总体论和简化论

2022-11-18T161307

模式分层(Schema Hierarchy)
特定知识背景下的语义层次形成不同层次的模式关联，上述的location即是。
比如军队的层级
集合分组分层(Set-Grouping Hierarchy)
将特定知识北京下
操作导出分层(Operation-Drived Hierachy)
某些数据包含其他信息，比如学号包含院校信息，进行操作导出分层。
基于规则分层(Rule-Based Hierarchy)
通过定义背景知识的抽象规则，在数据挖掘的过程中使用规则形成不同层次上的概念的抽象。

关联知识挖掘

关联知识(Association)反应一个时间和其他事件之间的依赖或关联。数据库中的数据关联是现实世界中事务联系的表现，可分为简单关联、时序关联、因果关联、数量关联等。这些关联是通过数据库中数据的关联分析获得的，因而对商业决策有新价值。

关联规则挖掘（Association Rule Minning）是关联知识发现的最常用方法，最为著名的是Agrawal等提出的Apriori及其改进算法。

类知识挖掘

类知识（Class）刻画了一类食物，这类事物有着共同点，并明显和不同类事物作区别。分为分类和聚类两个应用。

聚类

聚类就是不知道类别情况下的分类。

常用有以下算法

基于划分的聚类算法
- k-平均算法
- k-中心点算法PAM
  划分成离中心点较近的几个集合
基于层次的聚类算法
- 凝聚(Agglomeration)和分裂(Division)基本算法
  子集法
基于密度的聚类方法
划分成密度高的几个集合
基于网格的聚类方法
自适应高维线段树
基于模型的积累方法
每个模型只分一类
- …

预测型知识挖掘

趋势预测
股票涨不涨
周期分析
猪周期
序列模式
两年了，以前屯碘盐的现在终于快用完盐了，加仓盐企！
神经网络

特异型知识挖掘

孤立点分析
某个用户一天请求发送100次验证码，亏麻了。
序列异常分析
天天来踩点，我都认识。
特异规则发现
还记得，那个认为二战飞机引擎不需要加防护的理论吗。

关联规则挖掘理论及其算法

关联项目挖掘主要考察实体中属性集合的相关性，我们期望找到两个强相关的属性集合。

$I=\{i_1,i_2,\cdots,i_m\}$ 是一个项目集合，事务数据库 $D=\{t_1,t_2,\cdots,t_n\},t_i\in I$ 。

支持度(Support)：设 $I_1\subseteq I$ , $\text{support}(I_1)=|| \{t\in D | I_1 \subseteq t \} || / || D ||$

置信度(Confidence)：一个定义在 $I$ 和 $D$ 上的形如 $I_1\Rightarrow I_2$ 的关联规则, $\text{Confidence}(I_1\Rightarrow I_2)=\text{support}(I_1 \cup I_2) / \text{support}(I_1)$ ，其中 $I_1,I_2\subseteq I,I_1 \cap I_2 =\emptyset$

我们会指定最小支持度 Minsupport 和 Minconfidence，期望找到频繁项目集(Frequent Itemsets)/大项目集(Large Itemsets),最大项目集(Maximum Large Itemsets)和强关联规则(String Association Rule)。

$\text{Frequent Itemsets}=\{I_1 | I_1 \subseteq I \land \text{support}(I_1)\ge \text{Minspport}\}$

$\text{Maximum Large Itemsets}=\{I_1 | I_1 \in \text{Frequent Itemsets} \land \forall I_2 \in \text{Frequent Itemsets} ,I_1 \not \subset I_2\}$

$\text{String Association Rule}=\{ I_1\Rightarrow I_2 | I_1,I_2 \subset I \land \min(\text{support}(I_1),\text{support}(I_2))\ge \text{Minsupport} \land \text{Confidence}(I_1\Rightarrow I_2)\ge \text{Minconfidence}\}$

Apriori算法

理论1：设 $I_0\subset I_1\subset I_2$ ，则 $\text{support}(I_0)\ge \text{support}(I_1) \ge \text{support}(I_2)$

Apriori

基本思路就是对大小为k的频繁项目集成员（称为k-项子集）合并笛卡儿积的操作推出k+1的频繁项目集成员。

L[1]=所有大小为1的频繁项目集成员;
FOR k FROM 2 TO |I|-1 DO BEGIN
    Ck=apriori-gen(L[k-1]);
    FOR t IN D DO BEGIN
        Ct=Subsets(Ck,t);
        FOR c in C[t] DO c.count++;
    END
    L[k]={c in C[k] | c.count >= minsup_count};
END
L=join(L[1..k])

apriori-gen

这里的集合类似C++里的set，外部观察为升序数组。

FUNCTION apriori-gen(L[k]) BEGIN
    FOR p IN L[k] DO
        FOR q IN L[k] DO
            IF p[1]=q[1] and p[2]=q[2] and ... p[k-1]=q[k-1] and p[k]<q[k] THEN BEGIN
                c=join(p,q)
                IF has_infrequent_subset(c,L[k]) THEN
                    delete c;
                ELSE add c to Ck;
            END
    RETURN Ck;
END

has_infrequent_subset

FUNCTION has_infrequent_subset(c,L[k]) BEGIN
    FOR a IN c DO
        IF (c-{a}) NOT IN L[k] THEN RETURN TRUE;
    RETURN FALSE;
END

Close算法

nmd所以闭合项目集格空间是个啥子玩意啊

Close算法基于这样的原理：频繁闭合项目集b指的是不存在一个 $b\subset a$ ,b是频繁项目集。

闭包(Gen_Closure)： $\text{Close}(FCC)[a]=\bigcap_{c\in FCC \land a\subseteq c\land \text{c is Frequent Itemsets}} c$

筛选出Frequent Itemsets单独处理，筛选前叫FCC，筛选后叫FC。

基本思路就是Apriori算法后如果 k-项子集成员p并上FC[k-1]的元素的元素的闭包包含p 就把p删掉。（Gen_Generator）

最终将闭合添加到答案中，在对答案的所有元素尝试分解即可。（Deriving frequent itemsets）

FCC[1].gen = {1-iteamsets};
FOR (i=1;FCC[1].gen = emptyset;i++) DO BEGIN
    FCC[i].closures = emptyset;
    FCC[i].support = 0;
    FCC[i]=Gen_Closure(FCC[i]);
    FOR c IN FCC[i] DO BEGIN
        IF (c.support >= minsupport) THEN FC[i]=join(FC[i],{c});
    END
    FCC[i+1]=Gen_Generator(FC[i]);
END
FC=join(FC[i],FC[i].closure);
Deriving frequent itemsets(FC,L);

分类方法

给定一个数据库 $D=\{t_1,t_2,\cdots,t_n\}$ 和一组类 $C=\{C_1,C_2,\cdots,C_m\}$ ，分类就是确定一个映射 $f:D\rightarrow C$ 。一般这个映射是在自然环境中依托背景知识得出的映射，无法程序化，需要借助数据挖掘算法让其可被计算机计算。

在下文中，已经通过人类计算知晓 $f$ 的 $D$ 的子集被称为T。

基于距离的分类方法

基于距离的分类方法使用相似性函数 $sim$ 来对数据分类，如果 $sim(t_i,C_j)\ge sim(t_i,C_k)$ ，则 $t_i$ 归为 $C_j$ 中，一般选取为距离函数，此时 $C_j$ 也是一个实体。

k-最邻近方法

k-最邻近方法可以分类一个实体，取t为计算出的某个 $C_j$ 。

N=emptyset
FOR d IN T DO BEGIN
    IF |N| <= k THEN
        N=join(N,{d});
    ELSE
        IF exist u in N,sim(t,u)<sim(t,d) THEN
            BEGIN
                N=N-{u};
                N=join(N,{d});
            END
END
c=在N中出现最多的分类数量

基于决策树的分类算法

高级版搜索树

ID3算法

决策树中每一个非叶节点对应一个非类别属性，树枝代表这个属性的值。叶子节点代表一个类别属性值。
每一个非叶节点都将与属性中具有最大信息量的非类别属性相关联。
采用信息增益选择出能够最好的将样本分类的属性。

基于信息熵的分类算法使用子集的熵来对数据分类

设 $S$ 是 $s$ 个数据样本的集合，m个不同类别 $C_i$ ，设 $s_i$ 是类 $C_i$ 的样本数。对于这个给定的样本分类所需的期望信息： $I(s_1,s_2,\cdots,s_m)=-\sum p_i \text{lb}(p_i)$ ，一般 $p_i=s_i/s$

对于决策树熵每一个非叶节点，其转移到儿子节点时相当于根据 $S$ 的取值空间大小为 $m$ 属性 $A$ 划分 $S$ 为 $m$ 个 $S_j$ ，设 $s_{ij}$ 为 $S_j$ 中类 $C_i$ 的样本数。

这一个划分的熵： $E(A)=-\sum_{j=1}^v \frac{\sum_{i=1}^m s_{i,j}}{s}I(s_{1j},s_{2j},\cdots,s_{mj})$

对于某个点上分支所获得的信息增益： $Gain(A)=I(s_1,s_2,\cdots,s_m)-E(A)$

对于每一个节点都做类似的处理，直到节点里面的分类信息全部一致。

FUNCTION ID3(T,C) BEGIN
IF T中全为同一类C THEN BEGIN
    标记为类别为C的叶子节点;RETURN;
END
IF C=空集 OR T的在C上所有属性都一样 THEN
    标记为类别为D中样本最多类别的叶子节点;RETURN
END
按照节点信息增益，从A中选出最优划分属性a*;
FOR ai IN a* DO BEGIN
    为本节点新建一个分支;令Di表示D在a*上取值为ai的样本子集;
    if Di=空集 THEN BEGIN
        标记为类别为D中样本最多类别的叶子节点;RETURN;
    END ELSE BEGIN
        以ID3(Di,A/A*)为分支节点。
    END
END

聚类方法

聚类就是将数据划分，划分出来的每一个集合都能通过一些特征来描述。通常有以下几种方式

通过类的中心或类的边界表示一个类
使用聚类树中的节点图形化表示一个类
使用样本属性的逻辑表达式表示一个类

k-平均(k-Means)算法

准则函数： $E=\sum_{i=1}^k \sum_{x\in C_i}|x-\overline{x_i}|^2$

首先随机选择 $k$ 个对象作为 $k$ 个簇的初始中心，将其他对象分配给最近的簇（分类），然后重新计算每个簇的平均值。直到准则函数收敛。

就是不带随机退火的退火算法

随机选择k个对象作为k个簇的初始中心;
REPEAT
FOR j FROM 1 TO n DO
    分配x[j]给最近的簇;
FOR i FROM i to k DO
    \overline{x}[i]=\sum_{x\in C_i} x/|C_i|;
计算E;
UNTIL E的变化值小于某个阀值;

评价

优点

经典、简单、快速。
对大数据集，相对可伸缩且高效率。
结果簇是密集情况下效果好。

缺点

平均值处于良定义才能用
必须给出结果簇大小k，对初始值敏感
对噪声和孤立点数据敏感

K-medoids算法

同k-平均，但是把离平均值最近的点当成中心。

层次聚类方法

对层次凝聚/分裂。

AGNES算法

是一个凝聚的算法。

AGNES(AGglomerative NESting)算法最初将每一个对象当成一个簇，然后这些簇根据某些准则一步一步合并。

Prim算法

把每个对象当成一个初始簇;
REPEAT
    根据两个簇中最近的数据点找到最近的两个簇;
    合并这两个簇;
UNTIL 达到定义的簇的数目;

DIANA算法

是一个分裂的算法。

AGNES(AGglomerative NESting)算法最初将每一个对象归为一个簇，然后这些簇根据某些准则一步一步合并。

簇的直径： $\max_{d(x_i,x_j)}$

平均相异度（平均距离）： $d_{avg}(C_i,C_j)=\frac{1}{n_in_j}\sum_{x\in C_i}\sum_{y\in C_j}|x-y|$

将所有对象归为一个初始簇;
FOR i FROM 1 TO k-1 DO BEGIN
    从所有簇中挑选出最大直径的簇;
    找出簇中与其他点平均相异度最大的一个点放入splinter group,其他放入old party;
    REPEAT
        在old party中找到splinter group中点的最近距离<=到old party中点的最近距离的点，将其加入splinter group;
    UNTIL 没有新的点加入splinter group;
    选中的簇分裂为splinter group和old party两个簇;
END

密度聚类算法

DBSCAN算法

对象的 $\omega-$ 邻域：给定对象在半径 $\omega$ 内的区域。

核心对象：对象的 $\omega-$ 邻域至少包含 $\text{MinPts}$ 个对象，则其为核心对象。

直接密度可达（核心对象直达）：给定一个对象集合 $D$ ，如果 $p$ 是在 $q$ 的 $\omega-$ 邻域内，而 $q$ 是一个核心对象，则 $p$ 从 $q$ 出发是直接密度可达的。

密度可达的（核心对象转达）：如果存在一个对象链 $p_1,p_2,\cdots,p_n,p_1=q,p_n=p$ ，对 $p_i\in D$ ， $1\le i \le n,p_i+1$ 是从 $p_i$ 关于 $\omega$ 和 $\text{MinPts}$ 直接密度可达的，则 $p$ 是从 $q$ 关于 $\omega$ 和 $\text{MinPts}$ 密度可达的。

密度相连的（一个对象转达两个对象）：如果对象集合 $D$ 中存在一个对象 $o$ 使对象 $p$ 和 $q$ 是从 $o$ 关于 $\omega$ 和 $\text{MinPts}$ 密度可达的，则 $p$ 和 $q$ 是关于 $\omega$ 和 $\text{MinPts}$ 密度相连的。

噪声：一个基于密度的簇是基于密度可达性的最大的密度相连对象的集合，不包含任何簇中的对象被认为是噪声。

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法检查数据集中每个对象的 $\omega-$ 邻域来寻找聚类，如果其 $\omega-$ 邻域多于 $\text{MinPts}$ 个对象，则创建一个以 $p$ 为核心对象的新簇。然后尽量找密度可达的对象，按需要合并密度可达簇。

REPEAT
    选一个没处理过的点a;
    IF a是核心点 THEN 找出所有从a密度可达的对象，合并成一个簇;
    ELSE CONTINUE;
UNTIL 所有点被处理;

评价

优点

速度快，容易发现任意形状的空间聚类
跟k-MEANS相比不需要输入结果簇大小
聚类簇的形状没有偏倚
有效处理噪声

缺点

内存I/O随数据量增长而增长显著
当空间聚类密度不均匀、聚类间距差距很大时聚类质量差，此时MinPts和Eps选区困难。
依赖于距离公式，实践常用欧式距离，对于高维数据存在维数灾难。

时间序列和序列模式挖掘

REF:Github/Lyfive/HnusterComputer/数据挖掘/数据挖掘.md

时间序列数据挖掘通过研究信息的时间特性，深入洞悉事物进化的机制，是获得知识的有效途径。

时间序列挖掘在宏观的经济预测、市场营销、客流量分析、太阳黑子数、月降水量、河流流量、股票价格变动等众多领域得到应用。事实上，社会、科学、经济、技术等领域中广泛存在着大量的时间序列数据有待进一步的分析和处理。

**时间序列(Time Series)挖掘：**就是要从大量的时间序列数据中提取人们事先不知道的、但又是潜在有用的与时间属性相关的信息和知识，并用于短期、中期或长期预测，指导人们的社会、经济、军事和生活等行为。通过对过去历史行为的客观记录分析，揭示其内在规律，进而完成预测未来行为等决策性工作。

Web挖掘技术

常用于搜索引擎，爬虫等。

页面等级评价方法

把页面和其超链接当作点和边，就变成了一个有向图。

基本u页面的等级方法R(u)：设u为一个web页， $B_u$ 为指向 $u$ 的页面的集合， $F_u$ 为 $u$ 指向的页面的集合, $c$ 是一个常数， $R(u)=c\sum_{v\in B_u}\frac{R(v)}{|F_v|}$ 。

就是一个页面的Rank平均分给他指向的所有页面。

成环不好算
$|F_v|=0$ 也不好算

随机冲浪模型的u页面的等级方法R(u)： $R(u)=(1-d)+d\sum_{v\in B_u}\frac{R(v)}{|F_v|}$

d推荐为0.85或0.5，能避免过小导致传递中断或者过大导致成环无限放大。

PageRank算法

具体计算可以使用PageRank算法，PageRank是一种随机算法，统计随机冲浪下每个页面的频率并当作概率。

随机游走算法的网页应用版本。

先计算出M=(1-d)*Q+d*A;Q=(q[i][j]),q[i][j]=1/n;A为邻接矩阵导出的概率矩阵;

根据G生成概率转移矩阵M;
设定点击概率d;等级值向量初始值$R_0$;迭代终止条件omega;
i=1;
REPEAT
    R[i+1]=M*R[i];
    omega[i]=|| R[i+1]-R[i] ||;
UNTIL omega[i] <= omega;
返回R[i+1];

权威页面和中心页面

权威页面值包含需求信息的最佳资源页面
中心页面是一个包含权威页面链接的页面

简单来说中心页面就是github上那一堆awsome仓库，权威页面就是cppreference这种网页。