0 概述

由于生物遗传和变异，自然界中存在大量性状相同的物种，其在进化上或个体发育上因具有共同来源呈现出的相似性称为同源性。这种同源性被广泛应用于医疗健康、生物制药和遗传研究等诸多领域^[1-2]，也为虚拟空间中在线用户行为相似性研究提供了新思路。在虚拟空间中，不同用户群体的行为特征通常存在不同程度的差异性^[3-4]和相似性^[5-6]。文献[7]基于用户主题感知和行为相似性分析动态用户的相关性，指出同种社区类型的用户具有强相关性，不同社区类型的用户具有弱相关性。文献[8]对16个国家微博用户行为的差异性和相似性进行研究，发现在人口少且凝聚力强的国家，用户更关注微博的社会功能，而在人口较多的国家，用户仅将微博作为新闻传播平台。

在证实虚拟空间中用户行为特征具有差异性和相似性的基础上，研究人员结合在线用户的自身特征属性给出部分应用场景^[9-11]。文献[12]提出一种基于同义词组的用户行为汇聚方法，利用汇聚结果对用户进行性别预测，证明不同性别群体的兴趣具有差异性，该方法能根据用户性别进行有效的个性化系统推荐。文献[13]通过调查欧洲60 000多名工人的收入、教育程度、职业类型、自治水平、时间压力和社会互动6个维度的信息，提出双变量有序概率计量经济模型以衡量互联网对工人工作满意度的影响，该研究对提高企业管理水平具有重要意义。

用户点击路径反映出用户在一段时间内点击的页面和驻留时间^[14]，分析用户的点击行为是研究用户行为相似性的有效方法^[15]。目前关于用户行为相似性缺乏统一量化标准，对虚拟空间中在线同源用户(根据同源理论，即点击序列相似度超过30%的在线用户)是否存在也未有验证。此外，关于不同特征属性对在线同源用户行为相似性影响程度的研究也较少。因此，本文提出一种虚拟空间中在线同源用户识别算法。从在线用户行为数据集中提取点击流数据，采用序列对齐方法处理点击流数据以度量在线用户的行为相似性。同时从数据集的人口统计信息中获取在线用户不同维度的特征属性，研究各种特征属性对在线同源用户行为相似性的影响程度。

1 数据描述

用户的在线行为主要通过点击流数据来体现。本文采用中国互联网信息中心(China Internet Network Information Center，CNNIC)提供的在线行为日志作为数据集(以下称为CNNIC数据集)进行研究，其中数据要素包含每个用户的点击路径以及每个路径对应的点击时刻，点击时刻采用标准时间格式记录。CNNIC数据集中某用户的部分点击流数据如表 1所示。

本文主要研究在线同源用户的识别及特征属性对其行为的影响程度，因此用户特征属性提取是关键。利用上述数据集中的人口统计信息提取用户的年龄、社会阶层、教育程度、性别、户籍和收入水平6个维度的特征属性，部分用户的人口统计信息如表 2所示。对每个特征属性进一步分类，结果如表 3所示。

2 研究方法

本文提出基于序列对齐的在线同源用户识别(Sequence Alignment-based Online Homologous User Recognition，SA-OHUR)算法，其主要包括以下步骤：1)处理点击行为数据；2)基于序列对齐思想计算在线用户的行为相似度，并对其以相似度矩阵形式进行量化；3)根据行为相似度矩阵对用户进行聚类验证并识别在线同源用户。此外，采用基于特征属性的方法计算聚类结果的熵值和纯度，并由此分析在线用户特征属性对其行为的影响程度。

2.1 在线同源用户识别算法

在线用户行为由一系列点击路径及其对应的点击时刻构成，若将每个点击路径看作用户点击序列中一个字符串，则在点击流数据中点击路径和对应路径花费的时间可反映用户的点击行为，其用包含时间的字符串序列表示。例如，表 1中点击流数据对应的该用户点击序列S_F={(['explorer.exe']，08-01 20：29：57)，(['AliIM.exe']，08-01 20：29：59)，(['SohuNews.exe']，08-01 20：30：05，)，(['360SE.exe']，08-01 20：30：23)，(['AliIM.exe']，08-01 20：30：27)，(['360SE.exe']，08-01 20：30：31)，(['AliIM.exe']，08-01 20：30：59)}。用户行为相似度计算问题可转换为编辑距离的问题。

