刘晓慧 江 峰 杜军威 余东瑾

（青岛科技大学信息科学技术学院 青岛 266061）

1 引言

随着互联网时代的崛起和飞速发展，各种信息和数据正呈指数级增长，在这种数据爆炸式扩张的情况下，却出现一种有价值信息匮乏的现象，从丰富复杂的数据信息中提取出具有实际意义的信息已经成为当代的迫切需求［1］。因此，随着时代的发展，数据挖掘也在迅速发展，并且正在遍及于各个领域。由CNNIC公布的39期中国互联网络发展状况显示，到2017年12月为止，中国互联网用户数量为7.72亿，渗透率上升为55.8%。在以人为本的web3.0平台下，需使用更人性化的方式对互联网用户的兴趣点［2］进行分析，并且利用此兴趣点来为互联网浏览用户实现有针对性的服务。

用户的偏好分析可以由用户的浏览内容得到，以分类、聚类的方式对用户浏览内容进行细致划分，通过挖掘用户搜索行为进一步得到更为具体的搜索内容信息，进而得到用户的细粒度偏好输出。近些年来，越来越多的学者们关注于用户的偏好方面的分析，从用户角度出发的如协调过滤等算法［3］，或关注电子商务领域中的用户的模型构建［4］。从而分析不同用户的偏好特点。然而，目前的用户偏好分析方法仍然有很多不足［5］。首先，现有的大多数算法是挖掘浏览用户的原始属性，因此在用户的细粒度分析部分变得难以实现；另外，在挖掘细粒度偏好时，现有算法的精度和效率不是很理想。

在传统的无向图层次聚类［6］中，首先将无向图所有的边执行排序操作，然后在所有的边中选择最大权重［7］的一条边，最后算法对该边的相邻节点完成合并，并对连接到邻居节点的每一条边重新计算权重。普通聚类算法在执行聚类时一次只能对两个点合并，即便在加速算法中也会由于点冲突会导致每轮合并的节点的数量受到限制，以致算法效率不高，且对多边点［8］的处理也存在问题。此外，传统算法聚类时会使用衰减因子对合并点的邻边权重控制衰减［9］，这就会导致一个多边点经过衰减因子的多次衰减后，边的权重因此严重降低而不再能代表其原有的含义。基于上述分析，本文以互联网app为研究数据来源，介绍无向图层次聚类算法及对其并行优化的算法原理，并通过实验验证算法的有效性。

2 无向图层次聚类算法

2002年Girvan和Newman在PNAS上的一篇文章《Community structure in social and biological net⁃works》，指出复杂网络中普遍存在着聚类特性［10］，此后越来越多的学者开始对复杂网络进行算法探究。在基于优化的复杂网络聚类算法研究过程中，局部搜索算法和谱聚类算法成为最为典型的两个算法。谱聚类算法主要是把每个样本数据视为节点，根据数据之间的相似度对边进行赋权值从而得到无向带权图［11］，由此把聚类转变成对图的划分。近几年来，具有代表性的成果有GBR算法［12］，基于dominant集的点对聚类算法［13］和基于最大θ距离子树的聚类算法［14］等。在无向图层次聚类算法中，更是遵循了谱图原理［15］，即对无向图所有的边排序，通过选择权重最大的边对其相邻节点合并，并对新节点边的权重重新计算，当没有节点可以合并或者满足停止条件时输出聚类结果的层次结构。

在对用户偏好分析中，用户的搜索行为可当作是一个有向图，用户搜索的关键词和点击的内容看作是图的顶点，每一条搜索日志可认为是有向图的一条边。这样形成一个关于关键词到内容的有向图，由于是非连通的图，内容不含有指向任何节点的有向边，由于存在这样的问题导致不能通过有向图对用户行为偏好进行分析挖掘。所以在通过用户的搜索记录进行关键词与内容之间建模时，采用由无向图的方式代替有向图来表达二者之间的映射关系，这样内容也有可指向关键词的边。通过无向图层次聚类对用户搜索日志信息执行聚类，最后可以通过关键词和内容之间的映射关系得到聚类结果，聚合内容的类名可作为关键词［16］，聚合内容即为用户搜索内容。

3 无向图层次聚类并行优化算法POHCUGO

3.1 构建无向图

用户的搜索行为［17］会在每天生成大量的搜索日志，所以在数据挖掘过程前需要对数据进行预处理，删除部分没有用处的日志以避免后续冗余的计算。数据的清理［18］主要有两点：

1）用户在输入关键词时，不可避免会出现单复数现象或拼写错误，首先需要对关键词进行归一化操作处理。对关键词设置一定的阈值，比如拼写错误为小概率发生事件，当关键词发生概率值小于设置的阈值时可以当作是拼写错误过滤掉，另外降低搜索关键词的数量级，通过将一些不易识别的特殊字符统一变更为空格格式，由此把关键词归一化为一种形式。除了关键词之外，内容也需要设定一个阈值对内容也进行筛选，过滤冷门内容。

