Web信息网络社区挖掘的关键技术研究

论文摘要

自由开放共享的Web 2.0使得数以亿计的Web用户成为互联网的主角。以博客网络、邮件网络与在线聊天室网络等为代表的Web信息网络已经深入到人们的生产生活中,这些各式各样的Web信息网络承载着人们在生产生活中形成的复杂结构模式。如何从这些纷繁芜杂的关系结构中挖掘出隐藏的潜在有价值的社区结构模式是一个极具挑战性的研究问题,这对于提升信息服务质量,增强公共信息安全以及推进复杂网络分析等多个方面都具有广泛的理论和应用价值。本文以Web信息网络社区挖掘为核心,遵循从内容特征驱动的社区挖掘开始,然后到结构特征驱动的社区挖掘,最后到内容与结构相融合特征驱动的社区挖掘这样一条研究路线,对Web信息网络社区挖掘的关键技术模型与算法进行了深入细致的探讨。本文的主要工作成果与创新如下:1)针对基于传统向量空间模型的Web文档聚类挖掘算法会产生假相似的低质量Web文档社区结构,提出一个基于粒度理论与文章结构理论的集文档表示与文档聚类于一体的多粒度层次模型MHRM,在文档表示过程中引入段落级粒度知识来缩小文档级知识粒度与特征词级知识粒度之间跨度,在段落级聚类时设计了基于容差粗集与基于Ontology的两种可供选择的零相似处理方法以降低聚类对象零相似发生的机率,在文档级聚类时提出了段落级粒度知识对文档级粒度知识的主题贡献度度量方法,MHRM模型能有效挖掘真实Web文档集隐含的社区结构。2)从种群多样性的角度分别设计了基于优生理论的遗传算法EBSGA与基于民主领导的粒子群算法MLCPSO,仿真实验表明此两种算法具有良好的寻优能力。在此基础上,提出了EBSGA与MLCPSO相混合的优化算法EBSGA/MLCPSO,把遗传算法所具有的优越局部搜索能力与粒子群算法所具有的超强全局搜索能力进行有机结合,结合新闻组社区挖掘的具体场景,引入SVD技术寻找新闻组的潜在语义子空间。提出的3种算法在真实新闻组数据的社区挖掘实验表明: EBSGA算法、MLCPSO算法与EBSGA/MLCPSO算法都能较好地发现新闻组内在的社区结构,但是EBSGA/MLCPSO算法挖掘的新闻组社区结构的质量最高。3)设计了一种基于离散粒子群算法的非重叠社区挖掘算法CDPSO,该算法给出了一种基于邻居节点有序表的粒子编码方案,将非重叠社区的模块度值引入作为粒子适应度,改进了传统离散粒子群算法的粒子位置更新策略,并从理论上分析了粒子位置更新策略的收敛性,算法CDPSO能够在无先验信息的条件下快速有效地揭示网络内在的社区结构。在CDPSO的基础上引入线图的概念,给出了线图节点集合的一个划分对应于原图节点集合的一个覆盖的线图性质并加以理论证明,提出了重叠社区挖掘算法LGPSO,该算法把原图的重叠社区挖掘转变成对应线图的非重叠社区挖掘,能够有效地挖掘网络的重叠社区结构。4)从理论上分析了典型谱聚类算法的基本思路,指出了每种算法的优势和不足,并在Web社区发现的实验场景中进行了各种典型谱聚类算法的性能比较,将谱图理论与粗糙集理论相结合,提出了一种基于谱映射与粗糙聚类的重叠社区发现方法RSC,该算法用上下近似来刻画网络节点的社区归属,边界表示社区之间共享的节点,通过优化重叠社区结构模块度来实现重叠社区的有效挖掘。5)分析了在线社交网络的异构性与海量性,给出了在线社交网络及其挖掘的形式定义,考虑到社区定义的多样性与不同定义的社区有着不同的应用背景,在分析现有的启发式挖掘算法的基础上提出了一个具有良好开放性的广义的启发式挖掘框架。6)结合聊天数据的特点,提出了一个内容特征与结构特征相结合的聊天室社区挖掘算法,该算法一方面借助WordNet等语义计算工具对聊天数据的内容相似性进行研究,另一方面借鉴语言学知识来分析聊天数据的对话线程结构关联性,该算法能有效地挖掘出聊天者之间隐含的关系。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景、目的及意义
• 1.1.1 研究背景
• 1.1.2 Web 信息网络研究面临的挑战与存在的不足
• 1.1.3 研究的目的与意义
• 1.2 研究现状
• 1.2.1 基本概念
• 1.2.2 社区的定义
• 1.2.3 基于结构特征的Web 社区挖掘
• 1.2.4 基于内容特征的Web 社区挖掘
• 1.3 研究思路
• 1.4 研究内容及创新点
• 第二章 Web 文档聚类的多粒度层次表示模型
• 2.1 前言
• 2.2 文档表示模型
• 2.2.1 布尔模型
• 2.2.2 统计语言模型
• 2.2.3 向量空间模型
• 2.3 文档聚类方法
• 2.4 多粒度层次表示模型
• 2.4.1 预备知识
• 2.4.2 模型表示
• 2.4.3 零相似的处理策略
• 2.4.4 文档的聚类算法
• 2.5 实验与分析
• 2.5.1 数据集与评价标准
• 2.5.2 Web 文档聚类质量
• 2.5.3 算法可扩展性
• 2.5.4 容差阈值的影响
• 2.5.5 语义相似度阈值的影响
• 2.6 本章小结
• 第三章 基于自然计算的新闻组社区挖掘
• 3.1 前言
• 3.2 种群多样性的度量
• 3.3 基于优生理论的选择策略
• 3.3.1 标准的GA 算法
• 3.3.2 基于优生理论的选择算子
• 3.3.3 实验与分析
• 3.4 基于民主领导的粒子群优化算法
• 3.4.1 标准的PSO 算法
• 3.4.2 基于民主领导的粒子飞行策略
• 3.4.3 实验与分析
• 3.5 基于EBSGA/MLCPSO 混合优化的新闻组社区挖掘算法
• 3.5.1 基于潜在语义分析的新闻表示模型
• 3.5.2 个体编码
• 3.5.3 目标函数
• 3.5.4 算法描述
• 3.5.5 实验与分析
• 3.6 本章小结
• 第四章 基于粒子群算法的社区挖掘
• 4.1 前言
• 4.2 网络社区挖掘的粒子群算法
• 4.2.1 离散粒子群优化算法
• 4.2.2 CDPSO 算法
• 4.2.3 实验与分析
• 4.3 网络重叠社区挖掘的粒子群算法
• 4.3.1 定义与性质
• 4.3.2 LGPSO 算法
• 4.3.3 实验与分析
• 4.4 本章小结
• 第五章 基于谱图理论的网络社区挖掘算法
• 5.1 前言
• 5.2 Web 社区发现的谱聚类比较研究
• 5.2.1 谱聚类相关理论与基本思想
• 5.2.2 典型谱聚类算法
• 5.2.3 基于谱聚类的Web 社区发现
• 5.2.4 实验与分析
• 5.3 网络重叠社区挖掘的粗糙谱算法
• 5.3.1 粗糙集理论与粗糙聚类
• 5.3.2 谱映射
• 5.3.3 粗糙谱算法
• 5.3.4 实验与分析
• 5.4 本章小结
• 第六章 在线社交网络社区的启发式挖掘框架
• 6.1 前言
• 6.2 启发式挖掘框架
• 6.2.1 形式定义
• 6.2.2 挖掘框架
• 6.2.3 挖掘框架的特性
• 6.2.4 挖掘框架的特性验证
• 6.3 实验与分析
• 6.3.1 数据集与评价标准
• 6.3.2 实验结果与分析
• 6.4 本章小结
• 第七章 内容与结构相结合的聊天室社区挖掘算法
• 7.1 前言
• 7.2 聊天数据的特征分析
• 7.3 聊天室社区关系的挖掘
• 7.3.1 数据预处理
• 7.3.2 基于内容的相似度
• 7.3.3 基于线程结构的相似度
• 7.3.4 社区构建
• 7.4 实验与分析
• 7.4.1 数据集与评价标准
• 7.4.2 实验结果分析
• 7.5 本章小结
• 结论与展望
• 参考文献
• 攻读博士学位期间取得的研究成果
• 致谢