0蒙彼利埃大学博士学位论文0计算机科学0博士学位授予学校：蒙彼利埃大学信息、结构、系统学院0研究单位UMR55060减少视觉混乱：应用于人物传记数据的可视化和探索0FatiCHEN于2022年6月29日提交0在Pascal PONCELET和ArnaudSALLABERRY的指导下0评审委员会成员：0Pascale KUNTZ女士，教授，LS2N，南特大学 评审员0David AUBER教授，LaBRI，波尔多大学 评审员0Marianne HUCHARD女士，教授，LIRMM，蒙彼利埃大学 主席0Francesco BERETTA博士，CNRS研究员，LARHRA，里昂第二大学 评审员0Cédric du MOUZA博士，高级讲师，CEDRIC，巴黎国立高等工程学院 评审员0Arnaud SALLABERRY博士，高级讲师，LIRMM，保罗瓦莱里蒙彼利埃大学 共同导师0Pascal PONCELET教授，LIRMM，蒙彼利埃大学 导师0摘要0历史学家使用人物传记记录来研究一群历史人物的共同特征，通过对他们生活的集体分析。信息可视化为分析人物传记数据提供了有趣的视角。本论文的工作就是在这个背景下展开的。首先，我们介绍了ProsoVis平台，用于分析和浏览人物传记数据。我们描述了不同的需求，并详细说明了设计选择和可视化技术。我们使用包含1800年至1950年法律教师职业数据的Siprojuris数据库来说明其使用。大量数据的可视化会导致视觉混乱的问题。在这种情况下，我们解决了图中节点重叠的问题。虽然存在不同的方法，但由于评估标准不同，很难进行比较。因此，我们提出了一项现有技术算法的研究，通过比较它们在相同标准下的结果。最后，我们解决了地图中的视觉混乱问题，并提出了一种空间聚类方法F-SAC，它比现有技术提供的方法更快，同时保证了相同的结果质量。0关键词-人物传记数据，信息可视化，视觉混乱，节点重叠消除，空间聚类0摘要0历史学家使用人物传记记录来研究一群历史人物的共同特征，通过对他们生活的集体分析。信息可视化为分析人物传记数据提供了有趣的视角。本论文的工作就是在这个背景下展开的。首先，我们介绍了ProsoVis平台，用于分析和浏览人物传记数据。我们描述了不同的需求，并详细说明了设计选择和不同的视图。我们使用包含1800年至1950年法律教师职业数据的Siprojuris数据库来说明其使用。大量数据的可视化会导致视觉混乱的问题。在这种情况下，我们解决了图中节点重叠的问题。即使存在不同的方法，但由于它们的评估不基于相同的质量标准，很难进行比较。因此，我们提出了一项对现有技术算法的研究，通过比较它们在相同标准下的结果。最后，我们解决了地图中的类似视觉混乱问题，并提出了一种空间聚类方法F-SAC，它比现有技术提供的方法更快，同时保证了相同的结果质量。0关键词 - 人物传记数据，信息可视化，视觉混乱，重叠消除，空间聚类v0致谢0首先，我要感谢我的伴侣JulieRipoll，在整个论文过程中给予我的支持、无条件的支持、帮助和宝贵的建议。我的家人，我的父母Deyan Chen和Fatima Artemieff，我的兄弟Yusu Chen和我的姐妹MayaChen，感谢他们的支持和鼓励。谢谢Abellan-Romita家族，Raphaël，Nathalie，Francis，感谢你们的支持，感谢你们从高中以来一直鼓励我。正是因为你们，我才能够在今天站在这里，我由衷地感谢你们。0我要感谢我的两位导师，Arnaud Sallaberry和PascalPoncelet，他们给了我这个机会去做这个博士论文，给了我信任，花费了大量时间来指导和帮助我。非常感谢你们。0我还要感谢评审委员会的成员。Pascale Kuntz和DavidAuber同意审阅这篇论文，并提出了很多有见地的意见。MarianneHuchard在整个博士期间一直陪伴着我。Cédric du Mouza和FrancescoBeretta同意评估我的工作。Dino Ienco在整个博士期间一直跟踪我。0我还要感谢蒙彼利埃大学（UM），蒙彼利埃信息、机器人和微电子实验室（LIRMM）和ADVANSE团队为我提供的接待，以及ANR DAPHNE为这项工作提供的资金支持。0我还要感谢我团队的所有成员，过去和现在的，WEB3，MAB，GraphiK团队，LIRMM的秘书处，以及更广泛的所有这些美好的人，常驻人员，博士后，博士生，实习生，我有幸遇到并从他们那里学到了很多知识，无论是我们共度的时光还是他们传授给我的知识。0特别感谢Arnaud Castelltort，Jérome Azé，Maximilien Servajean，Sandra Bringay，NancyRodriguez，Morgan Soulié，Alexis Delaforge，Hugo le Baher，LeonardoMoros，Laëtitia Viau，Samy Benslimane，Vincent Raveneau，Waleed Ragheb，SamihaFadloun，Erick Cuenca，Constantin Todorov，Clement Jonquet，AndonTchechmedjiev，Faaiz Hussain Shah，Martin Jedwabny，Bruno Yun，AbdelraoufHecham，Sylvain Milanesi，Nikolaï Romashchenko，Benjamin Linard，VincentLefort，Marie Mille，Sylvain Pulicani，Johannes Wirtz，Raphaël Romero和VirginieFeche，感谢你们所有有趣和不那么有趣的讨论。0最后，我要感谢所有的朋友们对我的支持和倾听，William Blachère，AnthonyCarmona，Maxime Pyz，Adam Garcia，Jessica Vargas Andrande，谢谢你们。22.3.2Le modèle de données . . . . . . . . . . . . . . . . . . . . . . . .222.4Conception de la plateforme ProsoVis . . . . . . . . . . . . . . . . . . .242.4.1Vue globale. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .252.4.2Vue détaillée . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .292.4.3Filtres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .372.4.4Discussion préliminaire . . . . . . . . . . . . . . . . . . . . . . .382.5Siprojuris . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .422.5.1Intégration des données . . . . . . . . . . . . . . . . . . . . . . .422.5.2Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .432.6Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .462.7Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .503AGORA513.1Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .523.2Définitions et notations préliminaires . . . . . . . . . . . . . . . . . . . .533.3Critères de qualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .543.3.1Préservation de l’ordre orthogonal . . . . . . . . . . . . . . . . .563.3.2Minimisation de l’expansion. . . . . . . . . . . . . . . . . . . .573.3.3Préservation du rapport de forme. . . . . . . . . . . . . . . . .583.3.4Minimisation du mouvement des nœuds . . . . . . . . . . . . .593.3.5Préservation des longueurs des arêtes . . . . . . . . . . . . . . .613.4Comparaison des algorithmes . . . . . . . . . . . . . . . . . . . . . . . .623.4.1Qualité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .633.4.2Temps de calcul . . . . . . . . . . . . . . . . . . . . . . . . . . . .670目 录01 引言 101.1 背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101.2 贡献 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401.3 论文组织 . . . . . . . . . . . . . . . . . . . . . . . . . . 702.1 背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1002.2 现状 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1002.2.1 事件可视化 . . . . . . . . . . . . . . . . . . . . . 1102.2.2 个体可视化 . . . . . . . . . . . . . . . . . . . . . 1202.2.3 混合可视化 . . . . . . . . . . . . . . . . . . . . . . . . 1602.2.4 人物传记数据可视化 . . . . . . . . . . . 1702.3 人物传记数据建模 . . . . . . . . . . . . . . . 213.4.3Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .693.5AGORA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .703.6Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .723.7Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .734F-SAC754.1Contexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .764.2Problématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .774.2.1Problème SAC en ligne . . . . . . . . . . . . . . . . . . . . . . . .774.2.2Problème SAC hors ligne . . . . . . . . . . . . . . . . . . . . . . .784.3État de l’art . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .794.3.1O-SAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .794.3.2QUAD+ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .804.3.3QUAD+BIG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .814.4F-SAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .814.4.1Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .824.4.2Fast SAC en ligne. . . . . . . . . . . . . . . . . . . . . . . . . . .855.2.2AGORA. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1045.2.3F-SAC. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10504.5 实验 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8604.5.1 实验设备 . . . . . . . . . . . . . . . . . . . . . . . 8704.5.2 数据集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8704.5.3 定性分析 . . . . . . . . . . . . . . . . . . . . . . . . . . 8804.5.4 定量分析 . . . . . . . . . . . . . . . . . . . . . . . . . 9204.6 讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9804.7 结论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10005 结论和展望 10105.1 摘要 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10105.2 展望 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1020参考文献 10710第1章0引言0从词源学的角度来看，prosopographie意味着“个人的描述”（希腊语πρόσωπον：“（戏剧）人物”），它首次出现在18世纪，当时它指的是一个人的列表。后来，历史学家们将其用于指代传记条目，以研究历史行动者群体的共同特征，通过对他们的生活进行集体分析（Stone，1971）。更具体地说，这种集体研究旨在通过对他们的生活和经历进行系统观察，揭示一个社会群体（例如，社区，机构，地位，职业等）的共同特征（Delpu，2015）。在这种背景下，信息可视化对历史学家来说具有有趣的前景。在本介绍中，我们首先介绍我们方法的背景，然后介绍我们的贡献。01.1 背景0计算机科学的进步（例如数据库，信息组织或结构化，图像识别，数字化等）和数字人文的兴起促进了许多人物数据库项目的发展，例如COL&MON1，该项目提供有关卡洛林改革至特伦特大公会（816-1563）的修道院和修道院的信息，Biblissima 2，该项目提供中世纪保存或已知的书面遗产的访问，PASE3，该项目记录了从6世纪末到11世纪末在英格兰普查的居民信息，PBW4，旨在描述拜占庭帝国及其周边地区的个人在642年至1265年之间的情况。Akoka等人（2020）对人物数据库项目进行了最新的综述。0对于历史学家来说，这些数据通常很难获得，难以结构化，并需要长时间的研究工作，但它们非常重要，因为它们可以尝试回答许多问题或提出新的假设，例如：这个社区中的这种思想流派是如何出现的？它是否与不同的个体在同一时间和地点相遇有关？01. https://colemon.huma-num.fr . 本论文中的所有链接在2022-01访问。 2.https://projet.biblissima.fr/fr/projet/presentation 3. https://pase.ac.uk 4.https://pbw2016.kdl.kcl.ac.ukINTRODUCTION20在同一地点？为什么和如何个体在时间和空间中的功能发生了变化？一个个体是否能够在他的社会群体中产生很大的影响？如果是的，为什么？何时？如何？是否存在一个时期或地点促进了某一机构思想流派的出现？为了回答这些问题，可以使用SPARQL等查询语言来查询数据库。然而，除了对于历史学家来说查询的表达方式远非简单之外，数据通常是不确定的（例如，不同的名称变体），具有不同的粒度（例如，时间段或日期），可能随时间变化（例如，地点名称不再相同）等。即使一些项目依赖于地理信息系统（GIS）来定位事件，查询通常仅限于在地图上定位一个或多个个体，无法观察时间的变化。0另一方面，信息可视化研究使用图形和交互式计算机图形来促进数据的获取和使用（Card等，1999年，第6页）。它提供了所有功能，帮助用户浏览和分析这些数据。个人、时间、空间和事件是人物传记数据库的核心。然而，正如我们在后面的论文中将看到的，对于这种类型的数据，可视化方法很少。这就是本论文的背景所在：0为专家提供什么样的信息可视化来探索和导航人物传记数据，并帮助他们回答问题或测试假设？0为了提供适当的可视化，设计师必须回答三个问题：什么？为什么？怎么样？（Sallaberry，2020年）。Munzner（2014年）提供了关于可视化设计空间的当前知识的概述，为回答这些问题提供了建议、推荐或建议，设计师应该从中汲取灵感，找到最适合领域专家需求的答案。0什么？0我们首先需要回答的问题是处理的数据是什么？人物传记数据确实是时空相关的，与个人和事件相关，但它们还具有许多特殊性：可能是不完整的数据，可能是精确的、未知的或对应于某个时期的日期，可能是随时间变化的位置（例如，2016年法国地区的合并），可能是不精确的位置（例如，巴黎大学在哪里？城市中是否有分布在不同建筑物中的巴黎大学？）等等。这种分析将帮助我们更好地组织这些原始数据，以便随后可以通过平台进行可视化或探索。当然，在这个阶段，会做出选择，并且这些选择会对设计空间产生影响，即与这些选择相关的可视编码类型和可用交互的集合。幸运的是，已经存在分类法（例如，Munzner，2014年），可以帮助设计师从可用元素中找到最适合组织数据集的元素。301.1. 背景0然而，即使在这个层面上，我们可以考虑结构，但不能忽视信息可视化的主要目标，即回答为什么的问题。0为什么？0为了回答这个问题，与领域专家的合作和交流是必不可少的，因为在这里我们定义了将通过可视化实现的不同任务。这个概念阶段对应用程序的设计师来说，不仅是列出问题，而且更重要的是将问题转化为可以用先前问题的答案所选择的数据结构来完成的任务。0评论？0前两个步骤可以很好地指示我们想要做什么（回答为什么）以及在什么上面做（回答什么）。我们已经将与专家领域相关的问题转化为可视化问题。现在的问题是如何解决这些问题。因此，作为设计师，我们的目标是寻找适合的可视化方法，以及（更重要的是？）提供给专家方便地操作数据的交互技术。当然，诸如修改、选择、导航（例如滚动、缩放等）之类的元素在我们的背景下是必要且不可或缺的。然而，与可能会被发现的不同任务相关联，可能需要在不同的可视化之间进行其他交互。明显的结果是，这也会对可视化设计空间产生影响，可能...也会对其他问题产生影响。0正如我们所看到的，这些问题之间的关系非常密切，对一个问题的回答必然会对其他问题产生影响。因此，本论文的主要目标是回答这三个问题，以提供适应专家需求的人物数据可视化平台。为了回答这些问题，我们将做出一些选择。这些选择引发了其他目标。例如，直观上，我们知道需要表示一组个体。根据Munzner（2014）的分类法，特别适合的结构是图。众所周知，对图进行交互（例如缩放）可能会导致重叠问题（Misue等，1995）。在这种情况下，另一个目标也是确定哪种算法最适合处理这些问题。有许多提议，对于设计者来说，关键是在考虑到许多参数（例如时间、变形等）的情况下，在其上下文中确定最适合的解决方案，始终以提供适应专家需求的界面。最后，数据是时空数据。对于专家来说，能够根据他们的研究定位一个地点是必不可少的。因此，需要提供一个平台，可以在地图上表示一个或多个事件，或者一个人或一组人（在这个阶段，还不清楚将表示什么）。在这里，交互对于在地图上导航是必不可少的。最后一个目标是1.2ContributionsFigure 1.1 – ProsoVis : une plateforme de visualisation et d’exploration de données prosopographiques5. Découverte dans les bAses Prosopographiques Historiques de coNnaissancEs (ANR DAPHNE17-CE28-0013-01) https://anr.fr/Projet-ANR-17-CE38-00136. LAboratoire de Recherche Historique Rhônes-Alpes http://larhra.ish-lyon.cnrs.fr/7. Laboratoire de recherche en TECHnologies Numériques pour l’Éducation https://techne.labo.univ-poitiers.fr/8. Centre d’Études et De Recherche en Informatique et Communications https://cedric.cnam.fr/9. LAboratoire de Médiévistique Occidentale de Paris https://lamop.pantheonsorbonne.fr/40引言0我们希望能够通过地图、一组点和交互来提供最流畅的导航，例如在某些缩放级别下，最小化用户等待时间以进行对象聚合。0这篇论文是在蒙彼利埃的LIRMM（蒙彼利埃计算机、机器人和微电子实验室）的ADVANSE（数据科学高级分析）团队中完成的。它是在ANR DAPHNE5的框架下进行的。论文期间的工作是与LARHRA 6、TECHNÉ 7、CÉDRIC 8和LAMOP9实验室的团队合作完成的。0为了回答对人物数据可视化的使用，我们提出了 ProsoVis平台（见图1.1），该平台提供了许多功能，用于在数据中导航。它通过全局视图（所有个体）或详细视图（一个或多个个体）可以跟踪不同人物随时间和空间的变化。0为了简化导航或信息过滤，以及帮助专家完成定义的各种任务，提出了许多可视化和交互。该平台目前使用的是基于1.2. ContributionsSiprojuris 10 mais a été conçue pour pouvoir intégrer facilement d’autres types de basesprosopographiques.Une des approches traditionnelles pour représenter un ensemble de personnesen visualisation est d’utiliser le diagramme nœuds-liens du réseau/graphe formépar ces personnes. C’est ce diagramme que nous avons utilisé pour que l’utilisateurpuisse avoir une vue globale de tous les individus de la base de données. Une vuestatique peut facilement être réalisée via des algorithmes de placement dans un graphe.Cependant, dès que des interactions sont proposées à l’utilisateur (e.g. déplacement,zoom), cela pose de nouveaux problèmes dont celui des chevauchements des nœudsdu graphe : les nœuds représentant, par exemple, le nom des individus se superposentet il n’est plus possible de lire les informations. Pour résoudre ce problème, il existedifférentes approches qui ont été proposées dans la littérature. La question est alors :quelle est l’approche la plus adaptée à ma problématique? Bien que de nombreuses métriquespour évaluer les approches ont été proposées, aucune des propositions de la littératuren’offrent de comparaisons sur les mêmes critères. Par exemple, si une approche proposede conserver la minimisation de l’expansion, elle n’utilise pas la même métrique pourl’évaluer qu’une autre. De la même manière, l’utilisation des temps d’exécution pourraitêtre utile mais comment comparer des temps quand les implémentations sont réaliséesdans des langages différents. Pour permettre de choisir et montrer les raisons qui nousont poussé à sélectionner une approche particulière pour ProsoVis, nous avons comparéles différents algorithmes existants. Pour cela, les algorithmes ont été implémentés dansun même langage et nous proposons une classification des différents critères et pourchacun d’entre eux une mesure représentative. Des expérimentations ont été menéessur 854 graphes synthétiques (aléatoires, arbres, à invariant d’échelle, petits-mondes)et réels afin d’analyser le comportement des algorithmes. Nous montrons ainsi, enfonction des critères attendus pour une visualisation, quel est l’algorithme le plusadapté. Ces travaux ont donné lieu à la publication suivante :Chen, F., Piccinini, L., Poncelet, P., & Sallaberry, A. (2019). Node overlap removalalgorithms: A comparative study. In D. Archambault & C. D. Tóth (Éd.),Proceedings of the international symposium on graph drawing and network visualization(GD) (p. 179-192). Springer. https://doi.org/10.1007/978-3-030-35802-0_14Cet article a été sélectionné dans les Best Papers de la conférence ce qui nous a permisd’en publier une version étendue en journal :Chen, F., Piccinini, L., Poncelet, P., & Sallaberry, A. (2020). Node overlap removalalgorithms: An extended comparative study. Journal of Graph Algorithms andApplications, 24(4), 683-706. https://doi.org/10.7155/jgaa.00532La représentation de la dimension spatiale des données de ProsoVis a une grandeimportance car elle permet aux utilisateurs de pouvoir localiser les évènements sur unecarte. Cependant, lorsque des fonctionnalités, de zoom par exemple, sont proposées, ildevient important de mettre en évidence, non plus les points individuels mais plutôtdes regroupements de points proches géographiquement sous une forme commune. Ceproblème correspond à une problématique bien connue d’encombrement visuel. De10. http://siprojuris.symogih.org/5INTRODUCTIONnombreuses techniques ont été proposées et, parmi celles-ci, le Regroupement SpatialAgglomératif s’est avéré très adapté. L’objectif est le suivant, à partir d’une carte et d’unnombre de points géolocalisés, il s’agit de fusionner les points qui se chevauchenten clusters, la quantité de points qu’ils contiennent affectant directement leurs taillesapparantes. Il suffit ensuite d’afficher à la fois les clusters et les points qui n’ont pas étéregroupés sur la carte afin d’obtenir une visualisation sans chevauchements. Différentsalgorithmes ont été proposés et considèrent deux types d’approches : (1) en ligne où leclustering est effectué en temps réel pour un niveau de zoom donné et doit être relancélorsque l’utilisateur change de niveau et (2) hors ligne où l’ensemble de tous les clustersest déterminé au préalable pour chaque niveau de zoom, offrant ainsi plus de fluiditélors de l’interaction. Nous proposons un nouvel algorithme, F-SAC, se déclinant en enligne et
我的内容管理
展开
