数据挖掘考试聚类题目详解

"数据挖掘考试题目-聚类.doc" 数据挖掘是信息技术领域的重要分支，而聚类是数据挖掘中的基础任务之一，它旨在无监督的情况下将数据集中的对象按照相似性进行分组，形成所谓的“簇”。本考试题目主要关注聚类算法中的密度基聚类算法——DBSCAN。 1. 密度的基于中心的方法如DBSCAN将点分为三类：核心点、边界点和噪声点。核心点是其邻域内有足够的点（满足MinPts条件）的点；边界点位于至少一个核心点的邻域内，但自己不是核心点；噪声点则是既不属于核心点也不属于边界点的点。 2. DBSCAN算法的时间复杂度在最坏的情况下是O(n^2)，空间复杂度为O(n)，其中n是数据集中点的数量。这意味着在大数据集上，DBSCAN可能会变得效率较低。 3. DBSCAN算法的优点包括其耐噪声的能力，能处理任意大小和形状的簇，无需预先指定簇的数量。这使得DBSCAN相对于其他聚类算法具有更高的灵活性。 4. 然而，DBSCAN的缺点在于处理高维数据和变密度的数据时可能效果不佳。高维数据中的“维度灾难”可能导致点之间的相似度难以准确计算，而变密度的数据则可能导致簇的边界难以确定。 5. DBSCAN的两个关键参数是EPS（邻域半径）和MinPts（邻域内点的最小数量）。这两个参数的恰当选择对聚类结果至关重要。 6. 聚类有效性的评估通常分为非监督度量和监督度量。非监督度量如簇的凝聚性和分离性，常用指标如均方差（SSE），用于度量簇内部的相似性和外部的差异。监督度量，又称外部指标，通常涉及与已知类别标签的匹配，例如监督指标的熵。 7. 监督度量度量簇标号与外部提供的标签的匹配程度，这通常通过比较如准确率、召回率等监督指标来实现。 8. 在评估聚类效果时，如果相似度矩阵显示出明显的簇结构，矩阵应大致呈现块对角形式，即同一簇内的点彼此相似，不同簇间的点差异较大。 9. DBSCAN的参数确定通常需要观察点到它的第K个最近邻的距离（K-距离），以找出合适的Eps值，确保邻域内有足够多的点。 10. 不引用附加信息评估聚类分析结果对数据拟合情况的技术称为非监督学习，因为这种评估方式不依赖于预先存在的类别信息。 选择题部分： 1. DBSCAN算法的正确过程是先将所有点标记为核心点、边界点和噪声点，然后删除噪声点，为距离在Eps之内的所有核心点赋予边，接着每组连通的核心点形成一个簇，最后将边界点指派到相应的簇中。所以正确答案是B。 2. DBSCAN在最坏情况下的时间复杂度是O(m^2)，其中m是数据点的数量，故答案是C。 3. 基本DBSCAN的参数选择中，点到它的K个最近邻的距离中的K常被用作MinPts参数，因此答案是B。 4. 当采用K-距离的方法选择DBSCAN的Eps和MinPts参数时，K-距离被用来帮助确定这些参数的合适值，所以选项B也是正确的。