文本聚类分析结果可视化方法研究

情报学报　 　 　

doi:10.3772/j. issn. 1000⁃0135. 2011. 02. 001

=

ISSN 1000-0135第30卷第2期115-120, 2011年2月

JOURNAL OF THE CHINA SOCIETY FOR SCIENTIFIC AND TECHNICAL INFORMATION ISSN 1000-0135

February 2011Vol. 30No. 2, 115-120

文本聚类分析结果可视化方法研究1)

吴江宁　 王桂才

(大连理工大学系统工程研究所, 大连116024)

摘要　 　 针对文本聚类分析结果表达中缺乏语义关系的缺陷, 本文利用人们在可视化形式下对模型和结构的理解和

获取能力, 提出了一种新的可视化表达方法㊂ 通过改进的Force⁃directed 模型对聚类分析结果进行文本布局, 表现文本间的语义相似关系; 使用等值线生成算法构建层次性主题图, 聚集和提炼文本主题; 最终实现文本聚类分析结果的语义直观表达㊂ 实验结果表明, 这种可视化方法不仅能够有效地表达聚类结果, 体现类间㊁ 文本间的语义相关程度, 而且还有助于发现隐含的信息, 并通过类别之间的关联实现有效的信息导航㊂

关键词　 　 可视化　 布局算法　 文本聚类　 主题图

Research on the Visualization Method for Text Clustering Results

Wu Jiangning and Wang Guicai

(Institute of Systems Engineering , Dalian University of Technology , Dalian 116024)

visual way. Through the improved Force⁃directed model, the clustering results of texts are projected onto a plane, whose layout

visualization method is proposed, which helps people to fully understand the model and structure of original textual data in the

Abstract 　 　 Considering the lack of semantic relations in the expression of current text clustering analysis, a new

Keywords 　 　 visualization, placement algorithm, text clustering, theme map

the clustering analysis, but also facilitates to find the hidden knowledge and retrieve the information between clusters.

semantic form. Experiments show that the proposed method not only expresses the difference between clusters and texts during

to show the distribution of textual themes. As a result, the textual clustering results can be represented in a more intuitive and

represents the semantic relations between texts. Furthermore, a hierarchical theme map is constructed by the contour algorithm

1　 引　 言

文本聚类分析是数据挖掘㊁ 知识发现的重要手的㊁ 对决策有潜在价值的信息[1]㊂ 用可视化的方法模型和结构的直观理解力, 解决信息量大㊁ 无法快速和有效交流的问题, 同时可视化技术可帮助观察㊁ 筛选㊁ 发现和理解信息, 发现隐藏在数据和信息背后的知识[2]㊂ 经典的可视化形式有简单图, 如树图㊁ 平面

　 　 收稿日期:2009年11月6日

图㊁ 有向图㊁ 无向图等, 最近的研究趋向于复杂的可视化表现方式, 如复合图和聚类图[3]等, 这些复杂图形能够表达更全面的信息和较复杂的知识结构㊂

目前的研究中多采用饼图㊁ 柱状㊁ 导航式的树型结构标签等形式来表现文本聚类分析结果, 但是这些表现形式往往只能反映聚类结果中类与类之间的数量关系㊁ 类内成员的比例关系以及隶属关系等, 由于丢失了文本及其之间的语义信息, 所以这类可视化表示方法不能进一步利用成员的内容信息反映语义关系[4], 增加了对聚类分析结果理解的困难㊂

为了充分表现聚类簇内文本间的语义关系, 以

段, 可以从海量的数据集合中抽取隐含的㊁ 先前未知

对聚类结果进行表示, 能很好地利用人们对可视化

才, 男,1984年生, 硕士研究生, 研究方向:知识可视化㊂

　 　 作者简介:吴江宁, 女,1964年生, 教授, 主要研究领域:知识发现与获取㊁ 知识可视化㊂ E⁃mail:jnwu@ dlut,edu. cn㊂ 王桂

　 　 1)　 国家自然科学基金资助项目(70771019),国家高科技研究发展计划863资助项目(2008AA04Z107)㊂

115

情报学报　 第30卷　 第2期　 2011年2月

提高聚类分析结果表达的直观性和易理解性, 结合信息可视化技术的优势, 本文提出了一种适于中文文本聚类分析结果可视化的方法㊂ 该方法充分利用文本聚类结果的树形结构的层次特点以及文本之间的语义关系进行文档抽象布局; 通过山峰模型形成等值线, 进而构建主题图的可视化表现形式用以表现文本集合中的语义关系㊂ 在文本抽象布局时, 采用了改进的Force⁃directed 布局算法, 提高了语义相似性与直观距离之间的表现程度; 使用等值线表现文本的聚集程度, 提高了聚类分析结果的可理解性, 有利于发现新模式㊁ 新知识㊂

包含了一个语义图G 和一个层次树T , 层次树T 仅反映聚类文本的层次关系㊂ G 中的每个结点是T 中的叶结点, T 中的每个结点代表一个类V '(n ) , 其中V '(n ) 是T 中以n 为根结点的子树的所有叶结点㊂ 聚类层次分解图如图1所示㊂

图中, 实心结点代表分析的文本, 所有实心结点构成了V , 它们之间的关系构成了E , 图G 代表现存文本及其相互关系的集合; 虚拟结点(虚线表示) 代表聚类分析中得到的包含相关文本的类㊂

本文正是利用上述文本间的语义关系和聚类层次关系对聚类结果进行可视化表示㊂ 这种方法不仅能够表现已知的信息和关系, 而且有助于挖掘信息中隐藏的知识和规律㊂

