南航暑期国际课程大数据可视化第8讲1

Collaborativelosslessvisualizationofn-DdatabyCollocatedPairedCoordinates(CPC)BorisKovalerchuk1,VladimirGrishin

2

1Dept.ofComputerScience,CentralWashingtonUniversity2ViewTrendsInternationalMotivationThegoalofmultivariate,multidimensionalvisualizationisrepresentingn-tuples(n-Dvectors)in2-Dor3-Dtoenhancen-Ddatapatterndiscovery.Oftenmultidimensionaldataarevisualizedbylossydimensionreduction(PCA)andsplittingn-Ddatatoasetoflowdimensionaldata(pairwisecorrelationplots).PCA-PrincipalComponentAnalysisWhilesplittingisusefulitdestroysintegrityofn-Ddata,andleadstoashallowunderstandingcomplexn-Ddata.Tomitigatesplittingdifficultyanadditionalanddifficultperceptualtaskofassemblinglow-dimensionalvisualizedpiecesofeachrecordtothewholen-Drecordmustbesolved.Analternativewayfordeeperunderstandingofn-Ddataisdevelopingvisualrepresentationsofn-Ddatainlowdimensionswithoutsuchdatasplitting.E.g.,ParallelandRadialcoordinates.(0.5,0.4,0,0.6,0.5,1)MotivationVisualshapeperceptionsupplies95-98%ofinformationforpatternrecognition.However,recentvisualizationtechniquesdonotuseitefficiently[4,5].Multipleopportunitiestoimproveareemerging.

Thispapercontinuesourlong-termefforts[1-3]onenhancementofvisualizationperformance.Wefocusonimprovingamodernlossymappingofmultidimensionaldataspaceonto2-Dplane,bycreatinglosslessmappingofn-Dto2-D.OurCollaborativeApproachtoEnhanceVisualization(CAEV)(1)ShapePriorityforPerceptionandCommunication:MoreeffectiveusageofhumanvisioncapabilitiesofshapeperceptionbyPolardisplays(Stars),whichadvantagesofvs.ParallelCoordinates(PCs)forshaperecognitionfollowingfromGestaltandhaveconfirmedbyourpsychologicalexperimentsfordetectionofhyper-tubesand-planesstructureswithdimensionupto100.Itselectsfeaturesandclassifiesobjects2-3timesfasterthanwithPCs[8].(2)LosslessDisplays,asanalternativewayforlossyvisualizationPrimaryusageofvisualrepresentationsin2-Dthatfullypreservesn-Ddata,suchaslosslessmethodsofParallelandRadialcoordinates,someheatmaps,etc.,whichprovideclearinterpretationoffigurefeaturesintermsofdataproperties.(3)QuantitativeModelingoftheDataStructureRecognitionwithdifferentformsofdatadisplays.Thisisabasistochooseandadjuststructuresashyper–tubes,hyper-planes,hyper-spheres,etc.Wefocusonaformaldatastructurestoenhancegeneralizationofvisualizationincombinationwithaninteractivecollaborativevisualizationapproach.ReviewofLineCoordinatesTypeCharacteristicsGeneralLineCoordinates(GLC)Drawingncoordinateaxesin2Dinvarietyofways:curved,parallel,unparalleled,collocated,disconnected,etc.CollocatedPairedCoordinates(CPC)in2-DSplittingann-Dvectorxintopairsofitscoordinates(x1,x2),…,(xn-1,xn);drawingeachpairas2-Dpointinthesametwoaxesontheplane;andlinkingthesepointstoformanorientedgraphfromthesepointsforeachn-Dvector.CollocatedPairedCoordinates(CPC)in3-DSplittingncoordinatesintotriplesandrepresentingeachpairas3-Dpointinthesamethreeaxes;andlinkingthesepointstoformanorientedgraphforeachn-Dvector.ShiftedPairedCoordinates(SPC)Drawingeachnextpairintheshiftedcoordinatesystem(incontrastwithCPC).X1X2CartesianCoordinatesCollocatedPairedCoordinatesTheideaofthepairedcoordinatesisconvertingasimplestringofelementsofvectorx=(x1,x2,…xn)incoordinatesX1,X2,…,Xntoamorecomplexstructurewithconsecutive2-Delements(pairs)forevenn:{(x1,x2)(x3,x4),…,(xi,xi+1),…,(xn-3,xn-2),(xn-1,xn)}.ThescalesofcoordinatesX1-Xnarenormalizedtosomeinterval,e.g.,[0,1]andconstructedpairs(xi,xi+1)areplottedonthesame(X,Y)2-Dplane.Theexamplebelowillustratesthisprocess.Examplein6-D:astatevectorx=(x,y,x`,y`,x``,y``),xandyarelocationoftheobject,x`andy`arevelocities(derivatives),andx``andy``areaccelerations(secondderivatives)ofthisobject.Themainstepsofthealgorithm:Groupingattributesintoconsecutivepairs(x,y)(x`,y`)(x``,y``),PlottingeachpairinthesameorthogonalnormalizedCartesiancoordinatesXandY,andPlottingadirectedgraph(x,y)(x`,y`)(x``,y``)withdirectedpathsfrom(x,y)to(x`,y`)andfrom(x`,y`)to(x``,y``).Thesamevectorxintheparallelcoordinates.requires5linestoshowx,incontrastcollocatedcoordinatesrequireonly2lines,whichleadtolessclutterwhenmultiplen-Dvectorsarevisualized.ThisisanadvantageofthePairedCoordinates.PairedCoordinatesandLineCoordinatesTheShiftedPairedCoordinates(SPC)showeachnextpairintheshiftedcoordinatesystem.Thefirstpair(5,4)isdrawninthe(X,Y)system,pair(0,6)isdrawninthe(X+1,Y+1)coordinatesystem,andpair(4,6)isdrawninthe(X+2,Y+2)coordinatesystem.

