基于Hausdorff距离的关系层次聚类算法

唐四慧，庄 东，刘 潇

(1.华南理工大学工商管理学院，广州 510640；2.澳大利亚国立大学计算机科学与工程学院，澳大利亚，堪培拉 0200；3.暨南大学管理学院，广州 510632)

0 引言

大数据的爆炸不全来自于物理世界，其中70%来自于近2年人类的行为包括通讯、社交、购物、互联网活动等。非常多的应用希望利用这种关系数据来了解人类，以期解释群体社会行为如席卷伊斯兰世界(以及一部分西方世界)的宗教原教旨主义，集体经济安全，全球变暖和我们时代的大流行[1]。早在过去的60年里，社会学家就开始关注人类的交互行为和群体行为，他们还构建了网络分析方法来量化这些行为，但是社会现象不仅包括大量的异质个体而且这些行为还会在时间和空间展开。基于样卷的网络分析方法不再适用于互联网环境下多时间多空间尺度的群组，这里的个体行为我们需要考虑1)个体的经历，2)与其它个体的竞争、合作、比较的关系，3)他所在的组织和制度，4)以及所有成分之间的相互作用。只有了解这些关系，我们才能预测群体过程。聚类算法是分析群体行为的工具，将传统的算法应用于人类关系数据的研究需要解决以下问题：

2)网络的层次结构。异质性和斑块镶嵌是流动发生的基础但层级结构是稳定这种结构的机制[8]，同时层次结构也使得系统中的流最大化如生态系统[9]，对人类群体行为理解后还希望能优化它的功能比如控制流动[10]。关系的非对称性是建构层次结构的基础。

3)在海量关系数据上有好的速度。

目前的网络聚类算法不能同时将这3个问题全部解决。在这篇文章中，我们首先运用迭代系统隐喻个体结构的变化，构建个体结构谱，通过结构谱确定节点结构属性；再将Hausdorff距离(H氏距离)引入DBSCAN算法，用以解决关系数据非对称性的距离测度，运用Hutchinson算子中的加和算子对同结构节点进行合并，用输入输出关系实现层次结构的并算子；加和及并算子均为单调增量方式，处理结果在时间和空间维度上可以复用，从而使得算法在大型关系数据集上有良好的速度。文章的撰写按以下的方式来组织：第2部分对已有的层次聚类、划分算法进行特征归纳，得出关系数据层次聚类算法应考虑的问题和设计标准。第3部分运用迭代系统的输入输出关系构建关系数据的非对称距离测度。第4部分对算法进行阐述，首先依据第3部分将节点进行结构标识，然后用结构标识筛选出相关网络数据子集并送入DBSCAN算法中。第5部分应用中国复杂网络研究群体的数据验证算法的有效性及带来的新发现。第6部分对算法进行总结及阐述进一步研究的方向。

1 层次聚类算法的设计标准

层次聚类算法按处理过程可分为：全局(划分)和局部(聚集)[11]。全局过程需要知道全局的信息比如决策树，明确知道类的划分，然后依据这个划分来优化和评价聚类过程。网络社团划分方法中，GN算法是全局过程，边的介数中心性是全局指标，要运用到网络中所有节点来计算。局部过程不需要知道全局信息，它是一种启发式方法。根据局部过程对核心节点的认定大致分为3类：簇中所有节点均为核心节点(LPM，Modularity Q)；簇中部分节点为核心节点(DBSCAN,CPM)；一个簇中只有一个核心节点(K-means,K-mediods)，DBSCAN和CPM算法会继续在非核心节点中区分噪声节点，噪声节点不参与簇质量的计算。

按是否为层次分类可分为两类：划分和层次。划分算法中无需考虑簇与簇的合并，故不用衡量簇与簇之间的距离而层次聚类需要考虑，故延伸出最小值、最大值、平均值及平均距离等方法[12]。对于簇与簇的合并，层次算法中会运用加和算子和并算子，加和算子是处理同质簇仅为数量上的增加，在系统组成元素类型上没变化；并算子不仅在数量上有增加而且在系统组成元素上也有增加，例如决策树中如果有风和无风是并运算，那么有风天气时下雨和不下雨只是加合运算。

