面向NLP基于GSDPMM和主题模型的Mashup服务谱聚类方法

摘要

一种面向NLP基于GSDPMM和主题模型的Mashup服务谱聚类方法，包括以下步骤：第一步：通过GSDPMM方法计算出Mashup服务数量的主题个数；第二步：根据上下文信息和服务标签信息计算单词的语义权重信息从而得到文档‑单词语义权重信息矩阵D；第三步：统计单词共现信息，计算出SPPMI矩阵信息；第四步：基于文档‑单词语义权重信息矩阵D和SPPMI矩阵M，通过分解M得到词嵌入信息矩阵，将上述两种信息进行结合，计算服务的主题信息；第五步：得到的Mashup服务主题特征作为谱聚类的输入进行聚类。本发明融合优化的词嵌入和单词语义权重计算方法来缓解短文本带来的稀疏性问题，找到更优的解集。

说明书

技术领域

本发明涉及到一种面向NLP基于GSDPMM和主题模型的Mashup服务谱聚类方法

背景技术

随着云计算的发展和服务计算“服务化”的思想驱动，越来越多的公司将数据、资源或者相关业务通过Web服务的形式发布到互联网上，以提高信息的利用率和自身竞争力。然而传统基于SOAP协议的Web服务，存在技术体系复杂、扩展性差等问题，难以适应现实生活中复杂多变的应用场景。为克服传统服务带来的问题，近年来，互联网上涌现出一种轻量级的信息服务组合模式——Mashup技术，可以混搭多种不同Web API，开发出多种全新的Web服务，以缓解传统服务难以适应复杂多变应用环境的问题。

随着Mashup服务快速增长，如何在众多Mashup服务中找到高质量的服务，已经成为一个大家关注的热点问题。自然语言处理(Natural Language Processing，NLP)是计算机科学领域以及人工智能领域的一个重要的研究方向，它研究用计算机来处理、理解以及运用人类语言，Mashup服务描述文档是由自然语言进行描述，需要借助NLP中的方法处理Mashup服务才能让计算机能够理解服务所描述的内容。

目前现有的方法，主要采用潜在狄利克雷分配(Latent Dirichlet Allocation,LDA)或者非负矩阵分解(Non-negative Matrix Factorization,NMF)等方法得到Mashup服务主题特征后，进一步进行聚类工作。然而Mashup服务描述文档通常比较简短、特征稀疏、信息量少，LDA模型在处理短文本上效果远远不如长文本，导致目前大部分主题模型很难对缺乏训练语料的短文本进行很好地建模，另一方面短文本内单词基本都是出现一次，缺少高频词信息，对于词频-逆向文档频率(term frequency–inverse document frequency，TF-IDF)模型而言则很难计算出单词的语义权重。除此之外LDA，NMF等主题模型通常需要指定主题个数，然而服务的主题个数事前很难直接确定。同时目前多数服务聚类算法都是将K-means聚类算法作为最后主题特征值的聚类算法，但是传统K-means算法由于受聚类中心点随机性以及无法发现非凸形状簇的影响，可能导致聚类质量不理想。

发明内容

为了能克服现有传统主题模型对短文本建模能力欠缺、主题数难以确认、以及K-means聚类算法质量不高导致Mashup服务聚类质量不高的问题，本发明提出一种面向NLP基于GSDPMM(a collapsed Gibbs Sampling algorithm for the Dirichlet MultinomialMixture Model)和主题模型的Mashup服务谱聚类方法。该方法利用非负矩阵分解NMF对Mashup服务进行主题挖掘，引入改进的Gibbs采样的狄利克雷过程混合模型(DirichletProcess Mixture Model,DPMM)来自动确定主题数量，融合优化的词嵌入和单词语义权重计算方法来缓解短文本带来的稀疏性问题，最后采用谱聚类算法对Mashup服务的主题特征进行聚类，从而找到更优的解集。

本发明解决其技术问题所采用的技术方案是：

一种面向NLP基于GSDPMM和主题模型的Mashup服务谱聚类方法，包括以下步骤：

第一步：通过GSDPMM方法计算出Mashup服务数量的主题个数，步骤如下：

1.1初始化矩阵z,n

1.2遍历所有Mashup服务，计算n

1.3对所有Mashup服务进行Gibbs采样操作；

1.4根据轮盘赌选法，选择文档d的主题；

1.5根据当前文档d的所属主题k,令m