Forvector(5,4,0,6,4,10),thegraphconsistsofthearrows:from(5,4)to(1,1)+(0,6)=(1,7)thenfrom(1,7)to(2,2)+(4,10)=(6,12).AnchoredPairedCoordinates(APC)TheAnchoredPairedCoordinates(APC)representeachnextpairstartingatthefirstpairthatservesan“anchor”.pairs(x`,y`)and(x``,y``)arerepresentedasvectorsthatstartatanchorpoint(x,y)withplottingvectors((x,y),(x+x`,x+y`))and((x,y),(x+x``,x+y``)).TheadvantageoftheAPCisthatthedirectionhasameaningasactualvectorsofvelocityandaccelerationinthisexample.Inthetraditionalradialcoordinatedthedirectionsarearbitrary.CircularCoordinatesN-gonCoordinatesStraightlinesGeospatialdatavisualizationCircularandn-gonecoordinatescanbeusedtoshowgeo-referenceddataifn-Dvectorscontainlocationcoordinates,say(x1,x2).Anyotherpairofcoordinatescanserveaspseudo-location.Thesetwocoordinatesareusedtoidentifylocationofthecenterofthecircleandothern-2coordinatesareusedtobuildacircleor(n-2)-gonwithappropriatescalingtoavoidoverlap.(x1,x,2,x3,x4,…,xn)Resultsoflosslessn-DdatavisualizationsCollaborativeApproachtoEnhancevisualization(CAEV)Thegeneratedfiguresalloweffectiven-Ddatastructureanalysisbymeansofcollaborativeshapeperception.Visualizationoflargen-Ddatasetsforpatterndiscoverycanbeaccomplishedcollaborativelybysplittingadatasetandtasksbetweencollaboratingagents,whichincludebothhumansandsoftwareagents.Eachagentanalyzesandvisualizesasubsetofdataand/ortasksandexchangesfindingswithotheragents.Splittingofactivitiestosupportcollaborationbasedon:Locationofdataonn-Dspace(eachagentworksofthedatafromaspecificlocationonn-Dspaceproducedbydataclustering).Classofdata(eachagentworksonlyonthedataofaspecificclass/classes),Attributesofdata(eachagentworksonlyontheprojectionofdatatothespecificsubsetofattributes.)Tasks(agentsarespecializedondifferentvisualtasks).Dataarenotsplit,butorganizedandvisualizeddifferently,e.g.,