2）对用户的搜索日志信息按照某种规则进行清理筛选，一般而言浏览历史记录分为显示、点击和下载等多种形式，为提高准确性应保证关键词和内容之间的关联性，对添加到无向图中的关键词与内容要求二者之间能够进行高度匹配，故只有点击以上的强行为才能加入无向图中完成聚类。

根据以上提出的方法对数据进行处理得到关键词与内容的对应关系，并且以此对应关系为基础生成搜索日志无向图，为防止数据膨胀采用关键词到内容的操作次数的对数值作为对应边的权重，如图1所示。

图1 搜索无向图

3.2 节点合并

在传统层次聚类中，从下而上合并类簇，每次找到距离最短的两个节点合并，但这种合并的效率非常低。通常首先对所有的边按权重值进行排序，合并权重值最大也即最近的节点对，此时应注意在合并时主要多对节点之间避免有相连的边，防止在合并时产生冲突问题。如图2所示，假使图中进行聚类的距离最近的节点分别是AB、CD、EC，我们不能对EC进行合并，只能对AB和CD进行合并，由于合并后的AB需再次计算与A、B全部相邻节点的边权重，并且E与A相邻，如果EC节点进行合并则可能导致计算冲突。

图2 无向节点合并

在合并之后会得到一个新节点，新节点相邻的边权重需要进行重新计算，此时通常需要对边的权重按照一定值进行衰减，例如AB进行合并时，新AB节点为位于A、B之间的点，这意味着AB会包括A和B的相关数据信息，也使得E与AB的权重值要小于E与A的权重值，因此算法需采用一个衰减因子将合并后的节点到相邻节点的边权重执行衰减。

3.3 并行化加速

一般来说热门关键词会对应较多的热门内容，如图3所示。经常会出现很热的内容与关键词进行多次合并［19］，由于衰减因子［20］的影响，在若干轮迭代后，关键词长尾的边权重值会因为衰减而变得很小，从而失去可比性。

图3 高热关键词节点

对于这种情况，提出一种并行［21］合并［22］的解决方案。如图4所示，把含信息量很大的关键词节点划分成为多个对应的关键词子节点，并且把原来相连的边按照一定的权重分别赋值于这多个子节点，此处的拆分并非逻辑上的，如图4中所示的K2节点依旧是之前唯一节点，只是将一个K2节点在物理层面上分为多个子节点，K2通过各个子节点连接到C1、C2、C3、C4，由此其中一个 K2与 C1、C2点连接，另外一个K2与C3、C4连接，将节点拆分不仅能够并行的方式合并这些点，而且还能够优化边权重的衰减，K2可以在一轮聚合中同时与C1和C3进行合并，因此算法的收敛速度得到快速提升。

图4 高热节点并行优化

我们一般会采用迭代次数作为聚类的停止条件，为对合并层数进行有效控制我们增加另外两个停止条件：首先限制边的衰减次数，删除被衰减n次的边；其次设置阈值，当一条边的权重小于该阈值则看作是无意义的，去除小于该阈值的边。通过整理后会得到同时包含内容和关键词的集群聚类，选择出现频率最大的关键词作为类名。

3.4 POHCUGO算法

POHCUGO算法如下：

4 POHCUGO在用户偏好分析中的应用

POHCUGO算法以互联网用户的搜索行为［23］为出发点，通过对用户的搜索行为进行挖掘，使用搜索关键词作为类名，将用户感觉是一致的信息聚合到一个类中。本文后续的实验将以某网站的真实app作为实例，把app的分类标签转换为用户关于标签的偏好。用户对于app的行为分为三种：浏览、搜索和下载。用户搜索的关键词能够详细地代表其搜索目的，即可以认为是用户关于搜索关键词的偏好，这种偏好可以由用户对app的操作行为转换得到。即互联网用户对于关键词的偏好分可由以下公式所得：

由公式可以清楚地看出偏好分数通过用户的搜索、浏览和下载行为获得，因为用户对app的偏好与这三种操作行为密切相关，并且我们可以得到下载行为影响最强、其次是搜索、浏览最弱。用户的主动意图可以由搜索关键词很好的表示，这种比标签更为细致地搜索关键词特征使得内容展现出更细化的表示［24］，也因此更利于对用户行为的偏好进行分析挖掘，进而能够更好地针对每位用户的需求提供符合个人偏好的服务。并且，根据挖掘用户的行为可以为其展示内容的聚类，此外同时融合用户历史的搜索行为进行分析，不仅能够得到用户对内容的偏好，还可转换成对于搜索关键词以及用户对于关键词下其他搜索内容的偏好。

5 实验分析

5.1 实验数据及实验设置

为验证本文提出的POHCUGO算法的有效性，本文针对互联网app聚类进行了多次实验。本文的实验数据来自于某网站的真实app浏览日志数据信息，主要包含app的搜索、浏览、点击和下载等相关数据，对于本文算法，有效的试验数据是app的搜索、点击、下载相关信息，试验数据的具体如表1所列。

表1 app搜索日志