1.6重复步骤1.3-1.6直至处理完所有Mashup服务；

1.7重复1.3-1.6直至达到迭代次数Iter；

第二步：根据上下文信息和服务标签信息计算单词的语义权重信息从而得到文档-单词语义权重信息矩阵D，步骤如下：

2.1使用Python中的自然语言工具包(Natural language toolkit，NLTK)，对Mashup服务描述文档进行中的单词进行词性标注，NLTK是著名的自然语言处理库，可以用于处理与自然语言相关的东西；

2.2：统计单词词频信息，计算TF-IDF信息；

2.3：提取Mashup服务标签信息，并基于名词集Nset和TF-IDF值，重新计算Mashup服务描述文档中的每一个单词的语义权重；

第三步：统计单词共现信息，从而计算出SPPMI矩阵信息，步骤如下：

3.1统计词共现信息，由于Mashup服务描述文档较短，为了能更准确地获取上下文共现信息，将整个服务描述文档作为滑动窗口的长度，计算每个单词和其他单词在上下文中共同出现的次数；

3.2点互信息(Pointwise Mutual Information，PMI)计算，PMI被广泛用于计算单词间相似度的关系，当两个单词在文本中共现概率越大时，单词间的相关性就越强，PMI计算公式如下所示：

x和y表示两个单词，P(x,y)表示单词x和y共现的概率，P(x)表示单词x在上下文中出现概率。根据单词w

#(w

3.3计算偏移正点互信息值(Shifted Positive Pointwise MutualInformation，SPPMI)矩阵，SPPMI矩阵通过PMI值计算，SPPMI矩阵的计算方式为：

