前言:此篇复习笔记结合了课程ppt和deepseek回答进行总结,如有谬误恳请指正。
期末考例题
(名词解释*10、简答*6、论述*6)
一、名词解释
数据挖掘
过拟合(Overfitting)
Apriori算法
决策树(Decision Tree)
K-means聚类
数据预处理
信息增益
频繁项集
剪枝
离群点检测
集成学习
二、简答题
解释数据清洗的概念和重要性。
为什么需要对数据进行归一化(Normalization)?列举两种常用方法。
解释关联规则中支持度(Support)和置信度(Confidence)的定义及计算公式。
对比分类与聚类的区别(至少3点)。
ID3决策树算法如何选择分裂属性?写出其核心公式并解释含义。
简述K-means算法的步骤,并说明其局限性。
第一章 绪论
1.1 KDD
从数据中发现知识(KDD):指从大量数据中提取有效的、新颖的、潜在有用的、最终可被理解的模式的非平凡过程。包括数据清理、数据集成、数据选择、数据变换、数据挖掘、模式评估和知识表示几个步骤。数据清理、集成、选择、变换属于数据预处理过程,模式评估、知识表示是结果的解释与评估。
KDD过程
数据清理(Data Cleaning)
功能:处理数据中的噪声、缺失值、不一致和异常数据。
具体任务:
解决不一致问题(如统一单位或格式)。
识别并处理异常值(如使用统计方法或领域知识)。
平滑噪声数据(如分箱、回归或聚类)。
填补缺失值(如用均值、中位数或插值法)。
数据集成(Data Integration)
功能:将来自多个数据源的数据合并为一个一致的数据存储。
具体任务:
处理数据冗余和冲突(如通过相关性分析或冲突检测)。
解决实体识别问题(如不同数据源中的同名异义或异名同义)。
合并不同数据库、文件或API的数据。
数据选择(Data Selection)
功能:从集成后的数据中选择与分析任务相关的数据子集。
具体任务:
使用维度规约(如主成分分析)或采样技术减少数据量。
根据目标筛选相关属性(特征)或样本(记录)。
数据变换(Data Transformation)
功能:将数据转换为适合挖掘的形式。
具体任务:
泛化数据(如用高层次概念替换原始值,如“年龄”替换为“青年”“中年”)。
构造新特征(如聚合或计算派生变量)。
离散化连续数据(如分箱或聚类)。
规范化或标准化数据(如最小-最大缩放、Z-score标准化)。
数据挖掘(Data Mining)
功能:应用算法从数据中提取模式或知识。
具体任务:
调整参数以优化模型性能。
使用算法(如决策树、神经网络、Apriori、K-means)发现模式。
选择挖掘技术(如分类、聚类、关联规则、回归、异常检测)。
模式评估(Pattern Evaluation)
功能:评估挖掘出的模式的有效性和价值。
具体任务:
领域专家评估模式的实际意义。
统计验证(如假设检验或交叉验证)。
使用兴趣度度量(如支持度、置信度、提升度)筛选模式。
知识表示(Knowledge Presentation)
功能:以用户可理解的方式呈现发现的知识。
具体任务:
集成到决策支持系统或知识库中。
生成报告或规则(如自然语言描述或逻辑表达式)。
可视化(如图表、树状图、热力图)。
KDD的研究进展:KDD已经从学术研究走向工业级应用,成为企业决策、智慧城市、医疗健康等领域的核心技术。目前的研究的重点是提高原先数据挖掘算法在(空间)数据库中的执行效率,开发新的模型与算法以及挖掘结果表达的研究,数据挖掘成为人工智能的研究热点。
数据结构金字塔:数据(未处理过的信息)— 信息(组织、整理之后展现的数据)— 知识(经过读、看之后得到的知识)— 智慧(知识经过精炼整合萃取出的精华)
1.2 空间数据挖掘
空间数据挖掘(Spatial DataMining,SDM),或称从空间数据库中发现知识(Knowledge Discovery from Spatial Databases):是指从空间数据库中提取用户感兴趣的空间模式与特征、空间与非空间数据的普遍关系及其它一些隐含在数据库中的普遍的数据特征。
空间数据的特点:海量数据,空间属性之间的非线性关系、尺度特征、空间信息的模糊性、空间维数的增高、空间数据的缺值。
空间数据库的特点:存储了空间对象的一般属性数据、几何属性数据、对象之间的空间关系,其非结构化、分层、矢量栅格数据格式并存的特点,使得其访问和操作模式更加复杂。
空间数据挖掘VS.数据挖掘:存储结构非结构化;
空间数据挖掘VS.传统地学分析:追求在机理不明的情况下对数据的规则、规律的发现和提取。
1.3 相关论述题
为什么要进行KDD
1、解决数据爆炸与信息匮乏的矛盾:
海量数据中蕴含的、能够直接用于决策或理解的有价值信息和知识却相对匮乏,KDD从海量数据中提取出真正有用的、可理解的、可操作的知识。
2、揭示隐藏的模式和关系:
数据中往往隐藏着人类难以直接观察或想象的复杂模式、趋势、关联规则和异常情况,KDD 利用数据挖掘等算法技术,能够自动或半自动地发现这些隐藏的、有价值的知识,揭示数据背后的规律和洞察。
3、支持智能决策:
基于从数据中发现的知识(如预测模型、分类规则、聚类结果),企业、组织和个人可以做出更明智、更数据驱动的决策。
4、将数据转化为竞争优势和价值:
KDD是将原始数据转化为实际商业价值、科学发现或社会效益的关键过程。它帮助企业发现新的市场机会、优化流程、降低成本、提升服务质量、开发新产品,从而获得竞争优势。
5、自动化知识提取过程:
面对海量数据,依靠人工手动分析来寻找模式和知识是低效、耗时、甚至不可能完成的。
KDD 提供了一个系统化、自动化的流程框架(包括数据预处理、转换、挖掘、评估、解释),使得从大数据中高效、大规模地提取知识成为可能。
KDD的应用
遥感影像智能解译: 运用 聚类、分类算法 从海量卫星/航拍影像中 自动发现 土地覆盖类型、植被变化趋势、灾害损毁区域等 隐藏知识。
地理文本信息挖掘: 利用 自然语言处理技术 分析社交媒体、新闻等文本,挖掘 带有地理位置的情绪热点分布、突发事件的空间位置及传播规律等 隐含信息。
城市移动模式发现: 通过 轨迹挖掘算法 分析手机信令、出租车 GPS 等数据,揭示 人群活动规律、城市功能区划分、交通拥堵成因等 潜在模式。
城市环境关联分析: 应用 关联规则挖掘、时空分析技术,整合多源传感器数据,发现 空气污染与交通流量、工业布局之间的 隐藏关联,溯源污染。
设施使用规律洞察: 基于 频繁模式挖掘、预测模型,分析共享单车、充电桩等物联网数据,预测 需求高峰、优化 设施布局,提升服务效率。
第二章 SDM的理论技术体系
2.1 数据质量度量
数据质量的多维度量:精确度、完整度、一致性、现时性、可信度、附加价值、可访问性
2.2 数据清洗
空缺值处理方法
- 忽略元组:当类标号缺少时通常这么做(假定挖掘任务设计分类或描述),当每个属性缺少值的百分比变化很大时,它的效果非常差。
- 人工填写空缺值:工作量大,可行性低
- 使用一个全局变量填充空缺值:比如使用unknown或-∞
- 使用属性的平均值填充空缺值
- 使用与给定元组属同一类的所有样本的平均值
- 使用最可能的值填充空缺值:使用像Bayesian公式或判定树这样的基于推断的方法
噪声数据:一个测量变量中的随机错s误或偏差。处理噪声数据:分箱、聚类、回归。
分箱平滑噪声:首先排序数据,并将他们分到等深的箱中,然后可以按箱的平均值平滑、按箱中值平滑、按箱的边界平滑等等。
注意:下图中等深度中的深度指每个箱包含的值的数量。
2.3 数据集成
数据集成将多个数据源中的数据整合到一个一致的存储中。
数据集成的作用
1、构建统一数据视图:通过模式转换、数据清洗解决命名冲突、格式差异、单位不统一等问题,形成标准化数据集。
2、提升数据质量与一致性:在集成过程中清洗冗余、修正错误、补全缺失值,确保后续数据挖掘以及分析结果可靠
2.4 数据变换
1、平滑:去除数据中的噪声 (分箱、聚类、回归)2、聚集:汇总,数据立方体的构建3、数据概化:沿概念分层向上汇总4、规范化:将数据按比例缩放,使之落入一个小的特定区间最小-最大规范化、z-score规范化、小数定标规范化5、属性构造:通过现有属性构造新的属性,并添加到属性集中;以增加对高维数据的结构的理解和精确度。
分层聚类:建立聚类的层次结构,存储在多层索引树中。有聚合型(agglomerative)和分裂型(divisive)两类。
聚合法最初将每个数据点作为一个单独的聚类,然后迭代合并,直到最后的聚类中包含所有的数据点。它也被称为自下而上的方法。分裂聚类遵循自上而下的流程,从一个拥有所有数据点的单一聚类开始,迭代地将该聚类分割成更小的聚类,直到每个聚类包含一个数据点。
数据离散化: 通过将属性域划分为区间,减少给定连续属性值的个数。区间的标号可以代替实际的数据值。
概念分层:通过使用高层的概念(比如:青年、中年、老年)来替代底层的属性值(比如:实际的年龄数据值)来规约数据。
方法:分箱、直方图分析、聚类分析、基于熵的离散化、通过自然划分分段。
第三章 空间关联规则挖掘技术
3.1 空间关联规则挖掘
频繁模式:频繁地出现在数据集中的模式;(可以是项集、子序列或子结构)
频繁项集:如果项集的频率大于(最小支持度×D中的事务总数),则称该项集为频繁项集。
关联规则挖掘:发现大量数据中项集之间有趣的关联。(1)找出所有的频繁项集;(2)由频繁项集产生强关联规则。
支持度和置信度计算
支持度是指事务集D中包含A∪B的百分比,support(A→B)=P(A∪B);
置信度是指D中包含A的事务同时也包含B的百分比,confidence(A→B)=P(B|A)=P(A∪B)/P(A)
3.2 Apriori算法示例
L1、L2、L3:频繁k项集
连接步:为找出Lk,通过将Lk-1与自身连接产生候选k项集的集合。
剪枝步:如果一个候选k项集的(k-1)项集不在L(k-1)中,则该候选也不可能是频繁的,可以从Ck中删去。如下图中{A,B}和{A,E}不是频繁项集,因此在由L2产生L3的过程中,可以将{A,B,C}、{A,B,E}、{A,E,C}删去。
由上述过程可以产生所有频繁项集,后续根据频繁项集可以找强关联规则。
如何提高Apriori算法效率
1、基于散列的技术(散列项集到对应的桶中) :将每个项集通过相应的hash函数映射到hash表中的不同的桶中,这样可以通过将桶中的项集技术跟最小支持计数相比较先淘汰一部分项集。
2、事务压缩(压缩进一步迭代的事务数):不包含任何k-项集的事务不可能包含任何(k+1)-项集,这种事务在下一步的计算中可以加上标记或删除。
3、划分(为找候选项集划分数据):将事务集划分为不同分区,找出所有的局部频繁项集,再通过评估每个候选的实际支持度,以确定全局频繁项集。
3、抽样(在给定数据的一个子集挖掘):选择原始数据的一个样本,在这个样本上用Apriori算法挖掘频繁模式。通过牺牲精确度来减少算法开销,为了提高效率,样本大小应该以可以放在内存中为宜,可以适当降低最小支持度来减少遗漏的频繁模式。可以通过一次全局扫描来验证从样本中发现的模式,通过第二此全局扫描来找到遗漏的模式。
4、动态项集计数(在扫描的不同点添加候选项集):在扫描的不同点添加候选项集,这样,如果一个候选项集已经满足最少支持度,则在可以直接将它添加到频繁项集,而不必在这次扫描的以后对比中继续计算。
3.3 FP-growth算法示例
频繁模式增长(FP-growth):发现频繁模式而不产生候选频繁项集。(1)扫描数据库,导出频繁项集的集合(1项集);(2)将项按照降序排序;(3)再次扫描数据库构建FP树并生成频繁项集。具体过程可参考b站视频:关联规则挖掘FP-growth例题https://www.bilibili.com/video/BV1HS4y1G7h6?spm_id_from=333.788.videopod.sections&vd_source=487cc32bed199e5a2a5013ff10b420e4
此处省略添加事务的步骤,最终FP树如下图所示。
从最低频的i5开始,找到所有条件模式基,根据支持度确定条件FP树,排列组合得到频繁项集。i5的频繁项集求解过程如下。其他项同理,不再展示。
注:过程源自视频截图。
Apriori算法VS.FP-growth算法:
从时间效率上,① Apriori算法需要多次扫描数据库,对于挖掘k项集需要扫描至少k次数据库;而FP-growth算法仅需要进行两次扫描,分别用于构建头表和构建FP-Tree;②Apriori算法在项数多或最小支持度低时会产生海量的候选项集,而FP-growth算法直接通过FP-Tree的结构和递归挖掘策略发现频繁项集。
从空间效率上,空间效率取决于数据特性,对于事务长、项之间关联性强、共享前缀多的密集数据集,FP-Tree的压缩效果极佳,空间效率更高;对于非常稀疏的数据集,事务短且差异大,共享前缀少时,由于还要存储节点、指针等结构,压缩效果不好,还有可能比原始数据更大。
多层关联规则挖掘:是一种在具有层次结构的数据中发现跨不同抽象层级项之间关联规则的方法。"多层"指数据项具有明确的层级划分,通常由领域知识构建的树状分类体系。方法:受控的层交叉单项过滤策略、检查冗余的多层关联规则。
对强关联规则的批评
强规则不一定有趣:置信度和支持度度量不足以过滤掉这些无趣的关联规则。因此,需要引入提升度(lift)的概念:
lift(A,B)=P(A∪B)/P(A)P(B)
如果值小于1,则二者是正相关的,大于1则是负相关。这种负相关无法被支持度-置信度框架识别。
元规则:是指导关联规则生成的高层规则模板,通过预定义规则结构和约束条件,缩小搜索空间,提升挖掘效率。年龄(X,青年) ∧ 购买(X,手机) → 购买(X,耳机)
空间谓词:空间谓词是描述地理对象间空间关系的逻辑条件,用于构建空间关联规则或查询。相邻(城市A, 城市B) → 经济合作(A,B)
第四章 空间聚类挖掘技术
4.1 聚类挖掘
聚类:聚类是根据某个相似性准则对模式集进行自动分组,达到组内差异最小、组间差异最大的过程。其中每个分组称之为“类别”,也叫“簇”(cluster)。由于根据模式间的相似性与差异性进行自动归类,聚类被看作是一种非监督学习过程,因此也被称为“非监督分类”。
模式表示:是指为聚类算法选定类别的个数、聚类模式数目、特征数目、类型和尺度等要素的过程,这些是聚类分析的原始信息。模式是由一组特征构成的向量,包括定量特征和定性特征。
定量特征分为连续型、离散型、间隔型;定性特征分为名称型、顺序性等。相似性度量:指选定能够衡量模式间亲疏关系的指标体系过程,一般用模式对间的距离函数来定义其相似/邻近关系。但也由基于(距离)/密度/模型的相似性度量方法。
数据分组:聚类分析的主体部分,一般可分为分割式聚类、层次型聚类、基于密度的聚类、基于模型的聚类。
数据抽象:提取简单和紧凑的数据集表示的过程。
聚类挖掘的要求
可伸缩性:能够适应大数据集。
多类型属性支持:兼容数值、分类、序数等混合数据类型。
任意形状发现:突破球状簇限制(欧氏/曼哈顿距离易导致偏差)。
参数依赖最小化:减少人工输入(如簇数),避免结果敏感性问题。
噪声鲁棒性:容忍离群点、缺失值等噪声干扰。
顺序不敏感:输入数据顺序变化不影响聚类结果。
高维处理能力:克服维数灾难(高维稀疏数据挑战)。
约束聚类支持:融合用户定义约束(如业务规则)优化分组。
可解释性:结果需关联语义,满足应用场景需求。
4.2 K-Means算法
K-Means聚类算法核心思想是通过迭代的方式,将数据划分为K个不同的簇,并使得每个数据点与其所属簇的质心(中心点或均值点)之间的距离之和最小。
算法的执行过程通常包括以下几个步骤:
初始化:随机选择K个数据点作为初始的簇质心。
分配:根据每个数据点与各个簇质心的距离,将其分配给最近的簇。
更新:重新计算每个簇的质心,即取簇内所有数据点的平均值作为新的质心。
迭代:重复分配和更新步骤,直到满足终止条件,如簇质心不再发生显著变化或达到预设的迭代次数。
K-means聚类算法的优点与局限性
K-means算法的优点在于其简单易懂、计算速度快且易于实现。
缺点:
①仅当簇的均值有定义时才能使用;
②用户必须事先给定要生成的簇数k;
③不能保证其收敛于全局最优解,并且她常常终止于一个局部最优解;
④不适合于发现非凸状的簇,或者差别很大的簇;
⑤对噪声和离群点敏感,因为当噪声点归为一个簇时,很容易扭曲簇的形状。
BIRCH:利用层次结构的平衡迭代规约和聚类, 是一种用于大规模数据集的增量式层次聚类算法。其核心思想是将数据点信息压缩为聚类特征 (CF) 向量,并动态构建内存中的CF-树来高效维护数据聚类摘要,从而实现快速、可伸缩的聚类,尤其擅长减少I/O开销。它常作为预聚类步骤使用。
CF-树:聚类特征树,是 BIRCH 聚类算法的核心内存数据结构,是一种高度平衡树。其节点存储聚类特征 (CF) 条目 (CF = (N, LS, SS)
),用于压缩概括子簇或子节点群的信息。CF 向量具有可加性,支持高效合并和计算统计量(质心、半径等)。通过分支因子 B
、叶节点因子 L
和阈值 T
控制树的结构与子簇紧密度,支持数据的动态增量更新。
密度聚类,DBSCAN算法(重要)
4.3 DBSCAN算法
第五章 空间分类和空间趋势项分析
区分分类VS.预测:
分类:预测分类标号(或离散值);根据训练数据集和类标号属性,构建模型来分类现有数据,并用来分类新数据。
预测:建立连续函数值模型,比如预测空缺值。
区分有监督VS.无监督
有指导的学习(用于分类):模型的学习在被告知每个训练样本属于哪个类的“指导”下进行;新数据使用训练数据集中得到的规则进行分类
无指导的学习(用于聚类):每个训练样本的类编号是未知的,要学习的类集合或数量也可能是事先未知的;通过一系列的度量、观察来建立数据中的类编号或进行聚类。
5.1 过拟合
过拟合:过拟合是指机器学习模型在训练数据上表现过于优异(如准确率高、误差低),但在未知数据(测试集或新样本)上表现显著下降的现象。
核心原因:
模型复杂度过高:模型过度学习训练数据中的噪声或随机波动(而非底层规律);
训练数据不足:数据量少导致模型无法泛化到真实分布;
训练迭代过多(如神经网络):过度优化训练集细节。
解决方案:
降低模型复杂度:减少参数数量(如剪枝决策树、减少神经网络层数);
正则化(Regularization):添加惩罚项(如L1/L2正则化);
增加数据量:数据增强(图像/文本)、收集更多样本;
交叉验证:早停法(Early Stopping)防止过度训练;
集成方法:如Bagging(降低方差)。
5.2 信息增益
此段落内容来自博客:信息增益的计算https://blog.csdn.net/guomutian911/article/details/78599450
熵的概念:
信息增益计算方法:
通过信息增益构造决策树:
5.3 贝叶斯分类
贝叶斯分类:统计学分类方法,可以预测类隶属关系的概率,如一个给定的元组属于一个特定类的概率。
计算朴素贝叶斯分类过程(以上面的8.1例题数据为例)
袋装法(Bagging)是一种并行式集成学习方法。其核心思想是通过自助采样法(Bootstrap Sampling)从原始数据集中有放回地抽取多个子数据集,分别训练多个同质基学习器(如决策树),最终通过投票(分类)或平均(回归)聚合预测结果。代表算法为随机森林。
提升法(Boosting)是一种序列式集成学习方法。其核心思想是通过迭代训练多个弱学习器(如浅层决策树),每一轮调整样本权重或关注前一轮错误样本,最终通过加权投票(分类)或加权求和(回归)结合预测结果。典型代表:XGBoost。
5.4 k最邻近算法
k最近邻算法(The k-Nearest Neighbor Algorithm,KNN)
定义:一种基于实例的惰性学习分类与回归方法。
核心思想:通过计算待测样本与训练集中所有样本的距离,选取距离最近的 kk 个邻居,根据邻居的多数投票(分类)或平均值(回归)进行预测。
算法流程:
输入待测样本、训练集及参数 kk;
计算待测样本与所有训练样本的距离(常用欧氏距离);
选择距离最近的 k 个邻居;
分类任务:输出邻居中占比最高的类别;
回归任务:输出邻居标签的均值。
第六章 拓展内容
大数据的特点:
Volume(数据量大):如遥感影像、社交媒体数据、传感器数据等。
Velocity(速度快):实时或近实时数据流(如气象数据、交通数据)。
Variety(多样性):结构化(如数据库)、半结构化(如JSON)、非结构化(如遥感影像、文本)。
Veracity(真实性):数据质量、噪声、不确定性(如GPS定位误差)。
Value(价值密度低):需挖掘高价值信息(如从海量遥感数据中提取灾害信息)。
大数据的分析流程:
数据采集:遥感影像、社交媒体、物联网(IoT)数据等。
数据存储与管理:分布式存储(HDFS)、时空数据库(PostGIS)。
数据预处理:清洗(去噪)、归一化、空间插值、坐标转换。
数据分析:机器学习(如分类、聚类)、空间统计分析(如热点分析)。
数据可视化:GIS 地图、时空动态展示(如热力图)。
决策支持:应用于智慧城市、灾害监测等。
遥感图像特征提取方法:
光谱特征:波段反射率(如NDVI植被指数)。
纹理特征:GLCM(灰度共生矩阵)、Gabor滤波。
形状特征:边缘检测(Canny算子)、形态学运算。
空间特征:对象基分类(OBIA)、空间上下文信息。
深度学习特征:CNN(卷积神经网络)自动提取高层特征。
遥感指数的概念:
遥感指数是通过 多光谱波段计算 的定量指标,用于增强特定地物信息,例如:
NDVI(归一化植被指数):(NIR−Red)/(NIR+Red)(NIR−Red)/(NIR+Red),监测植被健康。
NDWI(归一化水体指数):(Green−NIR)/(Green+NIR)(Green−NIR)/(Green+NIR),提取水体。
NDBI(归一化建筑指数):(SWIR−NIR)/(SWIR+NIR)(SWIR−NIR)/(SWIR+NIR),识别城市建筑。
文本数据挖掘的概念:
文本数据挖掘(Text Mining) 是指从非结构化或半结构化文本数据中自动提取有价值的信息、模式和知识的过程。它结合了自然语言处理(NLP)、机器学习(ML)和统计学 方法,用于分析大规模文本数据,并转化为结构化信息,以支持决策和分析。例如:
社交媒体分析(如Twitter、微博的灾害舆情监测)
地名识别与地理编码(如从新闻中提取位置信息)
文献挖掘(如科研论文中的空间趋势分析)
文本数据挖掘面临的挑战:
非结构化数据:文本格式多样(如缩写、方言)。
空间隐含性:如“北京暴雨”需关联地理坐标。
多语言处理:全球数据需跨语言分析。
实时性要求:如灾害事件的快速舆情分析。
信息要素的类型:
空间数据:位置、形状(点、线、面)。
属性数据:描述性信息(如人口、土地利用类型)。
时间数据:时序变化(如城市扩张动态)。
关系数据:拓扑关系(如相邻、包含)。
地理编码的概念:
地理编码指将地名的详细地址以地理坐标(如经纬度)表示的过程。其中,将地址信息映射为地理坐标的过程称之为地理编码;将地理坐标转换为地址信息的过程称之为逆地理编码。
元数据的概念:
描述数据的数据,用于 数据共享与管理,例如:
遥感影像元数据:成像时间、传感器类型、空间分辨率。
GIS数据元数据:坐标系、数据来源、字段说明。
网页数据采集方法:
API 调用:如Twitter API、Google Maps API。
网络爬虫(Web Scraping):Scrapy、BeautifulSoup。
地理空间数据采集:OpenStreetMap(OSM)数据下载。
实时数据流:MQTT、Kafka(如气象传感器数据)。