原始数据由用户最近三个月的点击信息、下载日志组成，且以日志的操作类型为标准对数据进行筛选清理，只采用用户关于app的点击、下载日志的数据信息。通过以下几点对实验结果进行验证：

1）测评聚合到一起的app在hot中的覆盖率。2）判断聚类所得到的搜索关键词与类内app是不是为同一app为原则计算算法的准确率。

3）在准确率和效率方面对传统方法、普通多点合并加速（HCUGO）算法以及本文研究的POHCU⁃GO算法进行比较，对本文算法的有效性进行证明。

由于没有很好的方式来评估标记的精准程度，故在本文通过人工盲评的形式评估该标签标记算法的准确程度。本文进行了三次实验，均采用同一环境，通过对每轮算法的平均迭代时间和算法的迭代收敛轮数比较以完成POHCUGO算法的证明，其中实验数据量、环境及参数配置如下：

1）整理实验数据，最终计算是无向图的节点数量是10w，其中关键词节点数量是6w，app节点数量是4w，边数量是240w。

2）算法是通过Graph分布式框架完成验证的，因此本文进行实验的3种算法的提交参数均如下所示：worker数量30、每个worker内存10G。本文对系统资源进行限制进而实现算法环境的统一。

3）把衰减因子的值均设置为0.96，将最小合并边的权重设置为8。（参数信息由数据分析得到，取决于数据）

5.2 实验结果

根据三次实验结果进行分析，总结之后得到如图5所示的算法的hot覆盖率对比信息。

图5 算法覆盖率

对图5进行分析可得出传统算法与HCUGO算法在覆盖率上相差无几，由于多变点问题使得二者对hot覆盖率相对比较低。举例说明，对于每日下载次数很多的twitter来说，它是特别火热的社交app，由此也会带动其相关的twitter tools的app的下载次数，然而与twitter相比，这类tools下载热度相对较低。即是在多边点无向图中权重中长尾的边在全部边中属于权重比较大的，但是这样的边会因为频繁衰减不断降低其所附带的数据信息，当其不再有意义时不能被聚类。因此导致传统算法和HCUGO算法在hot的覆盖率相对比较低。而PO⁃HCUGO在分裂节点中避免了由于多边点所带来的消极影响。由实验结果可以很容易看出，POHCU⁃GO通过节点分裂使其在hot的覆盖率方面比其他两种算法高。

其次，对传统算法、HCUGO算法和POHCUGO算法的准确率方面进行分析比较。在实验结果中分别随机选取100个分类，并通过人工盲评方法评估算法的准确性。评估结果如图6所示，通过比较发现传统算法［25］的精度与HCUGO算法［26］的准确率分别为83%和82%，本文所提的POHCUGO算法以91%的准确率显然高于另外两种算法。对此结果进行研究，由于节点的分裂并行降低了边权重的衰减轮数，也因此减低了边的信息耗损率。通过对本次的实验结果进行分析可得出本文研究的PO⁃HCUGO算法在准确率上要优于HCUGO算法和传统算法。

图6 算法准确率

最后，根据比较3次实验结果的平均迭代时间、算法时间和迭代收敛轮数，分析算法的效率，三种算法消耗时间如表2所列。

表2 算法效率

对表2进行分析可得出，算法的平均迭代时间大致一样，由表格得到大部分时间花费于算法迭代收敛轮数上，对于传统算法而言，在每轮迭代时只对两个节点进行合并；HCUGO算法在每轮迭代时只能对多对不相邻的节点进行合并；而POHCUGO算法由于并行可以在每次合并多个节点，因此PO⁃HCUGO算法与其他两种算法相比所用时间更少。通过实验结果可得到在算法效率上POHCUGO算法远高于HCUGO算法。

通过对传统算法、HCUGO算法和本文提出的POHCUGO算法在准确率、覆盖率、效率上进行了实验并对试验结果进行分析比较，可以明显得到本文所提出的POHCUGO算法更优于传统方法和HCUGO算法，从而也证明了POHCUGO算法的有效性。

6 结语

聚类是当前数据挖掘范畴中不可分割的重要组成成分，并且已经在多个领域［27］有实际成效。本文首先讲述了无向图层次聚类并进而介绍其优化算法POHCUGO算法。POHCUGO算法对高热节执行分裂，降低了由于衰减因子引起的消极作用，并且，算法通过节点并行的方法实现加速并优化图聚类的效果。最后通过用户对于关键词的偏好进行聚类来表达其对搜索内容的偏好，进而完成用户关于内容的偏好分析。通过将传统算法、HCUGO算法和本文研究的POHCUGO算法的实验结果进行比较，验证了本文算法的有效性。

然而，在对用户搜索历史进行聚类时只是通过用户的历史搜索信息作为原始数据进行挖掘用户偏好，并未考虑时间维度所带来的影响，因此在下一步研究时考虑加入时间维度的影响，通过在时间维度上研究用户搜索行为的偏好进行挖掘探索在时序上关于用户搜索内容的规律。