SPPMI(w

其中κ为负采样系数。通过上述公式得到单词的上下文SPPMI矩阵M；

第四步：基于第二步，第三步得到Mashup服务文档单词的文档-单词语义权重矩阵D，单词的上下文SPPMI矩阵M，通过分解M得到词嵌入信息矩阵，进一步将上述两种信息进行结合，计算服务的主题信息，步骤如下：

4.1通过由第二步给定全局文档-单词语义权重矩阵D，通过NMF将其分解为文档-主题矩阵θ和主题-单词矩阵Z乘积，分解矩阵D的函数表示为：

其中

4.2通过第三步计算得到单词的上下文SPPMI矩阵M，分解矩阵M引入词嵌入信息，分解M的公式如下所示：

S是一个额外的对称因子，用于M的近似求解，W为单词的词嵌入矩阵；

4.3利用Mashup服务文档和单词间的关系，可以发现主题信息，通过文档内单词上下文的共现信息，可以学习到词嵌入信息；但是这两个部分并不相互孤立，语义相关的单词属于相似的主题，在嵌入空间中也很接近；可知单词嵌入与它们的主题相关，关系公式如下所示：

4.4在步骤4.3中将主题-单词矩阵Z分解为主题嵌入矩阵A和词嵌入矩阵W的乘积，将词嵌入与主题信息相联系起来，进一步提高了主题建模的准确性；

结合步骤4.1，4.2和4.3，得到主题模型的目标函数：

求解该目标函数，使用矩阵迹运算将上述公式展开：

J(θ,Z,W,S,A)＝λ

+λ

+λ

其中J(θ,Z,W,S,A)为J

J(θ,Z,W,S,A)＝λ

+λ

+λ

Tr表示矩阵求迹，λ

其中α,β,γ,

令α⊙θ＝0,β⊙Z＝0,γ⊙W＝0,

-(DZ)⊙θ+(θZ

-(λ

-2(λ

-(Z

进一步更新参数：

通过上述参数更新方式，可求解出Mashup服务文档-主题矩阵θ和主题-单词矩阵Z，词嵌入矩阵W，主题嵌入矩阵A；

第五步：将4.4中得到的Mashup服务主题特征，作为谱聚类的输入进行聚类，谱聚类是从图论中演化出来的算法，后来在聚类中得到了广泛的应用；它的主要思想是把所有的数据看做空间中的点，这些点之间可以用边连接起来；距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高。通过对所有数据点组成的图进行切图，让切图后不同的子图间边权重和尽可能的低，而子图内的边权重和尽可能的高，从而达到聚类的目的，步骤如下：

5.1计算相似度矩阵SI，服务主题特征之间的相似度可以高斯核函数计算。公式中θ

5.2将矩阵SI的每一列的元素相加，并将每一列作为元素添加到度矩阵G对角线上，公式如下。

5.3通过G计算Laplacian矩阵L＝G–SI；

5.4利用python中eig函数计算

其中arg min

5.5将特征值从小到大排序，取前C个特征值，C指定的聚类簇的数量，得到前C个特征值的特征向量，作为初始聚类中心；

5.6计算特征向量到聚类中心的欧式距离dist，将Mashup服务划分到距离最小的簇，计算公式如下：

其中f

5.7更新聚类中心为每个簇中特征向量累加的平局值；

5.8计算新聚类中心和旧聚类中心的欧式距离作为误差值；

5.9重复步骤5.6-5.8直至误差小于一定阈值，或者迭代次数到达最大迭代次数。

进一步，所述1.2的过程如下：

1.2.1根据z

1.2.2遍历文档d中的每一个单词w,令，n

1.2.3重复1.2.1-1.2.2直至处理完所有Mashup服务。

再进一步，所述1.3的过程如下：

1.3.1根据z

1.3.2遍历文档d中的每一个单词w,令，n

1.3.3遍历每一个主题，计算文档d在原来主题上的概率，计算公式如下：

1.3.4计算文档d在新主题下的概率，计算公式如下：

其中α,β为超参数，z

更进一步，所述1.4的过程如下：

1.4.1将文档d在每个主题下的概率进行累加，得到总概率prob；

1.4.2在[0,prob]内随机生成一个随机数thred；

1.4.3累加文档d在每个主题下的概率，若当前主题k上的累加和大于等于thred，则文档d的主题为k。

所述2.1的过程如下：

2.1.1遍历当前Mashup服务描述文档中的每一个单词，利用NLTK对单词进行词性还原；

2.1.2利用NLTK提取单词词根，并判断单词是否是名词性单词，若是名词性单词加入名词集合Nset；

2.1.3重复步骤2.1.1-2.1.2直至处理完所有Mashup服务。

所述2.2的过程如下：

2.2.1遍历Mashup服务描述文档中的每个单词，统计当前文档中每个单词的出现的次数，计算每个单词TF值，计算公式如下：

其中TF

2.2.2统计每个单词出现过的Mashup服务文档数量，计算IDF值，计算公式如下：

IDF(x)表示单词x的IDF值，N表示Mashup文档的数量，doc(x)表示包含单词x的Mashup文档数量；

2.2.3遍历所有Mashup文档中的单词，计算单词的TF-IDF值计算公式如下：

TF-IDF(x)＝TF(x)*IDF(x)

TF-IDF(x)表示单词x的TF-IDF值，TF(x)表示单词x的TF值。

所述2.3的过程如下：

2.3.1遍历当前Mashup服务文档中每一个单词w

其中sim(w

2.3.2计算单词的服务标签语义权重信息WeightTag(w

其中Tag

2.3.3基于TF-IDF值，并结合2.3.1和2.3.2中的计算结果，重新计算单词的语义权重。

优选的，所述2.3.3的操作如下：

2.3.3.1遍历当前Mashup服务描述文档中的每一个单词w

2.3.3.2赋值单词的语义权重为其TF-IDF值，计算公式如下：

SemWeight(w

2.3.3.3重复2.3.3.1-2.3.3.2直至处理完所有Mashup服务，得到文档-单词语义权重矩阵D。

所述3.1的过程如下：

3.1.1对于当前Mashup服务，计算该Mashup服务描述文档长度Len，设定滑动窗口长度为Len。

3.1.2统计Mashup服务描述文档中单词和其他单词的共现情况，若当前单词的其上下文单词，即该单词前后的单词，在滑动窗口Len的距离内，则该单词和其在滑动窗口内的上下文单词共现次数加1；

3.1.3重复3.1.2直至处理完Mashup中的所有单词；

3.1.4重复3.1.1-3.1.3直至处理完所有Mashup服务。

本发明的有益效果主要表现在：利用非负矩阵分解NMF对Mashup服务进行主题挖掘，引入改进的Gibbs采样的狄利克雷过程混合模型(Dirichlet Process Mixture Model,DPMM)来自动确定主题数量，融合优化的词嵌入和单词语义权重计算方法来缓解短文本带来的稀疏性问题，最后采用谱聚类算法对Mashup服务的主题特征进行聚类，从而找到更优的解集。

具体实施方式

下面对本发明作进一步描述。

一种面向NLP基于GSDPMM和主题模型的Mashup服务谱聚类方法，包括以下步骤：

第一步：通过GSDPMM方法计算出Mashup服务数量的主题个数，步骤如下：

1.1初始化矩阵z,n

1.2遍历所有Mashup服务，计算n

1.2.1根据z

1.2.2遍历文档d中的每一个单词w,令，n

1.2.3重复1.2.1-1.2.2直至处理完所有Mashup服务；

1.3对所有Mashup服务进行Gibbs采样操作，过程如下：

1.3.1根据z

1.3.2遍历文档d中的每一个单词w,令，n

1.3.3遍历每一个主题，计算文档d在原来主题上的概率，计算公式如下：

1.3.4计算文档d在新主题下的概率，计算公式如下：

其中α,β为超参数，z

1.4根据轮盘赌选法，选择文档d的主题，过程如下：

1.4.1将文档d在每个主题下的概率进行累加，得到总概率prob；

1.4.2在[0,prob]内随机生成一个随机数thred；

1.4.3累加文档d在每个主题下的概率，若当前主题k上的累加和大于等于thred，则文档d的主题为k；

1.5根据当前文档d的所属主题k,令m

1.6重复步骤1.3-1.6直至处理完所有Mashup服务；

1.7重复1.3-1.6直至达到迭代次数Iter；

第二步：根据上下文信息和服务标签信息计算单词的语义权重信息从而得到文档-单词语义权重信息矩阵D，步骤如下：

2.1使用Python中的自然语言工具包(Natural language toolkit，NLTK)，对Mashup服务描述文档进行中的单词进行词性标注，NLTK是著名的自然语言处理库，可以用于处理与自然语言相关的东西，过程如下：

2.1.1遍历当前Mashup服务描述文档中的每一个单词，利用NLTK对单词进行词性还原；

2.1.2利用NLTK提取单词词根，并判断单词是否是名词性单词，若是名词性单词加入名词集合Nset；

2.1.3重复步骤2.1.1-2.1.2直至处理完所有Mashup服务；

2.2：统计单词词频信息，计算TF-IDF信息，过程如下：

2.2.1遍历Mashup服务描述文档中的每个单词，统计当前文档中每个单词的出现的次数，计算每个单词TF值，计算公式如下：

其中TF

2.2.2统计每个单词出现过的Mashup服务文档数量，计算IDF值，计算公式如下：

IDF(x)表示单词x的IDF值，N表示Mashup文档的数量，doc(x)表示包含单词x的Mashup文档数量；

2.2.3遍历所有Mashup文档中的单词，计算单词的TF-IDF值计算公式如下：

TF-IDF(x)＝TF(x)*IDF(x)

TF-IDF(x)表示单词x的TF-IDF值，TF(x)表示单词x的TF值；

2.3：提取Mashup服务标签信息，并基于名词集Nset和TF-IDF值，重新计算Mashup服务描述文档中的每一个单词的语义权重，过程如下：

2.3.1遍历当前Mashup服务文档中每一个单词w

其中sim(w

2.3.2计算单词的服务标签语义权重信息WeightTag(w

其中Tag

2.3.3基于TF-IDF值，并结合2.3.1和2.3.2中的计算结果，重新计算单词的语义权重，操作如下：

2.3.3.1遍历当前Mashup服务描述文档中的每一个单词w

2.3.3.2赋值单词的语义权重为其TF-IDF值，计算公式如下：

SemWeight(w

2.3.3.3重复2.3.3.1-2.3.3.2直至处理完所有Mashup服务，得到文档-单词语义权重矩阵D；

第三步：统计单词共现信息，从而计算出SPPMI矩阵信息，步骤如下：

3.1统计词共现信息，由于Mashup服务描述文档较短，为了能更准确地获取上下文共现信息，将整个服务描述文档作为滑动窗口的长度，计算每个单词和其他单词在上下文中共同出现的次数，过程如下：

3.1.1对于当前Mashup服务，计算该Mashup服务描述文档长度Len，设定滑动窗口长度为Len。

3.1.2统计Mashup服务描述文档中单词和其他单词的共现情况，若当前单词的其上下文单词，即该单词前后的单词，在滑动窗口Len的距离内，则该单词和其在滑动窗口内的上下文单词共现次数加1；

3.1.3重复3.1.2直至处理完Mashup中的所有单词；

3.1.4重复3.1.1-3.1.3直至处理完所有Mashup服务；

3.2点互信息(Pointwise Mutual Information，PMI)计算，PMI被广泛用于计算单词间相似度的关系，当两个单词在文本中共现概率越大时，单词间的相关性就越强，PMI计算公式如下所示：

x和y表示两个单词，P(x,y)表示单词x和y共现的概率，P(x)表示单词x在上下文中出现概率。根据单词w

#(w

3.3计算偏移正点互信息值(Shifted Positive Pointwise MutualInformation，SPPMI)矩阵，SPPMI矩阵通过PMI值计算，SPPMI矩阵的计算方式为：

SPPMI(w

其中κ为负采样系数，通过上述公式得到单词的上下文SPPMI矩阵M；

第四步：基于第二步，第三步得到Mashup服务文档单词的文档-单词语义权重矩阵D，单词的上下文SPPMI矩阵M，通过分解M得到词嵌入信息矩阵，进一步将上述两种信息进行结合，计算服务的主题信息，步骤如下：

4.1通过由第二步给定全局文档-单词语义权重矩阵D，通过NMF将其分解为文档-主题矩阵θ和主题-单词矩阵Z乘积，分解矩阵D的函数表示为：

其中

4.2通过第三步计算得到单词的上下文SPPMI矩阵M，分解矩阵M引入词嵌入信息，分解M的公式如下所示：

S是一个额外的对称因子，用于M的近似求解，W为单词的词嵌入矩阵；

4.3利用Mashup服务文档和单词间的关系，可以发现主题信息，通过文档内单词上下文的共现信息，可以学习到词嵌入信息；但是这两个部分并不相互孤立，语义相关的单词属于相似的主题，在嵌入空间中也很接近；可知单词嵌入与它们的主题相关，关系公式如下所示：

4.4在步骤4.3中将主题-单词矩阵Z分解为主题嵌入矩阵A和词嵌入矩阵W的乘积，将词嵌入与主题信息相联系起来，进一步提高了主题建模的准确性；

结合步骤4.1，4.2和4.3，得到主题模型的目标函数：

求解该目标函数，使用矩阵迹运算将上述公式展开：

J(θ,Z,W,S,A)＝λ

+λ

+λ

其中J(θ,Z,W,S,A)为J

J(θ,Z,W,S,A)＝λ

+λ

+λ

Tr表示矩阵求迹，λ

其中α,β,γ,

令α⊙θ＝0,β⊙Z＝0,γ⊙W＝0,

-(DZ)⊙θ+(θZ

-(λ

-2(λ

-(Z

进一步更新参数：

通过上述参数更新方式，可求解出Mashup服务文档-主题矩阵θ和主题-单词矩阵Z，词嵌入矩阵W，主题嵌入矩阵A；

第五步：将4.4中得到的Mashup服务主题特征，作为谱聚类的输入进行聚类。谱聚类是从图论中演化出来的算法，后来在聚类中得到了广泛的应用；它的主要思想是把所有的数据看做空间中的点，这些点之间可以用边连接起来；距离较远的两个点之间的边权重值较低，而距离较近的两个点之间的边权重值较高。通过对所有数据点组成的图进行切图，让切图后不同的子图间边权重和尽可能的低，而子图内的边权重和尽可能的高，从而达到聚类的目的，步骤如下：

5.1计算相似度矩阵SI，服务主题特征之间的相似度可以高斯核函数计算。公式中θ

5.2将矩阵SI的每一列的元素相加，并将每一列作为元素添加到度矩阵G对角线上，公式如下。

G

5.3通过G计算Laplacian矩阵L＝G–SI；

5.4利用python中eig函数计算

其中arg min

5.5将特征值从小到大排序，取前C个特征值，C指定的聚类簇的数量，得到前C个特征值的特征向量，作为初始聚类中心；

5.6计算特征向量到聚类中心的欧式距离dist，将Mashup服务划分到距离最小的簇，计算公式如下：

其中f

5.7更新聚类中心为每个簇中特征向量累加的平局值；

5.8计算新聚类中心和旧聚类中心的欧式距离作为误差值；

5.9重复步骤5.6-5.8直至误差小于一定阈值，或者迭代次数到达最大迭代次数。

本说明书的实施例所述的内容仅仅是对发明构思的实现形式的列举，仅作说明用途。本发明的保护范围不应当被视为仅限于本实施例所陈述的具体形式，本发明的保护范围也及于本领域的普通技术人员根据本发明构思所能想到的等同技术手段。