新闻网络与概念格中的数据挖掘方法探索

# 新闻网络与概念格中的数据挖掘方法探索 ## 1. 新闻网络演化模式挖掘 ### 1.1 新闻网络分析背景 新闻报道数量会直接影响受众反应，甚至带来负面影响。新闻网络可用于分析灾难响应、救援与援助之间的关系，剖析新闻故事中实体间的交互，还能分析公众情绪等。分析新闻网络的一项重要任务是刻画热门事件的演变，或找出网络中随时间演变的主题。不过，挖掘动态模式面临两大挑战：一是难以确定显著演变的位置，挖掘过程耗费大量 CPU 时间和内存；二是难以有效验证提取的演变模式。 ### 1.2 显著性驱动框架 为解决上述问题，提出了一个显著性驱动的框架来刻画和提取新闻报道网络中的演变模式。具体步骤如下： - **提取网络模体并计算演变显著性**：网络模体是特定的小子图，在网络中出现的次数显著高于随机网络。通过比较网络局部结构与随机网络，使用 Z - Score 和 SP 两个显著性指标来衡量模体的显著性。 - **Z - Score**：定义为 \(Z_i=(N_{real_i}-Avg_i)/std_i\)，其中 \(N_{real_i}\) 是网络中观察到的模体数量，\(Avg_i\) 和 \(std_i\) 是具有相同度序列的随机网络集合中模体 \(i\) 计数的均值和标准差。一般来说，如果模体的 Z - Score 小于某个阈值，则可忽略该模体。 - **SP**：是 Z - Score 归一化到长度为 1 的值，\(SP_i=Z_i/(\sum Z_j^2)^{1/2}\)，强调子图的相对显著性，便于不同大小网络的比较。 ### 1.3 框架的三个阶段 #### 1.3.1 聚类显著演变的模体 - **枚举和比较模体**：对于每个网络快照，枚举所有可能的 3 或 4 节点模体，并与随机网络的平均计数进行比较。可使用 MFinder、FANMOD 等工具进行模体检测和计数。 - **定义演变向量**：模体的演变向量由按时间顺序排列的 Z - Score 列表组成，如 \(V = < z_1, z_2, …, z_t >\)，用于分析演变趋势和聚类相关模体。 - **聚类相关模体**：在适当的时间间隔内聚类具有相关演变向量的模体，这些模体在网络中共同演变，具有相关的演变行为。 #### 1.3.2 刻画显著演变 定义两个演变度量来评估演变趋势与随机网络在特定时间间隔内变化相比的统计显著性。 - **潜在指数（PI）**：衡量当前模体向下一个时间戳演变的趋势。对于一个模体簇 \(M\)，在时间戳 \(t\) 到 \(t + 1\) 的潜在指数定义为 \(PI(M, t)=\frac{1}{|M|}\sum_{i = 1}^{|M|}(SP_{x_{i,t + 1}} - SP_{x_{i,t}})\)，其中 \(|M|\) 是模体簇 \(M\) 中的模体数量。当模体簇中只有单个模体时，PI 也可用于检验单个模体的演变显著性。 - **演变显著性得分（E - Score）**：计算模体簇在一段时间内累积的潜在指数，用于评估时间间隔内的连续模式。定义为 \(E - Score(M, T)=\sum_{i = 0}^{|T| - 1}\gamma^i\cdot PI(M, t + i)\)，其中 \(0\leq\gamma < 1\) 是衰减因子。 #### 1.3.3 提取动态行为 通过聚类与共同演变模体同构的子结构来提取动态行为。 ### 1.4 实验分析 使用 DaysALL 数据集（路透社恐怖新闻网络）进行实验。该数据集基于路透社在 2001 年 9 月 11 日美国遭受袭击后的 66 天内发布的所有报道。网络顶点是单词，边表示两个单词出现在同一文本单元中，边的权重是其出现频率。 - **聚类模体**：在 15 天内从 DaysAll 网络中获得一个 3 节点模体（id 238）和两个 4 节点模体，其 Z - Score 大于 2.0 且 p - 值小于 0.05。 - **寻找显著演变**：通过潜在指数发现从第 8 天到第 9 天的演变具有统计学显著性，由模体 238 和 13278 主导。 - **识别演变模式**：给定 \(\gamma = 0.8\)，时间间隔 \(T = [7, 9]\)，计算三个模体的 E - Score，发现模体 238 和 13278 引入的演变更具统计学意义。聚类与模体 238 和 13278 同构的子结构，可得到特定日期的模式。例如，在第 9 天得到一个包含巴基斯坦总统佩尔韦兹·穆沙拉夫和一个三角形模体（ID 238）的小社区，表明当时巴基斯坦政府宣布加入美国领导的反恐联盟成为热门话题。 ### 1.5 总结 提出的显著性驱动方法能有效探索和刻画新闻网络的演变，定义的两个显著性度量为网络动态行为的特征提供了新的见解，通过 DaysAll 网络的实验验证了该方法的有效性。 ## 2. 定量概念格中的关联规则挖掘 ### 2.1 关联规则挖掘背景 1993 年，Agrawal 等人首次提出客户交易数据库中关联规则挖掘的问题和解决方案。此后，出现了许多典型的关联规则挖掘方法。粗糙集和概念格是关联规则挖掘的常用工具。 ### 2.2 粗糙集与概念格的对比 - **粗糙集**：主要通过寻找最小约简（包括属性约简和值约简）来挖掘规则。常见的属性约简方法有 Skowron 可分辨矩阵、基于属性显著性的 Pawlak 启发式算法和基于互信息的约简算法等。值约简方法寻找一个最小范围来保持与原始值相同的容量，最终得到决策规则。但粗糙集在挖掘过程中需要删除重复的行或列，导致关联规则的支持度和置信度无法准确获取，还存在组合爆炸和信息丢失的问题。 - **概念格**：基于属性和对象之间的二元关系建立层次结构。概念格的 Hasse 图中的每个节点对应一个形式概念，包括外延和内涵。通过内涵之间的关系实现关联规则的提取，反映了外延之间的直接包含关系。 ### 2.3 定量概念格的优势 定量概念格通过对概念格的外延进行量化构建，包含了所有的外延信息。其关联规则挖掘算法采用广度优先遍历的方式搜索概念节点，有效避免了粗糙集存在的组合爆炸问题。通过相对概念节点的支持度可以准确获取规则的置信度，还能有效避免粗糙集约简中存在的信息丢失问题，从而提高关联规则挖掘的效率。 ### 2.4 基本概念定义 - **关联规则**：假设 \(I = \{i_1, i_2, i_3… i_n\}\) 是一个项集，\(