面向数据流的加权聚类及演化分析研究

@126.comDijkstraTP1811GuhaS[1]2000LOCALSEARCHO’CallaghanL[2]2002STREAMAggarwalC.[3]2003CluStream(micro-Cluster)(macro-Cluster)V.Ganti[4],CharuC.Aggarwal[5,6],VenkateshGanti[7]MohamedMedhatGaber[8][9]2003[10]2005[11]2006ACluStreamCluStream-1-CluStreamCluStreamCluStream22.11(,Cluster)mDSm=},,,,,,{2211NNjjjjjjTXTXTXLDSC=},,,,{11nniiiiTXTXLDS(Cluster)=DS(Cluster)CluStreamncfcfCFCFttxx,1,2,1,2)2,,2(21xmxxCFCFCFL=(()∑==niijjkxkxCF122mk,,1L=)DSCk)1,,1(11xmxxCFCFCFL=(()∑==niijjkxkxCF11mk,,1L=)DSCk()∑==niijjtTcf122DSC∑==niijjtTcf11DSCnDSC[3]2.2-2-(,Clusters)mDSm=DS(Clusters)=(W,K,p)},,,,,,{2211NNjjjjjjTXTXTXL),,(1m=DSmmKpK2.31(,AdditivityTheorem)C1C),1,2,1,2(11111ncfcfCFCFttxx2),1,2,1,2(22222ncfcfCFCFttxxC=C1C2),11,22,11,22(2121212121nncfcfcfcfCFCFCFCFttttxxxx+++++2(,SubtractionTheorem)C1C),1,2,1,2(11111ncfcfCFCFttxx2),1,2,1,2(22222ncfcfCFCFttxxC=C2-C1),11,22,11,22(1212121212nncfcfcfcfCFCFCFCFttttxxxx−−−−−[3]33.13.1.1DS(Cluster1),DS(Cluster2),DS(Cluster)Cluster1,Cluster;//Cluster;//-3-(Cluster)=DS(Cluster1)+DS(Cluster2)3.1.2DS(Cluster1),DS(Cluster2),DS(ClusterDifference)Cluster1,Cluster2;//ClusterDifference;//Step1.Step2.2DS(ClusterDifference)=DS(Cluster2)DS(Cluster1)3.23.2.14DS(Clusters1)=(W1,K1,p1),Clusters1={C11,C12,…,C1K1}DS(Clusters2)=(W2,K2,p2),Clusters2={C21,C22,…,C2K2}DS(Clusters)=(W,K,p),Clusters={C1,C2,…,CK}Clusters1,Cluster2;//Clusters;//Step1.2211⋅+⋅=ωω121=+ωω2/1,21=ωω-4-(Clusters)=DS(Clusters2)+DS(Clusters1)Step3.3.2.24DS(Clusters1)=(W1,K1,p1)Clusters1={C11,C12,…,C1K1}DS(Clusters2)=(W2,K2,p2)Clusters2={C21,C22,…,C2K2}DS(ClustersDifference)=(W,K,p)ClustersDifference={C1,C2,…,CK}Clusters1,Cluster2;//ClustersDifference;//Step1.1122⋅−⋅=ωω121=+ωω2/1,21=ωωStep2.DS(ClustersDifference)=DS(Clusters2)DS(Clusters1)Step3.4C4.11,2,3,4,5,6,7,8,94.2-5-[i](i=1,2…,K)5CluStream(summarystatistics)(evolution)SD=},,,,,{11LLNNTXTX()mi()i(timestamp)),,(1imiixxXL=LL,,,1Ni=iTLL,,,1ni=CluStreamCluStreamStep1.Step2.Step3.Step2-6-://[1]GuhaS,MishraN,MotwaniR,O’CallaghanL.Clusteringdatastreams.In:FOCS2000.2000.359−366.[2]O’CallaghanL,MishraN,MeyersonA,GuhaS.Streaming-Dataalgorithmsforhigh-qualityClustering.In:ICDEConf.2002.685−704.[3]AggarwalC,HanJ,WangJ,YuPS.AframeworkforClusteringevolvingdatastreams.In:VLDB2003.2003.81−92.[4]V.Ganti,J.Gehrke,R.Ramakrishnan,W.-Y.Loh.AFrameworkforMeasuringDifferencesinDataCharacteristics.ACMPODSConferenceProceedings,1999.[5]CharuC.Aggarwal.AFrameworkforDiagnosingChangesinEvolvingDataStreamsSIGMOD2003[6]CharuC.Aggarwal.AnIntuitiveFrameworkforUnderstandingChangesinEvolvingDataStreams.[7]VenkateshGanti,JohannesGehrke,RaghuRamakrishnan,Wei-YinLoh.AFrameworkforMeasuringDifferencesinDataCharacteristics.JournalofComputerandSystemSciences64,542–578(2002).[8]MohamedMedhatGaber,ArkadyZaslavskyandShonaliKrishnaswamy.MiningDataStreams:AReview.18-25.SIGMODRecord,Vol.34,No.2,June2005[9],,,.,().28(9):1157-1162,2005[10]...26(5):1130-1169,2005[11],,...2006,17(3):379−387.-9-:ClusterMerging;SubtractingofCluster;ClustersMerging;EvolutionAnalysisofClusters-10-{doubleCF2x[m];//CF2xmdoubleCF1x[m];//CF1xmdoublecf2t[m];//cf2tmdoublecf1t[m];//cf1tmintn;};typedefstructCluster*ClusterPointer;//structKPointer//KK{ClusterPointer*q;//ClusterPointerq[K],q1,q2,…,qk;};typedefstructKPointer*PKPointer;//KstructClusters//{intK;//doublew[m];//mPKPointerp;//pK};typedefstructClusters*ClustersPointer;//1.doubledistance(Cluster*cp1,Cluster*cp2){inti;-11-=0;for(i=0;im;i++){disM+=((cp1-CF1x[i]/cp1-n)-(cp2-CF1x[i]/cp2-n))*((cp1-CF1x[i]/cp1-n)-(cp2-C