2. 2　 可视化流程

2　 方法总体思想

本文的核心思想是利用文本聚类结果的树形结构层次特点以及文本间的语义相似程度, 根据聚类分析结果中的类间㊁ 类成员间以及类与成员间的信息设计平面布局方法, 并根据平面布局数据自动生成直观的㊁ 具有层次信息的可视化主题图㊂

2. 1　 聚类层次图的定义

本文可视化方法分为两个步骤:文本可视化布局和主题图构建㊂

2. 2. 1　 文本聚类可视化布局

文本布局的目的是在二维平面上用直观可测的距离表现文本内容间的语义相似程度:相似程度较高的文本, 距离较近, 聚集在一个区域, 不相似的文本则相互分离, 因此在二维平面上可形成疏密有致的分布效果㊂ 流程如图2所示㊂

语义图G =(V , E ) 包含一个有限点集合V 和有限边集合E ⊆ V × V , 是文本之间语义关系的表达, V 是文本的集合, E 是关系的结合㊂ 聚类图C =(G , T )

　

图1　 聚类层次分解图

116

文本聚类分析结果可视化方法研究

图2　 文本聚类布局流程框图

2. 2. 2　 主题图构建

主题图构建是用等值线的形式分区域㊁ 分层次地表现文本的聚集情况, 反映文本间的语义相似关系, 进一步地表现文本集合的主题提取和分布状况, 从而形成更加形象的 信息岛屿” 形式的主题图㊂

下面将分别详述文本布局和主题图构建的模型与方法㊂

3　 文本布局模型与方法

在图形布局领域, 有多种布局模型和算法, 其中基于Force⁃directed 和Energy⁃based 的布点绘图方法被广泛应用于无向图㊂ 本文的文本布局方法是基于经典

, 并可使用不同的可视化标准给出满意效果

[5]

的Force⁃directed 方法[6]改进的Force⁃directed 方法通过模拟物理中的弹簧力, 并在此基础上进行改进㊂ 和电子力来计算类及其成员的运动方向和距离㊂ 两

个对象间的理想距离定义为其语义相关程度, 所有对象在弹簧力的作用下向理想距离位置移动㊂ 当所有对象之间的距离达到理想距离时, 对象相对静止, 达到相对稳态㊂ 此时, 对象间的相对位置反映了它们之间的语义相似程度㊂

该方法包含两部分:力和能量评估模型以及一个对象集达到稳态的算法㊂

3. 1　 力模型

根据文本可视化布局的思想, 布局中需处理的对象有两类:文本对象和虚拟类对象, 这里我们使用类的质心表示类㊂ 根据处理目的㊁ 对象及其关系的不同, 我们在不同的对象之间分别建立不同的力模型:弹簧力模型和电子力模型㊂

3. 1. 3　 弹簧力模型

弹簧力模型是模拟物理中弹簧两端的对象通过

弹簧的相互作用, 该种力是为了将两个对象控制在代表其语义相似程度的理想距离附近, 适用于存在语义关系的对象(1)F ㊂ 该模型中的弹簧力分为以下四种:s (1)中的虚线所示㊂ :同一层次中类质心之间的力, 如图3点划线所示(2)F s (2)㊂ :质心和子结点之间的力, 如图3中的实线所示(3)F s (3)㊂

:同一类中文本之间的力, 如图3中的弱, 如图(4)3F s (4)中的粗短线所示

:结点与其他质心之间的力㊂

, 该力最

图3　 力模型

任何两个存在语义关系的对象(质心/文本) 间

的弹簧力借鉴经典的弹簧力计算公式[7]给出:

, 可由下式F s (a , b ) =k s (i )

