**图1：**我们的系统截图显示了一个分析人员探索一个真实世界的系谱数据集，观察集群的结构和属性特征。(a) 控制面板允许用户指定我们的集群模型的参数。(b) 家谱视图以结构概述的形式显示选定集群的所有家谱。(c)平行坐标视图被设计用于显示家谱的多维属性。(d)投影视图显示族聚类，其中聚类的分布根据学习向量和多个属性的相似性和多个属性确定，聚类的符号编码多个属性特征。
聚类是能够提出一个简短的说明，为感兴趣的家庭和模式的重要性在大规模的系谱数据集。在传统的聚类方法中，主要采用拓扑特征进行总结和组织。然而，丰富的属性被忽略了，这对增强对系谱聚类特征的理解和解释也很重要。因此，将结构和属性组合成一个聚类模型来探索族谱数据集是一项至关重要的任务。本文提出了一种基于偏最小二乘法(PLS)的属性增强拓扑聚类方法。首先，利用 graphlet kernel(图核)的方法来测量家谱之间的结构差异。然后，我们利用PLS结合学习向量和多个属性，和联合降维方法应用项目高维向量到二维空间的基于距离的聚类方法来聚合类似的家谱考虑拓扑结构和属性特征。此外，我们实现了一个具有多视图协作的可视化分析系统，包括字形、家谱视图和平行坐标视图，以表示、评估和探索聚类特征。基于真实世界的系谱数据集的案例研究和定量比较已经证明了我们的方法在系谱聚类和探索方面的有效性
随着系谱数据集的不断增加，为人口统计学、进化生物学、人类迁移、姓氏起源、家族遗传学等提供了巨大的机会。因此，对系谱的研究引起了从社会科学家到历史学家越来越多的关注。然而，由于数据量大、树状结构的异质性和相关的属性信息，专家往往无法在大规模的系谱数据集中快速发现感兴趣的家族和重要的模式。根据“以概述为主，放大和过滤，然后按需详细说明”的原则，创建一个直观的、简单而又全面的关于大量家谱的概述是非常重要的。因此，专家们将很容易地获得整个系谱数据集的可视化摘要，并关注具有特定模式的家庭，以进一步深入了解家庭发展和进化的特征。
聚类是简化数据认知和表达的一种常用方法，它将相似的家庭分组到相同的聚类中，使专家能够在聚合级别上获得整个系谱数据集的一般模式。以往的工作主要集中在基于拓扑聚类的家谱的总结和组织上。然而，目前开放的系谱数据集往往是有用的。除了个人之间的亲属关系外，他们还包含了丰富的个人信息，包括性别、住所、出生/死亡时间和婚姻状况等。因此，这将更有利于同时考虑拓扑结构和属性特征，对家谱进行聚类，并揭示家谱与社会属性之间的相关性。例如，家庭成员的平均寿命和几代数之间的关系是什么？迁移行为如何影响家庭人口？男性创始人第一次出生的年龄会导致家庭分支的不平衡发展吗？然而，如果考虑到结构信息和属性特征，那么要将家谱聚合成集群，仍然存在三个挑战：
C1.树的结构总是用拓扑关系来描述的，这与属性特征有很大的不同，因此很难有效地组合它们。
C2.聚类特征涉及丰富的信息，这使得直观地理解隐式知识和捕获感兴趣的模式非常困难。设计直观的可视化来直观地呈现集群的结构特征和属性信息是很重要的。
C3.对于[51,54]的用户来说，结构与属性之间的相关性难以发现，因此开发一个可视化分析系统，使用户能够对系谱聚类特征进行定量比较、交互分析和深入探索是一个迫切的任务。
为了解决上述挑战，本文提出了一种系谱聚类的结构-属性融合模型。首先，我们利用一个图形核(graphlet kernel(图核))方法来测量家谱之间的结构差异。然后，利用偏最小二乘(PLS)将学习到的向量和多个属性相结合，采用联合降维方法将家谱投影到低维特征空间，并基于距离聚类方法进一步对具有相似结构和属性的家谱进行聚合。此外，我们提供了各种质量指标来评估聚类特征，并设计了一组多尺度的符号来直观地呈现它们的结构和属性特征。此外，设计了多个协调视图、一系列视觉线索和交互，使用户能够选择这些感兴趣的集群并获得更深入的见解。我们通过案例研究和基于真实数据集的专家访谈，进一步证明了我们的系统的有效性和有效性。
本文的主要贡献总结如下：
- 提出了一种基于结构和属性特征组合的族树聚类聚合方法。
- 提供了丰富的可视化和交互，以可视化表示和探索家谱集群，使用户能够对这些感兴趣的集群和原始的大规模系谱数据集获得更深入的更深入的见解。
- 基于真实世界的家谱数据集进行了案例研究和定量比较，以评估聚类结果，并验证了该系统的有效性和实用性。
本文的结构如下。第二节简要介绍了相关的工作。第3节总结了分析任务，并介绍了我们工作的系统概述。第4节列出了我们的属性增强拓扑聚类的细节。第5节基于真实数据集的案例研究和定量比较以及讨论。最后，第6节对本文进行了总结。
我们将相关工作分为系谱数据分析、拓扑数据聚类、属性增强的拓扑数据分析和可视化聚类分析技术等四类。
系谱学一直是人们的流行活动。Kemp[13]发现，家谱的受众从年轻到年老，也有种族群体。虽然系谱学很受公众的欢迎，但它为人文和社会科学的许多研究提供了重大贡献。例如，Tsuya等人[34]研究了欧洲和亚洲的系谱，以估计长期人口比率的趋势。SW等人[8]从深度、男性成员数量和倾向等方面探讨了中国历史上的父权社会。刘等人[22]分析了与结构、人口、迁移和其他人口统计信息相关的家庭的发展。
然而，在大规模系谱数据分析[47]中存在许多问题，如大量庞大的分支和复杂的层次结构。可视化学者对简化系谱学的表达进行了大量的研究。家谱的可视化大致可以分为三类。（1）基于节点链接的可视化。节点表示族成员，边表示父子关系[33]，布局模式可以是正交布局、缩进布局或径向布局。（2）基于线的可视化[40]。个体用一条水平线表示，每条线的长度代表相应个体的寿命。此外，为了表示个体之间的关系（线），绘制垂直线来绘制亲子关系，绘制线之间的收敛和发散来绘制婚姻和离婚关系。（3）基于矩阵的可视化。布局可以是一个对角填充矩阵，其中行是个体，列是核心族[1]；它也可以是一个邻接矩阵，其中非零项表示图中两个相应顶点之间的边。也有一些利基表示，如扇形图、沙漏图、双树等。
拓扑数据聚类是聚类的主要研究领域之一。基于拓扑的数据聚类[44]的技术，可分为图聚类和树聚类两大类。
图聚类。迄今为止，已经提出了许多图聚类技术，它们基于各种标准，包括基于归一化切割、模块化或结构密度的聚类。还有其他的聚类方法，它们依赖于在图上定义的相似度函数。例如，编辑距离[12]计算了无向无环图之间的距离，即在将一个图有效地转换为另一个图时的成本之和。图直方图技术[29]以直方图的形式捕获数据特征，然后使用直方图距离函数计算图之间的距离。Dexter等人[7]比较了基于RMSD矩阵的蛋白质结构的差异，并通过 LanceWilliams更新算法将它们聚类。图聚类是一项探索性的数据分析任务，已得到广泛的应用。例如，Kong等人[15]提出了一种基于图结构聚类算法MST的数据包分析僵尸网络检测方法。Kutz等人[17]介绍了专利跨类别的分布，这提高了对专利组合随时间推移的演变的理解。
树聚类。与图的聚类一样，大多数树的聚类技术也是基于树的比较的。例如，SW等人[8]根据倾斜度等相应的标准对所有家谱进行过滤和收集。DAViewer[48]通过强制不同解析算法的基本语篇单元相同，允许对树的结构进行比较。TreeJuxtaposer[27]通过将一个树中的每个节点与另一个树中的最佳对应节点关联起来，从而对树进行分类。Kosaka等人[16]提出了一种基于最大似然准则的树形结构说话人聚类算法。希莉斯等人[10]通过使用多维尺度比较树到树的距离来可视化系统发育树集之间的关系。
多元网络数据集中的关联属性信息可以帮助用户分析关系的建立、社区的形成和网络的演化。例如，Wang等人[37]探讨了学者学术影响的几个因素，如论文数量、引用和合作关系。Ko等人[14]通过利用多维时空信息可视化航空网络数据，探索了机场间航班延误的类型和数量。Nober等人[28]可视化了一个家庭的多变量临床数据，以探讨遗传和环境因素如何影响个体健康。瓦滕伯格[38]设计了数据透视图，这是一个软件工具，关注节点属性和多元图连接之间的关系。探路者[30]在网络上使用路径查询，并将结果的路径呈现为一个线性的排序列表，并与丰富的属性数据并列来判断路径。路径线[26]同时观察了跨时间、物种、基因和代谢物的多组值，以比较物种之间的趋势。金等人[11]提出了一种基于文本语义表示和词共现图结构的文本聚类算法，以提高聚类效果。杨等人[45]将原始网络结构和个体利益属性相结合，挖掘隐式聚类结构网络，并对热事件的传播过程进行预测。
为了评估聚类的质量，许多质量指标已经被提出，如Calinski-Harabaz index [3], Silhouette Coeffificient [32],和Davies-Bouldin index [6]。此外，可视化聚类分析技术也被广泛应用于高质量的聚类发现过程中。例如，vista[5]允许用户在2D投影上可视化地评估聚类结果。但是，该方法不支持多重聚类结果的比较。聚类视觉[18]支持通过使用五种指标对聚类结果进行排序来找到高质量的聚类结果。XCluSim[24]使用户能够交互式地生成并使用多个协调视图比较多个集群结果。DICON[4]是一种基于图标的集群可视化方法，它将统计信息嵌入到多属性显示中来解释和评估集群。迭代聚类的可视化方法将自动化与交互式方法相结合，允许用户定义种子（中心），并帮助用户与进程[2]进行交互。集群系统使用最小化函数来自动进行参数选择，允许用户定义集群并修改要执行的集群的特性[25]。
我们用来进行研究的真实世界数据集是CMGPD-LN。中国多代面板数据集-辽宁(CMGPD-LN)是由清朝政府从1749年至1909年在中国东北辽宁省编制的人口登记册中转录而成的。该数据集有超过150万条记录，为超过26万人提供了社会经济、人口统计学和其他特征。根据个体间的关系，我们建立了大约12000棵家谱。此外，从成员信息中提取并构建5个属性来描述家庭特征，包括时间跨度(TS)、平均年龄(AA)、位置数(PN)、村数(VN)和父子平均差距(AG)。
我们的系谱聚类系统的设计是通过采访两位专家(E1和E2)来实现的。E1是一家研究所的教授，在图形可视化和挖掘方面有着丰富的经验。E2是一名人文和社会科学领域的大学教授，他在人口统计学、历史和人类迁移方面的知识渊博。为了为系统的设计和开发提供信息，我们与领域专家进行了初步设计研究。具体来说，我们首先采访专家询问他们之前的工作，并询问他们工作过程中普遍存在的主要问题。聚类是一个重要的手段来探索和分析家谱数据集，这是一个重要的任务考虑拓扑结构和属性特征，因为这些关键元素在家谱有利于发现家谱和社会属性之间的相关性。此外，从专家对我们的系统的评论中获得了一系列需求，并用于指导我们的系谱聚类系统的开发。根据这几轮对专家的访谈，需求任务总结如下。
R1：系谱聚类的属性和结构的融合。基于拓扑的聚类方法需要提前比较家谱之间的结构差异[49]。族树是一种具有特殊拓扑结构的图，因此传统的图相似度测量方法可以用于系谱数据。此外，家谱还具有丰富的属性信息，而属性增强的聚类能够使聚类特征具有更大的实际意义。然而，拓扑关系和属性特征的大小不同，很难将它们均匀组合。因此，专家们需要一种有效的联合聚类方法来综合考虑这两个特征。
R2：系谱聚类结果的直观可视化表示。集群包含关于多个维度的信息[19]，包括结构和属性。一个有效的视觉表示必须传达数据的每个维度，并确保其数据被忠实地表示，以便用户能够直观地理解内隐知识。此外，为了捕捉人们感兴趣的模式，并对人口统计学、历史等领域有更多的见解。从族谱数据集中，集群的可视化表示不仅需要支持用户查看每个集群之间的全局信息的细节，还需要查看集群中每个家谱的局部信息，并验证它们在结构和属性方面的性能。
R3：对聚类结果的评估。在对系谱数据集的探索和分析的具体场景下，需要验证聚类的有效性。在不同特征组合的情况下，聚类内的家族和聚类外的家族以及不同簇之间的差异在聚类结果中是相当不同的 [50]。因此，需要质量指标和视觉线索来展示聚类特征的质量，使用户能够从不同的角度评估有效性，并直观地解释聚类特征。
R4：系谱数据的聚类分析系统。在社会科学领域中使用的传统的系谱分析方法和商业软件并不支持仅对具有特定特征的系谱数据集进行分析。此外，分析结果仅限于数值统计，不利于对大规模系谱数据集的直观理解和快速探索和分析。因此，需要一个系谱数据集的可视化分析系统来支持非专家用户捕获感兴趣的家谱，并以一种简单的探索性交互式方式在大规模系谱数据集中获得更深入的见解。
图2。基于属性-结构同步的族谱聚类系统的流程。
基于已确定的需求，我们设计了一个可视化框架，使用户能够基于属性增强的拓扑聚类方法来探索和分析族谱数据集。系统流程如图2所示。首先，将一个大规模的系谱数据集加载到可视化系统中，并分别采用graphlet kernel(图核)和统计方法捕获结构和属性特征。在此基础上，建立了一种新的系谱聚类模型，将学习到的向量与基于PLS的多属性相结合，在联合降维后实现基于距离的聚类(R1)。此外，设计了一组多尺度符号，从多维视角可视化地呈现聚类的特征，并进一步计算各种质量指标来评估聚类特征(R3)的有效性。将多个协调视图和一系列交互集成到可视化系统中，进行系谱的可视化聚类，使用户能够探索和分析大规模的系谱数据集(R4)。
在本节中，我们将详细介绍关于基于属性-结构同步的家谱聚类的过程。
我们的基于拓扑的系谱聚类方法是预先通过graphlet kernel(图核)来计算成对族之间的结构差异，并将家谱数据转换为向量数据。然而，向量数据具有高维数的[36]，因此我们利用t-SNE来降低数据的维数。基于拓扑的聚类算法主要包括以下两个步骤。
实际上，graphlet kernel(图核)是最近发展迅速的，成为图形数据分析的一个重要分支。两个图的核值与分解后的子结构的相似性有关，可以描述两个图之间的近似值。graphlet kernel(图核)算法和基于拓扑的聚类的详细内容如下。
给定两个家谱T1(V1、E1)和T2(V2、E2)，一种图分解方法F，即基于 Metropolis-Hasting random walk[31]的图采样方法，分解后得到的子结构为F(T1)={S1,1，S1,2，...，S1，N1}；F(T2)={S2,1，S2,2，...，S2，N2}。现在，我们使用graphlet kernel(图核) 将图形数据映射到高维空间φ中的向量数据中，并将 graphlet kernel(图核) 定义如下：
$$
k(T1,T2) = <ϕ(T1), ϕ(T2)>
$$
其中，ϕ(T)是一个图形频率向量，定义为族树T的分量ϕi(T)对应于图形Si的相对频率。在本质上，树的图形频率向量就是树的特征向量。核k（T1、T2）可以看作是两个家谱之间的接近程度。如果有N个族树，从图核得到的结果可以用K=(k(Ti，Tj))N×N表示，称为核矩阵。
利用graphlet kernel(图核)，将N族树的相似性表示为高维空间中的核矩阵K=(k(Ti，Tj))N×N。高维数据往往具有冗余特征或不相关的特征，这些都会增加计算复杂度，影响聚类算法的效率，甚至导致维灾难，因此降维是必要的。
t-Distributed Stochastic Neighbor Embedding (t-SNE)[35]是一种有效的降维方法，它能够在降维空间[42, 46]中保留全局特征的同时增强局部特征。在降维后，我们得到了二维向量数据，它同时保持了系谱数据的主要结构特征[43]。然后在投影空间中，使用基于距离的聚类算法K-means对降维家谱进行聚类。
我们将介绍如何从家谱中提取属性特征，并基于拓扑聚类对其进行增强。
基于族谱的领域知识，从微观和宏观层面提取家谱的属性。宏观层次属性是指家谱的全局特征，如时间跨度，它们反映了面向家族的信息。相比之下，微观层面的属性可以通过与节点相关联的值的总和或平均值来获得，如村数、平均年龄等。这反映了以个人导向的信息。这些宏观和微观的属性构成了每个家谱的属性向量，Ai={ai1，ai2，...，aiNA}，其中NA是指从家谱Ti中提取的属性的数量。
基于上述对结构特征和属性特征的提取，假设我们在一个大规模的系谱数据集中获得了两组特征集。给定一个族树Ti，两个对应的特征向量是si⊂Rq和ai⊂Rp，其中p和q分别是这些向量的维数。所有族树的结构和属性特征向量构成两个数据矩阵S∈Rp+n和A∈Rq+n，其中n为族树的总数。我们将变量分散，使AT和ST的列为零均值。然后我们定义A和S的集间协方差矩阵为(1/n−1)Sas，其中Sas=AST。
PLS的目的是分别为a和S找到一对权重向量，即输入权重α和输出权重β，以使输入和输出变量a和S之间的协方差最大化。
该方法将高共线性变量分解为一维变量A-score T 和 S-scores U，表述如下：
其中P和Q是加载矩阵，E和F是残差。PLS算法是一个迭代过程，其表述如下：
我们初始化E0=AT，F0=ST和h=1。经过上述迭代和最终收敛后， A-scores T可以表示为Th=Eh−1αh。Uh和βh也可以用相同的方式推导出。所有m对权重向量，{αi；βi}m1，分别构成两个投影矩阵WA={α1，α2，...，αm}和Ws={β1，β2，...，βm}。通过上述PLS算法，我们可以分别获得两组简化向量。每一对PLS组件都可以通过
最后，对于大型系谱数据集中的每个家谱，可以通过上述PLS将原始属性特征和结构特征转换为一对新的向量，使两个特征之间的协方差最大。然后，我们直接将它们连接为一个属性结构-融合的向量。基于上述PLS的特征融合，将结构和属性将大型族谱数据集中的所有家谱表示为高维融合向量。与上面提到的基于拓扑的聚类相同，然后我们使用t-SNE将它们投影到一个二维空间中。我们利用 K-means对二维向量进行了基于距离的聚类。
图3。为一个集群设计的字形设计。外扇区(a)表示聚类中具有代表性家谱的结构，内圈(b)编码聚类中族的5个属性值。黄色、紫色、粉色、橙色和绿色的扇形扇区分别映射到属性“PN”、“AA”、“VN”、“TS”和“AG”。
图4。与结构相关的视图。所选集群中所有家族的层次结构显示在家族树视图(a)中，该结构的三个统计指标以箱形图(b).的形式显示
当一组相似的家谱被组合到一个集群中时，一个集群中的家谱的属性和结构特征必须被组合成一个单一的符号表示，如图3所示。部分考虑到扇形图的美学吸引力以及它们相对于更常见的节点-链接图的紧凑外观，我们在符号的外部部分提供了另一个版本的家谱，如图3(a).所示在径向空间填充树中采用的增量布局方法遵循了传统的太阳突发可视化的一般格式。对于每个圆弧线，填充颜色的阴影映射生成，长度编码后代的数量，以及带宽映射的寿命。
基于计数器的树图视图的目标是在集群符号中显示家族树的属性。我们在径向空间[41]上扩展了一个迭代的切片尺度过程，以拟合一个基于轮廓的树状图，如符合的内圆所示。内圈平均分为5个不同颜色的扇区，每个扇区代表一个簇中所有族的一种属性分布，如图3(b).所示具体来说，风扇被切成许多方面，根据映射族的属性值，映射的数量可以设置为50,100，或集群中所有家族的数量。此外，面的面积还对属性值进行编码。通过观察计数器的形状，用户可以直观地了解集群中所有族属性的概述。
为了评估聚类结果的有效性，我们从结构和属性的角度提供了一些多尺度的指标。
与结构相关的视图是家谱视图和箱线图视图。当用户选择一个集群时，家谱视图将以节点-链接的树形图的形式详细显示家谱的结构，如图4(a).所示对于每个节点，它的形状编码了性别。此外，集群的结构统计索引以箱线图的形式显示。箱线图可以帮助总结一个集群中所有家谱的三个结构统计指标，包括后代的平均数量(AO)、家族成员的数量（节点）和家族的世代（深度）。在方框图中，如图4(b)所示，方框绑定了系谱数据的第一和第三个四分位数。方框内的水平线是集群中家谱的结构特征值的中间值或中值。这个范围以上和以下的系谱数据的离散度用垂直尾巴标记，它延伸到四分位数范围1.5倍的最极端值。
与属性相关的视图是平行坐标视图。本系统采用并行坐标视图进行多维属性可视化。我们已经确定了系谱的几个重要属性，包括时间跨度、村庄数量、位置号和其他一些统计特征。平行坐标视图具有垂直轴，表示家谱的每个特征，并为每个家谱绘制一条交叉线。线和簇的颜色统一，可以更好地区分不同簇对应的线，如图1(c).所示。
我们开发了一套交互作用来帮助用户在多个协调的视图之间切换。首先，用户可以通过调整控制面板中的数字向下图（图1a）来更改投影视图中的集群数（图1d）。另外，还可以通过在控制面板中勾选相应的属性复选框来自由指定投影元素(图1a)。设置这两个参数后，用户可以进行探索和分析。具体来说，用户可以通过单击投影视图右下角的簇摘要符号的彩色条带来选择一个簇，如图5所示，其中每个彩色补丁代表一个簇，其宽度与每个簇中的家族数量成正比。在选择集群时，不仅会显示结构相关视图（图1b），并显示系谱树的层次结构和统计数据，而且平行坐标视图（图1c）也会自动突出显示所选族的线条。此外，用户可以观察所选集群的整体特征，用户可以点击投影视图右上角的按钮“符号”，查看上述符号。
图5。聚类摘要符号。每个簇被总结为一条具有相同颜色的条纹。条纹根据集群中的族的数量按降序排列，宽度与数量成正比。
在本节中，我们将实验使用真实世界的系谱数据集CMGPD-LN，以评估我们的聚类方法的有效性。然后，以两个真实词数据集为基础进行案例研究，以验证我们的视觉聚类视觉系统的有效性和方便性。
我们进行了一组实验来验证我们的聚类策略的有效性。为了减轻随机性的影响，每个聚类操作被执行了20次，并取平均值。我们将我们的方法与两种聚类策略进行了比较：（1）结构(Str)通过graphlet kernel(图核)量化了家族树的结构，而不考虑属性。（2）属性(Attr)集群基于多维属性的族谱，没有结构。
为了进一步比较不同聚类策略的有效性，我们分别采用以下指标来评价聚类质量：（1）结构相似度(SS)。聚类的SS定义为聚类中任意两点之间的平均结构相似度，用图核度量，范围从0到1。定义良好的集群具有较高的SS值。（2）属性相似性(AS)。AS被定义为每个聚类中所有族的属性值的标准差的平均值。AS值较低，说明家谱在属性方面与自己的集群匹配良好。（3）轮廓系数(SC)。聚类的SC[32]定义为聚类内距离与聚类附近距离之差与这两个距离的最大值的比值，其中距离由二维向量的欧氏距离定义。SC值越高，表明家谱与自己的聚类匹配较好，与相邻的聚类匹配较差。表1总结了不同聚类(C).下不同聚类策略的实验结果：
在聚类相似性比较中可以发现我们的方法优于Attr，在结构相似性方面优于Str。随着C的增加，我们的方法与Attr之间的差距逐渐扩大，与Str之间的差距逐渐缩小。此外，在属性相似性方面，我们发现我们的方法的性能优于Str，而不如Attr。这表明，该方法结合了族树的结构和属性信息，实现了结构相似性和属性相似性之间的平衡。此外，我们的方法在轮廓系数方面几乎优于Str和Attr，这表明我们的聚类方法不仅提高了聚类内的族相似性，而且降低了结构和属性特征结合下聚类之间的相似性。以上结果表明，该聚类方法有效地保持了结构和属性的相似性。
我们实现了一个基于大规模系谱数据集的聚类可视化框架，该框架集成了上述聚类和可视化设计，并提供了一系列的交互，使用户能够探索系谱。为了研究我们的系统的有效性，我们邀请了网络挖掘和系谱(E1和E2)领域的专家来举办了几次研讨会。首先，我们向专家介绍了我们的系统的视觉设计和交互，然后让他们使用我们的系统来免费探索现实世界的系谱数据集。我们的聚类方法所涉及的交互和评估，以及我们的专家发现的几个案例被制定为案例研究。
将数据加载到系统后，E1首先将集群数设置为“12”，并在控制面板上点击“project”。投影视图立即显示了二维空间中所有家庭的彩色簇，专家预测，那些位于附近的家庭拥有相似的结构。然后E1点击表示符号的图标，投影视图根据集群的中心点的位置显示所有的符号。他开始对粉色簇上的符号感兴趣，它只有两个弧线，如图6(e)所示，然后在投影视图中全面检查了该簇的族。专家发现，这些家庭大多数是两代结构，有一个父亲和一个孩子，如图6(c).所示，专家说：“集群中的家族结构彼此相似，与符号的外部部分相似，所以我们可以通过所有符号快速理解所有家谱的特征。”
图6。在基于拓扑的聚类环境中，评估和比较具有不同家庭数量的不同聚类。(a)是一个具有大量简单家族的小集群。(b)呈现出一个具有较少复杂家族的大集群。
图7。在投影视图(a)上同时考虑结构和属性的簇。(b)、(c)、(d)和(e)给出了相应集群的详细特征。
此外，为了评估基于属性增强拓扑聚类的聚类质量，专家们在控制面板中依次点击5个属性复选框和“项目”按钮，然后在投影视图中观察所有特征组合下的族的分布情况，如图7(a).所示E1最初点击了一个橙色的簇，发现族树视图中大多数族的结构非常相似，平行坐标视图的每个纵轴上的属性值的分布也相对紧密，如图7(b).所示。E1称赞道：“多维特征在一个集群中保存得很好。”随后，E1随机点击聚类摘要符号的不同颜色条纹，发现了一个奇怪的现象。一方面，从平行坐标视图和基于计数器的树状图可以看出的五种属性中，橙色和深蓝色簇的分布没有显著差异。但另一方面，在二维空间中对应的簇之间的距离很大，如图7(a).所示。在这种混乱中，E1仔细观察了扇形图和家谱视图，发现这两个集群中的家庭结构有很大的不同。其中，橙色簇中的家族表现出的世代较多，后代较少的结构特征，而深蓝色簇中的家族表现出的世代较少，后代较多，如图7(b，c)所示。在进一步探索的过程中，专家发现情况与上述完全相反，即投影图中相距遥远的绿色和浅蓝色簇的家族呈现出相似的结构和区别属性，如图7(d，e)所示。E1说：“这一发现很好地证明了基于PLS的聚类方法的有效性，该方法同时考虑了结构和属性。”
图8。评估集群的质量，并从与结构相关的视图中获得见解。(a)、(b)、(c)和(d)是基于拓扑集群的投影视图中不同的聚类。
专家们感兴趣的是寻找相似家庭的群体，以提取具有特定特征的有意义的家庭群体。例如，在许多家族中，成员可能具有相同的属性或结构特征，但对其他特征的反应会不同。他们相信，如果他们能将家庭划分为具有相似特征的群体，他们就能对感兴趣所在的群体有更深入的了解。
在探索结构投影视图的过程中，E2发现了一个奇怪的问题，即摘要字形中最宽的色块对应的簇的面积出乎意料地小，如图6(a).所示然后，通过仔细观察家谱，发现集群中的大多数家庭都是一个简单的层次结构，有父亲和儿子。“由于这个集群中的家族结构如此简单，几乎相同，导致许多点重叠，所以应该占据最大区域的集群只显示为一个非常小的集群。”，专家说。相反的情况如图6(b).所示。然后，E2依次点击以下条纹，发现随着每个集群中家庭数量的减少，家庭中的后代数量呈增加的趋势。简而言之，有多个后代的家庭数量往往少于有较少后代的家庭数量。为了验证这一发现，专家比较了平均后代(AO)中每个簇的箱形图，发现该结论是有效的，如图8所示。“层次结构的可视化呈现和结构统计指标可以帮助我们捕捉和验证一些模式。”，专家说。
接下来，专家E2将注意力转向了不同特征的组合。E2通过控制面板，在属性框中选择“AA”和“VN”进行投影。然后在投影视图中呈现不同颜色的簇。通过从家谱图和平行坐标图中比较不同簇的特征，他发现了一些有趣的故事。例如，在最大的集群中，AA在20到32之间，VN几乎为1，家族结构相对简单。在第二个大集群中，AA在35到45之间，VN接近2，其中大多数是有许多代的大家庭。在较小的集群中，AA在30-50之间，而VN几乎是3。这些集群中家庭结构的复杂性呈不断增加的趋势。这充分证明了有长寿的家庭和有更多村庄的家庭会很生气。此外，通过对集群中家庭数量的比较，发现当时的家庭结构并不太复杂。从这些，E2推断两个原因根据当时的社会背景，一个是很难记录家谱，和记录可能丢失或不准确，另是战争陷入混乱，和家庭的连续性大大受到频繁的变化。”从符号和平行坐标图可以看出，每个簇的AG值彼此相似，符合简单的数学规则。“，专家说。最后，专家认为，我们的系谱聚类系统只是有利于基于结构和属性融合的数据集的探索和分析。
在专家们用我们的系统探索了真实世界的图形数据集之后，我们进行了一个半结构化的访谈，以收集专家们关于系统的可用性、视觉设计和交互的反馈，如下所示。
**系统的能力和有效性。**这两位专家对我们的系统印象非常深刻，特别是支持结构和属性融合的聚类模型。E1评论说，我们的系统使快速分析满足结构和属性相似性的家谱更容易。此外，他还说：“系统提供的多属性组合方便我指定感兴趣的属性，并得到在不同相似度量下的系谱聚类。”
**视觉设计和互动。**我们的专家们很欣赏这些可视化的观点。他们发现在集群细节视图中设计的集群符号在视觉上很有吸引力，并传达了关于结构和属性的互补信息。专家们评论说，每个视图的融合及其在系统接口中的逻辑交互是清晰的。此外，专家们也很欣赏多视角和交互式评估的协作，这提供了一种直观和方便的方法来表示、评估和探索集群质量。
与传统的聚类策略相比，我们的族谱聚类模型增强了家谱的属性特征。其主要的优点是，我们采用了一个PLS模型来融合结构和属性，并设计了一个符号来表示集群的特征。但本文仍有一些问题没有得到很好的解决。
（1）在本文中，我们利用graphlet kernel(图核)和统计方法来分别度量家谱之间的结构和属性的相似性。然而，系谱的特征存在表达不一致的问题，很难有效地融合。本文虽然使用了PLS，但目前并没有充分考虑到特征的具体意义。在未来的工作中，我们将探索一种更有效的特征融合方法来有效地、充分地表达数据的多维特征。
（2）在本文中，我们提供了一个新的符号来共同表达同一空间中簇的结构和属性，但这提出了一个视觉缩放问题。当一个家谱的结构过于复杂或一个集群中的家族数量太大时，我们的符号在视觉感知方面将面临巨大的压力。在未来的工作中，我们将研究更精细的特征表示设计，以增强视觉扩展，或将更多的元素集成到我们的视觉设计中，以丰富设计的表达。
（3）聚类是简化系谱数据分析的重要组成部分，但它不是结束。根据领域专家的要求，对系谱数据的分析需要进一步探索系谱与人文、社会、历史、经济等领域的相关性。在进一步的工作中，我们将引入更多的算法模型来对上述关系进行深入的相关分析，并绘制因果关系来分析社会现象，获得更多的见解。
本文利用图形核来表示图的结构，并设计了一个偏最小二乘(PLS)模型，将其结构和属性信息结合到一个融合的嵌入空间中。然后，我们在一个真实字系谱数据集上采用基于距离的系谱聚类方案。此外，还提供了一套可视化的界面，使用户能够交互式地执行系谱聚类，并从各个角度可视化地评估聚类结果的相似性。基于真实世界数据集的定量比较和案例研究已经证明了该系统的有效性。