由此可以得出一个层次凝聚聚类算法应包括核心节点和噪声节点的确定、加和运算和并运算。首先是核心节点和噪声节点的确定，划分算法有确定核心节点的方式而层次聚类则默认簇中的节点就是核心节点，K-means用虚拟节点，K-medoid用具体节点，DBSCAN算法在距离定义的基础上增加了密度要求(NEps(q)≥MinPts)，CPM算法要求核心节点位于k-clique中(k-clique为k个全连接的节点)，节点度数为k，且k个邻居互为邻居[13]。所有算法都要求核心节点能代表群体，在单个节点不具有的群体属性上制定划分标准。

产生出核心节点后就可以确定噪声，式(1)描述了DBSCAN算法的确定方式：

(1)

CPM算法则是根据与核心节点是否存在连边进行判断，这里可以看到划分节点类型时并算子的运用

表1 噪声、边缘及核心节点间的并运算

流动会发生在核心节点与边缘节点及核心节点之间，它们之间有关系也存在有并算子，非对称关系包含对称关系。

表2 不同节点间关系的并运算

层次结构除了有同层运算还需要处理不同层之间的连接。空间层次聚类中相似尺度从高到低体现了空间维度的包含关系，相似尺度从0.8变化到0.4会包含小于0.8和不小于0.8，从0.4到0.2包含小于0.4和不小于0.4，决策树是类别数据的包含。在做层与层之间的并运算时，要求不断添加原有系统中没有的元素并使得某一系统的全局指标单调变化，空间层次是空间距离，决策树是熵。在CPM算法中k-clique中的k不断增大，但这一过程并没有在系统组成元素中添加新的成份，4-clique可以看成是4个3-clique，仅为数量增加；DBSCAN算法要求簇与簇合并时，簇之间的距离要求小于Eps(任意节点间的最小距离)，距离从1Eps扩展到2Eps；决策树在作簇与簇的合并时合并是非关系。

由此得出一个关系凝聚层次聚类算法的设计标准：能够识别核心和噪声节点；定义节点间的连接关系；定义簇之间的关系；所有定义要体现加和及并算子，加和算子仅为同类数量的增加，并算子要求有类别的变化。

2 关系数据的非对称性处理及距离测度

从社会学角度来看，识别不同簇的原因在于不同的簇具有不同的功能，迭代系统中功能用输入输出对表示，簇间的输出输入关系构建了层次，如果一个簇的输出作为另一个簇的输入，那么后一个簇就比前一个簇的层级结构高，由此形成了更高的功能。找出簇是发现层次结构的基础，按照DBSCAN算法的流程，首先需要找出在结构上能代表簇的核心节点，它要求核心节点能够接受簇能接受的所有输入并产生相同的输出。不同于簇，节点不存在非我的空间关系扩展，它的迭代发生在时间维度上——上次和这次。

2.1 处理关系数据的非对称性

对于关系的非对称性，2002年Yadohisa基于Jambu扩展Lance and Williams对称的簇间距离的计算方法提出非对称性关系的距离计算方法[6]。

距离dK(IJ)则在参数上进行变化用以度量非对称性。非对称性主要发生在层间聚类中，高一层次的簇在包含子集时，因为子集的状态存在不同，故高一层的簇与不同子集的距离不同，这时我们关注的是高一层次的簇和子簇之间的距离，不用再考虑同层子簇与子簇之间的距离，除非同一层的某个子簇可以代表高一层的簇。基于空间距离测度的算法，因为节点间的距离与簇间的距离在计算时是可压缩变换所以可以用子簇和子簇距离来表示上一层与子层的距离。关系数据在欧氏距离的测度下是非压缩的[14]，本算法中运用反馈系统中的迭代关系来表示层间的距离。

迭代系统可用函数Xn+1=F(Xn)来表示，比如指数函数xn+1=axn、幂律函数xn+1=xnα。在研究迭代系统的输入输出转换关系时，有两点需要关注一是系统的状态已经变为系统的输出，二是系统的输入也变为系统当前的输出。指数函数会将系统状态变为系统输出但系统的输入仍然是系统最初的输入，由公式xn+1=axn=a*axn-1=a*a*axn-2可看出；幂律函数xn+1=xnα的接受状态和输入都会变为系统的输出。为了更具体地解析输入、状态及输出的关系，我们将迭代了n次的系统(1+x)n表示为1+a1x+a2x2+…+anxn，当下次接收相同的输入(1+x)时，系统会产生新的项an+1xn+1，它是由原系统中anxn项产生(相同的输入x因个体的状态不同产出也不同)。接着是输出是输入的部分，我们将输出拆分为与上一次迭代系统相同的部分1+a1x+a2x2+…+anxn和原来没有的部分an+1xn+1，只有最新产生的部分去接收最新产生的输入才会得到系统原来绝对没有的部分(an+1xn+1接受an+1xn+1一定会让系统元素增加)。具有最高等级结构序列的个体在时间维度上包含了所有群体在空间维度上可接受的输入然后通过接受最新的输入让结构单调递增变化，因此在算法中我们用具有最高等级结构序列的个体来代表群体。我们用表3说明这一事实并给出关系输入输出的例子来更好的理解状态、输入及输出的关系。

