基于图形处理单元的异构特征时序数据演化聚类方法

摘要

一种基于图形处理单元的异构特征时序数据演化聚类方法，包含以下步骤：（１）提取原始数据特征，采用多视图方式表示原始数据的异构特征；（２）申请显存空间，并利用图形处理单元提供的数据传输函数把数据传到图形处理单元的显存中；（３）在图形处理单元上进行多矩阵非负分解，迭代的更新特征模矩阵、时序模矩阵和数据对象模矩阵，直到目标函数收敛为止；（４）归一化模矩阵,得到簇中每个特征的隶属概率、簇的时序演化趋势及每个数据对象隶属于每个簇的概率；（５）最后释放显存空间。本发明利用图形处理单元的高并发性来加速多矩阵非负分解过程，在多视图表示中引入时序特征视图，利用多矩阵非负分解后的时序模矩阵，获得簇随时间的演化趋势。

说明书

技术领域

本发明涉及一种并行异构特征时序数据演化聚类方法，尤其涉及一种基于 图形处理单元的异构特征时序数据演化聚类方法，属数据处理技术领域。

背景技术

在现实世界中，绝大部分数据都带有时间特征，如社会化媒体数据、股票 数据、医疗数据、科学文献数据等。这些数据中的时间特征可以被用来发现事 件的演化趋势、检测异常行为、预测事件发展等。时序数据演化聚类在现实应 用中有许多潜在的需求，例如在社会化媒体数据中，大量用户发布、交流、传 播和跟踪各种与社会、政治等相关的热点事件，这个过程实时反映了人们对正 在传播事件的观点及看法。因此，对于政府部门来说，通过演化聚类方法可以 从社会化媒体数据中挖掘出事件的起因、讨论的热度以及人们的观点，同时， 随着事件的进一步发展，还可以挖掘出人们观点及讨论热度的变化。在这个过 程中，政府可以实时地监控、引导舆情的变化。这对于维护社会稳定和国家网 络信息安全来说是至关重要的。

近年来,随着信息技术和互联网技术快速发展，特别是移动互联网的迅猛发 展，数据的获取变得越来越容易，数据规模也越来越大。这使得传统的时序数 据演化聚类时间代价太高，不能适应现有的大规模时间数据的演化聚类。此外， 由于现实应用的复杂性，这些应用产生的数据对象通常也包含多种类型的特征， 例如社会化媒体数据中包含文本、图形、视频、标签、表情等特征。如何利用 这些异构特征进行综合学习，获取数据集中簇结构的演化趋势也是时间数据演 化聚类的一个难点。

现有的多视图数据聚类方法也能够处理异构特征数据的聚类问题。例如 2009年，Chi等人通过加权融合图像特征和文本特征进行多视图数据聚类(Chi  M,Zhang P,Zhao Y,et al.Web image retrieval reranking with multi-view  clustering，www,2009)。但是，这种简单的对不同量纲的数据进行加权融合 会使融合后的数据失去可解释性，而且找到一组合适的加权参数也是一项非常 困难的事情。由于时序数据的特殊性(如时间的延续性)，简单的把时间特征 作为异构特征数据的一个视图进行聚类不能得到有效地演化聚类效果。

基于潜层狄利克雷主题模型(Latent Dirichlet Allocation)，Wang和 McCallum人提出了时间主题模型(Topic over Time，Wang X,McCallum A.Topics  over time:a non-Markov continuous-time model of topical trends，ACM  SIGKDD，2006)。该方法通过引入贝塔分布(Beta Distribution)来归一化 每个话题在时间维度上的分布，利用话题在时间分布上的不同来区分在内容上 相似的话题。该方法限制每个话题在时间上都必须服从贝塔分布，然而，现实 应用中很多话题在时间上的演化并不服从贝塔分布。此外，时间主题模型只能 利用文本和时间两种特征，现实数据中的其他特征信息并不能被有效利用，从 而提高演化聚类的效果。