d (a (0

l a , b

=-F s (b , a )

s (i ) 其中, k

s (i ) 是弹簧系数, 代表对象间的关系类型对力的影响程度, 比如, 对象是同一类时k s 则大, 对象属于不同类时k s 则小; d (a , b ) 是对象a , b 之间的可视化距离; l a , b 是a , b 之间的理想距离, 它是a , b 之间的相似度sim (a , b ) ㊁ 调节参数α , β 的函数㊂

其中, α , β 是可调参数(100l a , b =

2

α ㊂ 其中

117

情报学报　 第30卷　 第2期　 2011年2月

标准距离㊂

3. 1. 4　 电子力模型

电子力模型模拟物理中电子之间的相互作用, 使得对象相互排斥, 避免重叠, 起到辅助布局的作用, 适用于所有的对象㊂

任何两个对象(质心/文本) 之间的电子力计算公式:

(a )=∑ F e (a , b ); (a );

☆　 计算a 与所有其他点间的电子力之和:F e

☆　 计算a 受到的力的总和:F (a )=F s (a ) +F e ☆　 根据受到的力与平衡关系, 计算a 的新Step 3:

对布局系统进行能量评估:E (p ); 位置;

F e (a , b ) =k e

b ) 是对象d q a q b

=-F e (b , a )

a (, a b , b 之间的可视化距离)) 2

(3)

其中, d (a , ; q q a 和

b 是两个常量; k e 是电子斥力系数, 代表对象间的关系类型对力的影响程度, 比如, 同一类中对象间的排斥力比不同类中对象间的排斥力要小, 相应的k e 也小㊂

3. 2　 能量评估模型

每种布局都是文本聚类分析结果映射到二维或三维空间中的映射函数p , 我们使用能量评估函数E 评价各种映射函数p 的布局效果㊂

布局中的对象在力的作用下向理想的位置移动, 在整个布局系统中产生能量E (p ), 形成不稳定状态; 对象通过移动不断被布局在理想位置附近, 系统的能量E (p ) 也逐渐变小, 布局效果不断优化; 当E (p ) 达到全局最小时, 映射函数p 将得到最优的布局效果㊂ 所以, 能量评估模型定义如下(4)

其中, v ∑ :

E (p ) =

o

v 2o o 是对象o 在力的作用下运动的速度, v 2o

是对象o 的能量㊂

3. 3　 算法

聚类分析结果的布局既要尽可能地保留文本间语义相关程度的信息, 又要尽可能地反映聚类层次信息㊂ 该算法通过对象间的理想距离和可视化距离计算施加在对象之间的力, 根据力的大小和布局能量对布局进行调整, 最终达到最优的布局效果㊂

算法主要步骤描述如下:Step 1:

随机初始化布局和能量阈值θ ; Step 2:对于每个点a :

的和☆　 :F 计算a 与其存在语义关系的点间的弹簧力

s (a )=∑ F s (a , b );

118

Step 4:

如果E (p )

执行Step 5;

Step 5:

根据所有点的新位置, 更新布局㊂ 然后返回Step 2㊂

4　 主题图构建

通过文本布局方法可得到表现文本语义相似关系的二维平面布局图㊂ 在该布局图中, 主题相近的文本被组织在一起形成高密度的区域, 而主题不集中的 文本相互分散形成稀疏的区域, 我们用更加形象的

现为具有高山峰的岛屿信息岛屿” 来表现这种布局, 它们通过低山峰的岛屿相㊂ 其中, 密度高的区域表连, 每个山峰代表一个相关的主题, 山峰的高低代表主题的聚集程度㊂ 使用这种表现形式, 可以很容易地定位感兴趣的区域和导航浏览相关文本㊂

主题图构建方法是基于一个山峰模型和等值线生成算法实现的㊂

4. 1　 山峰模型

布局中的每一个文本对象表示为一个小山峰㊂ 如果在一个小的区域内文本对象相互聚集, 重叠的山峰和高度将进行叠加, 构成更大和更高的结构 山脉 文本的主题

㊂

图4　 山峰模型图

山峰模型的构建公式和效果图如公式(5)和图

文本聚类分析结果可视化方法研究

4所示:

z (x , y ) =λ *e-θ *((x -x 0)

2+(y -y ) 2)

其中, (x 0, y 0) 是文本对象布局中的坐标, z (x , y ) 表示高度值, λ 控制山峰的高度, θ 控制山峰的影响范围

(λ >0,θ >0) 　 (5)

受(x 0, y 0) 处山峰模型的影响, (x , y ) 处所形成的

其中, (X , Y ) 是特定高度Z 的点的坐标, 已知(x 1, y 1) 和(x 2, y 2) 的高度分别是z 1和z 2㊂ 两个等值点的连线就是一条等值线片段㊂

4. 2. 3　 等值线追踪

ìïX =x 1+Z -z 1(x 2-x 1)

2-z 1ï

　 í

Z -z 1ï

ïY =y 1+-z (y 2-y 1) î21

(z 1≤ z 0≤ z 2) 　 (6)

的大小㊂

4. 2　 等值线生成算法

绘制等值线是对大量离散的㊁ 又具有一定规律的几何量值或物理量值用数学的方法插值并转换成图的过程, 常采用网格法, 广泛应用于测绘㊁ 地理信息系统等领域[8]般为:离散数据网格化㊂ 各种网格法绘制等值线的步骤一

㊁ 网格点数值化㊁ 等值点的计算㊁ 等值线追踪㊁ 光滑和标记等值线㊁ 填充等值线区域等㊂

本文根据文本可视化的需要, 提出基于网格法的等值线生成算法, 通过高度值构建㊁ 等值点计算㊁ 等值线追踪和等值线区域着色4个步骤构建主题图㊂

4. 2. 1　 高度值构建

可视化视野由许多网格组成, 根据文本对象在可视化视野中的布局和山峰模型的思想, 将叠加的高度值赋予相关的网格上的点㊂ 这样就构建了反映文本对象布局特征的高度值㊂

4. 2. 2　 等值点计算

特定高度的点构成了等值线, 然而网格中的点是离散的数据点, 具有离散的高度㊂ 所以, 本文利用插值法计算等值点

㊂

图5　 网格切分

如图5所示, 每一个网格可以分两个三角形㊂ 对于任意一个三角形, 使用插值法计算落在边上的等值点的公式为:

对不同高度的等值点所构成的等值线片段进行追踪则可连接成一个整体㊂ 根据等值线的构成不同, 本文将其分为封闭等值线和非封闭等值线, 并提出如下等值线追踪算法描述:

输入:网格点高度值集, 特定高度序列输出:等值线集序列对于每一特定高度:Step 1:

等值线段首尾相接构成等值线片段; Step 2:

如果存在等值线片段, 继续; 否则输出等值线集序列;

Step 3:

如果等值线片段首尾端点不同, 继续; 否则转Step 7;

Step 4:

等值线片段首尾相接; Step 5:

如果端点不是边界点, 转Step 3; 否则转Step 6; Step 6:

生成边界等值线, 转Step 8; Step 7:

生成封闭等值线, 转Step 8; Step 8:

剔除连接所用的等值线片段, 转Step 2㊂ 4. 2. 4　 等值线区域着色

对生成的等值线图区域, 根据一定的梯度进行着色, 构建具有层次的主题图㊂

5　 实验及结果分析

为进一步说明本文提出方法的直观性和有效性, 将其应用于专利领域, 并进行分析说明㊂

实验数据来自于国家知识产权局[9], 为清晰地展

119

情报学报　 第30卷　 第2期　 2011年2月

示聚类结果及主题的分布情况, 本文仅提取40篇类别下的专利申请书, 使用经典的凝聚层次聚类分析方法进行分析, 并使用参考文献[10]所提出的方法概化出6个类别(如表1所示), 形成三层聚类结果树, 即原始文本层㊁6 个类别层和顶层抽象文本集层㊂

G06Q10/00(用于行政㊁ 管理的数据处理系统或方法)

局在一起, 形成高的等值区域, 反映出该区域的专利聚焦于同一领域的相同技术㊂

图中空心的专利点是关注的专利, 并显示出该专利的申请号和专利名称; 根据实际需要, 可依据图中与其位置的相近程度来分析相关的专利, 为非领域专家进行专利分析提供信息导航功能㊂

表1　 专利聚类分析结果

类别专利数主题词

Cluster_13购买㊁ 信息发布㊁ 软件产品㊁ 产品㊁ 指纹㊁ 指纹验证㊁ 广告㊁ 下载㊁ 互联网络㊁ 经营场所Cluster_28应用程序㊁ 可视化㊁ 商业应用㊁ 购物㊁ 文件管理系统㊁ 管理信息㊁ 邮件地址㊁ 邮件㊁ 任务㊁ 应用

Cluster_35管理功能㊁ 资产㊁ 控制器㊁ 物品㊁ 电池㊁ 控制㊁ 装置㊁ 资产管理㊁ 风险评估㊁ 管理方案Cluster_413交易㊁ 代码㊁ 认证㊁ 确认㊁ 车辆㊁ 评估㊁ 读取㊁ 设备㊁ 多功能㊁ 指令

Cluster_57邮件㊁ 上下文㊁ 知识管理㊁ 集成㊁ 文档㊁ 管理系统㊁ 集成方法㊁ 集成服务㊁ 重要㊁ 无线通讯网络

Cluster_6

4

打印㊁ 垃圾邮件㊁ 税务㊁ 彩票㊁ 公安㊁ 监控㊁ 邮件㊁ 垃圾㊁ 系统软件㊁ 打印机

应用本文提出的方法得到的可视化结果如图6所示㊂ 其中每个节代表一篇专利文本, 而点之间的距离表示了全局中两点之间的语义相似程度㊂ 相似度大的文本点之间距离小, 反之距离大㊂

Cluster_3,Cluster_4,Cluster_6)图6明显地由5个山峰(Cluster_1,Cluster_2,

与聚类分析结果基本对应㊂ Cluster_5组成, 构成形成的山峰不5个主题, 5明显和Cluster_4, 和Cluster_4的语义相似程度较大基本在一个山脉中, 是, 说明Cluster_4Cluster_题中的外围专利主题类㊂ 这是在其他非可视化的聚

主类分析结果表达中无法得到的隐含模式㊂

ｕｓ铸ｊ

斤五丙而雨丽正霸再趸丽雨露丽丽焉爱蚕碾

图6　 可视化实例

利用等值线构建的主题图还可反映专利文本中的主题聚集情况及其层次关系㊂ 主题相似的专利布

120

6　 结　 论

针对文本聚类分析结果表达中忽略语义层面信息造成的信息丢失㊁ 不易理解等问题, 本文提出一种以主题图方式表达聚类结果的可视化方法㊂ 充分利用聚类分析结果中的层次关系和聚类文本间的语义相似关系, 通过改进Force⁃directed 布局方法, 对聚类分析后的文本进行布局; 并通过构建山峰模型生成等值线, 构建层次性的可视化主题图㊂ 实验表明, 使用该可视化方法不仅能较充分地反映文本间的语义关系, 还能有助于发现其中隐含的知识模式和结构, 实现有效的知识导航㊂

参　 考　 文　 献

[1]　杨峰方法研究, 周宁[J]., 吴佳鑫情报学报. 基于信息可视化技术的文本聚类

,2005,24(6):679⁃683.[2]　北京周宁:, 科学出版社张玉锋, 张李义,2005. . 信息可视化与知识检索[M].[3]　Drawing

Eades P , Algorithms

Feng Q W , Lin for

X Hierarchical

M , et al . Straight Graphs

⁃ Line

Clustered 周宁, 吴佳鑫Graphs[J]., 张少龙Algorithmica,2006,44(1):1⁃32.and

[4]　析[J].情报学报,2008,27(5):714⁃720.. 基于图的Web 信息可视化探[5]　London:Springer⁃Verlag,2001.

Brandes U. Drawing Graphs:Methods and Models[M].[6]　Fruchterman T M J,Reingold E M. Graph drawing by

[7]　Experience,1991,21(11):1129⁃1164.

force⁃directed placement [J ].Software Practice &

Eades drawing P,Huang using a Ｃｌｕ

modified M L,Wang spring J H. algorithm[J].Online animated Journal graph

[8]　Visual 孙桂茹Languages and Computing,1998,9:17⁃28.of

法[J]., 天马亮津, 大路登平学学报, 等(自. 等值线生成与图形填充算

然科学与工程技术版),

[9]　2000,33(06):816⁃818.

www. 国家sipo. 知识gov. 产权cn 局/sipo2008专利检/索zljs . /.[2009⁃05⁃12 ].http://

[10]　吴江宁[J].情报学报, 田海燕,2007,26(3):323⁃331.

. 基于主题地图的文献组织方法研究

(责任编辑　 马　 兰)

情报学报　 　 　

doi:10.3772/j. issn. 1000⁃0135. 2011. 02. 001

=

ISSN 1000-0135第30卷第2期115-120, 2011年2月

JOURNAL OF THE CHINA SOCIETY FOR SCIENTIFIC AND TECHNICAL INFORMATION ISSN 1000-0135

February 2011Vol. 30No. 2, 115-120

文本聚类分析结果可视化方法研究1)

吴江宁　 王桂才

(大连理工大学系统工程研究所, 大连116024)

摘要　 　 针对文本聚类分析结果表达中缺乏语义关系的缺陷, 本文利用人们在可视化形式下对模型和结构的理解和

获取能力, 提出了一种新的可视化表达方法㊂ 通过改进的Force⁃directed 模型对聚类分析结果进行文本布局, 表现文本间的语义相似关系; 使用等值线生成算法构建层次性主题图, 聚集和提炼文本主题; 最终实现文本聚类分析结果的语义直观表达㊂ 实验结果表明, 这种可视化方法不仅能够有效地表达聚类结果, 体现类间㊁ 文本间的语义相关程度, 而且还有助于发现隐含的信息, 并通过类别之间的关联实现有效的信息导航㊂

关键词　 　 可视化　 布局算法　 文本聚类　 主题图

Research on the Visualization Method for Text Clustering Results

Wu Jiangning and Wang Guicai

(Institute of Systems Engineering , Dalian University of Technology , Dalian 116024)

visual way. Through the improved Force⁃directed model, the clustering results of texts are projected onto a plane, whose layout

visualization method is proposed, which helps people to fully understand the model and structure of original textual data in the

Abstract 　 　 Considering the lack of semantic relations in the expression of current text clustering analysis, a new

Keywords 　 　 visualization, placement algorithm, text clustering, theme map

the clustering analysis, but also facilitates to find the hidden knowledge and retrieve the information between clusters.

semantic form. Experiments show that the proposed method not only expresses the difference between clusters and texts during

to show the distribution of textual themes. As a result, the textual clustering results can be represented in a more intuitive and

represents the semantic relations between texts. Furthermore, a hierarchical theme map is constructed by the contour algorithm

1　 引　 言

文本聚类分析是数据挖掘㊁ 知识发现的重要手的㊁ 对决策有潜在价值的信息[1]㊂ 用可视化的方法模型和结构的直观理解力, 解决信息量大㊁ 无法快速和有效交流的问题, 同时可视化技术可帮助观察㊁ 筛选㊁ 发现和理解信息, 发现隐藏在数据和信息背后的知识[2]㊂ 经典的可视化形式有简单图, 如树图㊁ 平面

　 　 收稿日期:2009年11月6日

图㊁ 有向图㊁ 无向图等, 最近的研究趋向于复杂的可视化表现方式, 如复合图和聚类图[3]等, 这些复杂图形能够表达更全面的信息和较复杂的知识结构㊂

目前的研究中多采用饼图㊁ 柱状㊁ 导航式的树型结构标签等形式来表现文本聚类分析结果, 但是这些表现形式往往只能反映聚类结果中类与类之间的数量关系㊁ 类内成员的比例关系以及隶属关系等, 由于丢失了文本及其之间的语义信息, 所以这类可视化表示方法不能进一步利用成员的内容信息反映语义关系[4], 增加了对聚类分析结果理解的困难㊂

为了充分表现聚类簇内文本间的语义关系, 以

段, 可以从海量的数据集合中抽取隐含的㊁ 先前未知

对聚类结果进行表示, 能很好地利用人们对可视化

才, 男,1984年生, 硕士研究生, 研究方向:知识可视化㊂

　 　 作者简介:吴江宁, 女,1964年生, 教授, 主要研究领域:知识发现与获取㊁ 知识可视化㊂ E⁃mail:jnwu@ dlut,edu. cn㊂ 王桂

　 　 1)　 国家自然科学基金资助项目(70771019),国家高科技研究发展计划863资助项目(2008AA04Z107)㊂