表3 状态、输入及输出对应表

迭代系统中可接受的输入与状态有关，通过结合状态及输入可能产生原有系统没有的新特性。

图1 不同输入产生相同输出

依据输入输出对的关系图1中，a(3)、b(3)的结构是不同的，因为它们的输入不同，产生出的新特性不同，a(3)产生出不在社团中的一条连边，b(3)产生出一个社团。随着Ego节点邻居数的不断增加，可以构建一个以邻居数为横轴，输出结构为纵轴的二维图谱，图2。随着结构的变化，Ego节点可接受的输入数增多，相应的输出结构数也增多。算法中只考虑由Ego发出的变化，所以只研究实线箭头不研究虚线箭头，实线箭头中再区分Ego节点是否用到最新的状态去接受最新的输入产生出原来系统不存在的结构。图3中，b(2)比a(2)、b(3)比a(3)的结构等级高，因为b(2)考虑到b(1)有一个邻居，新认识的第二个邻居要认识已有邻居，b(3)考虑到现有邻居都在一个社团中，要求第三个邻居不在现有社团中；而a(2)、a(3)则一直按a(1)的方式在新增邻居，没有用到a(1)的现有状态信息。

图2 Ego节点邻居数与结构变化关系图

图3 结构等级比较

由此可以得到一个单调的关系迭代序列，这里an+1=f(an)n=0,1,2…

图4 Ego节点结构单调变化图谱

2.2 关系功能距离的测度

图4采用的算子是并，对于并运算，H氏距离具有压缩性，所以这里引入功能距离的测度——H氏距离，运用H氏距离来描述系统变化的单调递增性。

图5 H氏距离的定义[13]

图5中，具有包含关系时H(B,A)=0，而不具包含关系时需要用最小的包含B的ε-环来定义，H(A,B)=aε[14]。具体到关系的功能距离，在图4中，因为a1包含a0，故H(a1,a0)=0而H(a0,a1)=1，直接的输入输出关系定义为1，输入的输入则定义为2，依次。H氏距离具有加合性H(a2,a0)=H(a2,a1)+H(a1,a0)=0；H(a0,a2)=H(a0,a1)+H(a1,a2)=2。显然H氏距离是非对称的H(a1,a0)≠H(a0,a1)。序列中用到的H氏距离满足d(f(x),f(y))≤cd(x,y)0≤c<1。定义了H氏距离后，可以将关系网络中的连接分为两类：结构连接、功能连接。结构连接表示节点间有连边存在如合作关系、关注关系、引用关系；功能连接是基于结构连接之上的，依据节点对结构上的距离来定义。

3 关系数据的层次聚类

3.1 算法概念

在传播研究场景下，传播意味着接受传播物，扩散意味着采纳数量的增多，对于核心节点除了能接受传播物外还要求其有扩散意愿和扩散能力。对于一个传播物最想传播它的是当次将其转换为输出的结构，因为这类个体在采纳后获得了收益。算法先在图4的结构谱中确定结构进而按结构选定备选核心节点，接着要求核心节点的邻居中要有足够多的点能接受传播物。首先是同结构和上层的个体，因为它们接受过这样的输入，知道这样输入的作用。接着就是下一层的结构，它们具有接受传播物的结构同时接受后可改变其现有结构。对于下两层及之后的结构，因其不具接受传播物的状态故无法采纳，将不被计入可传播的个体中。按H氏距离理解，上层个体与同层个体因为是包含关系所以H氏距离为0，下一层的个体因为是直接输入关系所以H氏距离为1，下两层及之后的个体H氏大于1。传播中首先要求结构距离必须为1，接着要求功能(H氏)距离小于等于1，这两种距离之间具有包含关系。

定义1节点p的可传播邻居数表示为NEps(P)，其中NEps(P)={q∈D|H(p,q)≤1}。

