文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 基于k最相似聚类的子空间聚类算法
侵权投诉

基于k最相似聚类的子空间聚类算法

计 算 机 工 程 第 35 卷 第14期

Vol.35 No.14 Computer Engineering ·博士论文·

文章编号:1000—3428(2009)14—0004—03

文献标识码:A

2009年7月

July2009

中图分类号:TP311

基于k最相似聚类的子空间聚类算法

单世民,闫 妍,张宪超

(大连理工大学软件学院,大连 116621)

摘 要:子空间聚类是聚类研究领域的一个重要分支和研究热点,用于解决高维聚类分析面临的数据稀疏问题。提出一种基于k最相似聚类的子空间聚类算法。该算法使用一种聚类间相似度度量方法保留k最相似聚类,在不同子空间上采用不同局部密度阈值,通过k最相似聚类确定子空间搜索方向。将处理的数据类型扩展到连续型和分类型,可以有效处理高维数据聚类问题。实验结果证明,与CLIQUE和SUBCLU相比,该算法具有更好的聚类效果。 关键词:聚类算法;子空间聚类;高维数据

Subspace Clustering Algorithm Based on k Most Similar Clustering

SHAN Shi-min, YAN Yan, ZHANG Xian-chao

(School of Software, Dalian University of Technology, Dalian 116621)

【Abstract】Subspace clustering is an important part and research hotspot in clustering research, which resolves the problem of clustering sparsedata in high dimensional data environment. A subspace clustering algorithm based on kmost similar clustering is presented. This algorithm holds thek most similar clustering by the similarity of the clusters, discovers the different subspace through the different local density threshold, ascertains thesubspace search direction by the k most similar clustering and clusters both continuous data and categorical data. The high dimensional data can beeffectively clustered in this algorithm. Experimental results show that this algorithm is more effective in clustering than CLIQUE and SUBCLU. 【Key words】clustering algorithm; subspace clustering; high dimensional data

1 概述

高维聚类分析是聚类分析的研究难点[1],具体表现为:(1)高维数据中存在大量无关属性,导致在全维空间中存在簇的可能性几乎为零;(2)在高维空间中,数据间距几乎相等的情况普遍存在。传统聚类算法在低维数据集上表现良好,但在对高维数据对象聚类时会遇到困难。为解决上述问题,文献[2]首先提出子空间聚类的概念。

CLIQUE算法是最早且最具代表性的子空间聚类算法[3],它搜索最大的密集超立方体,并以此为基础发现子空间聚类。另一个具有代表性的算法SUBCLU[4]具有更好的聚类精度,它采用DBSCAN算法中的密度连通概念形成子空间聚类。以上2个算法通过全局密度阈值确定子空间聚类,如果子空间维数的不同,子空间密集程度也会不同。它们没有考虑数据类型的多样性。用于分类型数据的聚类算法ROCK[5]虽然取得了较好的聚类结果,但全局方法的使用导致算法复杂度增加。

针对上述算法存在的问题,本文算法的主要工作集中在以下3个方面:(1)采用一种聚类间相似度计算方法,通过其确定k最相似聚类,缩小搜索空间,提高了算法可伸缩性和执行效率;(2)在子空间聚类搜索过程中摒弃传统算法采用的全局密度阈值,在不同子空间中采用不同密度阈值,提高了子空间聚类算法聚类结果的精度;(3)将子空间聚类算法处理的数据对象扩展为连续型数据和分类型数据。

n个位于d维特征空间的数据对象组成的集合,记为DB={Xi|i∈[1,n],xij=Xi.Aj},其中,点Xi=(xi1,xi2,…,xij,…,xid),Xi的第j个属性值xij为其在Aj维上的取值。

设k维子空间Sk A,其中,k≤n。在Sk子空间中的元组集合记做TSk(xi1, xi2,…, xik)={Xi|Xi∈Sk, xij=Xi.Aj|j∈[1,k]}。将Sk子空间投影到每一维产生的不同元组的数目记为πSk(DB)。 2.2 算法基本策略

2.2.1 算法策略及相关定义

本文以所有一维空间聚类为基础,通过发现包含相同数据对象的相似聚类来确定子空间搜索方向,进而将不同维度中的相似聚类进行合并,最终发现子空间聚类。

