Computing and visualizing concept lattices [Elektronische Ressource] / von Serhiy Yevtushenko

Sujets

• Informatik

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2004
• Nombre de lectures: 16
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Computing and Visualizing
Concept Lattices
Dissertationsschrift
genehmigtvomFachbereichInformatik
derTechnischenUniversit¨atDarmstadt
von
Master des Wissenschaft Serhiy Yevtushenko
ausKyiv,Ukraine
zurErlangungdesakademischenGradeseines
DoktorsderNaturwissenschaft(Dr.rer.nat.)
Darmstadt2004
Hochschulkennziffer D17
Erstreferent: Prof.Dr.WolfgangBibel
Koreferent: Prof.Dr.BernhardGanter
TagderEinreichung: 29. Juli2004
TagderDisputation: 7.Oktober2004Declaration
Iherebydeclarethatthissubmissioncomprisesmyoriginalworkexcept
wheredueacknowledgementhasbeenmadeinthetexttoallothermaterial
used.
Signed:i
To the memory of my MotheriiAcknowledgements
First of all, I would like to acknowledge the constant support and the in-
crediblepatienceofmythesissupervisor,Prof.WolfgangBibel. Iamreally
gratefulthatIhavetheopportunitytoworkattheIntellecticsgroup.
I would like to thank a lot to the current and former members of the
Intellectics group for many interesting discussions, their help and a lot of
useful advice and just creating environment in which it is fun to work. In
particular I would like to thank Thomas Stutzle,¨ Gunter Grieser, Hesham
Khalil, late Hartmut Bittner, Marco Chiarandini, Ulrich Scholz, Luis Pa-
quete, MarcoPranzo, Tommaso Schiavinotto, IrinaDumitrescu, MauroBi-
rattariandKlausVarrentrapp.
IamindebtedtoPeterGrigorievforafriendship,helpingmetoadaptin
Germany,ajointworkthatwasjollytodoandlotoffunminutes.
IwouldliketothankProf.BernhardGanterforinvitingmeseveraltimes
toDresdenandinterestingandhelpfuldiscussions.
I wish to express my gratitude to Prof. Tatyana Taran for guiding my
firstresearchattempts.
IamgratefultoSergeiObjedkov andSergeiKuznetsov forscientific co-
operationandalotofhelpfulsuggestionsanddiscussions.
IamgratefultoNataliyaIvashchenkoforbeingafriendandhersupport,
help, encouragement and giving me inspiration to start writing the thesis.
Andlast,butnotleast,I’dliketothankElenaKravchenkoforbeingareal
friendandprovidingsupportinthehardesttimes.ivContents
1Introduction 1
2 Formal Concept Analysis 5
2.1Ashortintroduction....................... 5
2.2Basicterminology.............. 5
2.3Linediagramsofconceptlatices..... 8
2.4Implicationsets....11
2.5 Relationshipbetweenthreekindsofknowledgerepresentation
inFCA...............................13
2.6FCAandknowledgediscoveryindatabases...........14
2.7FCAfromtheviewpointofKR......16
2.7.1 MappingbetweenterminologyofFCAandDL. . . . . 18
3 FCA Algorithms 19
3.1Usagescenarios..........................19
3.2Desirablepropertiesofalgorithms.....21
3.3Constructionofthesetofconcepts....2
3.4 Decompositionofcontextw.r.t.anattribute ..........29
3.5Computationalcomplexityofalgorithms............35
3.5.1 Generalintractabilityofthetaskofcomputingallcon-
cepts............................35
3.5.2 WorstcasecomplexityofalgorithmfromFig.3.3 . . . 36
3.5.3 WorstcasecomplexityoffromFig.3.6 . . . 37
3.6Experimentalcomparisonofthealgorithms...........37
3.6.1Themethodologyofcomparison.............37
3.6.2 Theresultsofthecomparisonforartificialdatasets . . 39
3.6.3 Theresultsofthecomparisononthereal-worlddatasets 40
3.7Furtherwaysofimprovingthealgorithm............43
3.8Usingimplicitrepresentations..................44
3.8.1BinaryDecisionDiagrams.....45
3.8.2 UsingaBDDtorepresentthesetofallintents. . . . . 46vi CONTENTS
3.8.3 Calculationofallintersectionsbetweentwosets....49
3.8.4 ThealgorithmsusingBDDfortheconstructionofthe
setofalintents......................49
3.8.5 Experimentalcomparison51
3.8.6 Conclusions.............54
3.9Relatedwork...........55
3.9.1 Batchandincrementalalgorithms............56
3.9.2 Batchalgorithm.................61
3.9.3 Datamining-basedalgorithms..............63
3.9.4 Othermethods......67
3.10Conclusions.................67
4 Search Space Analysis 71
4.1Characteristicsofruleminingdatasets.............71
4.2Thedistributioncharacteristicsoflatices......74
4.3ExplorationofbinarydatasetsforJSM.....79
4.3.1 ShortinformationabouttheJSM-method..79
4.3.2 Descriptionofexperiments................82
4.4Effectsofcontexttransformations82
4.5Conclusions.................86
5 Visualizing Concept Lattices 89
5.1Generalrequirementstodrawinglinediagrams.........89
5.2Thelayeredapproach..................90
5.3Theforce-directedapproach........91
5.3.1 Force-directedscheme..92
5.3.2 Fresemethod............93
5.4Additivelinediagrams.................94
5.4.1 Embeddingofthelaticeinton-dimensionalgrid....95
5.5Comparisonofmethods..........95
5.5.1 Testlatices........95
5.5.2 Results...........................96
5.6Relatedwork10
5.7Conclusionsandfuturework........101
6 Conclusions 103
6.1Contributions...........................103
6.2Futurework.105