2.1.1 序列对齐方法

序列对齐也称编辑距离，主要通过对齐的方法来度量两个序列的相似性^[16]，其核心思想是利用一个序列转换为另一个序列所花费的最小代价衡量两个序列的相似性。序列Q和序列C之间的编辑距离和相似度分别定义为：

$ {d}_{\mathrm{S}\mathrm{A}\mathrm{M}(Q, C)}=({\omega }_{d}D+{\omega }_{i}I)+\mu R $

(1)

$ {S}_{\mathrm{S}\mathrm{A}\mathrm{M}(Q, C)}=1-\frac{{\mu }_{\mathrm{S}\mathrm{A}\mathrm{M}(Q, C)}}{\left|Q\right|+\left|C\right|} $

(2)

其中，d_SAM(Q，C)为序列Q和序列C之间的编辑距离，S_SAM(Q，C)为序列Q和序列C之间的相似度，D、I和R分别为转换过程中删除、插入和重排的次数，|Q|和|C|分别为序列Q和序列C的长度，$ \omega $_d、$ \omega $_i和$ \mu $分别为序列Q转换为序列C过程中删除、插入和重排操作的代价，且均为用户给定的正常数。

2.1.2 数据预处理

本文基于序列对齐思想处理持续点击流数据，具体步骤如下：

1) 计算在线用户在每个点击路径的持续时间，当前点击路径的持续时间即为当前点击时刻与前一个点击时刻之差，若某一个点击路径的持续时间超过30 min，则默认为用户已经下线，并将该点击路径及其持续时间从用户点击序列中去除，即会话时间间隔阈值定义为30 min^[17]，处理后的持续点击流数据如表 4所示。

2) 记录用户一个月内的点击路径并计算其对应的持续时间，处理后的累计点击流数据如表 5所示，用户累计点击序列S_U={(['explorer.exe']，2)，(['AliIM.exe']，24)，(['Sohu News.exe']，18)，(['360SE.exe']，32)}。

2.1.3 在线用户行为相似度算法

本文提出的SA-OHUR算法是利用基于序列对齐的在线用户行为相似度算法获得用户间相似度。由于该算法所用累计点击序列的时间为累计时间，因此不考虑点击路径的先后顺序，即转换过程中重排操作代价为0。同时，若两个用户点击路径相同但对应路径的累计时间不同，则可能造成点击行为的差异，因此，增加两个在线用户点击的相同路径所对应累计时间差值的绝对值作为补偿操作。设在线用户U_i的点击序列S$ {}_{{U}_{i}} $={(a_i1，T_i1)，(a_i2，T_i2)，…，(a_in，T_in)}，在线用户U_j的点击序列$ {S}_{{U}_{j}} $={(a_j1，T_j1)，(a_j2，T_j2)，…，(a_jm，T_jm)}。其中，(a_i1，a_i2，…，a_in)与(a_j1，a_j2，…，a_jm)分别为在线用户U_i和U_j的点击路径集A_i和A_j。(T_i1，T_i2，…，T_in)与(T_j1，T_j2，…，T_jm)分别为在线用户U_i和U_j的累计时间集T_i和T_j。在线用户U_i和U_j基于序列对齐的编辑距离定义为：