为了处理不同类型的数据,对于连续型数据,采用DBSCAN方法在每一维上对所有数据对象进行聚类。对于分类数据,由于其自身的无序性特点,在每一维上将属性值相同的数据对象作为一个自然聚类。

定义1(基本聚类) 将以上方法产生的所有一维空间的聚类的集合称为基本聚类,记为C1。

定义2(基本聚类相似度) 给定c1, c2∈C1,其中,c1在Ai维,c2在Aj维,且i≠j,其相似度定义为基本聚类c1, c2所包含数据对象集合的交集的元素数目,记为sim(c1,c2)=|c1∩ c2|。

1

定义3(最相似聚类) 给定聚类c∈C,c的最相似聚类MSC(c)∈C1满足条件: cp∈C1, sim(c, MSC(c))≥sim(c, cp),

基金项目:国家自然科学基金资助项目(70671016, 60873180, 60673066)

2 问题描述及算法策略

2.1 问题描述 作者简介:单世民(1978-),男,讲师、博士,主研方向:知识发现;

设A=﹛A1,A2,…,Ad﹜代表数据维集合,A=A1×A2×…×Ad闫 妍,硕士研究生;张宪超,副教授、博士

代表一个d维数据空间,其中,d为正整数。设DB代表由 收稿日期:2009-02-25 E-mail:ssm@dlut.edu.cn —4—

第1页

你可能喜欢

  • 数据挖掘聚类算法
  • 空间聚类
  • 遗传算法聚类分析
  • 空间统计
  • kmeans聚类算法
  • 模糊聚类算法

热门文档

相关文档

  • 子空间聚类改进算法研究综述

    子空间聚类改进算法研究综述李霞1’2,徐树维2(1....聚类操作的基础是数据对象之间相似性的度量,相似度高...②发现类:子空间搜索的目的是发现k维空间及其子空 ...

  • 1一种新的子空间聚类算法

    1一种新的子空间聚类算法_IT/计算机_专业资料。...聚类 , 则 S 也是该数据空间的任意一个 K - 1...数据去描述的事物总是具有比较多的值相近或相似 的...

  • 子空间聚类改进算法研究综述

    和网格的子空间聚类算法 ,自动子空间聚类算法的实用...聚类操作的基础 是数据对象之间相似性的度量 , 相似...② 发现类 : 子空间搜索的目的是发现 k 维空间...

  • 基于方差权重矩阵模型的高维数据子空间聚类算法

    的聚类分析方法基本上都是通过搜索出数据集中某 一维相似程度最高 / 距离最短...模型的高维数据子空间聚类算法 等: · 2869· 1 m -1 ∑k= σ2 k ? ...

  • 子空间聚类算法的研究及应用

    将客户分成若干个具有相似特征的客户群,并对客户群...基于k均值,k中心点和其他一些方法的聚类分析工具已经...维子空间聚类算法效率不高,随着包含簇的子空间的最...

  • 一种改进的子空间选择算法在聚类中的应用

    关键词 聚类 ; 空间; 郁近; 子k 近似部近中图法分类号 T3Pl 聚类是数据...可以认 n一i()ts 最早提出的子空间聚类算法是c QE5用 ILu〔,〕 类似于”...

  • 2一种适用于高维数据流的子空间聚类方法

    A 类似的我们可 k 以在子空间找到 ξ 个网格单元 。 一种基于网格的子空间聚类算法 , 文中提出了一种记录单元 格数据信息的数据结构 ,并且每个簇所选用的维度...

  • 1采用属性聚类的高维子空间聚类算法

    的聚类算法 ,聚类结果即为所有兴趣度子空间的候选集合 ,最后调用聚类算法得到...其中 , k 是数据点的聚集常数 ,表示数据点分布相对 于均匀分布的密度倍数 , ...

  • 子空间聚类算法的研究新进展

    子空间聚类算法的研究新进展_工学_高等教育_教育...数有 : 簇的数 量、 相同或相近 的簇 的大小 ...k 新维 中进行 有效聚类 ,个 从而达 到减 少维...

  • 高维分类属性的子空间聚类算法

    有很多聚类结果在全维属性 空间中并不相似 , 但...了子空间聚类算法的相关研究 . 最先 出现 的是 ...k,≠ja和jj ( )对所 有的 j∈{,k,21…, }...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email