115

情报学报　 第30卷　 第2期　 2011年2月

提高聚类分析结果表达的直观性和易理解性, 结合信息可视化技术的优势, 本文提出了一种适于中文文本聚类分析结果可视化的方法㊂ 该方法充分利用文本聚类结果的树形结构的层次特点以及文本之间的语义关系进行文档抽象布局; 通过山峰模型形成等值线, 进而构建主题图的可视化表现形式用以表现文本集合中的语义关系㊂ 在文本抽象布局时, 采用了改进的Force⁃directed 布局算法, 提高了语义相似性与直观距离之间的表现程度; 使用等值线表现文本的聚集程度, 提高了聚类分析结果的可理解性, 有利于发现新模式㊁ 新知识㊂

包含了一个语义图G 和一个层次树T , 层次树T 仅反映聚类文本的层次关系㊂ G 中的每个结点是T 中的叶结点, T 中的每个结点代表一个类V '(n ) , 其中V '(n ) 是T 中以n 为根结点的子树的所有叶结点㊂ 聚类层次分解图如图1所示㊂

图中, 实心结点代表分析的文本, 所有实心结点构成了V , 它们之间的关系构成了E , 图G 代表现存文本及其相互关系的集合; 虚拟结点(虚线表示) 代表聚类分析中得到的包含相关文本的类㊂