different

orderoftheattributespresentedtodifferentagents.Visualizationinparallelcoordinatesandpairedcoordinatesaresensitivetothischange.CollaborativeApproachtoEnhancevisualization(CAEV)Thegeneratedfiguresalloweffectiven-Ddatastructureanalysisbymeansofcollaborativeshapeperception.Visualizationoflargen-Ddatasetsforpatterndiscoverycanbeaccomplishedcollaborativelybysplittingadatasetandtasksbetweencollaboratingagents,whichincludebothhumansandsoftwareagents.Eachagentanalyzesandvisualizesasubsetofdataand/ortasksandexchangesfindingswithotheragentsusingacollaborationplatform.CollaborationplatformJointvisualsolutionAgenttask4/data4Agent1task1/data1Agent2task2/data2Agent3task3/data3Splittingofagents’activitiesBasedon:Locationofdata

onn-Dspace(eachagentworksofthedatafromaspecificlocationonn-Dspaceproducedbydataclustering).Classofdata

(eachagentworksonlyonthedataofaspecificclass/classes),Attributesofdata

(eachagentworksonlyontheprojectionofdatatothespecificsubsetofattributes.)Tasks

(agentsarespecializedondifferentvisualtasks).Dataarenotsplit,butorganizedandvisualizeddifferently,e.g.,

different

orderoftheattributespresentedtodifferentagents.Visualizationinparallelcoordinatesandpairedcoordinatesaresensitivetothischange.CollaborationwithtaskssplittingTaskT1onn-Ddatasubsetofagent1

TaskT2onn-Ddatasubsetofagent2TaskT3onn-Ddatasubsetofagent3

TaskT4onn-Ddatasubsetofagent4TaskT1onn-Ddatasubsetofagent1Simple?simplesimplecomplexTaskT3onn-Ddatasubsetofagent3TaskT2onn-Ddatasubsetofagent2Differentagentsanalyzedifferentvisualizationsofthesamedataonfoundpatternsandexchangeconclusions.Advantagesoflosslessvisualizations

Themotivationforanewclassofcoordinatesistwo-fold:thereisaverylimitednumberofavailablelosslessvisualizationmethodsofn-Ddata,andthereisnosilverbulletvisualizationthatisperfectforallpossibledatasets.Ourexperiments[2]hadshownthebenefitsofnewvisualizationsforWorldHungerdata,ChallengerDisaster,aswellasonmodeleddatavs.ParallelCoordinates(PCs).IntheexamplesaboveCPCrevealastructureofspecificdataclearerthantheparallelcoordinates.Whatareadvantagesoflosslesscollaborativevisualizations?Atfirstglancemanyrelationscanbeeasilydiscoveredanalyticallywithoutcollaborativevisualization.Infact,theanalyticaldiscoveringissearchinginanassumedclassofrelationsthatis

difficulttoguess.Analyticalsearchisdifficultinaverylargeclassofrelations--aneedleinahaystack.Thevisualcollaborativeautomatedapproachassistedbysoftwareagentshelpstoidentifyandtonarrowthisclass.Itcaneveneliminatetheanalyticalstage,ifweonlyneedtoknowthatarelationthatseparatestwoclassesexists.Analternativecollaborative“manual”wayoftenisnotscalable

becausewecannotlookthroughlargedatatablestodiscovertherelation.Itisaslow

sequential

process,whiletheobservingthatimagesinthevisualizationisafastparallelprocess.MathStatementsonlosslessvisualizationsBelowwedescribedatafeaturesthatcanbevisuallyestimatedusingCPC.Apoint

