论文部分内容阅读
摘要：随着信息技术的发展，人们由一个信息匮乏的时代进入到了信息爆炸的时代，大量信息通过媒体、互联网等各种途径冲击着人们的大脑。面对庞大的数据，人们很难找到他们想要的信息。为解决这种问题，研究者们开始着手在大量数据中挖掘有用的信息、对庞大的信息建立索引、在文档集中提取话题等方向。本文从专利文档角度出发，对公司的专利文档进行分析，提取其潜在的热点话题，并将其集成到专利检索系统Patent Miner中。在挖掘公司潜在信息，提高用户的搜索效率方面具有重要意义。
关键词：话题提取 话题模型 PLSA 专利分类 Google Chart Tools
1 概述
信息超载这个词最早出现在1970年AlvinTomer的《未来震撼》一书中并被人们所熟知[1]。进入信息时代，信息技术以前所未有的速度迅猛发展着，信息超载的现象越来越清晰地呈现在人们的眼前。随着网络技术的飞速发展，人们接受的信息正以各种形式纷至沓来，信息量的日益增多使得用户很难轻松准确地找到他们想要的信息。为解决这种问题，研究者们开始着手在大量数据中挖掘有用的信息、对庞大的信息建立索引、在文档集中提取主题等方向。
话题提取旨在挖掘文档集合中的重要信息，在学术信息检索领域具有重要的作用。研究者们很早就注意到了挖掘文本信息这个重要领域，并且做了很多研究。1990年Deerwester等人提出LSA模型，认为文档和单词之间还有一层潜在语义空间[2]，1998年Papadimitriou等人则在明确地指出文档和单词之间存在topic层[3]，后来的研究者们便开始从topic层面进行话题提取并衍生出一系列的模型以及应用。
本文从公司的专利文档入手，从topic层面试图提取公司的热点话题并分析其发展趋势，如图1所示。本文所实现的话题提取有两种思路，第一种主要基于PLSA算法，另外一种则是根据专利文档的特点，利用专利所属的类别名称来表示公司话题。由于篇幅有限，第二种方法就不进行介绍了。在公司话题趋势分析方面，本文利用Google Chart Tools图表将每个公司的话题演化趋势以折线图的方式展现给用户，方便用户浏览查看，提高用户查找效率。
■
图1 公司话题提取示例
2 研究目的及方法
随着计算机和互联网的迅猛发展，信息迎来了大爆炸时代。大量的数据的出现给人们的使用和选择都带来了困扰。话题的提取则可以有效地缓解这种困扰，用户不需要阅读大量的文献就可以发掘这些关键的信息，对于提高用户的搜索效率和工作效率以及提高网站的可用性方面都具有很重要的意义。
本研究课题是科研项目专利检索系统Patent Miner项目的一个子课题，在195，263家公司的海量专利数据的基础上对公司话题进行提取分析。实验采用Myeclipse开发平台，主要运用Java语言进行开发，并需要掌握一定的Html，CSS和JavaScript知识。
2.1 形式化的问题定义
给定一个公司A，让DA表示这个公司A所有文档的集合，即DA={d■■，d■■，…，d■■}。根据Bag-of-Words模型假设文档集合DA可以生成相应的字典W={w■■，w■■，…，w■■}，那么就可以把数据集表示成一个N×M的共生矩阵，其中N=（N（d■■，w■■））i，j，n（d■■，w■■）表示A公司中字典中的第j个单词在第i个文档中出现的次数。
我们可以将公司话题提取的问题描述如下：对于一个给定的公司A，M个该公司下文档的集合DA和对应的N×M的共生矩阵，我们的目标是：
找到几个topic，这些topic可以用字典中的词表示
根据PLSA模型，在文档与字典之间存在一层隐含语义空间topic，文档服从在topic上的多项分布θ，θ1+θ2+…+θk=1，（k≤N）；话题服从单词上的多项分布φ，φ1+φ2+…+φN=1。只要根据PLSA模型计算出topic在word上的分布，再对结果进行排序取概率最大的几个word即可。根据上面的定义，给出问题的最终定义：
问题2.1：基于PLSA模型的公司话题提取对于一个给定的公司，话题提取的目标是对全部文档集进行遍历，生成字典W和矩阵n（d■■，w■■），利用PLSA模型得出若干话题，并得出每个话题在word上的分布{P（wi|zj）imN，jmK}，并对其排序。
2.2 PLSA算法
Probabilistic Latent Semantic Analysis（PLSA） 是概率统计模型中经典的模型之一，是Latent semantic analysis（LSA）的改进版。
LSA是在传统的单词与文档的映射中间加入了潜在语义空间，通过奇异值分解（Singular Value Decomposition）的方式来求解这个潜在语义空间。由于基于SVD，迭代计算次数非常多，在处理海量文本数据时，文档和词的维度将急剧增加，使SVD的计算复杂度呈三次方增长。鉴于此，Hofmann于1999年提出一种基于概率的潜在语义分析PLSA模型。PLSA继承了“潜在语义”的概念，通过“统一的潜在语义空间”来关联词与文档；通过引入概率统计的思想，避免了SVD的复杂计算。由于统计技术的引用，PLSA可以解决模型拟合，模型结合，模型控制等问题，可以更有效的处理多义词并明确区分不同的含义和不同类型的词语用法。
PLSA的贝叶斯网络结构如图2所示。像其他所有的统计潜变量模型一样PLSA模型引入了条件独立性假设，即在潜在变量z下文档d和词w是相互独立的。其中w∈W={w1，…，wN}，d∈D={d1，…，dD}，z∈Z={z1，…，zK}，z≤N。
■
图2 PLSA结构图 在条件独立性假设下，整个数据集的生成过程如图3所示：
■
图3 PLSA的生成过程
通过上述生成过程，最终可以生成不含zk的可观察变量对（d，w）。该生成过程可以形式化为d与w联合概率：
P（d，w）=P（d）P（w|d），where P（w|d）=■P（w|z）P（z|d）
P（d，w）=P（d）■P（w|z）P（z|d） （2-1）
根据贝叶斯定理边缘化潜在话题z，则可观察变量（d，w）的联合概率可以表示为：
P（d，w）=■P（z）P（d|z）P（w|z） （2-2）
公式2-1和公式2-2是等价的，可以用贝叶斯法则推理得出。
在PLSA中使用最大似然估计来训练隐含量。最大似然
估计中比较常用的算法就是期望最大化算法，即Expectation-
Maximization（EM）算法，首先为参数赋予随机初值，之后根据更新公式迭代的更新参数值直到算法收敛。其中更新步骤包括Expectation（E）步和Maximization（M）步：
①Expectation Step——隐含参数的估计，根据当前的参数值计算隐含语义话题的后验概率P（d，w）；
②Maximization Step——确定实际参数，通过前面得到的参数的值最大化对数似然函数（公式2-1或者公式2-2），更新参数。
2.3 PLSA算法实现
本实验采用公式（2-2）的求解方法，求解P（z），P（w|z），P（d|z）。代码设计过程如下：
需要声明的变量：
double[][]p_dz，|D|*|Z|//P（d|z）
double[][]p_wz，|W|*|Z|//P（w|z）
double[]p_z，|Z|//P（z）
程序执行步骤如下：
①读取单词对应文档的矩阵数据
ArrayList doc； // all the docs
DocWordPair （word_id， word_frequency_in_doc）
②变量初始化
给变量P_dz，p_wz和p_z赋一个随机的double类型的值，满足∑dp_dz=1，∑dp_wz，∑dp_z=1
③迭代，直到最大似然估计小于给定的值threshold
计算P（z|w，d）
根据P（z|w，d）更新p_dz，d_wz和p_z的值
计算最大似然估计的对数Log-likelihood，看两次最大似然估计的差是否小于给定的阈值，差越小，越跟结果相似。
|Log-likelihood old_Log-likelihood| ④输出p_dz，p_wz和p_z
3 公司话题趋势分析及图形化表达
3.1 Google Chart Tools
实验采用Google Chart来进行公司话题趋势的展示。Google Chart是谷歌公司推出的一款免费的在线图表制作工具，相对于其他在线图表制作工具，Google chart 具有以下优点：
①在Google Chart Tool中数据和表现是分离的， 是MVC的思想。这样的好处是同一份数据可以用来显示曲线图，也可以显示成柱状图等等。
②图表呈现使用HTML5/SVG技术，提供跨浏览器兼容（包括旧版本的IE的VML）和跨平台的可移植性，可以完美地显示在iPhone，ipad以及Android上。这也是最主要的优势。
3.2 公司话题趋势的图形化表达
■图4 Exxon Mobil公司话题趋势
该部分实验是以利用专利所属的类别名称来表示公司话题的数据进行的。以Exxon Mobil公司为例，其话题趋势变化如图4所示。从图中的折线图变化趋势可以看出，从1976年至今Exxon Mobil公司一直致力于能源领域的工作，近年各个话题每年都有一定数量的专利发表，表明该公司研究方向没有太大变化。
4 总结
话题提取旨在提取文档集合中关键的、具有代表性的单词，可以提高搜索效率和用户体验，使学术信息检索领域具有重要的意义和价值。在这篇论文中，我们以专利检索系统Patent Miner为背景和数据来源，研究了公司话题提取的问题，主要基于PLSA话题模型来实现。通过对话题模型的学习、建模，实现了一个利用PLSA模型提取公司话题的系统。另外本文还根据专利自身的特点，探讨了一下利用USPTO的分类信息代表公司话题的研究，并且利用Google Chart Tools将该方法提取的公司话题数据显示在web页面上，图形显示部分则在Patent Miner上应用。
参考文献：
[1]维基百科.Information overload[EB/OL].http：//en.wikipedia.org/wiki/Information_overload.
[2]S.Deerwester，S.T.Dumais，G.W.Furnas，et al.Indexing by latentsemantic analysis[J].Journal of the AmericanSociety for Information Science，1990，41（6）：391-407.
[3]Christos H.Papadimitriou，Hisao Tamaki，PrabhakarRagha-
van，et al.Latent semantic indexing：a probabilistic analysis[A]. Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIG-
ART symposium on Principles of database systems，1998， 159-168.
关键词：话题提取 话题模型 PLSA 专利分类 Google Chart Tools
1 概述
信息超载这个词最早出现在1970年AlvinTomer的《未来震撼》一书中并被人们所熟知[1]。进入信息时代，信息技术以前所未有的速度迅猛发展着，信息超载的现象越来越清晰地呈现在人们的眼前。随着网络技术的飞速发展，人们接受的信息正以各种形式纷至沓来，信息量的日益增多使得用户很难轻松准确地找到他们想要的信息。为解决这种问题，研究者们开始着手在大量数据中挖掘有用的信息、对庞大的信息建立索引、在文档集中提取主题等方向。
话题提取旨在挖掘文档集合中的重要信息，在学术信息检索领域具有重要的作用。研究者们很早就注意到了挖掘文本信息这个重要领域，并且做了很多研究。1990年Deerwester等人提出LSA模型，认为文档和单词之间还有一层潜在语义空间[2]，1998年Papadimitriou等人则在明确地指出文档和单词之间存在topic层[3]，后来的研究者们便开始从topic层面进行话题提取并衍生出一系列的模型以及应用。
本文从公司的专利文档入手，从topic层面试图提取公司的热点话题并分析其发展趋势，如图1所示。本文所实现的话题提取有两种思路，第一种主要基于PLSA算法，另外一种则是根据专利文档的特点，利用专利所属的类别名称来表示公司话题。由于篇幅有限，第二种方法就不进行介绍了。在公司话题趋势分析方面，本文利用Google Chart Tools图表将每个公司的话题演化趋势以折线图的方式展现给用户，方便用户浏览查看，提高用户查找效率。
■
图1 公司话题提取示例
2 研究目的及方法
随着计算机和互联网的迅猛发展，信息迎来了大爆炸时代。大量的数据的出现给人们的使用和选择都带来了困扰。话题的提取则可以有效地缓解这种困扰，用户不需要阅读大量的文献就可以发掘这些关键的信息，对于提高用户的搜索效率和工作效率以及提高网站的可用性方面都具有很重要的意义。
本研究课题是科研项目专利检索系统Patent Miner项目的一个子课题，在195，263家公司的海量专利数据的基础上对公司话题进行提取分析。实验采用Myeclipse开发平台，主要运用Java语言进行开发，并需要掌握一定的Html，CSS和JavaScript知识。
2.1 形式化的问题定义
给定一个公司A，让DA表示这个公司A所有文档的集合，即DA={d■■，d■■，…，d■■}。根据Bag-of-Words模型假设文档集合DA可以生成相应的字典W={w■■，w■■，…，w■■}，那么就可以把数据集表示成一个N×M的共生矩阵，其中N=（N（d■■，w■■））i，j，n（d■■，w■■）表示A公司中字典中的第j个单词在第i个文档中出现的次数。
我们可以将公司话题提取的问题描述如下：对于一个给定的公司A，M个该公司下文档的集合DA和对应的N×M的共生矩阵，我们的目标是：
找到几个topic，这些topic可以用字典中的词表示
根据PLSA模型，在文档与字典之间存在一层隐含语义空间topic，文档服从在topic上的多项分布θ，θ1+θ2+…+θk=1，（k≤N）；话题服从单词上的多项分布φ，φ1+φ2+…+φN=1。只要根据PLSA模型计算出topic在word上的分布，再对结果进行排序取概率最大的几个word即可。根据上面的定义，给出问题的最终定义：
问题2.1：基于PLSA模型的公司话题提取对于一个给定的公司，话题提取的目标是对全部文档集进行遍历，生成字典W和矩阵n（d■■，w■■），利用PLSA模型得出若干话题，并得出每个话题在word上的分布{P（wi|zj）imN，jmK}，并对其排序。
2.2 PLSA算法
Probabilistic Latent Semantic Analysis（PLSA） 是概率统计模型中经典的模型之一，是Latent semantic analysis（LSA）的改进版。
LSA是在传统的单词与文档的映射中间加入了潜在语义空间，通过奇异值分解（Singular Value Decomposition）的方式来求解这个潜在语义空间。由于基于SVD，迭代计算次数非常多，在处理海量文本数据时，文档和词的维度将急剧增加，使SVD的计算复杂度呈三次方增长。鉴于此，Hofmann于1999年提出一种基于概率的潜在语义分析PLSA模型。PLSA继承了“潜在语义”的概念，通过“统一的潜在语义空间”来关联词与文档；通过引入概率统计的思想，避免了SVD的复杂计算。由于统计技术的引用，PLSA可以解决模型拟合，模型结合，模型控制等问题，可以更有效的处理多义词并明确区分不同的含义和不同类型的词语用法。
PLSA的贝叶斯网络结构如图2所示。像其他所有的统计潜变量模型一样PLSA模型引入了条件独立性假设，即在潜在变量z下文档d和词w是相互独立的。其中w∈W={w1，…，wN}，d∈D={d1，…，dD}，z∈Z={z1，…，zK}，z≤N。
■
图2 PLSA结构图 在条件独立性假设下，整个数据集的生成过程如图3所示：
■
图3 PLSA的生成过程
通过上述生成过程，最终可以生成不含zk的可观察变量对（d，w）。该生成过程可以形式化为d与w联合概率：
P（d，w）=P（d）P（w|d），where P（w|d）=■P（w|z）P（z|d）
P（d，w）=P（d）■P（w|z）P（z|d） （2-1）
根据贝叶斯定理边缘化潜在话题z，则可观察变量（d，w）的联合概率可以表示为：
P（d，w）=■P（z）P（d|z）P（w|z） （2-2）
公式2-1和公式2-2是等价的，可以用贝叶斯法则推理得出。
在PLSA中使用最大似然估计来训练隐含量。最大似然
估计中比较常用的算法就是期望最大化算法，即Expectation-
Maximization（EM）算法，首先为参数赋予随机初值，之后根据更新公式迭代的更新参数值直到算法收敛。其中更新步骤包括Expectation（E）步和Maximization（M）步：
①Expectation Step——隐含参数的估计，根据当前的参数值计算隐含语义话题的后验概率P（d，w）；
②Maximization Step——确定实际参数，通过前面得到的参数的值最大化对数似然函数（公式2-1或者公式2-2），更新参数。
2.3 PLSA算法实现
本实验采用公式（2-2）的求解方法，求解P（z），P（w|z），P（d|z）。代码设计过程如下：
需要声明的变量：
double[][]p_dz，|D|*|Z|//P（d|z）
double[][]p_wz，|W|*|Z|//P（w|z）
double[]p_z，|Z|//P（z）
程序执行步骤如下：
①读取单词对应文档的矩阵数据
ArrayList
DocWordPair （word_id， word_frequency_in_doc）
②变量初始化
给变量P_dz，p_wz和p_z赋一个随机的double类型的值，满足∑dp_dz=1，∑dp_wz，∑dp_z=1
③迭代，直到最大似然估计小于给定的值threshold
计算P（z|w，d）
根据P（z|w，d）更新p_dz，d_wz和p_z的值
计算最大似然估计的对数Log-likelihood，看两次最大似然估计的差是否小于给定的阈值，差越小，越跟结果相似。
|Log-likelihood old_Log-likelihood|
3 公司话题趋势分析及图形化表达
3.1 Google Chart Tools
实验采用Google Chart来进行公司话题趋势的展示。Google Chart是谷歌公司推出的一款免费的在线图表制作工具，相对于其他在线图表制作工具，Google chart 具有以下优点：
①在Google Chart Tool中数据和表现是分离的， 是MVC的思想。这样的好处是同一份数据可以用来显示曲线图，也可以显示成柱状图等等。
②图表呈现使用HTML5/SVG技术，提供跨浏览器兼容（包括旧版本的IE的VML）和跨平台的可移植性，可以完美地显示在iPhone，ipad以及Android上。这也是最主要的优势。
3.2 公司话题趋势的图形化表达
■图4 Exxon Mobil公司话题趋势
该部分实验是以利用专利所属的类别名称来表示公司话题的数据进行的。以Exxon Mobil公司为例，其话题趋势变化如图4所示。从图中的折线图变化趋势可以看出，从1976年至今Exxon Mobil公司一直致力于能源领域的工作，近年各个话题每年都有一定数量的专利发表，表明该公司研究方向没有太大变化。
4 总结
话题提取旨在提取文档集合中关键的、具有代表性的单词，可以提高搜索效率和用户体验，使学术信息检索领域具有重要的意义和价值。在这篇论文中，我们以专利检索系统Patent Miner为背景和数据来源，研究了公司话题提取的问题，主要基于PLSA话题模型来实现。通过对话题模型的学习、建模，实现了一个利用PLSA模型提取公司话题的系统。另外本文还根据专利自身的特点，探讨了一下利用USPTO的分类信息代表公司话题的研究，并且利用Google Chart Tools将该方法提取的公司话题数据显示在web页面上，图形显示部分则在Patent Miner上应用。
参考文献：
[1]维基百科.Information overload[EB/OL].http：//en.wikipedia.org/wiki/Information_overload.
[2]S.Deerwester，S.T.Dumais，G.W.Furnas，et al.Indexing by latentsemantic analysis[J].Journal of the AmericanSociety for Information Science，1990，41（6）：391-407.
[3]Christos H.Papadimitriou，Hisao Tamaki，PrabhakarRagha-
van，et al.Latent semantic indexing：a probabilistic analysis[A]. Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIG-
ART symposium on Principles of database systems，1998， 159-168.