本文正是利用上述文本间的语义关系和聚类层次关系对聚类结果进行可视化表示㊂ 这种方法不仅能够表现已知的信息和关系, 而且有助于挖掘信息中隐藏的知识和规律㊂

2. 2　 可视化流程

2　 方法总体思想

本文的核心思想是利用文本聚类结果的树形结构层次特点以及文本间的语义相似程度, 根据聚类分析结果中的类间㊁ 类成员间以及类与成员间的信息设计平面布局方法, 并根据平面布局数据自动生成直观的㊁ 具有层次信息的可视化主题图㊂

2. 1　 聚类层次图的定义

本文可视化方法分为两个步骤:文本可视化布局和主题图构建㊂

2. 2. 1　 文本聚类可视化布局

文本布局的目的是在二维平面上用直观可测的距离表现文本内容间的语义相似程度:相似程度较高的文本, 距离较近, 聚集在一个区域, 不相似的文本则相互分离, 因此在二维平面上可形成疏密有致的分布效果㊂ 流程如图2所示㊂

语义图G =(V , E ) 包含一个有限点集合V 和有限边集合E ⊆ V × V , 是文本之间语义关系的表达, V 是文本的集合, E 是关系的结合㊂ 聚类图C =(G , T )

　

图1　 聚类层次分解图

