自适应特征权重的Kmeans聚类算法

2012－09－102012－12－182013－03－05510690041972－、。http//．cnki．net/kcms/detail/61．1450．TP．20130305．0816．023．htmlK－means李四海1，满自斌2(1．甘肃中医学院，甘肃兰州730000;2．兰州理工大学，甘肃兰州730050)K－meansK－meansAFW－K－means。、UCIBCW。K－means。K－meansTP181A1673－629X201306－0098－04doi10．3969/j．issn．1673－629X．2013．06．025K－meansClusteringAlgorithmBasedonAdaptiveFeatureWeightedLISi－hai1MANZi－bin21．GansuCollegeofTraditionalChineseMedicineLanzhou730000China2．LanzhouUniversityofTechnologyLanzhou730050ChinaAbstractInordertoimprovetheaccuracyandstabilityoftraditionalK－meansalgorithmonmedicaldataclusteringproposedanadap-tivefeatureweightedK－meansclusteringalgorithmnamedAFW－K－means．Firstlyinitialclusteringcenterwaschosenbycalculatingmeansquaredeviationoffeatureattribute．Thenaccordingtotheresultsofeachiterationthefeatureattributeweightindistanceformulaismodifiedbasedontheprincipleofminimum－in－cluster－distanceandmaximum－between－cluster－distancewhichcanreflectthetruedistanceamongthedatapointsintheEuclideanspace．FinallythevalidityoftheproposedapproachisdemonstratedbytheexperimentofUCIdatasetsuchasBreastCancerWisconsindataset．TheresultsshowedthatthealgorithmhashigherprecisionofpredictionandbetterstabilitythantraditionalK－meansalgorithm．KeywordsK－meansmedicaldataclusteringAFWclusterevaluationconfusionmatrix0!。、、、、12。K－means、。。3～6。7。。Fisher89、10、。K－means。23620136COMPUTERTECHNOLOGYANDDEVELOPMENTVol．23No．6June2013。11。UCIK－means。1K－meansnkk。K－meansankbcdbc。K－meansdmn=∑mj=1xmj－xnj槡21。2K－means2．11nmX=x11x12…x1mx21x22…x2m…………xn1xn2…xnm0．011。2nKn1n2…nkKjdn=∑Kk=1∑nki=1xij－mkj22mkjkj。3Kjdw=∑Kk=1mkj－mj23mjj。4jcj=dw/dn4、。。2．2jwj=cj/∑mj=1cjwj∈01∑mj=1wj=151dmn=∑mj=1wjxmj－xnj槡26。。wj。2．3K－means。。K－means。K。、。2．4AFW－K－meansnmnm·99·6K－meanskk。1meanv1m。2CC=mean±2vk－1×jj=1…k/2∪meankmean±2vk×jj=12…k/2k{2v/k2v/k－1。3wj=1/mj=12…m4。。50。。6、。746。33．1。。、。K－means。、VDVI。C1C2…CkP1P2…Pkn11n12…n1kn21n22…n2k…………nk1nk2…nkkP1P2…PkkC1C2…Ck。。VDVI12VD=2n－∑imaxjnij－∑jmaxinij/2nVI=－∑ipilogpi－∑jpjlogpj－2∑i∑jpijlogpij/pipjK－means。VI。3．2MatlabR2010bK－meansK－means8。UCIIris。4petallengthpetalwidth。K－means107．3K－means54。Iris1图1Iris特征权重调整曲线1petallengthpetalwidth0．250．44840.4769。、。BreastCancerWis-consinBCW10、、、、、、、、BbenignMma-lignant。K－means85．41%7·001·231。35762123293．32%。。表1BCW数据集聚类结果BMB3516M32180BCWVDVI2表2BCW数据集VD和VI比较K－meansK－meansVD0．14590．07910．0668VI0．92640．75790．6516VDVI。2VD、VI。VD=1－VD。。UCI4102K－means。图2不同算法在4个数据集上的迭代次数2K－means。。K－means。UCI10103K－means10。表3不同K－means聚类算法的测试结果对比K－means%K－means%%Iris89．339696image51．3465．1963．98Wine87．9691．0192．13Breast85．4192．0993．32Balance_scale48．0047．0454．88lonosphere71．2370．6672．36Vehicle36．2937．5944．21Haberman50．0050．6550．65Waveform49．7650．0850．22Pima67．0667．0667．89Breast、HabermanPimaK－means。K－meansBal-ance_scaleVehicleK－meansK－meansK－meansBalance_scale0．25K－means。。4。K－means。1．J．(下转第105页)·101·6K－meansHQA。HQA、、13～15。。。。1．M．2．2005．2．FlowShopJ．200729793－95．3．J．2008272188－191．4．WebJ．201222339－43．5．J．200626122956－2960．6．J．2006345897－901．7．J．2010325150－155．8．JobShopJ．200945301077－1079．9．J．20114781235－1237．10．GAJ．201147131066－1069．11．J．201132355－58．12TuZhenguoLuYong．ARobustStochastieGeneticAlgorithmstGAforGlobalNumericalOptimizationJ．IEEETrans-actionsonEvolutionaryComputation200485456－470．13TalbiHDraaABatoucheM．ANewQuantum－inspiredGe-neticAlgorithmforSolvingtheTravelingSalesmanProblemC//2004IEEEInternationalConferenceonIndustrialTechnology．s．l．s．n．20048－10．14YuanBoGallagherM．OntheImportanceofDiversityMainte-nanceinEstimationofDistributionAlgorithmsC//Proceed-ingsofthe2005GeneticandEvolutionaryComputationCon-ference．WashingtonDCACM2005719－726．15LiPCLiSY．Quantum－inspiredevolutionaryalgorithmforcontinuousspaceoptimizationbasedonblochcoordinatesofqubitsJ．Neuroeomputing2008721－3581－591．檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪檪(上接第101页)200819148－61．2．D．2011．3．K－meansJ．200733365－66．4．K－meansJ．201121262－65．5XuJunlingXuBaowenZhangWeifeng．StableInitializationSchemeforK－meansClusteringJ．WuhanUniversityJour-nalofNaturalSciences200914124－28．6KangPChoS．K－meansclusteringseedsinitializationbasedoncentralitysparsityandisotropyC//Proceedingsofthe10thInternationalConferenceonIntelligentDataEngineeringandAutomatedLearning．BerlinSpringer2009109－117．7．K－J．2003406869－873．8ModhaDSSpanglerWS．FeatureWeightinginK－meansClusteringJ．MachineLearning2003523217－237．9．FisherK－meansJ．201027124439－4442．10．K－meansJ．20113161675－1677．11TsaiCYChiuCC．Developingafeatureweightself－adjust-mentmechanismforaK－meansclusteringalgorithmJ．ComputationalStatistics＆DataAnalysis200852104658－4672．12WuJunjieXiongHuiChenJian．AdaptingtheRightMeasuresforK－meansClusteringC//ProceedingsofThe15thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMiningKDD2009．Pariss．n．2009877－886．·501·6