基于张量非负分解方法，Lin等人提出基于多张量非负分解方法(Metafac， (Y.Lin,J.Sun,P.Castro,R.Konuru,H.Sundaram,and A.Kelliher, “Metafac:community discovery via relational hypergraph factorization, ACM SIGKDD，2009)。该方法利用多个张量来表示多种类型的数据特征，然后 同时对这些张量进行非负分解来获得每个对象在每个簇中的隶属度和每个簇中 特征的分布。然而该方法不能有效地利用时间特征来发现簇(或话题)的热点 趋势变化。同时，当数据量较大时，张量非负分解的速度非常慢，难以满足现 实应用的要求。此外，2014年，liu等人也提出了基于多矩阵非负分解多视图 聚类算法(Liu J,Wang C,Gao J,et al.Multi-view clustering via joint  nonnegative matrix factorization，SDM，2013)，但是该方法不能够直接有 效的处理时间特征并发现簇在时间维度上的演化趋势。

发明内容

本发明解决的技术问题是：提出一种基于图形处理单元的异构特征时序数 据演化聚类方法，克服现有技术不能够有效地利用数据中的异构特征进行演化 聚类和由于数据量大而导致的计算速度慢的问题。

实现本发明的技术方案是，提供一种基于图形处理单元的异构特征时序数 据演化聚类方法，所述方法将异构数据用多视图方法表示，整个数据集利用多 个矩阵来表示；根据异构数据的大小申请相应的显存空间，并把数据传入显存； 利用图形处理单元进行多矩阵非负分解得到特征模矩阵、时间模矩阵和数据对 象分配模矩阵；然后对模矩阵进行归一化处理，得到每个簇的属性分布、每个 对象在簇中的隶属度和簇的演化趋势；最后把所有的计算结果从显存回传到主 存，包括特征模矩阵、时间模矩阵和数据对象分配模矩阵，并释放所占用的显 存空间。

本发明方法的实现步骤如下：

(1)多视图数据表示：提取原始数据的异构特征，每一种类型的特征用一 个视图表示，在计算过程中，一个特征视图数据用一个矩阵表示Xⁱ，时序特征 用矩阵X^τ表示，这样，数据集可表示为X＝{X^τ,X¹,X²,...,X^p}，p为特征矩阵的 个数。

(2)申请显存空间：在运行聚类算法之前，需要申请的显存空间包括：存 放原始数据的空间、聚类算法运行的临时空间和结果存放空间,然后把多视图数 据X传到显存中。

(3)并行非负多矩阵分解：针对显存中存放的多视图数据，本发明设计一 种在图形处理单元上运行的基于平滑约束的并行多矩阵非负分解方法来获得特 征模矩阵、时序模矩阵和数据对象模矩阵，为了获得这三种模矩阵，本发明为 算法构建目标函数，设计了三个计算公式，分别用来计算特征模矩阵、数据对 象模矩阵和时序模矩阵。这三个计算是迭代进行的，其计算顺序为:计算特征模 矩阵->计算数据对象模矩阵->计算时序模矩阵]->[计算计算特征模矩阵->计算 数据对象模矩阵->计算时序模矩阵]->...，迭代循环，一直到目标函数收敛为 止；在计算过程中，每个步骤设计若干个核函数，运行在图形处理单元上。

(4)归一化模矩阵：针对并行多矩阵分解后的模矩阵做归一化处理，获得 每个簇中特征的分布，每个对象属于不同簇的概率及每个簇的演化趋势。

(5)释放显存空间：最后算法运行结束后，释放算法所占用的显存空间。

本发明提出的基于图形处理单元的异构特征时序数据演化聚类方法，围绕 着异构特征的时序数据展开演化聚类研究，利用联合多矩阵非负分解的思想融 合异构特征进行聚类，把多矩阵非负分解转化成图形处理器的矩阵乘法、矩阵 乘除、矩阵加减等核函数，加快矩阵分解的运行。同时，本发明矩阵分解的方 法来发现簇的演化趋势。在矩阵分解过程中，利用时间平滑约束来得到更加合 理的演化趋势，避免由于噪音带来演化趋势的剧烈振荡。

本发明与现有技术比较的有益效果是，本发明通过利用矩阵分解方法来发 现簇(或者话题)的演化趋势，提出了基于平滑约束的多矩阵非负分解方法， 可以有效地发现簇随时间的热度趋势变化。本发明的该特征可以用来追踪社会 热点、预测话题趋势变化。