116

文本聚类分析结果可视化方法研究

图2　 文本聚类布局流程框图

2. 2. 2　 主题图构建

主题图构建是用等值线的形式分区域㊁ 分层次地表现文本的聚集情况, 反映文本间的语义相似关系, 进一步地表现文本集合的主题提取和分布状况, 从而形成更加形象的 信息岛屿” 形式的主题图㊂

下面将分别详述文本布局和主题图构建的模型与方法㊂

3　 文本布局模型与方法

在图形布局领域, 有多种布局模型和算法, 其中基于Force⁃directed 和Energy⁃based 的布点绘图方法被广泛应用于无向图㊂ 本文的文本布局方法是基于经典

, 并可使用不同的可视化标准给出满意效果

[5]

的Force⁃directed 方法[6]改进的Force⁃directed 方法通过模拟物理中的弹簧力, 并在此基础上进行改进㊂ 和电子力来计算类及其成员的运动方向和距离㊂ 两

个对象间的理想距离定义为其语义相关程度, 所有对象在弹簧力的作用下向理想距离位置移动㊂ 当所有对象之间的距离达到理想距离时, 对象相对静止, 达到相对稳态㊂ 此时, 对象间的相对位置反映了它们之间的语义相似程度㊂

该方法包含两部分:力和能量评估模型以及一个对象集达到稳态的算法㊂

3. 1　 力模型

根据文本可视化布局的思想, 布局中需处理的对象有两类:文本对象和虚拟类对象, 这里我们使用类的质心表示类㊂ 根据处理目的㊁ 对象及其关系的不同, 我们在不同的对象之间分别建立不同的力模型:弹簧力模型和电子力模型㊂

3. 1. 3　 弹簧力模型

弹簧力模型是模拟物理中弹簧两端的对象通过

弹簧的相互作用, 该种力是为了将两个对象控制在代表其语义相似程度的理想距离附近, 适用于存在语义关系的对象(1)F ㊂ 该模型中的弹簧力分为以下四种:s (1)中的虚线所示㊂ :同一层次中类质心之间的力, 如图3点划线所示(2)F s (2)㊂ :质心和子结点之间的力, 如图3中的实线所示(3)F s (3)㊂

:同一类中文本之间的力, 如图3中的弱, 如图(4)3F s (4)中的粗短线所示

:结点与其他质心之间的力㊂

, 该力最

图3　 力模型

任何两个存在语义关系的对象(质心/文本) 间

的弹簧力借鉴经典的弹簧力计算公式[7]给出:

, 可由下式F s (a , b ) =k s (i )

