发帖
雷达卡
数据挖掘试题解析
一、简答题
1. DBSCAN算法的基本思想、伪代码、优点与缺点
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种基于密度的聚类算法。其核心思想是：对于一个簇，其内部的点在密度上是连通的，即在一个指定半径ε内包含足够多的邻近点（不少于MinPts）。不属于任何簇的点被视为噪声点。
该算法通过不断扩展高密度区域来发现任意形状的簇，并能有效识别离群点。
伪代码如下：
- 初始化所有点为未访问状态
- 对于每个未处理的点p：
- 标记p为已访问
- 找出以p为中心、ε为半径范围内的所有点（即邻域）
- 如果邻域内点数小于MinPts，则将p标记为噪声
- 否则，创建一个新的簇，加入p及其邻域中所有可达点，并递归地将这些点的密度可达点也加入该簇
- 结束循环
优点：
- 能够发现任意形状的簇
- 对噪声和异常值具有较强的鲁棒性
- 无需预先设定簇的数量
缺点：
- 对参数ε和MinPts敏感，选择不当会影响聚类效果
- 在高维空间中，由于“维度灾难”，密度定义变得困难
- 当数据分布不均匀时，难以使用统一的参数处理不同密度区域
2. K均值聚类计算题
给定一组二维数据点，要求使用K均值算法进行聚类。假设初始中心点已知，按照以下步骤迭代执行：
- 将每个点分配到距离最近的聚类中心所在的簇
- 重新计算每个簇的质心（即所有点坐标的平均值）
- 重复上述过程直到质心不再发生显著变化或达到最大迭代次数
注意：计算过程中需使用欧几里得距离衡量点与中心之间的距离。最终输出各个簇所包含的点以及最终的聚类中心坐标。
[此处为图片2]3. Hot Dogs与Hamburger课后习题第一、二问
题目涉及分类问题，给出若干顾客对hot dogs和hamburgers的偏好数据，要求完成以下任务：
（1）构建决策树模型，选择合适的属性划分标准（如信息增益），确定根节点及后续分支节点。
（2）利用训练好的模型对新样本进行预测，判断其更倾向于喜欢hot dogs还是hamburger。
解答时应先计算各属性的信息熵与信息增益，选取增益最大的属性作为分裂依据，逐步构造树结构，并对测试样本自顶向下遍历决策路径得出结果。
[此处为图片3]二、算法题
1. A卷：Apriori算法 / B卷：FP-Growth算法
A卷考察Apriori算法的应用。题目提供一个事务数据集，要求：
- 找出所有满足最小支持度阈值的频繁项集
- 应用Apriori原理（频繁项集的所有非空子集也是频繁的）剪枝候选项
- 逐层生成候选k-项集并统计支持度，直至无法生成新的频繁集为止
B卷考察FP-Growth算法。要求：
- 根据事务表构建FP树，合并相同前缀路径
- 从头表出发，按频率逆序依次提取条件模式基
- 构建各条件FP树，挖掘出所有的频繁模式
两种方法均可用于关联规则挖掘，但FP-Growth避免了生成大量候选项集，效率更高。
[此处为图片4]2. 给定6×6距离矩阵，共6个节点
（1）单链链接（Single Linkage）与全链接（Complete Linkage）的含义
单链链接定义两个簇之间的距离为其成员间最短距离，即取两簇中任意两点间的最小距离作为簇间距离。这种方法容易形成链式延伸的簇，适合发现细长结构，但对噪声敏感。
全链接则定义簇间距离为两簇中任意两点间的最大距离。它倾向于生成紧凑、球形的簇，对异常值较为敏感，但在分离度高的情况下表现良好。
（2）分别绘制单链接与全链接的层次聚类图
基于给定的距离矩阵，采用聚合式层次聚类策略：
- 初始时每个节点自成一类
- 每次合并距离最小的两个簇，更新距离矩阵
- 重复此过程直至所有点合并为一个大簇
根据不同的链接方式更新簇间距离：
- 单链：取min(d(i,j))，i∈C1, j∈C2
- 全链：取max(d(i,j))，i∈C1, j∈C2
最后依据合并顺序绘制树状图（Dendrogram），横轴表示对象，纵轴表示合并时的距离值。
[此处为图片5]三、分析题（15分）
信用卡欺诈检测问题：基于历史交易信息判断交易是否正常，是否存在刷单行为？请说明可采用的数据挖掘方法及其核心思想与步骤。
针对信用卡交易中的异常检测问题，可以采用多种数据挖掘技术结合的方式进行建模分析。
核心思想：正常交易具有一定的行为模式，而刷单或欺诈交易往往表现出异常特征，如短时间内高频交易、金额异常、地理位置跳跃等。通过挖掘历史数据中的规律，识别偏离常态的行为。
主要方法包括：
1. 异常检测算法
- 使用孤立森林（Isolation Forest）或One-Class SVM识别远离正常分布的交易记录
- 基于密度的方法如LOF（Local Outlier Factor）也可用于检测局部稀疏区域的异常点
2. 分类模型
- 若有标注数据（正常/欺诈），可构建监督学习模型，如逻辑回归、随机森林、XGBoost等
- 提取特征包括：交易金额、时间间隔、商户类型、设备指纹、IP地址、历史频率等
- 训练模型区分正常与可疑交易
3. 序列模式挖掘
- 分析用户交易的时间序列模式，识别突发性密集交易（可能为刷单）
- 使用滑动窗口统计单位时间内的交易次数，设置动态阈值报警
4. 图分析方法
- 构建交易网络图，节点为用户或商户，边表示交易关系
- 检测密集子图或环路结构，可能反映团伙式刷单行为
实施步骤：
- 数据预处理：清洗缺失值、标准化数值、编码分类变量
- 特征工程：构造统计特征（日均交易额、波动率）、行为序列特征等
- 模型训练：选择合适算法进行训练与验证
- 模型评估：使用准确率、召回率、AUC等指标评价性能
- 部署上线：实现实时预警机制，对高风险交易进行拦截或人工审核
综上，通过多维度建模与融合分析，可有效提升信用卡欺诈与刷单行为的识别能力。
[此处为图片6]
京公网安备 11010802022788号