传统的矩阵分解速度较慢，特别是当数据量大时，过高的时间代价往使得 该方法难以被广泛使用。本发明通过把多矩阵非负分解转化了矩阵乘法、矩阵 加减法、矩阵按元素操作等，充分发挥图形处理单元在这些操作上速度优势， 加快算法的运行。传统的时序演化聚类算法，通常只能利用单一的特征(如文 本特征)。本发明利用多矩阵分解来融合多类型的特征进行聚类，能够充分利用 数据中包含的多种类型的信息，从提高演化聚类的精度。

本发明基于图形处理单元的时序数据演化聚类方法能够有效地发现簇及其 演化趋势。同时相比于传统的矩阵分解算法，本发明在速度上可以提高100倍 的性能。

附图说明

图1为本发明的流程图；

图2为本发明的一个异构特征数据示例；

图3为本发明所需要申请的显存空间；

图4为本发明的矩阵乘除核函数示意图；

图5为本发明的计算时间模矩阵核函数示意图；

图6为本发明的矩阵加法核函数示意图；

图7为本发明的并行与串行多矩阵非负分解在模拟数据集上的加速；

图7－1为迭代次数与加速比的关系曲线；

图7－2为数据维度与加速比的关系曲线；

图7－3为数据对象数目与加速比的关系曲线；

图7－4为矩阵分解的秩(簇的数目)与加速比的关系曲线；

图7－5为特征视图数目与加速比的关系曲线；

图8为本发明的簇的演化趋势图；

图中，1－14指话题名称(英文)，1表示一个男学生的SARS恶作剧，2表 示美国白宫通过预算，3有示一艘渡船在孟加拉国的帕格拉附近沉没，4表示比 利时爆发群流感，5表示科尔号军舰攻击嫌疑逃犯，6表示西班牙选举，7表示 索萨有作弊嫌疑，8表示伊拉克核地址发生哄抢，9表示曼德拉85岁，10表示 法院起诉利比里亚总统，11表示同性恋主教，12表示科比性侵案，13表示约翰 尼·卡什的死亡，14表示爱德华·萨义德享年67岁。

具体实施方式

下面结合具体实施例，对本发明技术方案进一步说明。

如图1所示，本发明的具体实施方式是：提供一种基于图形处理单元的异 构特征时序数据演化聚类方法，包括如下步骤：

步骤01：多视图数据表示，提取原始数据的异构特征，每一种类型的特征 用一个矩阵表示，整个数据集可表示为X＝{X^τ,X¹,X²,...,X^p}，p为特征矩阵的个 数。

具体实施过程如下：在现实应用中，数据对象可能包含多种类型的特征， 如图2，一篇学术论文包含关键词、作者、引用和时间等特征。在多视图数据表 示步骤中，数据对象的每一种特征用一个矩阵表示 其中,p为特征种类，n为数据对象种类，mⁱ为第i种类型特征的属性数目，为第j个数据对象在第i种类型特征的第q 个属性上的属性值。X^τ为时间特征矩阵，其中T为 数据中时间点的数目，为数据对象在t时刻的值，当j对象不在t时刻出现 时，则为零。这样,整个数据集用多视图数据表示为X＝{X^τ,X¹,X²,...,X^p}。

步骤02：申请显存空间，在运行聚类算法之前，需要申请的显存空间包括： 存放原始数据的空间、聚类算法运行的临时空间和结果存放空间，如图3。

具体实施过程如下：在申请显存空间步骤中，首先在显存中申请存放原始 数据X＝{X^τ,X¹,X²,...,X^p}的空间；然后申请计算过程中需要用来存放临时数据的 临时空间XqUq(在更新第q个特征模矩阵时，存放第q个特征视图与上一次第 q个特征模矩阵的乘积，这里不需要为每个U^q,(1≤q≤p)申请临时显存空间，只 需要申请占最大显存空间的就行，在计算所有特征模矩阵时，共用这块显 存空间)，临时空间UqOO(在更新第q个特征模矩阵时，存放第q个特征视图与 两个分配矩阵乘积的乘积，同样是申请占最大显存空间的U^qO^TO就行，在计算 所有特征模矩阵时，共用这块显存空间)，临时空间SumXU(在更新对象分配矩 阵O时，存放第q个特征视图X与特征模矩阵U乘积的和)和临时空间SumUtU(在 更新对象分配模矩阵O时，存放上一次迭代的对象分配模矩阵O与第q个特征模 矩阵U与其转置乘积的乘积之和)。在更新时间矩阵X^τ时，也要利用临时变量 XqUq与UqOO。在申请完成这些显存空间后，通过图形处理单元的数据拷贝函数 把原始数据X＝{X^τ,X¹,X²,...,X^p}传到显存上，同时把其他临时空间初始化为零。