WisproducedbytheformulaW=A+tv,whereAisann-Dpoint,visann-Dvector,andtisascalar.Alinearsegmentinn-Disasetofpoint{W:W=A+tv,t[a,b]}.Statement.Ann-DlinearsegmentisrepresentedasasetofshiftedgraphsinCPC.Fortheproofseethepaper.Note:Directionsofthelinearshiftscandifferfordifferentpoints/nodesofthesamegraph.

Considertwoclassesofn-Dvectorsthatsatisfytwodifferentlinearrelations:W=A+tvandU=B+tq.

ThesedatawillberepresentedinCPCastwosetsofgraphsshiftedinvandqdirections,respectively.IfW=A+tv+e,whereeisanoisevector,thenwehavegraphsforn-DpointsWinthe“tube”withitswidthdefinedbye.CollaborativevisualizationVisualfeaturesthatCPCsupports.

HumanscanestimatethefollowingvisualfeaturesinCPCgraphs:typesofangles(e.g.,sharpangle),orientationanddirectionoflinesandangles,lengthofthelines,coloroflines,widthofthelength(asrepresentationofthenumberofvectorswithsuchvalues),widthandlengthofthecurves(Beziercurves),numberofcrossingofedgesofagraph,directionsofcrossededges,shapeofanenvelopethatcontainsthegraph,a“type”ofthegraph(dominantdirectionorabsenceofit:knot,L-shape,horizontal,vertical,Northwest,etc),relationsbetweengraphsofdifferentn-Ddataplottedonthesameplane.Tomakethisanalysisfasteragentscollaboratebydividinganalysisofthesefeaturesbetweenthemandbyexchangingresultsofanalysis:Findingrelationsbetweengraphsincludes:identifyingpropertiessuchas:parallel,rotated,affinetransformedrelativetoeachother,percentageofoverlap,thesize,andshapeoftheareaoftheoverlapofenvelopes,thedistance.xt=(xt1,xt2,…,xt8)isgivenbytheformula:(xt3=xt1)&(xt4=xt2+2)&(xt5=xt1+2)&(xt6=xt4)&(xt7=xt5)&(xt8=xt2).xt=(xt1,xt2,…,xt8)andxt+1=(xt+1,1,xt+1,2­,…,xt+1,8)isgivenbytheformulas:xt+1,i=3xti,i=1,3,5,7andxt+1,i=xt,i,i=2,4,6,8.Hereoddattributesgrowlinearlyandevenattributesareconstants.TubesThebottomfiguresshowthatallobjectshavethesamestructureinCPCthatislessevidentinparallelcoordinatesintheupperfigures.Thesearethesameshapesjustshifted.Intheparallelcoordinatestheshapesarenotidentical,butsimilar.Itiseasiertoseeidenticalshapesthansimilarshapes.AgentsandLosslessVisualizationFigures(a)and(c)showtubes(cylinders)in3-Dwithpointsincolors.Thematchedgraphs(lines)ofCPCrepresentationsareshowninthesamecolorsin(b)forthethreelefttubesandin(d)fromtheforth(left)tube.In2-Dvisualizationallobjectswithineachpipehavepracticallythesamedirections,similarlengthsandlocatedclosely.Thesesimilaritieshelpacollaboratingagenttodistinguishthemfromdatafromotherpipes.Thisiscriticalforthesuccessofcollaborativen-Ddatavisualanalysis.Such2-DlosslessCPCrepresentationallowsdistinguishingclassesvisually.Eachagentworksontheindividualclassandcanextractvisualfeaturesofeachclassandthenagentscombinetheirfeaturesasajointdescriptionofcharacteristicsthatdiscriminateclasses.ThisspeedsupthetotalvisualdiscoverycollaborativelyVisualseparationvs.AnalyticalseparationofclassesOurstudieshadshownthateverywherewhereotherlosslessvisualizations(parallelandradialcoordinates)areuseful,CPCalsouseful.Woulditbedifficulttoseparatenon-overlappinghyper-