定义1用于计算可传播邻居数，相较DBSCAN算法，该定义不仅要求结构可达S(p,q)=1而且功能可达H(p,q)≤1。通过规定MinPts可以将节点分为核心节点和非核心节点，算法中核心节点和非核心节点是基于一个传播物定义的，同理簇和噪声也是相对应于一个传播物。我们不能要求簇中的所有节点都是核心节点，有些节点可接受传播物但传播能力不够。对于边缘节点用下面的定义来阐述。

定义2直接传播物可达 在条件Eps和MinPts下，节点p从节点q是直接传播物可达的，如果：

1)p∈NEps(q)

2)|NEps(q)|≥MinPts(核心节点条件)

依定义1，可达邻居里分为3类：上层、同结构及下一层。这里虽全部表现为传播物直接可达，但采纳概率存在差别，因为上层已经采纳过并且已经接收了新的输入，此类输入对其结构的改变意义不大，能接受此输入的目的在于增强未采纳者的信心；对于同结构的虽采纳也不会改变结构，但采纳后对结构的影响感知深切，所以在这里再次采纳的可能性最高同时也愿意推广；对于下一层个体，因为无法知道采纳后带来的益处，所以采纳的概率最低但对于想要传播的人来讲，下一层个体的采纳是最有意义的。就传播概率来说，簇的空间扩展是基于核心节点的，因为核心节点在传播意愿上达成共识使得传播物的传播在核心节点网络上是无阻扩散的，由此自然得出直接传播物可达的规范扩展——传播物可达。

定义3传播物可达 条件Eps和MinPts下，如果存在一条传播链Pl……Pn,Pl=q,Pn=p，其中Pi+l到Pi是直接传播物可达，即节点p是从节点q传播物可达。

因为传播物在核心节点网络上的流动是无阻的，所以在直接传播可达的链上加载更多的核心节点，相当于把连接的核心节点看成是一个节点，由此完成簇的加和运算实现同层簇空间的扩展。

定义4传播物相连 条件Eps和MinPts下，如果存在一个核心节点o，它对节点p和q同时是传播物可达的，那么p和q是传播物相连。

非核心节点与非核心节点是通过关联的核心节点连接的，由此得到簇在边缘节点上的扩展。现在可以定义基于H氏距离的关系层次聚类算法，簇就是对传播物可达最大扩展后得到传播物相连的节点的集合，噪声则是不在所有簇中的节点。

定义5(簇)假设D是所有点的集合。在条件Eps和MinPts条件下，C是D中满足如下条件的子集：

1)∀p,q：如果p∈C,q密度可达pWrt.Eps and MinPts，则q∈c(Maximality)。

2)∀p,q:p,q是密度相连的Wrt.Eps and MinPts(Connectivity)。

定义6(噪声)假设C1……Ck为数据集D在条件Eps和MinPts下的簇i=1,2…k，则不属于任何簇的节点就是噪声。噪声={p∈D|i:p∉Ci}。

同层簇得到划分后，下一步是层次结构的发现，前面介绍过如果一个簇是另一个簇的输入那么后一个簇就在层次上较之前一个高，在构建节点结构描述时构建了一个时间序列，在这个序列中前一个结构是后一个结构的输入，同时，也阐述了用具有最高结构序列的节点来代表簇，所以在构建簇的层次结构时，可以用核心节点来代表簇的结构层次，沿着图4谱序列推进核心节点结构时就是对簇层次结构的一个爬升，这与传统的层次聚类方法一致。

3.2 算法实现

聚类首先是分层，每层首先在备选节点中选出核心节点，然后再通过核心节点之间的连边对核心进行扩展，最后再加上边缘节点形成完整的簇，构建结构谱上的所有层，由此构成关系数据的层次聚类结果。

1)Ego节点的结构标识

以Ego节点按时间序列找到子图，子图如图4所列举由结构最低的开始向上，标识Ego节点的最高结构StrID。因为图序列中的子图为输入输出关系，所以如果Ego节点不属于低一层次的结构，那么肯定不会存在高一层次的结构，在程序中可以递归的调用查询结果。对于数据集节点得到的最高结构的最大值，为层次结构的最大值。

2)同层簇的识别。

标识完所有节点的最高结构后，基于功能和结构距离做社团的识别，采用的算法同DBSCAN算法，细节上有一些差别，阐述如下：

(1)输入中要求加入核心节点结构值(Str)，Eps=1，MinPts=3

(2)根据核心节点结构值得到备选核心节点集Ccan={q∈D|StrID=Str}及相关节点集Neg={p∈D|H(p,q)≤1，q∈Ccan}