步骤03：并行非负多矩阵分解，针对显存中存放的多视图数据，设计一种 在图形处理单元上运行的基于平滑约束的并行多矩阵非负分解方法来获得特征 模矩阵、时序模矩阵和数据对象模矩阵，在计算过程中，每个步骤设计若干个 核函数，运行在图形处理单元上。在该步骤中,设计了三个计算公式分别计算三 个矩阵的值。这个算法是一个迭代算法，更新的步骤是：[计算特征模矩阵-> 计算数据对象模矩阵->计算时序模矩阵]->[计算特征模矩阵->计算数据对象模 矩阵->计算时序模矩阵]->...，迭代循环，一直到目标函数收敛为止。

具体实施过程如下：首先，本发明为算法构建了目标函数：

$P(O,T,U^1,\mathrm{...},U^p)=\frac{1}{2}(\underset{q=1}{\overset{p}{\Sigma }}{\left|\right|X^q-{\mathrm{OU}}^{q^T}\left|\right|}^2+{\left|\right|X^{\tau }-{\mathrm{OT}}^T\left|\right|}^2+\lambda \underset{i=2}{\overset{I_T}{\Sigma }}{\left|\right|t_{i.}-t_{(i-1).}\left|\right|}^2).$

X^q为第q个特征视图，X^τ为时间特征视图，O为数据对象分配模矩阵，T为时 间特征模矩阵，U^q为第q个特征模矩阵,λ为时序平滑因子，I_T为时间点个数， t_i.为为时间特征模矩阵的第i行。该目标函数旨在通过矩阵分解的方式找出数据 中的潜层结构。通过优化求解该目标函数，得到并行非负分解的三个子步骤： 更新特征模矩阵U^q,1≤q≤p、更新时间模矩阵T和更新数据对象分配矩阵O。 更新第q个特征模矩阵U^q的公式为：

$u_{ij}^q=u_{ij}^q\frac{{\left(X^{q^T}O\right)}_{ij}}{{\left(U^q{O}^{T}O\right)}_{ij}},$

式中，为第q个特征矩阵的第i行，第j列元素的值，最后通过按列归一化， 可以转化为第q类特征中第j个属性在第i个簇中出现的概率。在计算U^q时，首 先利用图形处理单元提供的矩阵乘法函数计算上式中和U^qO^TO，分别存在 临时空间XqUq和UqOO中。然后利用如图4所示核函数计算特征模矩阵U^q。 在计算过程中，为该核函数开启I_q×k(I_q为第q种特征的属性数目，k为簇的数 目)个线程，每个线程执行一个对元素的乘除操作。

更新时间特征矩阵T的公式为：

$t_{ij}=\left(\begin{array}{c}{t}_{ij}\frac{{\left(X^{{\tau }^T}O\right)}_{ij}+{\mathrm{\lambda t}}_{(i+1)j}}{{\left({\mathrm{TO}}^{T}O\right)}_{ij}+{\mathrm{\lambda t}}_{ij}},i\mathrm{fi}=1,\\ t_{ij}\frac{{\left(X^{{\tau }^T}O\right)}_{ij}+{\mathrm{\lambda t}}_{(i+1)j}+{\mathrm{\lambda t}}_{(i-1)j}}{{\left({\mathrm{TO}}^{T}O\right)}_{ij}+2{\mathrm{\lambda t}}_{ij}},if1<i<I_T\\ t_{ij}\frac{{\left(X^{{\tau }^T}O\right)}_{ij}+{\mathrm{\lambda t}}_{(i+1)j}}{{\left({\mathrm{TO}}^{T}O\right)}_{ij}+{\mathrm{\lambda t}}_{ij}},ifi=I_T.\end{array}\right),$

式中，t_ij为时间特征模矩阵的第i行、第j列的值，表示第i个簇在第j个时间 点的热度趋势。同样，在计算时间模矩阵T时，需要先利用图形处理单元提供 的矩阵乘法函数计算然后再设计核函数计算T的值，其核函数示意图如 图5所示。该核函数只计算时间模矩阵的中间I_T-2列(I_T为离散化后的时间戳 数目)，首列与尾列由中央处理器(CPU)来计算。因此，需要在图形处理器开 启上(I_T-2)×k个线程，每个线程计算一个元素t_ij的值。

