35十四、聚类分析

„14.1„14.2„14.3„14.4„14.514.1„„14.1„„„„“”“”“”14.1„RuiXu200514.1„“”„„“hardclustering”14.1„nK“”KkPk,,1),(L=ωKkpkk,,1),,|(L=θωx∑==KkkkkPpp1)(),|()|(ωθωθxx14.1„ndissimilarityKKn“”„„„14.1„jiiTiijjTijiijpdkpkjkijiijdkkjkijiijdTdiiinSCosddsMahalanobixxddMinkowskixxddRxxSxxxxMxMxxxxxxxxxx===⎟⎠⎞⎜⎝⎛−==⎟⎠⎞⎜⎝⎛−==∈==−==∑∑111211211),(),(),(),,(),,,(LL14.1„„„14.1HierarchicalClusteringHierarchicalClusteringPartitionalClusteringPartitionalClusteringNeuralNetworkbasedmethodsNeuralNetworkbasedmethodsSquarederrorbasedmethodsSquarederrorbasedmethodsCombinatorialsearchtechniquesCombinatorialsearchtechniquesTop-downDivisionTop-downDivisionBottom-upAgglomerativeBottom-upAgglomerativeOthermethodsOthermethodsFuzzy14.214.2„——14.2„∑∑===××=≠==≠=≤===∈==ninjjilkkKkkkkKnnjinnijdTdiiindLJlkCCSCCCnnKCCCddRxxS111111)),(,()(,)3)2)1),(},,{)),(()(D),,(),,,(xxxxxxxααφφIULLL14.2„„K-(K-meansC-means)„„„„„14.2„LDA∑∑∑∑∑∑∑=∈==∈====+=−−=−−=−−=KkkkniiCxikkbwtKkTkkkbTkiKkCkiwniTiitnnnnnkiki111111,1))(())(())((mxmxmSSSmmmmSmxmxSmxmxSx14.2)(max)(min)()()()()())(()(11bwbwtniiTiniTiittrtrtrtrtrtrtrSSSSSmxmxmxmxS+==−−=⎥⎦⎤⎢⎣⎡−−=∑∑==14.2„14.2∑∑∑∑∑∑∑∑∑∑=∈=∈=∈=∈=∈=−=−=−−=−−=KkCjikKkCjikKkCkiKkCkiTkiKkCTkikiwkjikjikikikidnntrtr1,21,21211),(2121)()(]))([()(xxxxxxxxxxxmxmxmxmxmxS14.2„K-(K-means)∑∑∑∈=∈=−==kikiCikkKkCkiCwCCntrCJxxxmmxS1||||min)(min)(min1214.2„“”„Kkk,,1,L=m2,,12min,kiKkjijiifCmxmxx−=−∈=L14.2„K-„1.„2.„3.„4.2-32,,12min,kiKkjijiifCmxmxx−=−∈=L14.2„K-„„O(ndK)„“”„„„outlier14.2„CkCl22||||1||||1lllkkknnnnJmxmx−++−−−=∆14.2„K-(K-means)⎩⎨⎧∉∈=−=−==∑∑∑∑===∈kikikiKknikikiKkCkiCwCCCCtrCJkixxmxmxSx01||||min||||min)(min)(min11212θθθ14.2„K-——kiuniuumuJkiKkkinKkiKKknikimkiMUMU0.,,1,1,)(],,[1,||||min),(min11112,,≥====−=∑∑∑=×==LLUmmMmxMU14.2„Lagrange()∑∑∑∑∑∑∑=========−=∂∂−−−=nimkiniimkiknikimkikniKkkiiKknikimkinuuuJuuJ111111121)()(02)1(||||),,,,(xmmxmmxMUλλλL14.2()()∑∑∑∑∑∑∑=−−=−=−−====−−==⎟⎟⎠⎞⎜⎜⎝⎛−⇒===⎟⎟⎠⎞⎜⎜⎝⎛−==−−=∂∂−−−=KjmjimkikiKkmkiiKkkimkiikiikimkikiniKkkiiKknikimkinumuniKkmumuuJuuJ11121121112111221111121||||1||||11||||1,,1,,,1,||||0||||)1(||||),,,,(mxmxmxmxmxmxMUλλλλλλLLL14.2„()())()()()(||||1||||11)1(1)1()1(1112)(112)()1(∑∑∑=+=++=−−+=−−=njmtkjnjjmtkjtkKjmtjimtkitkiuuuxmmxmx14.2())()()()(1,1,)(1)1()(1)()()1(1)1(1)1(1)1()1(1)()()()(1)()()()(tkjnjtkjtknjtktkjtkjjnjtkjnjmtkjnjjmtkjtknitkitkitktkinjtkjtkmtkitkiuuwwuwmxmmmxxxm−+=+−=======∑∑∑∑∑∑∑=+=+=+=+=++==∆∆ααααηαη14.2„K-——K-∑∑∑∑∑∑======+−=−=−⎩⎨⎧∉∈==−=nljljklkjknjjikjkiinjjkjkikikikikiniikikkKknikikiCCKnKnKnCCnCJ1,212121112),(1),(2),(||)(1)(||||~)(||01,)(1~||~)(||min)(minxxxxxxxxmxxxxmmxθθθφθφφθφθφθ14.2„K-K“”K14.2„“”„“”“”∑∑∈∈=−=kikiCiCikdxxxxxxm),(minarg||||minarg22∑∈∈=kikCiCkdxxxxm),(minarg214.2„K-medoids„1.medoids„2.medoids„3.medoids„4.2-3∑∈∈≡kikCiCkdxxxxm),(minarg2()()kiKkjijiddifCmxmxx,min,,2,,12L==∈14.314.3„——„„14.3„x1,x2,x3,x4,x5x1,x2,x3x4,x5x1,x2x1x2x3x4x514.3„„1.„2.„3.„4.214.3„1.51.11.21.31.52.22.11.81.71.71.61.71.42.01.8x1x2x3x4x5x6x9x8x75.01.014.3„——Single-Linkage),(min),(,minjiCClkdCCdljkixxxx∈∈=14.3„Single-Linkagex1x2x3x4x5x6x7x8x91.01.11.21.31.41.61.75.014.3„——Complete-Linkage),(max),(,maxjiCClkdCCdljkixxxx∈∈=14.3„Complete-Linkagex1x2x3x4x5x6x7x8x91.01.11.41.51.62.02.214.3„Average-Linkage——Average-Linkage∑∑∈∈=kiljCCjilklkaveragedCCCCdxxxx),(1),(14.3„Average-Linkagex1x2x3x4x5x6x7x8x91.01.11.41.41.61.751.814.3„Single-LinkageAverage-LinkageComplete-Linkage),(),(),(),(),(),(),(ljlijiljjliilkljiCCdCCdCCdCCdCCdCCdCCCd−+++==γβααU),(min),(,minjiCClkdCCdljkixxxx∈∈=∑∑∈∈=kiljCCjilklkaveragedCCCCdxxxx),(1),(),(max),(,maxjiCClkdCCdljkixxxx∈∈=14.3„),(),()),(),,(min(),min(5.05.05.05.0,0,5.0minminminminlkljiljlijliljliljlilkljiCCdCCCdCCdCCdddddddd====−−+=−====Uγβαα14.3„iCkCjCjikjilkCCCkjilCCdCCdU=≠∀≥,,),,(),(14.3„),(),(),(),(),(),(),(ljlijiljjliilkljiCCdCCdCCdCCdCCdCCdCCCd−+++==γβααU1,0,0≥++≥≥βααααjiji{}0,max0≤≤−−≥cjiααγ14.3),(),(),()),(),(()),(),((),(),(0),(),(,0),(),()),(),(()),(),((),(),(),(),(),(),(),(1jiijlijiljjjiliijilkijilkljlijiljjjiliijiljlijiljjliilkjiCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCdCCd≥−+−+−+≥≤≤−≥≥−+−+−+≥−+++=−−≥γααγαγγααγβααααβ14.3„„1.„2.„3.214.3„„O(n²)„14.3„„„„„14.3„——GGG(MinimumSpanningTree)„14.3„1.11.21.31.61.71.4x1x2x3x4x5x6x9x8x75.01.014.3„„1.„2.„14.3„x1,x2,x3,x4,x5,x6,x7,x8,x9x1,x2,x3,x4,x5x6,x7,x8,x9x6,x7x8,x9x8x9x4,x5x1,x2,x3x1,x2x3x1x2x6x714.3„„„14.3„{}{}TChdCChCdmedChCdChC=∈=∈=∑∈)(),(21)(,),,()(,),,(max)(,321yxyxyxyxyxyx14.3„1.51.11.21.31.52.22.11.81.71.71.61.71.42.01.8x1x2x3x4x5x6x9x8x75.01.054.14.15101)(5.1)(2.2)(131211=×===ChChCh275.12.1081)(7.1)(0.2)(232221=×===ChChCh14.3„{}jijijiCCChChCCd,,)(),(max),(min∀14.3„{}{}{}54.1)(),(max7.1)(),(max2.2)(),(max0.5),(23132212211121min====ChChChChChChCCd1.51.11.21.31.52.22.11.81.61.71.61.71.42.01.8x1x2x3x4x5x6x9x8x75.01.014.414.4„„„„14.4„„„„14.514.5„„„„14.5„„„[1]A.K.Jain,M.N.MurtyandP.J.Flynn,Dataclustering:areview.ACMComputingSurveys,Vol.31,Issue3,Sept.1999.„[2]DanielFasulo,Ananalysisofrecentworkonclusteringalgorithms.TechnicalReport01-03-02,UniversityofWashington,April1999.„[3]RuiXuandDonaldWunschII,Surveyofclusterin