Quantifiable Data Mining Using Principal Component

QuantiableDataMiningUsingPrincipalComponentAnalysisFlipKorn,AlexandrosLabrinidis,YannisKotidis,ChristosFaloutsos,AlexKaplunovich,DejanPerkovicfflip,labrinid,kotidis,christos,kaplunov,[e-mail]cienceUniversityofMarylandatCollegeParkAbstractAssociationRuleMiningalgorithmsoperateonadatamatrix(e.g.,customersproducts)toderiverules[2,22].Weproposeasingle-passalgorithmformininglinearrulesinsuchamatrixbasedonPrincipalComponentAnalysis.PCAdetectscorrelatedcolumnsofthematrix,whichcorrespondto,e.g.,productsthatselltogether.Therstcontributionofthisworkisthatweproposetoquantifythe\goodnessofasetofdis-coveredrules.Wedenethe\guessingerror:theroot-mean-squareerrorofthereconstructedvaluesofthecellsofthegivenmatrix,whenwepretendthattheyareunknown.Thesecondcontributionisanovelmethodtoguessmissing/hiddenvaluesfromthelinearrulesthatourmethodderives.Forexample,ifsomebodybought$10ofmilkand$3ofbread,ourrulescan\guesstheamountspenton,say,butter.Thus,wecanperformavarietyofimportanttaskssuchasforecasting,‘what-if’scenarios,outlierdetection,andvisualization.Moreover,weshowthatwecancomputetheprincipalcomponentswithasinglepassoverthedataset.Experimentsonrealdatasets(e.g.,NBAstatistics)demonstratethattheproposedmethodcon-sistentlyachievesa\guessingerrorofupto5timeslowerthanthestraightforwardcompetitor.1IntroductionDataMininghasrecentlybeenreceivingincreasinginterest[9],ofwhichthequintessentialproblemisassociationrulemining[2].Givenadatamatrix,with,e.g.,customersforrowsandproductsforcolumns,wewanttondrules.Existingalgorithmsndrulesoftheformfbread;milkg)butter,meaningthatcustomerswhobuy\breadand\milkalsotendtobuy\butter.WhatdistinguishesdatabaseworkfromAI/MachineLearningandstatisticsworkisitsemphasisonlargedatasets.TheinitialassociationruleminingpaperbyAgrawaletal.[2],aswellasallthefollow-updatabasework[4],proposedalgorithmstominimizethetimetoextracttheserulesthroughcleverrecord-keepingtoavoidadditionalpassesoverthedataset,throughparallelism,etc.ThisresearchwaspartiallyfundedbytheInstituteforSystemsResearch(ISR),bytheNationalScienceFoundationunderGrantsNo.EEC-94-02384,IRI-9205273andIRI-9625428.1Whatisnovelaboutthepresentworkisthatitattemptstoassesshowgoodthederivedrulesare,anissuethathasnotbeenemphasizedininthedatabaseliterature.Weproposethe\guessingerrorasameasureofthe\goodnessofagivensetofrulesforagivendataset.Theideaistopretendthatacellofthematrixis\hiddenfromus,andtotrytoguessthemissingvalueusingthederivedrules;theroot-mean-squareguessingerror(averagedoverallthecellsofthegivenmatrix)indicateshowgoodasetofrulesis.Thesecondmajorinnovationofthisworkistheuseofprincipalcomponentanalysis(PCA)toderivelinearrules,oftheform\customerstypicallyspend1:2:5dollarsonbread:milk:butter.Linearrulescanbeeasilyusedforextrapolations,andcanhelpdeterminehidden,missingandcorruptedvalues.Weprovidenovelalgorithmsforestimatingmissingvalues,evenifmultiplevaluesaresimultaneouslymissing/hidden.PCA(vialinearrules)cansupportthefollowingapplications,thankstotheirabilitytoreconstructmissing/hiddenvalues:Datacleaning:reconstructinglostdataandrepairingnoisyordamageddata;Forecasting:‘ifacustomerspends$1onbreadand$2.50onham,howmuchwills/hespendonmayonnaise?’;What-ifscenariosanddecisionsupport:‘WeexpectdoubleddemandofCheerios;howmuchmilkshouldwestockupon?’;Outlierdetection:‘Whichcustomersdeviatefromthetypicalsalespattern?’;Visualization:PCA,beingidenticaltotheKarhunen-Loevetransform[8],istheoptimaldimen-sionalityreductionmethod,mappingtherowsofthedatamatrixinto2-or3-dimensionalpoints,thatcanbeplottedtorevealthestructureofthedataset(e.g.,clusters,linearcorrelations,etc.);Thepaperisorganizedasfollows:Section2discussespastwork.Section3presentsanintroductiontoPCA.Section4introducestheproposedmethod.Section5givestheexperimentalresults.Section6providesadiscussion.Section7givessomeconclusionsandpointerstofuturework.2RelatedWorkAgrawaletal.distinguishbetweenthreedataminingproblems:identifyingclassications,ndingsequentialpatterns,anddiscoveringassociationrules[1].Wereviewonlymaterialrelevanttothelattersinceitisthefocusofthispaper.See[7]foranexcellent,recentsurveyofallthreeproblems.Theseminalworkof[2]introducedtheproblemofdiscoveringassociationrulesandpresentedanecientalgorithmforminingthem.Sincethen,newserialalgorithms[4,15,19]andparallelalgorithms[14,3,10]havebeenproposed.Inaddition,generalizedassociationruleshasbeenthesubjectofrecentwork[21,11].ThevastmajorityofassociationrulediscoverytechniquesarebasicallyBoolean,sincetheydiscardthequantitiesoftheitemsboughtandonlypayattentiontowhethersomethingwasboughtornot.AnotableexceptionistheworkofSrikantandAgrawal[22],wheretheyaddresstheproblemofminingquantitativeassociationrules.Theirapproachistopartitioneachquantitativeattributeintoaset2SymbolDenitionNnumberofrecordsMnumberofattributeskcuto(numberofprincipalcomponentsretained)hnumberofholesHsetofcellswhichhaveholesRMS1root-mean-squarederrorovereachholeRMShroot-mean-squarederroroverhholesmatrixmultiplicationXtheNMdatamatrixXcthecenteredver