更新数据对象分配模矩阵O的公式为：

$o_{ij}=o_{ij}\frac{{\left(X^{\tau }T+\underset{q=1}{\overset{p}{\Sigma }}{X}^q{U}^q\right)}_{ij}}{{\left({\mathrm{OT}}^{T}T+\underset{q=1}{\overset{p}{\Sigma }}{\mathrm{OU}}^{q^T}{U}^q\right)}_{ij}}.$

式中，o_ij为数据对象分配模矩阵第i行、第j列的值，通过按行归一化后，可 以表示第i个数据对象在第j个簇中出现的概率。在计算对象分配模矩阵O时， 首先需要利用图形处理单元提供的矩阵乘法操作计算X^τT、X^qU^q、OT^TT和 然后通过矩阵的加法核函数(如图6所示)计算上式中的分子与分母， 最后利用矩阵的乘除核函数(如图4所示)计算对象分配模矩阵O的值。图7给 出了并行多矩阵非负分解与传统串行多矩阵非负分解的在模拟数据集上随着迭 代次数的增加、数据维度的增加、数据对象数目的增加、簇数目的增加和特征 视图的增加的加速比变化。从图7中可以看出，并行多矩阵非负分解与串行多 矩阵非负分解的加速比在100以上，并且随着数据维度的增加、数据对象数目 的增加和簇数目的增加，加速比有进一步的提高。

步骤04：归一化模矩阵，针对并行多矩阵分解后的模矩阵做归一化处理， 获得每个簇中特征的分布、每个对象属于不同簇的概率及每个簇的演化趋势。

具体实施过程如下：在归一化步骤中，需要对特征模矩阵和数据对象分配 模矩阵分别进行归一化。对于每个特征模矩阵U^q(总共包含k列，k为簇数目) 按列进行归一化，归一化后的值表示属性在对应的簇中的分布，即每个簇包含 哪些属性及这些属性在该簇中出现的概率。对于数据对象分配矩阵O(O为I_o×k 的矩阵)按行进行归一化，归一化后的每行值表示对象属于每个簇的概率。本 发明直接利用步骤03得到的时间模矩阵T(T为I_T×k的矩阵)来表示簇的演化趋 势，其中每一列表示一个簇的演化趋势，每一个值表示话题在该时间点上的热 度。如图8所示为在实验数据集TDT5上的29个英文话题(图中只标注了14个 话题)的演化趋势图，从中可以明显的看出每个话题的讨论热度变化。

步骤05：释放显存空间，最后算法运行结束后，释放算法所占用的显存空 间。

具体实施过程如下：在释放显存空间步骤中，首先利用图形处理单元提供 的数据拷贝函数把显存中的结果数据回传到主存并保存到文件中。结果数据包 含特征模矩阵U^q,(1≤q≤p)、时间模矩阵T和数据对象分配矩阵O。然后释放算 法占用的所有显存空间，包括原始数据X、特征模矩阵U^q,(1≤q≤p)、时间模矩 阵T、数据对象分配矩阵O、临时空间XqUq、临时空间UqOO、临时空间SumXU 和临时空间SumUtU所占用的显存空间。

本发明的基于图形处理单元的异构特征时序数据演化聚类方法，将异构数 据用多视图方法表示，整个数据集利用多个矩阵来表示；根据异构数据的大小 申请相应的显存空间，并把数据传入显存；利用图形处理单元进行多矩阵非负 分解得到特征模矩阵、时间模矩阵和数据对象分配模矩阵；然后对模矩阵进行 归一化处理，得到每个簇的属性分布、每个对象在簇中的隶属度和簇的演化趋 势；最后把所有的计算结果从显存回传到主存，包括特征模矩阵、时间模矩阵 和数据对象分配模矩阵，并释放所占用的显存空间。本发明的基于图形处理单 元的异构特征时序数据演化聚类方法是一种无监督的学习方法，非常适合于处 理多种类型特征的时序大规模数据的聚类问题，具有聚类速度快的特点。

以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认 定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术 人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换， 都应当视为属于本发明的保护范围。