$ \begin{array}{l}{d}_{\mathrm{S}\mathrm{A}\mathrm{M}\left({U}_{i}, {U}_{j}\right)}=\sum \limits_{p=1}^{n}\left({T}_{ip}\times \mathrm{s}\mathrm{g}\mathrm{n}\left({a}_{ip}\notin {A}_{j}\right)\right)+\\ {{{{{{{{{{{}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}\mathrm{ }{\mathrm{ }}^{{}^{{}^{}}}\sum \limits_{q=1}^{m}\left({T}_{jq}\times \mathrm{s}\mathrm{g}\mathrm{n}\left({a}_{jq}\notin {A}_{i}\right)\right)+\\ {{{{{{{{{{{{}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}}^{{}^{{}^{}}}\sum \limits_{p=1, q=1}^{n, m}\left(|{T}_{ip}-\mathrm{ }{T}_{jq}|\times \mathrm{s}\mathrm{g}\mathrm{n}\left({a}_{ip}={a}_{jq}\right)\right)\end{array} $

(3)

其中，删除和插入的代价分别为删除和插入路径所对应的累计时间，$ |{T}_{ip}-{T}_{jq}| $为补偿操作的代价。

两个用户基于序列对齐的行为相似度计算公式为：

$ {S}_{\mathrm{S}\mathrm{A}\mathrm{M}\left({U}_{i}, {U}_{j}\right)}=1-\frac{{d}_{S\mathrm{A}\mathrm{M}\left({U}_{i}, {U}_{j}\right)}}{\sum \limits_{p=1}^{n}{T}_{ip}+\sum \limits_{q=1}^{m}{T}_{jq}} $

(4)

其中，当用户点击序列(点击路径及其对应的累计时间)完全相同时，用户的相似度为1，当点击序列完全不同时，相似度为0。在线用户U_i和U_j的行为相似度计算如算法1所示。

算法1   基于序列对齐的用户行为相似度算法

输入  n个用户的累计点击序列$ {S}_{{\boldsymbol{U}}_{1}} $，$ {S}_{{\boldsymbol{U}}_{2}} $，…，$ {S}_{{\boldsymbol{U}}_{n}} $

输出  在线用户点击行为相似度矩阵A_n×n

/*循环遍历n个用户的是点击序列，计算每一个用户与其他用户的行为相似度*/

1.i=0，j=0，T=0，S={}

2.For i in range(0，n)：

3.For j in range(i，n)：

4.If $ {\mathrm{a}}_{\mathrm{i}\mathrm{p}} $ not in $ {\mathrm{A}}_{\mathrm{j}} $：

5.T=T+$ {\mathrm{T}}_{\mathrm{i}\mathrm{p}} $

6.End If

7.If $ {\mathrm{a}}_{\mathrm{j}\mathrm{q}} $ not in $ {\mathrm{A}}_{\mathrm{i}} $：

8.T=T+$ {\mathrm{T}}_{\mathrm{j}\mathrm{q}} $

9.End If

10.If $ {\mathrm{a}}_{\mathrm{i}\mathrm{p}}={\mathrm{a}}_{\mathrm{j}\mathrm{q}} $：

11.T=T+$ |{\mathrm{T}}_{\mathrm{i}\mathrm{p}}-{\mathrm{T}}_{\mathrm{j}\mathrm{q}}| $

12.End If

13.$ {\mathrm{d}}_{\mathrm{S}\mathrm{A}\mathrm{M}({\mathrm{U}}_{\mathrm{i}}, {\mathrm{U}}_{\mathrm{i}})}=\mathrm{T} $

14.$ {\mathrm{S}}_{\mathrm{S}\mathrm{A}\mathrm{M}({\mathrm{U}}_{\mathrm{i}}, {\mathrm{U}}_{\mathrm{i}})}=1-\frac{{\mathrm{d}}_{\mathrm{S}\mathrm{A}\mathrm{M}({\mathrm{U}}_{\mathrm{i}}, {\mathrm{U}}_{\mathrm{i}})}}{\sum \limits_{\mathrm{p}=1}^{\mathrm{n}}{\mathrm{T}}_{\mathrm{i}\mathrm{p}}+\sum \limits_{\mathrm{q}=1}^{\mathrm{m}}{\mathrm{T}}_{\mathrm{j}\mathrm{q}}} $

15.S.append($ {\mathrm{S}}_{\mathrm{S}\mathrm{A}\mathrm{M}({\mathrm{U}}_{\mathrm{i}}, {\mathrm{U}}_{\mathrm{i}})} $)

16.End For

17.End For

18.Return S

/*将相似度转换成n×n的相似度矩阵，矩阵中第i行第j列表示第i个用户与第j个用户的行为相似度*/

19.SAM_matrix=numpy.zeros(n，len(S))

20.For x in S：

21.A_n×n[：，x]=1

22.End For

23.Return A_n×n

上述算法在用户行为相似度计算过程中，主要利用用户累计点击流数据，且无需考虑点击顺序。在处理点击流数据时，将点击序列按照点击路径进行扫描，可得到用户之间的行为相似度。由于在数据处理阶段已去除冗余点击路径，因此与传统的序列对齐算法相比，算法1复杂度大幅降低。

2.1.4 基于行为相似度矩阵的层次聚类

SA-OHUR算法最后一步是根据相似度矩阵对在线用户进行聚类，以验证在线同源用户的存在。为更直观地区分出用户在线行为并识别同源用户群，该算法采用基于行为相似度矩阵的层次聚类。由于传统层次聚类HC算法每进行一次簇间合并均需更新相似度矩阵，造成算法步骤重复，因此为避免该问题，SA-OHUR算法将相似度矩阵中在线用户之间相似度值和用户编号采用数组的形式按照相似度值进行降序排列，根据相似度值在数组中的位置从大到小合并用户，即引入优先级队列。

SA-OHUR算法将在线用户按照点击行为划分为不同类别，具体流程如下：1)初始化每个用户作为单独的簇；2)根据相似度矩阵将相似度值及其对应的用户存入已定义的数组并按照降序排列；3)合并数组中第1个相似度值，将最大相似度值对应的两个用户作为一个簇；4)从第二轮合并开始，若相似度值对应的两个用户均未合并到某个簇中，则将这两个用户合并为一个簇；若其中一个用户已合并到另外一个簇中，则将另一个用户也合并到该簇中；若两个用户分别合并到不同簇中，则将这两个用户所在的两个簇合并；5)按顺序取数组N的相似度值，且在每轮合并时簇的个数减少1；6)重复步骤4和步骤5直到生成K个簇。

给定在线用户集U={u₁，u₂，…，u_n}，将其根据点击行为相似性划分K个类C₁，C₂，…，C_K，要求每个类别不能为空且类与类之间用户不相同，主要步骤如算法2所示。

算法2   基于行为相似度矩阵的层次聚类算法

输入    在线用户行为相似度矩阵$ {\boldsymbol{A}}_{n\times n} $

输出   聚类结果C₁，C₂，…，C_K

1.For $ {\mathrm{S}}_{\mathrm{S}\mathrm{A}\mathrm{M}({\mathrm{U}}_{\mathrm{i}}, {\mathrm{U}}_{\mathrm{i}})} $ in $ {\mathrm{A}}_{\mathrm{n}\times \mathrm{n}} $：`

2.N.append(i，j，$ {\mathrm{S}}_{\mathrm{S}\mathrm{A}\mathrm{M}({\mathrm{U}}_{\mathrm{i}}, {\mathrm{U}}_{\mathrm{i}})} $)/其中元素分别为行号，列号，相似度值/

3.End For

4.Max(N=(a，b，$ {\mathrm{S}}_{\mathrm{S}\mathrm{A}\mathrm{M}({\mathrm{U}}_{\mathrm{a}}, {\mathrm{U}}_{\mathrm{b}})} $))/$ {\mathrm{S}}_{\mathrm{S}\mathrm{A}\mathrm{M}({\mathrm{U}}_{\mathrm{a}}, {\mathrm{U}}_{\mathrm{b}})} $为最大相似度值/

5.C_ab=(U_a，U_b)/将相似度值最大的两个用户a，b合并到一个簇中/

/*基于行为相似度矩阵的层次聚类算法流程将用户进行聚类*/

6.count=n

7.while(count > K)：

8.For item in N：

9.if U_p in C_p and U_q in C_q：

10.C_pq=(C_p，C_q)

11.count= count-1

12.if U_p not in C_p and U_q in C_q

13.C_pq=(U_p，C_q)

14.count= count-1

15.if Up in C_p and U_q not in C_q

16.C_pq=(Cp，Uq)

17.count= count-1

18.if U_p not in C_p and U_q not in C_q

19.C_pq=(U_p，U_q)

20.count= count-1

21.End For

22.Return C₁，C₂，…，C_K

在算法2中，先对n个用户的n×(n－1)/2个相似度进行快速降序排列，排序的时间复杂度为O(n²×lb n)^[18]，再对n个用户根据相似度进行聚类，该过程中聚类循环的时间复杂度为O(n)。因此，相较传统层次聚类的时间复杂度O(n³)，算法2的时间复杂度降低为O(n²×lb n)，算法运行效率更高。

SA-OHUR算法的关键是计算簇间相似度和簇内相似度，进而识别出在线同源用户群。由于每个簇即为在线用户集合，因此本文采用簇内在线用户与另一个簇内在线用户的平均相似度来表示。例如，给定聚类簇C_i和C_j，则两个簇间的相似度定义为：

$ {S}_{\mathrm{a}\mathrm{v}\mathrm{g}}\left({C}_{i}, {C}_{j}\right)=\frac{1}{\left|{C}_{i}\right|\cdot \left|{C}_{j}\right|}\sum \limits_{x\in {C}_{i}}\sum \limits_{z\in {C}_{j}}{S}_{\mathrm{S}\mathrm{A}\mathrm{M}\left(x, z\right)} $

(5)

其中，$ {S}_{\mathrm{a}\mathrm{v}\mathrm{g}}\left({C}_{i}, {C}_{j}\right) $为聚类簇C_i和C_j的相似度，x为属于聚类簇C_i的用户，z为属于聚类簇C_j的用户，$ {S}_{\mathrm{S}\mathrm{A}\mathrm{M}\left(x, z\right)} $为在线用户x和z的行为相似度，|C_i|和|C_j|分别为聚类簇C_i和C_j的在线用户个数。

2.2 基于特征属性的熵值和纯度算法

采用SA-OHUR算法对在线用户进行聚类时，为更好地将在线用户特征属性与其行为相似性进行结合，可用熵值和纯度来衡量用户特征属性对其行为相似性的影响程度。熵值和纯度可用来衡量某个指标的混乱度^[19]，本文分别计算基于表 3中6个不同特征属性下点击行为相似度聚类结果的熵值和纯度，由此判定特征属性对用户行为相似性的影响程度。

给定n个在线用户，根据在线用户行为相似度将其分为K个簇，其中每个簇分别包含n₁，n₂，…，n_K个用户。假设某个特征属性有M个类别，如教育程度分为初等教育水平、中等教育水平、高等教育水平3个类别，则在该特征属性下聚类簇i的熵值计算公式为：

$ {e}_{i}=-\sum \limits_{j=1}^{M}\frac{{n}_{ij}}{{n}_{i}}\mathrm{l}{\mathrm{b}}^{}\frac{{n}_{ij}}{{n}_{i}} $

(6)

在该特征属性下聚类的整体熵值计算公式为：

$ e=\sum \limits_{i=1}^{K}\frac{{n}_{i}}{n}{e}_{i} $

(7)

在该特征属性下聚类簇i的纯度计算公式为：

$ {p}_{i}=\mathrm{m}\mathrm{a}\mathrm{x}\left(\frac{{n}_{ij}}{{n}_{i}}\right) $

(8)

在该特征属性下聚类的整体纯度计算公式为：

$ p=\sum \limits_{i=1}^{K}\frac{{n}_{i}}{n}{e}_{i} $

(9)

其中，n_ij表示聚类簇i中用户属于类别j的个数，n_i为聚类簇i中所有用户个数，n为参加聚类的所有用户个数。基于特征属性的熵值和纯度计算如算法3所示。

算法3   基于特征属性的熵值和纯度算法

输入    某一个特征属性的M个类别包含用户集$ {m}_{1} $，$ {m}_{2} $，…，$ {m}_{M} $；K个聚类结果簇$ {C}_{1} $，$ {C}_{2} $，…，$ {C}_{K} $

输出    该特征属性下的熵值e和纯度p

/*统计聚类簇分属每个类别的用户数*/

1.For i range(0，K)：

2.For j range(0，M)：

3.For a range(0，n)：

4.If $ {\mathrm{U}}_{\mathrm{a}} $ in $ {\mathrm{C}}_{\mathrm{i}} $ and $ {\mathrm{m}}_{\mathrm{j}} $：

5.$ {\mathrm{n}}_{\mathrm{i}\mathrm{j}} $=$ {\mathrm{n}}_{\mathrm{i}\mathrm{j}}+1 $

6.If $ {\mathrm{U}}_{\mathrm{a}} $ in $ {\mathrm{C}}_{\mathrm{i}} $：

7.$ {\mathrm{n}}_{\mathrm{i}}={\mathrm{n}}_{\mathrm{i}}+1 $

8.End For

/*计算聚类结果每个簇的熵值和纯度*/

9.For i range(0，K)：

10.For j range(0，M)：

11.$ {\mathrm{e}}_{\mathrm{i}}={\mathrm{e}}_{\mathrm{i}}+\frac{{\mathrm{n}}_{\mathrm{i}\mathrm{j}}}{{\mathrm{n}}_{\mathrm{i}}}\mathrm{l}\mathrm{b}\frac{{\mathrm{n}}_{\mathrm{i}\mathrm{j}}}{{\mathrm{n}}_{\mathrm{i}}} $

12.If $ {\mathrm{p}}_{\mathrm{i}} $ < $ \frac{{\mathrm{n}}_{\mathrm{i}\mathrm{j}}}{{\mathrm{n}}_{\mathrm{i}}} $：

13.$ {\mathrm{p}}_{\mathrm{i}} $=$ \frac{{\mathrm{n}}_{\mathrm{i}\mathrm{j}}}{{\mathrm{n}}_{\mathrm{i}}} $

14.Return $ {\mathrm{e}}_{\mathrm{i}} $，$ {\mathrm{p}}_{\mathrm{i}} $

15.End For

/*计算聚类结果整体的熵值和纯度*/

16.For i range(0，K)：

17.e=e+$ \frac{{\mathrm{n}}_{\mathrm{i}}}{\mathrm{n}}{\mathrm{e}}_{\mathrm{i}} $

18.p=p+$ \frac{{\mathrm{n}}_{\mathrm{i}}}{\mathrm{n}}{\mathrm{e}}_{\mathrm{i}} $

19.Return e，p

算法3是通过聚类结果的熵值和纯度衡量特征属性对行为相似性的影响程度。若基于某一个特征属性计算得到的聚类结果熵值越小，混乱程度越低，该特征属性下类别分散程度越小，则基于该属性聚类结果的综合评价越好，即特征属性对同源用户行为相似性的影响程度越大。而纯度相反，若基于某一个特征属性计算得到的聚类结果纯度越大，混乱程度越低，该特征属性下的类别分散程度就越小，则基于该属性聚类结果的综合评价越好，即特征属性对用户行为相似性的影响程度越大。

3 实验与结果分析

本文抽取848名用户一个月内约1.2亿条点击流数据进行分析，实验采用Windows 8操作系统和8 GB运行内存并通过Python3.6实现。

3.1 结果分析

按照SA-OHUR算法流程，本文将点击流数据进行处理后得到在线用户累计点击行为序列。例如，在线用户U_a的累计点击行为序列S$ {}_{{U}_{\mathrm{a}}} $={(['explorer.exe']，2)，(['AliIM.exe']，24)，(['SohuNews.exe']，18)，(['360SE.exe']，32)}，在线用户U_b的累计点击行为序列S$ {}_{{U}_{\mathrm{b}}} $={(['explorer.exe']，2)，(['AliIM.exe']，34)，(['xmp.exe']，5)}，并由式(4)计算得到用户U_a与U_b的相似度如下：

$ {S}_{\left({U}_{\mathrm{a}}, {U}_{\mathrm{b}}\right)}=1-\frac{18+32+5+\left|24-34\right|}{2+24+18+32+2+34+5}=0.44 $

(10)

采用算法1得到848名用户间相似度并将结果以相似度矩阵A输出，表达式如下：

$ \boldsymbol{A}=\left[\begin{array}{l}\begin{array}{c}1.00\\ 0.63\\ 0.01\end{array}\begin{array}{c}0.63\\ 1.00\\ 0.28\end{array}\begin{array}{c}0.01\\ 0.28\\ 1.00\end{array}\begin{array}{c}\cdots \\ \cdots \\ \cdots \end{array}\begin{array}{c}0.58\\ 0.05\\ 0.86\end{array}\begin{array}{c}0.65\\ 0.38\\ 0.31\end{array}\\ \begin{array}{c}⋮\\ 0.58\\ 0.65\end{array}\begin{array}{c}⋮\\ 0.05\\ 0.38\end{array}\begin{array}{c}⋮\\ 0.86\\ 0.31\end{array}\begin{array}{c}\\ \cdots \\ \cdots \end{array}\begin{array}{c}⋮\\ 1.00\\ 0.22\end{array}\begin{array}{c}⋮\\ 0.22\\ 1.00\end{array}\end{array}\right] $

(11)

相似度矩阵A是一个848×848对称矩阵，其中第i行第j列的数值表示第i个在线用户和第j个在线用户的点击行为相似度，对角线元素表示每个在线用户与自身行为的相似度，相似度值均为1，在该矩阵中相似度取值分布范围为0~1。

由相似度矩阵A得到在线用户不同相似度区间数量统计如图 1所示。其中，x轴为相似度值，y轴为投影在该区间相似度值的个数。图 1中相似度值主要分布在(0.00，0.60)区间内，表明虚拟空间中存在行为相似度超过30%的在线同源用户，SA-OHUR算法能有效验证在线同源用户的存在。

为进一步识别在线同源用户群，采用SA-OHUR算法基于相似度矩阵A和算法2对用户进行聚类。不同聚类簇个数下的簇间相似度值和簇内相似度值的对比如图 2所示。可以看出，随着聚类簇个数的增加，簇内相似度值逐步上升并最终稳定在(0.4，0.5)区间，而簇间相似度值虽然呈现上升趋势但始终低于簇内相似度值，且最大值不超过0.3。这表明属于同一个簇的在线用户即为在线同源用户且其点击行为相似度超过40%，而属于不同簇的在线用户即为在线非同源用户，采用SA-OHUR算法能有效识别在线同源用户群。识别出在线同源用户后，可根据表 3中用户特征属性类别，采用SA-OHUR算法将用户分为2个簇、3个簇和4个簇，并利用算法3研究特征属性对在线同源用户行为相似性的影响程度。不同特征属性下各个簇及聚类结果整体的熵值和纯度如图 3所示。

由图 3可以看出，基于性别、户籍和教育程度的聚类结果整体熵值分别为0.541、0.754和0.622，其结果低于基于收入水平、社会阶层和年龄的聚类结果(熵值分别为1.689、1.259和1.144)，表明基于性别、户籍和教育程度的聚类结果分散程度低且综合评价较好，即该3类特征属性对在线同源用户行为相似性影响较大。基于性别、户籍和教育程度的聚类结果整体纯度分别为0.890、0.872和0.878，其结果高于基于收入水平、社会阶层和年龄的聚类结果(纯度分别为0.517、0.740和0.732)，表明基于性别、户籍和教育程度的聚类结果纯度较高且混乱度较低，这3类特征属性对在线同源用户行为相似性影响更大。综上可知，性别、户籍和教育程度3种特征属性对在线同源用户行为相似性的影响程度大于收入水平、社会阶层和年龄的影响程度，其中影响最高的特征属性为性别，影响最低的特征属性为收入水平。

3.2 对比实验

为验证SA-OHUR算法的时间复杂度，本文采用时间序列相似性度量(DTW)^[18]和莱文斯坦相似性度量(Leven)^[20]两种经典的相似性度量算法，分别计算点击流数据中前200名、400名、600名和800名在线用户的相似度，3种算法运行时间如表 6所示。

由表 6可知，SA-OHUR算法在一定程度上减少程序运行时间，提升了程序运行效率，在处理大批量数据时该算法有明显优势。这是因为SA-OHUR算法采用累计点击数据流进行计算，无需考虑累计点击数据流中序列的顺序性，同时去除冗余序列，降低了算法复杂度。

相较传统层次聚类HC算法，SA-OHUR算法降低了时间复杂度，提高了运行效率，但其聚类效果还未知。因此，本文将采用传统层次聚类HC算法和SA-OHUR算法所得聚类结果的熵值和纯度进行对比，结果分别如表 7和表 8所示。

由表 7和表 8可知，SA-OHUR算法得到的聚类结果整体熵值较低且纯度较大，其中在社会阶层属性中较反常。从整体来看，年龄对行为相似性影响程度低于性别、教育程度、户籍3种属性，对结果影响不大。因此，在分析特征属性对在线同源用户行为相似性影响程度时，基于相似度矩阵的层次聚类整体效果更好。

4 结束语

利用海量的互联网信息找出在线用户行为的主要影响因素，并据此对不同用户群体进行分类具有重要意义。本文基于序列对齐技术提出一种在线同源用户识别算法，提取在线用户点击流数据和特征属性，采用序列对齐方法计算用户行为相似度，识别具有相似行为的在线同源用户，并分析不同特征属性对用户行为相似性的影响程度。实验结果表明，该算法能有效区分在线同源用户，用户行为相似性受性别、户籍和教育程度3种特征属性影响较大。本文主要研究独立的特征属性，未考虑不同特征属性组合对用户行为的影响，后续将从用户行为权值较大的部分特征属性入手，进一步研究包含该部分属性不同组合的用户行为。