文档介绍：基于网格的聚类措施研究
摘要:已有的聚类算法对于发现任意形状的聚类和解决离群点效果不抱负,分析了既有基于格的聚类算法。使用格措施的数据分析措施将空间划分为由(超)矩形格单元构成的格,然后在格单元上进行聚类。最后,总结全文并提出密度函数来决定切割平面,可以将数据空间划分为规则的或不规则单元,和老式的等间距的划分相比,可以用此来解决高维聚类的问题。而CLTree用划分后的信息增益来选择最优划分。
自顶向下划分措施的核心长处在于不需要顾客指定划分参数,而是根据数据的分布对空间进行划分,因此这种划分更为合理。数据空间维度对自顶向下格措施的影响较小,可以迅速将大型高维数据集中的簇分隔开。这一类措施的计算复杂度和数据集大小和维度所有呈线性关系适合于解决高维数据。由于划分是基于数据分布的,而一般觉得噪音是在整个空间均匀分布的,因此自顶向下划分措施对噪音不敏感。但是,由于这种措施得到的格单元的体积远不小于由底向上格措施中的格单元体积,因此措施产生的簇的描述精度比由底向上的格措施得到的簇的描述精度要低。并且在自顶向下的划分过程中,同一种簇也许被划分到不同样的区域中,最后得到的同一区域也也许涉及不同样的簇,这样就进一步减少了算法的对的度。此类划分措施的另一种缺陷是它在划分过程中,需要对数据集进行多次扫描。
而由底向上划分措施在于只需对数据集进行一次线性扫描和较高的簇的描述精度。因此,两类措施合用于不同样的问题。前者适于解决高维数据集,后者能有效解决存替代价较大的超大型数据集和动态数据。
3 基于格的聚类过程
基于格的聚类算法的基本过程是,一方面将数据空间W划分为格单元,将数据对象集O 映射到格单元中,并计算每个单元的密度。根据顾客输入的密度阈值MinPts 鉴定每个格单元与否为高密度单元,由邻近的稠密单元组形成簇[11],如表1。
算法1中的环节1已经在上文具体阐明,下面具体简介环节24的内容。
格单元的密度
簇就是一种区域,该区域中的点的密度不小于和之相邻的区域。在格数据构造中,由于每个格单元所有有相似的体积,因此格单元中数据点的密度即是落到单元中的点的个数。据此可以得到稠密格单元的密度是,设在某一时刻t一种格单元的密度为density,定义density=单元内的数据点数/数据空间中总的数据点数,设密度阈值为, 为顾客输入的密度阙值,当density> 时,该格单元是—个密集格单元。
相对于稠密格单元来说,大多数的格单元涉及很少甚至空的的数据,这一类格单元被称为稀疏格单元。大量的稀疏格单元的存在会极大的减少聚类的速度,需要在聚类之前对稀疏格单元进行解决,定义稀疏密度阈值为,当density>时,该格单元是—个稀疏单元。对于稀疏格单元的解决措施一般采用压缩的措施或直接删除的措施,如果需要保存稀疏格单元用于后续解决,可以使用压缩的措施;如果在既有数据的基本之上直接聚类,可以删除稀疏格单元,理论分析和实验证明删除稀疏格单元并不影响聚类的质量[12]。
%
由稠密格单元形成簇
在基于格的聚类算法中,根据以上分析,由邻接的稠密单元形成簇是相对直截了当的,这也是基于格的措施的长处之一。但是需要一方面定义邻接单元的含义。设n维空问中的存在任意两个格单元U1和U2,当这两个格