d (a (0

l a , b

=-F s (b , a )

s (i ) 其中, k

s (i ) 是弹簧系数, 代表对象间的关系类型对力的影响程度, 比如, 对象是同一类时k s 则大, 对象属于不同类时k s 则小; d (a , b ) 是对象a , b 之间的可视化距离; l a , b 是a , b 之间的理想距离, 它是a , b 之间的相似度sim (a , b ) ㊁ 调节参数α , β 的函数㊂

其中, α , β 是可调参数(100l a , b =

2

α ㊂ 其中

117

情报学报　 第30卷　 第2期　 2011年2月

标准距离㊂

3. 1. 4　 电子力模型

电子力模型模拟物理中电子之间的相互作用, 使得对象相互排斥, 避免重叠, 起到辅助布局的作用, 适用于所有的对象㊂

任何两个对象(质心/文本) 之间的电子力计算公式:

(a )=∑ F e (a , b ); (a );

☆　 计算a 与所有其他点间的电子力之和:F e

☆　 计算a 受到的力的总和:F (a )=F s (a ) +F e ☆　 根据受到的力与平衡关系, 计算a 的新Step 3:

对布局系统进行能量评估:E (p ); 位置;

F e (a , b ) =k e

b ) 是对象d q a q b

=-F e (b , a )

a (, a b , b 之间的可视化距离)) 2

(3)

其中, d (a , ; q q a 和

b 是两个常量; k e 是电子斥力系数, 代表对象间的关系类型对力的影响程度, 比如, 同一类中对象间的排斥力比不同类中对象间的排斥力要小, 相应的k e 也小㊂

3. 2　 能量评估模型

每种布局都是文本聚类分析结果映射到二维或三维空间中的映射函数p , 我们使用能量评估函数E 评价各种映射函数p 的布局效果㊂

布局中的对象在力的作用下向理想的位置移动, 在整个布局系统中产生能量E (p ), 形成不稳定状态; 对象通过移动不断被布局在理想位置附近, 系统的能量E (p ) 也逐渐变小, 布局效果不断优化; 当E (p ) 达到全局最小时, 映射函数p 将得到最优的布局效果㊂ 所以, 能量评估模型定义如下(4)

其中, v ∑ :

E (p ) =

o

v 2o o 是对象o 在力的作用下运动的速度, v 2o

是对象o 的能量㊂

3. 3　 算法

聚类分析结果的布局既要尽可能地保留文本间语义相关程度的信息, 又要尽可能地反映聚类层次信息㊂ 该算法通过对象间的理想距离和可视化距离计算施加在对象之间的力, 根据力的大小和布局能量对布局进行调整, 最终达到最优的布局效果㊂

算法主要步骤描述如下:Step 1:

随机初始化布局和能量阈值θ ; Step 2:对于每个点a :

的和☆　 :F 计算a 与其存在语义关系的点间的弹簧力

s (a )=∑ F s (a , b );

118

Step 4:

如果E (p )

执行Step 5;

Step 5:

根据所有点的新位置, 更新布局㊂ 然后返回Step 2㊂

4　 主题图构建

通过文本布局方法可得到表现文本语义相似关系的二维平面布局图㊂ 在该布局图中, 主题相近的文本被组织在一起形成高密度的区域, 而主题不集中的 文本相互分散形成稀疏的区域, 我们用更加形象的

现为具有高山峰的岛屿信息岛屿” 来表现这种布局, 它们通过低山峰的岛屿相㊂ 其中, 密度高的区域表连, 每个山峰代表一个相关的主题, 山峰的高低代表主题的聚集程度㊂ 使用这种表现形式, 可以很容易地定位感兴趣的区域和导航浏览相关文本㊂

主题图构建方法是基于一个山峰模型和等值线生成算法实现的㊂

4. 1　 山峰模型

布局中的每一个文本对象表示为一个小山峰㊂ 如果在一个小的区域内文本对象相互聚集, 重叠的山峰和高度将进行叠加, 构成更大和更高的结构 山脉 文本的主题

㊂

图4　 山峰模型图

山峰模型的构建公式和效果图如公式(5)和图

文本聚类分析结果可视化方法研究

4所示:

z (x , y ) =λ *e-θ *((x -x 0)

2+(y -y ) 2)

其中, (x 0, y 0) 是文本对象布局中的坐标, z (x , y ) 表示高度值, λ 控制山峰的高度, θ 控制山峰的影响范围

(λ >0,θ >0) 　 (5)

受(x 0, y 0) 处山峰模型的影响, (x , y ) 处所形成的

其中, (X , Y ) 是特定高度Z 的点的坐标, 已知(x 1, y 1) 和(x 2, y 2) 的高度分别是z 1和z 2㊂ 两个等值点的连线就是一条等值线片段㊂

4. 2. 3　 等值线追踪

ìïX =x 1+Z -z 1(x 2-x 1)

2-z 1ï

　 í

Z -z 1ï

ïY =y 1+-z (y 2-y 1) î21

(z 1≤ z 0≤ z 2) 　 (6)

的大小㊂

4. 2　 等值线生成算法

绘制等值线是对大量离散的㊁ 又具有一定规律的几何量值或物理量值用数学的方法插值并转换成图的过程, 常采用网格法, 广泛应用于测绘㊁ 地理信息系统等领域[8]般为:离散数据网格化㊂ 各种网格法绘制等值线的步骤一

㊁ 网格点数值化㊁ 等值点的计算㊁ 等值线追踪㊁ 光滑和标记等值线㊁ 填充等值线区域等㊂

本文根据文本可视化的需要, 提出基于网格法的等值线生成算法, 通过高度值构建㊁ 等值点计算㊁ 等值线追踪和等值线区域着色4个步骤构建主题图㊂

4. 2. 1　 高度值构建

可视化视野由许多网格组成, 根据文本对象在可视化视野中的布局和山峰模型的思想, 将叠加的高度值赋予相关的网格上的点㊂ 这样就构建了反映文本对象布局特征的高度值㊂

4. 2. 2　 等值点计算

特定高度的点构成了等值线, 然而网格中的点是离散的数据点, 具有离散的高度㊂ 所以, 本文利用插值法计算等值点

㊂

图5　 网格切分

如图5所示, 每一个网格可以分两个三角形㊂ 对于任意一个三角形, 使用插值法计算落在边上的等值点的公式为:

对不同高度的等值点所构成的等值线片段进行追踪则可连接成一个整体㊂ 根据等值线的构成不同, 本文将其分为封闭等值线和非封闭等值线, 并提出如下等值线追踪算法描述:

输入:网格点高度值集, 特定高度序列输出:等值线集序列对于每一特定高度:Step 1:

等值线段首尾相接构成等值线片段; Step 2:

如果存在等值线片段, 继续; 否则输出等值线集序列;

Step 3:

如果等值线片段首尾端点不同, 继续; 否则转Step 7;

Step 4:

等值线片段首尾相接; Step 5:

如果端点不是边界点, 转Step 3; 否则转Step 6; Step 6:

生成边界等值线, 转Step 8; Step 7:

生成封闭等值线, 转Step 8; Step 8:

剔除连接所用的等值线片段, 转Step 2㊂ 4. 2. 4　 等值线区域着色

对生成的等值线图区域, 根据一定的梯度进行着色, 构建具有层次的主题图㊂

5　 实验及结果分析

为进一步说明本文提出方法的直观性和有效性, 将其应用于专利领域, 并进行分析说明㊂

实验数据来自于国家知识产权局[9], 为清晰地展

119

情报学报　 第30卷　 第2期　 2011年2月

示聚类结果及主题的分布情况, 本文仅提取40篇类别下的专利申请书, 使用经典的凝聚层次聚类分析方法进行分析, 并使用参考文献[10]所提出的方法概化出6个类别(如表1所示), 形成三层聚类结果树, 即原始文本层㊁6 个类别层和顶层抽象文本集层㊂

G06Q10/00(用于行政㊁ 管理的数据处理系统或方法)

局在一起, 形成高的等值区域, 反映出该区域的专利聚焦于同一领域的相同技术㊂

图中空心的专利点是关注的专利, 并显示出该专利的申请号和专利名称; 根据实际需要, 可依据图中与其位置的相近程度来分析相关的专利, 为非领域专家进行专利分析提供信息导航功能㊂

表1　 专利聚类分析结果

类别专利数主题词

Cluster_13购买㊁ 信息发布㊁ 软件产品㊁ 产品㊁ 指纹㊁ 指纹验证㊁ 广告㊁ 下载㊁ 互联网络㊁ 经营场所Cluster_28应用程序㊁ 可视化㊁ 商业应用㊁ 购物㊁ 文件管理系统㊁ 管理信息㊁ 邮件地址㊁ 邮件㊁ 任务㊁ 应用

Cluster_35管理功能㊁ 资产㊁ 控制器㊁ 物品㊁ 电池㊁ 控制㊁ 装置㊁ 资产管理㊁ 风险评估㊁ 管理方案Cluster_413交易㊁ 代码㊁ 认证㊁ 确认㊁ 车辆㊁ 评估㊁ 读取㊁ 设备㊁ 多功能㊁ 指令

Cluster_57邮件㊁ 上下文㊁ 知识管理㊁ 集成㊁ 文档㊁ 管理系统㊁ 集成方法㊁ 集成服务㊁ 重要㊁ 无线通讯网络

Cluster_6

4

打印㊁ 垃圾邮件㊁ 税务㊁ 彩票㊁ 公安㊁ 监控㊁ 邮件㊁ 垃圾㊁ 系统软件㊁ 打印机

应用本文提出的方法得到的可视化结果如图6所示㊂ 其中每个节代表一篇专利文本, 而点之间的距离表示了全局中两点之间的语义相似程度㊂ 相似度大的文本点之间距离小, 反之距离大㊂

Cluster_3,Cluster_4,Cluster_6)图6明显地由5个山峰(Cluster_1,Cluster_2,

与聚类分析结果基本对应㊂ Cluster_5组成, 构成形成的山峰不5个主题, 5明显和Cluster_4, 和Cluster_4的语义相似程度较大基本在一个山脉中, 是, 说明Cluster_4Cluster_题中的外围专利主题类㊂ 这是在其他非可视化的聚

主类分析结果表达中无法得到的隐含模式㊂

ｕｓ铸ｊ

斤五丙而雨丽正霸再趸丽雨露丽丽焉爱蚕碾

图6　 可视化实例

利用等值线构建的主题图还可反映专利文本中的主题聚集情况及其层次关系㊂ 主题相似的专利布

120

6　 结　 论

针对文本聚类分析结果表达中忽略语义层面信息造成的信息丢失㊁ 不易理解等问题, 本文提出一种以主题图方式表达聚类结果的可视化方法㊂ 充分利用聚类分析结果中的层次关系和聚类文本间的语义相似关系, 通过改进Force⁃directed 布局方法, 对聚类分析后的文本进行布局; 并通过构建山峰模型生成等值线, 构建层次性的可视化主题图㊂ 实验表明, 使用该可视化方法不仅能较充分地反映文本间的语义关系, 还能有助于发现其中隐含的知识模式和结构, 实现有效的知识导航㊂

参　 考　 文　 献

[1]　杨峰方法研究, 周宁[J]., 吴佳鑫情报学报. 基于信息可视化技术的文本聚类

,2005,24(6):679⁃683.[2]　北京周宁:, 科学出版社张玉锋, 张李义,2005. . 信息可视化与知识检索[M].[3]　Drawing

Eades P , Algorithms

Feng Q W , Lin for

X Hierarchical

M , et al . Straight Graphs

⁃ Line

Clustered 周宁, 吴佳鑫Graphs[J]., 张少龙Algorithmica,2006,44(1):1⁃32.and

[4]　析[J].情报学报,2008,27(5):714⁃720.. 基于图的Web 信息可视化探[5]　London:Springer⁃Verlag,2001.

Brandes U. Drawing Graphs:Methods and Models[M].[6]　Fruchterman T M J,Reingold E M. Graph drawing by

[7]　Experience,1991,21(11):1129⁃1164.

force⁃directed placement [J ].Software Practice &

Eades drawing P,Huang using a Ｃｌｕ

modified M L,Wang spring J H. algorithm[J].Online animated Journal graph

[8]　Visual 孙桂茹Languages and Computing,1998,9:17⁃28.of

法[J]., 天马亮津, 大路登平学学报, 等(自. 等值线生成与图形填充算

然科学与工程技术版),

[9]　2000,33(06):816⁃818.

www. 国家sipo. 知识gov. 产权cn 局/sipo2008专利检/索zljs . /.[2009⁃05⁃12 ].http://

[10]　吴江宁[J].情报学报, 田海燕,2007,26(3):323⁃331.

. 基于主题地图的文献组织方法研究

(责任编辑　 马　 兰)