半监督的聚类和降维研究及应用

南京航空航天大学硕士学位论文半监督的聚类和降维研究及应用姓名：金骏申请学位级别：硕士专业：计算机应用技术指导教师：张道强20071201i1ROCSemi-ROC2SKFCMSKPCMSKFCM3VC++6.0iiAbstractSemi-Supervisedlearningisahottopicofmachinelearningrecently,relativetosupervisedlearningandunsupervisedlearningmethods,asemi-supervisedlearningalgorithmcanmakeuseoflabeledsamplesandunlabeledsamplesinthesametime,obviously,inthisformthelearningalgorithmcangetabetterperformance.Semi-supervisedlearningcanbedividedintotwowaysSemi-supervisedclassificationandsemi-supervisedclustering.Asemi-supervisedclusteringalgorithmusesomesupervisedsamplestoinstructtheclusteringprocedureinordertogetabetterresult,andasemi-supervisedclassificationusesomeunlabeledsamplestotrainabetterclassify.Thispaperbasedonthesemi-supervisedlearningandpaysitsattentiononsemi-supervisedclusteringalgorithmsandsemi-superviseddimensionreduction.Theprimaryworkofthispapercanbesummarizedasfollows:(1)BaseontheROC,asemi-supervisedalgorithm(calledSemi-ROC)isproposed,withthehelpofsupervisedsamples,thenewalgorithmscangetabetterperformance,theexperimentresultontheartificialdatasetandUCIdatasetshowstheproposedalgorithmiseffectiveandfeasible.(2)Severalsemi-supervisedkernelclusteringalgorithmsincludingsemi-supervisedkernelfuzzy-cmeans(SKFCM)andsemi-supervisedkernelpossibilistic-cmeans(SKPCM)wasproposed.Theresultontheartificialanducidatasetshowsitsefficiency.WealsotesttheSKFCMalgorithminanimagesegmentationexperiment,withthehelpofsupervisedinformation,abettersegmentresultisgot.(3)Proposedasemi-superviseddimensionreductionalgorithm,basedonthealgorithm,animageretrievalmethodusethesemi-supervisediiidimensionreductionalgorithmisproposedandimplemented.ThetestresultsonCoreldatasetshowthismethodiseffective.Basedontheresearchwork(3),amodelsystemforautomaticimageretrievalisimplementedundertheIDEVisualC++6.0.Thesystemconsistsofreal-timeimageretrievalandimageinformationaccess.Keywords:Semi-supervisedlearning,Semi-supervisedclustering,Dimensionalityreduction,Semi-superviseddimensionalityreduction,Kernelmethod,Imageretrieval,Imagecompressviii2.1SROC-----------------------------------------------------92.2Semi-ROC-------------------------------------------------132.3AddC,ROCSemi-ROC----152.4----------------173.1KPCMLSKPCM-ILSKPCM-II,CSKPCM-I,CSKPCM-II----------------------------------263.3------------------------------------------283.4----------------------------------293.5----------------------------------294.1()----------------384.2(Must-LinkCannot-Link)------------------------------------405.1-------------------------------465.2--------------------------50ix2.1AddCROCSemi-ROC13UCI---------------------------------------------------163.1Iris--------------------------------------------213.2KPCMLSKPCM-ILSKPCM-II,CSKPCM-I,CSKPCM-II-----------------------------------------------------254.1--------------------415.1ImageTable---------------------------------------485.2ImageFeatureTable-------------------------------48xDRH),(yxkϕTAXjiuivSROCSemi-SupervisedRobustOn-LineClusteringPCMPossibilisticC-Means)CROC(RobustOn-LineClustering)FCM(FuzzyC-Means)CAddCSVM(SupportVectorMachine)SKFCMSemi-SupervisedKernelFuzzyC-Means)CSKPCMSemi-SupervisedKernelPossibilisticC-Means)CLLE(LocalLinearEmbedding)LPP(LocalityPreservingProjections)COPE(ConstraintPreserveEmbedding)CCV(ColorCoherenceVector)CBIR(ContentBasedImageRetrieval),()11.1[1][1,2][1][1][1-3]21.1.1[3][4][4]1.2[2,5]1.2.13Semi-SupervisedLearning[4,6-13][14]1.2.2[4]1.34[3,5,15]Web[14][5]1.3.1[3,15]1KC-C-[3,16]C-C[17]C-5C-C-C-PCM[17]C-C-C-PCM2[3,15]34,5[18-20]61.3.21985W.Pedrycz[21]PartialSupervision[8,9]1[4,9,21]2[10]3[6,7]1EMstring-edit[22]2[8]3[11]S.Basu[6]1.4[2,3]71.4.11[3]PCALLELPP2FLDAFisher[3]Fisher3[23,24]RCA[23]DCA[25]1.51.Semi-ROCUCI2.SKFCMSKPCMUCISKFCM83.4.3VC++6.01.66UCISKFCMSKPCMUCISKFCM92.1[20]ROC[18]AddCSemi-ROC2.1SROC2.1.1AddCROCSemi-ROC10[18]K[19]EquiDistortion[26]GuedaliaAddC[18]AddC[20]ROCAddCROCAddC[27]2.22.2.11992COLTSVMs[28,29]SVMsSVMsSVMs[30,31]SVMsSVMsPrincipalComponentAnalysis[32]KernelBasedLearning112.2.2XϕXx∈DRHHH(,)(),()Kxyxyϕϕ=(2.1)Xyx∈,.,.AddCROCAddC22(,)||()()||()()2()()()()(,)2(,)(,)TTTdxyxyxxxyyyKxxKxyKyyϕϕϕϕϕϕϕϕ=−=−+=−+(2.2)(,)Kxy2(,)exp(||||/)Kxyxyσ=−−(,)(1)TdKxyxy=+Xx∈(,)1Kxx=2(,)dxy2(,)22(,)dxyKxy=−2.3PairwiseConstraints[10]12Semi-ROCAddCROC2.3.1AddCROCSemi-ROCMergei{i,j}iii,jiγδ==,jiγδ==,ijγδ==iiiδγδδγδδγγδccccccycyy+=++=,(2.3)0;==γγcxyAddCROCN-maxSemi-ROCROCSemi-ROC2.213Semi-ROCSN0N-maxi()0labeli≠()0labeli=fori=1to()sizeS//()sizeSisthenumofsamplesif()0labeli≠()xSi=;winner=()labeli;Updatethewinnercentroidwinneryanditsweightwinnercasfollows:winnerwinnerwinnerwinnerwinnerwinnerwinnercyxyyyxKcc−+=+=),((2.4)N=N+1;endifendforfori=1to()sizeSif()0labeli=()xSi=;winner=1argmin{(,)2(,)(,)}iNKxxKxyKyy≤≤−+(2.5)UpdatethewinnercentroidwinneryanditsweightwinnercusingEq.(3.4);endifN=N+1;ifNN-max=oneoftheemptycentroid0;==γγcxy;elseProcesstheMergestep;//describedinEq.(2.3)endifendforpost-processingchoosethecentroidswithcγεendofthealgorithm2.2Semi-ROC142.3.213UCI[33]AddCROCSemi-ROC0.025ε=20σ=2.3.2.1[20]2.3(a