_数据流中的突发性与分级结构.docxVIP

数据流中的突发性与分级结构Jon Kleinberg纽约伊萨卡镇14853号康奈尔大学计算机科学系kleinber@摘要：文本数据挖掘的一个基本问题是从按时间连续到达的文本流中提取出有意义的结构体。电子邮件和新闻文章就是两个这种数据流的例子。它们的特征是主题经历会出现，愈演愈烈一段时间，然后消失的过程。在特定研究领域中发表的文献中可以看作是在一个更长时间范围内对类似的现象的展示。在这一领域许多文本挖掘工作都是基于如下直观的假设的：如果一个主题具有在发生频率方面有显著增加这样确切的特征，则这个主题在文档数据流中的出现可以看作是一个事件的突发。当前工作的目标是开发一个正规的方法为这种突发建模，通过这种方法，强有力地高效地识别他们，同时提供一个有组织的框架用于分析基本内容。这种方法基于用无限状态的自动机对数据流进行建模。在这种模型中，事件突发表现为状态的转移。从某些方面看，它可以看作是使用排队论中的模型对突发网络流量进行分析。由此得到的算法是非常高效的，它嵌套展示了突发事件集，从而在整个数据流上加上了一个分级结构。对电子邮件和研究论文档案的实验表明这样的结构对于研究导致事件发生的内容方面很有意义。简介文档通常是按主题进行组织的，但是在许多情况下，我们也要从时间上检查他们是何时到达的。电子邮件和新闻文章就是这种文档流的两种清晰的例子：在这两种情况下，必须对文档的内容进行按时间进行排序，才能真正弄清楚其中的含义，如特定主题的出现，愈演愈烈，再次消失。在更长时间范围内，在特定研究领域发表的文章按这种方式理解也很有意义，可以看到某些研究课题在几年内明显增长和减少。通过在主题判别和跟踪[2,3,5,64,65]，文本挖掘[37,59,60,61]，和可视化[27,45,63]等方面的研究工作，人们已经探索出使用结合内容分析和时间顺序的建模，从组成新闻故事的文档数据流中识别出主题的方法。这些方法中许多都是基于如下直观的假设：如果一个主题具有在发生频率方面有显著增加这样确切的特征，则这个主题在文档数据流中的出现可以看作是一个事件的爆发。当前工作的目标是开发一个正规的方法为这种爆发建模，通过这种方法，有力地高效地识别他们，同时提供一个有组织的框架用于分析基本内容。在一定程度上，这里提出的方法可以看作是使用排队论中的模型对突发网络流量进行分析（见例[33]）。但是，除此以外，这种底层突发模式的分析揭示了数据流中潜在的分级结构，这种结构与数据流的内容通常都有关系。我起初研究这个问题的目的是很明确的：我想要一种更好的我积累的大量的个人电子邮件档案的组织原则。大量的奇闻轶事的证据和专业研究[6,44,62]，都表明我这种电子邮箱超载的经历是一种相当普遍的现象——这是电子邮件到达速度导致的结果，也是人们需要管理已保存的个人信件，而这些信件很容易就积累到几十甚至几百兆字节的纯文本的内容，导致的结果。而且，从更大规模看，电子邮件已经成为法律诉讼[35]和历史调查[8,39,46]的原始资料——举个例子，国家档案馆已经同意接收克林顿白宫的几千万的电子邮件信息。总的来说，在有些情况下，找到可以帮助我们弄清大量的电子邮件的内容的结构是至关重要的问题。有一条活跃的研究路线已经把文本索引和分类应用于开发电子邮件接口，这种接口可以将收到的信息按照特定的主题划分到不同文件夹中，有时会建议用户进行进一步的操作[4,9,13,30,31,40,49,50,52,53,54,56,57]——实际上，这个框架的目的就是使原本需要用户手动操作的文件系统自动化。也有人完成了查询完全索引的电子邮件集的接口的开发工作。我的兴趣是探索更加明确时间在电子邮件和其他文档数据流的角色的组织结构。确实，即使是一个单一话题的数据流也会被按照相关信息或者文档到达的速度进行调制，会被按照上面介绍的类型的突发活动分成更加本地化的片段。例如，我保存的电子邮件中包含1000条与捐赠建议有关的信息——新的基金项目的公告，规划建议，和共同作者的信件。构成邮件主题的某些人，项目，或者基金机构只在其中一些邮件出现，如果我们能够将这个集合根据这些内容分成子主题，就能得到一个同样自然的，大幅度正交的主题组织方式。这种组织考虑到了信息集合中反映的片段序列，即围绕某些提案的规划和撰写的突发话题。确实，某些子主题（如“为我们的大国家科学基金会信息技术研究的提案而将人们聚集在一起的程序”）通过在特定时间段突然的集中的信息发送比通过消息本身的文本特征更容易描述。人们很容易就提出，伴随着相关元素的流在某些关键时段增强，按照这种方式处理，许多文档流中描述的大主题通常会被突发话题所打断，穿插。突出这些突发话题的通用技术因而可能显示出大量的细微的结构。在转到对这种方法更加技术性的概述前，我先提出对这个问题进一步的想法，这个还比较遥远，是出于对