(3)根据邻域阈值在备选核心节点中找到核心节点Ccore={q∈Ccan||NEps(q)|≥MinPts}

(4)根据定义3得到最大核心节点集Cmax_core={p∈Cli|S(p,q)=1;q∈Cli;p,q∈Ccore}

(5)再根据定义4得到最大传播物连接集Cconn={s∈Cli|S(s,q)=1;q∈Cli;q∈Ccore}

3)层次的发现

改变核心节点结构值(Str)，再次调用2)，得到对应于结构值(Str)的簇，直到遍历所有结构值。

4 算法应用

数据来自于中国复杂网络协会，我们首先列出从该学会成立(2005)至今所有委员名单及其单位，然后在中国知网找出他们发表的文章，列出他们的合作者及单位，在知网里找出这些合作者发表的文章，为消除重名用单位做另一搜索关键字，共获得15 835位作者、18 205篇文章及36 720个关键词。基于以上数据可以构造一个科研人员合作网，然后基于科研人员合作网的层级结构对层级结构上的关键词扩散特征进行描述，从而找出层次对关键词扩散的影响。在构建人员合作网时，本文仅将第一作者与其他合作者进行连边，因为我们认为第一作者可以把关键字推向其他合作者，该网络为有向网络。

表4 科研人员合作网络的层级特征

NCmax_community为最大社团核心节点数；NCsec_community为次大社团核心节点数；Nmax_community为最大社团节点数

从社团结构统计数据可以看出第二层网络中出现一个极大连接社团，核心节点数为599，社团成员数为2 154占到总人数的84%，如果不对社团进行分层，无法在一个均匀大小社团结构(层次1)的网络中发现有极大连接的社团结构。

接着是在不同层的社团结构发现它对于关键词传播的影响，基于关键词出现频率及出现的时间特征对关键词进行分类：

图6 关键词特征划分

分类标准中跳跃是指关键词出现的年份不连续，不连续的时间大于3年。基于关键词的词频选出出现频率高于20的词共210个，然后在谷歌学术中找到这些词出现的次数。简单的对这210个词在不同层关联的作者数进行统计(关联作者表示作者被该关键词影响到)，210个词中共有162个词在层次2的社团中出现的次数大于等于层次1的次数，占到77%。再按谷歌学术出现的次数找出<100 000的关键词发现这一指标提高到79%。从这一指标我们可以推断出层次2的社团结构对没有大众传播效果词的影响效果更大，这与Watts在2012年发现的在线传播结构存在不同[15]，在复杂网络学术传播中人际传播的作用大于大众媒体。接着找出关键词中有1次以上跳跃的词41个，发现这一指标再次提升到80%。关键词在我们所选的样本中没有年年出现，在一定程度上表示不流行，但在4年后又能在社团中出现表示社会关系对这些词的传播有非常重要的作用。运用层次关系数据聚类算法从实际数据得出的新发现1)分层后的社团结构会呈现异质性，在一个均匀分布社团大小的一层社团结构中在分层后可能会出现不同的社团结构；2)分层的社团结构在传播物的扩散解释上要强于不分层的，本文的数据集中，层次2对于关键词的扩散起到重要作用；3)复杂网络研究学者通过建立互惠关系来实现研究工作的扩展，更加稳定的三角形关系和差异化关系在本次研究中的作用不大。

5 结论

通过对以往聚类算法的归纳我们发现了关系数据不同于空间数据的非对称性特点，就这一特点在距离度量上使得传统的度量方法变得不可压缩，为恢复度量的可压缩性本文借鉴迭代系统的输入输出关系用H氏距离来描述关系距离的非对称性，通过这种非对称的包含关系来完成聚类算法中尺度上卷，最后通过一个实例来描述这一改变的有效性，通过算法的设计我们得到以下结论:

1)对关系数据的社团划分需要区分加和算子和并算子，因为传统算法是基于距离的，加和与并算子是一致的，但在关系数据中并非如此。

2)不同层次的社团结构对不同传播物的扩散会产生不同的影响。

3)空间上的并算子与时间维度上的扩展相对应，籍此我们可以通过时间和空间的对应关系在时间维度上对群体行为做预测。

对于算法的应用，本文仅发现互惠关系的作用但等级更高的稳定三角形关系，差异化关系及双三角形关系的作用没有得到验证，今后可以用更难于传播的传播物来验证这些结构的作用。