资源描述：
《基于最近邻优先的高效聚类算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第36卷第6期四川大学学报(工程科学版)Vol.36No.62004年11月JOURNALOFSICHUANUNIVERSITY(ENGINEERINGSCIENCEEDITION)Nov.2004文章编号:100923087(2004)0620093207基于最近邻优先的高效聚类算法1111,21,314胡建军,唐常杰,李 川,彭 京,元昌安,陈安龙,蒋永光(1.四川大学计算机学院,四川成都610064;2.成都市公安局科技处,四川成都610017;3.广西师范学院信息技术系,广西南宁530001;4.成都
2、中医药大学,四川成都610075)摘 要:针对高维空间中任意形状的多层次聚类问题,基于“同类相近”的思想,提出并实现了最近邻优先吸收聚类算法NNAF算法。证明了最近邻点搜索定理,基于这一定理又提出了SNN(SearchingNearestNeighbors)算法和GSNN(Grid2basedSearchingNearestNeighbors)算法,其时间复杂度为O(n3log(n)),当用扫描图像所得数据时,时间复杂2度会降为O(n);而使用传统的搜索算法,时间复杂度为O(n);提出了实现任意形状高维空间聚
3、类的NNAF算法,时间复杂度为O(n);提出了MLCA(Multi2layerClusterAlgorithm)算法并证明了两个相关的定理,在改变阈值后重新聚类时,使用MLCA算法可以节省90%以上的时间。实验结果显示,以上算法适应于任意形状的高维空间数据的聚类,可以有效过滤噪声数据,且用户需要的先验知识少、可快速获得各种层次的聚类结果。关键词:数据挖掘;聚类分析;最近邻优先吸收;多层次聚类中图分类号:TP311.13文献标识码:AAnEfficientMulti2layerClusteringAlgorit
4、hmBasedonNearestNeighborsFirst1111,21,314HUJian2jun,TANGChang2jie,LIChuan,PENGJing,YUANChang2an,CHENAn2long,JIANGYong2guang(1.SchoolofComputer,SichuanUniv.,Chengdu610064,China;2.Dept.ofSci.andTech.,ChengduPublicSecurityBureau,Chengdu610017,China;3.Dept.ofIn
5、fo.andTech.,GuangxiTeachersEducationUniv.,GuangxiNanning530001,China;4.ChengduUniv.ofTraditionalChineseMedicine,Chengdu610075,China)Abstract:NearestNeighborsAbsorbedFirst(NNAF)clusteringalgorithmwasproposedtoresolvetheproblemofthemul2ti2layerclusteringforhi
6、ghdimensionaldatawitharbitraryshapebasedontheideathatthedatainsameclustermustbenear.Asearchingnearestneighbortheoremwasproved.Basedonthetheorem,SNN(SearchingNearestNeighbors)andGSNN(Grid2basedSearchingNearestNeighbors)algorithmswereproposedwithtimecomplexit
7、yO(n3log(n))orO(n)ifthedataaregainedbyscanningimage.Theyaremuchfasterthanthetraditionalsearchingnearestneighborsal22gorithmwithO(n).AclusteringalgorithmofNNAFtoprocessmulti2dimensionaldatawitharbitraryshapewasproposedwithtimecomplexityO(n).Multi2layerCluste
8、ringAlgorithm(MLCA)wasproposedandtwointerrelatedtheoremswereproved.Inthecaseforthresholdadjusting,itsavestimeover90%.Theexperimentsshowedthatthenewalgorithmscanefficientlyprocesshighdimensionaldatainar
