Studies in Classifi cation, Data Analysis, and Knowledge Organization Berthold Lausen Dirk Van den Poel Alfred Ultsch Editors Algorithms from and for Nature and Life Classifi cation and Data Analysis www.it-ebooks.info Studies in Classification, Data Analysis, and Knowledge Organization ManagingEditors EditorialBoard H.-H.Bock,Aachen D.Baier,Cottbus W.Gaul,Karlsruhe F.Critchley,MiltonKeynes M.Vichi,Rome R.Decker,Bielefeld C.Weihs,Dortmund E.Diday,Paris M.Greenacre,Barcelona C.N.Lauro,Naples J.Meulman,Leiden P.Monari,Bologna S.Nishisato,Toronto N.Ohsumi,Tokyo O.Opitz,Augsburg G.Ritter,Passau M.Schader,Mannheim Forfurthervolumes: http://www.springer.com/series/1564 www.it-ebooks.info www.it-ebooks.info Berthold Lausen Dirk Van den Poel (cid:2) Alfred Ultsch Editors Algorithms from and for Nature and Life Classification and Data Analysis 123 www.it-ebooks.info Editors BertholdLausen DirkVandenPoel DepartmentofMathematicalSciences DepartmentofMarketing UniversityofEssex GhentUniversity Colchester,UnitedKingdom Ghent,Belgium AlfredUltsch Databionics,FB12 UniversityofMarburg Marburg,Germany ISSN1431-8814 ISBN978-3-319-00034-3 ISBN978-3-319-00035-0(eBook) DOI10.1007/978-3-319-00035-0 SpringerChamHeidelbergNewYorkDordrechtLondon LibraryofCongressControlNumber:2013945874 ©SpringerInternationalPublishingSwitzerland2013 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped.Exemptedfromthislegalreservationarebriefexcerptsinconnection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work. Duplication of this publication or parts thereof is permitted only under the provisions of the Copyright Law of the Publisher’slocation,initscurrentversion,andpermissionforusemustalwaysbeobtainedfromSpringer. PermissionsforusemaybeobtainedthroughRightsLinkattheCopyrightClearanceCenter.Violations areliabletoprosecutionundertherespectiveCopyrightLaw. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) www.it-ebooks.info Preface RevisedversionsofselectedpaperspresentedattheJointConferenceoftheGerman Classification Society (GfKl) – 35th Annual Conference – GfKl 2011 – , the GermanAssociationforPatternRecognition(DAGM)–33rdannualsymposium– DAGM2011–andtheSymposiumoftheInternationalFederationofClassification Societies(IFCS) – IFCS 2011– heldat the UniversityofFrankfurt(Frankfurtam Main, Germany)August30 – September2, 2011,are containedin this volumeof “StudiesinClassification,DataAnalysis,andKnowledgeOrganization”. One aimoftheconferencewastoprovidea platformfordiscussionsonresults concerning the interface that data analysis has in common with other areas such as, e.g., computer science, operations research, and statistics from a scientific perspective, as well as with various application areas when “best” interpretations ofdatathatdescribeunderlyingproblemsituationsneedknowledgefromdifferent researchdirections. Practitionersandresearchers–interestedindataanalysisinthebroadsense–had the opportunityto discuss recent developmentsand to establish cross-disciplinary cooperation in their fields of interest. More than 420 persons attended the con- ference, more than 180 papers (including plenary and semiplenary lectures) were presented.Theaudienceoftheconferencewasveryinternational. Fifty-fiveofthepaperspresentedattheconferenceare containedin this.Asan unambiguousassignmentoftopicsaddressedinsinglepapersissometimesdifficult the contributions are grouped in a way that the editors found appropriate. Within (sub)chaptersthe presentations are listed in alphabetical order with respect to the authors’ names. At the end of this volume an index is included that, additionally, shouldhelptheinterestedreader. The editors like to thank the members of the scientific program committee: D. Baier, H.-H. Bock, R. Decker, A. Ferligoj, W. Gaul, Ch. Hennig, I.Herzog, E. Hu¨llermeier,K. Jajuga,H. Kestler, A. Koch,S. Krolak-Schwerdt,H. Locarek- Junge, G. McLachlan, F.R. McMorris, G. Menexes, B. Mirkin, M. Mizuta, A. Montanari, R. Nugent, A. Okada, G. Ritter, M. de Rooij, I. van Mechelen, G.Venturini, J. Vermunt, M. Vichi and C. Weihs and the additionalreviewers of the proceedings:W.Adler,M.Behnisch,C.Bernau,P.Bertrand,A.-L.Boulesteix, v www.it-ebooks.info vi Preface A.Cerioli,M. Costa,N.Dean,P.Eilers,S.L.France,J.Gertheiss,A.Geyer-Schulz, W.J. Heiser, Ch. Hohensinn,H. Holzmann,Th. Horvath,H. Kiers, B. Lorenz,H. Lukashevich,V. Makarenkov,F. Meyer,I. Morlini, H.-J. Mucha, U. Mu¨ller-Funk, J.W. Owsinski, P. Rokita,A. Rutkowski-Ziarko,R. Samworth,I. Schma¨deckeand A.Sokolowski. Last but not least, we would like to thank all participants of the conference for their interest and various activities which, again, made the 35th annual GfKl conferenceandthisvolumeaninterdisciplinarypossibilityforscientificdiscussion, in particular all authors and all colleagues who reviewed papers, chaired sessions or were otherwise involved. Additionally, we gratefully take the opportunity to acknowledgesupportby Deutsche Forschungsgemeinschaft(DFG) of the Sympo- siumoftheInternationalFederationofClassificationSocieties(IFCS)–IFCS2011. As always we thank SpringerVerlag, Heidelberg,especially Dr. Martina Bihn, forexcellentcooperationinpublishingthisvolume. Colchester,UK BertholdLausen Ghent,Belgium DirkVandenPoel Marburg,Germany AlfredUltsch www.it-ebooks.info Contents PartI Invited SizeandPowerofMultivariateOutlierDetectionRules .................... 3 AndreaCerioli,MarcoRiani,andFrancescaTorti Clustering and Prediction of Rankings WithinaKemenyDistanceFramework ....................................... 19 WillemJ.HeiserandAntonioD’Ambrosio SolvingtheMinimumSumofL1DistancesClusteringProblem by Hyperbolic Smoothing and Partitioninto Boundary andGravitationalRegions ...................................................... 33 AdilsonEliasXavier,ViniciusLayterXavier, andSergioB.Villas-Boas PartII ClusteringandUnsupervisedLearning OntheNumberofModesofFiniteMixturesofEllipticalDistributions... 49 GrigoryAlexandrovich,HajoHolzmann,andSurajitRay ImplicationsofAxiomaticConsensusProperties............................. 59 FlorentDomenachandAliTayari ComparingEarthMover’sDistanceanditsApproximations forClusteringImages............................................................ 69 SarahFrostandDanielBaier AHierarchicalClusteringApproachtoModularityMaximization........ 79 WolfgangGaulandRebeccaKlages MixtureModelClusteringwithCovariatesUsingAdjusted Three-StepApproaches.......................................................... 87 DerejeW.GudichaandJeroenK.Vermunt vii www.it-ebooks.info viii Contents EfficientSpatialSegmentationofHyper-spectral3DVolumeData........ 95 JanHendrikKobargandTheodoreAlexandrov ClusterAnalysisBasedonPre-specifiedMultipleLayerStructure........ 105 AkinoriOkadaandSatoruYokoyama FactorPD-Clustering............................................................ 115 CristinaTortora,MireilleGettlerSumma,andFrancescoPalumbo PartIII StatisticalDataAnalysis,VisualizationandScaling ClusteringOrdinalDataviaLatentVariableModels........................ 127 DamienMcParlandandIsobelClaireGormley SentimentAnalysisofOnlineMedia........................................... 137 MichaelSalter-TownshendandThomasBrendanMurphy Visualizing Data in Social and Behavioral Sciences: AnApplicationofPARAMAPonJudicialStatistics......................... 147 UlasAkkucuk,J.DouglasCarroll,andStephenL.France PropertiesofaGeneralMeasureofConfigurationAgreement............. 155 StephenL.France ConvexOptimizationasaToolforCorrectingDissimilarity MatricesforRegularMinimality............................................... 165 MatthiasTrendtelandAliU¨nlu¨ PrincipalComponentsAnalysisforaGaussianMixture.................... 175 CarlosCuevas-Covarrubias Interactive Principal Components Analysis: A New TechnologicalResourceintheClassroom..................................... 185 Carmen Villar-Patin˜o, Miguel Angel Mendez-Mendez, andCarlosCuevas-Covarrubias One-ModeThree-WayAnalysisBasedonResultofOne-Mode Two-WayAnalysis................................................................ 195 SatoruYokoyamaandAkinoriOkada LatentClassModelsofTimeSeriesData:AnEntropic-Based UncertaintyMeasure ............................................................ 205 Jose´ G.Dias RegularizationandModelSelectionwithCategoricalCovariates.......... 215 JanGertheiss,VeronikaStelz,andGerhardTutz FactorPreselectionandMultipleMeasuresofDependence................. 223 NinaBu¨chel,KayF.Hildebrand,andUlrichMu¨ller-Funk www.it-ebooks.info Contents ix IntrablocksCorrespondenceAnalysis......................................... 233 CampoEl´ıasPardoandJorgeEduardoOrtiz DeterminingtheSimilarityBetweenUSCitiesUsingaGravity ModelforSearchEngineQueryData ......................................... 243 PaulHofmarcher,BettinaGru¨n,KurtHornik,andPatrickMair PartIV BioinformaticsandBiostatistics AnEfficientAlgorithmfortheDetectionandClassificationof HorizontalGeneTransferEventsandIdentificationofMosaicGenes..... 253 AlixBoc,PierreLegendre,andVladimirMakarenkov Complexity Selection with Cross-validation for Lasso andSparsePartialLeastSquaresUsingHigh-DimensionalData.......... 261 Anne-LaureBoulesteix,AdrianRichter,andChristophBernau ANewEffectiveMethodforEliminationofSystematicError inExperimentalHigh-ThroughputScreening................................ 269 VladimirMakarenkov,PlamenDragiev,andRobertNadon Local Clique Merging: An Extension of the Maximum CommonSubgraphMeasurewithApplicationsinStructural Bioinformatics.................................................................... 279 ThomasFober,GerhardKlebe,andEykeHu¨llermeier IdentificationofRiskFactorsinCoronaryBypassSurgery................. 287 JuliaSchiffner,ErhardGodehardt,StefanieHillebrand,Alexander Albert,ArturLichtenberg,andClausWeihs PartV Archaeology and Geography, Psychology and EducationalSciences ParallelCoordinatePlotsinArchaeology..................................... 299 IrmelaHerzogandFrankSiegmund ClassificationofRomanTileswithStampPARDALIVS.................... 309 Hans-JoachimMucha,JensDolata,andHans-GeorgBartel ApplyingLocationPlanningAlgorithmstoSchools:TheCase ofSpecialEducationinHesse(Germany)..................................... 319 AlexandraSchwarz DetectingPersonHeterogeneityinaLarge-ScaleOrthographic TestUsingItemResponseModels.............................................. 329 ChristineHohensinn,KlausD.Kubinger,andManuelReif LinearLogisticModelswithRelaxedAssumptionsinR .................... 337 ThomasRusch,MarcoJ.Maier,andReinholdHatzinger www.it-ebooks.info