在社交网络中的事件挖掘

摘要

一种用于从社交流中检测事件的方法和系统。该方法包括以下步骤：从社交网络接收社交流，其中社交流包括至少一个对象并且该对象包括文本、文本的发送方信息、和文本的接收方信息；基于在对象与聚类之间的相似度值而将所述对象指配到聚类；监测聚类中的至少一个聚类的改变；并且在聚类中的至少一个聚类的改变超过第一门限值时触发警报，其中使用计算机设备来执行步骤中的至少一个步骤。

说明书

技术领域

本发明涉及事件挖掘，并且更具体地涉及从社交流中检测新事 件。

背景技术

由于文本数据在广泛多种场景、比如web、社交网络、新闻馈送 和许多其它场景中普遍可用，文本挖掘问题已经在信息检索界中被 广泛研究。文本数据中的许多文本数据在时间应用、比如新闻馈送 和社交网络流的情境中出现，在这些时间应用中，文本作为连续和 规模文档流到达。由于经常有必要在单次通过中处理数据并且不能 在盘上存储所有数据用于再处理，流应用给这样的问题带来特殊挑 战。

时间的和流的文本数据的情境中的重要问题是与主题检测和跟 踪问题密切相关的在线事件检测问题。这一问题也与流分割密切相 关，并且尝试确定文本流中的新主题趋势及其显著演变。思想是现 实中的重要和有新闻价值的事件(比如在中东内的新近动荡)经常 以与社交流中的文档密切相关的时间猝发的形式被捕获。可以在经 监督的和不经监督的场景二者中提出该问题。在不经监督的情况下， 假设无训练数据可用以便引导流的事件检测过程。在经监督的情况 下，关于事件的在先数据可用以便指导事件检测过程。

发明内容

因而，本发明的一个方面提供一种用于从社交流中检测事件的 方法。该方法包括以下步骤：从社交网络接收社交流，其中社交流 包括至少一个对象，并且对象包括文本、文本的发送方信息和文本 的接收方信息；基于在对象与聚类之间的相似度值将所述对象指配 到聚类；监测在聚类中的至少一个聚类的改变；并且在聚类中的至 少一个聚类的改变超过第一门限值时触发警报，其中使用计算机设 备来执行步骤中的至少一个步骤。

本发明的另一方面提供一种从社交流中检测事件的系统。该系 统包括：用于从社交网络接收社交流的接收模块，其中社交流包括 至少一个对象，并且对象包括文本、文本的发送方信息和文本的接 收方信息；用于基于在对象与聚类之间的相似度值将所述对象指配 到聚类的聚类模块；用于监测聚类中的至少一个聚类的改变的监测 模块；以及用于在聚类中的至少一个聚类的改变超过第一门限值时 触发警报的触发模块。

附图说明

图1示出流程图，该流程图图示根据本发明的一个优选实施例 的检测社交网络中的事件的方法100。

图2示出根据本发明的一个优选实施例的用于检测社交网络中 的事件的系统。

图3图示用于实施或者执行本发明的至少一个实施例的硬件配 置。

图4示出流程图，该流程图图示根据本发明的一个优选实施例 的用于在分割步骤102期间将对象指配到现有聚类或者创建新聚类 的方法的流程图。

图5示出流程图，该流程图图示根据本发明的另一优选实施例 的维护方法500。

图6示出根据本发明的另一优选实施例的用于聚类维护的详细 总体算法。

图7图示根据本发明的一个优选实施例的聚类算法在聚类纯度 方面的有效性结果。

图8示出根据本发明的一个优选实施例的聚类方式关于增加的 聚类数目的效率。

图9图示根据本发明的一个优选实施例的经监督的事件检测方 法的结果。

具体实施方式

本发明的以上和其它特征将通过与附图组合示出的实施例具体 描述而变得更明显。相同标号代表本发明的附图中的相同或者相似 部分。

如所属技术领域的技术人员将意识到的，本发明的多个方面可 以实现为系统、方法或计算机程序产品。因此，本发明的各个方面 可以具体实现为以下形式，即：完全的硬件实施方式、完全的软件 实施方式(包括固件、驻留软件、微代码等)，或硬件和软件方面 结合的实施方式，这里可以统称为“电路”、“模块”或“系统”。此外， 本发明的各个方面可以采取体现在任何一个或多个计算机可读介质 中的计算机程序产品的形式，该计算机可读介质具有体现在其中的 计算机可读程序代码。

可以采用一个或多个计算机可读介质的任意组合。计算机可读 存储介质可以是，例如，电、磁、光、电磁、红外线、或半导体的 系统、装置、器件或者任意以上的组合，但不限于此。计算机可读 存储介质的更具体的示例(非穷举的列表)可以包括下列：具有一 个或多个导线的电连接、便携式计算机盘、硬盘、随机存取存储器 (RAM)、只读存储器(ROM)、可擦式可编程只读存储器(EPROM 或闪存)、光纤、便携式紧凑盘只读存储器(CD-ROM)、光存储设备、 磁存储设备、或者上述的任意合适的组合。在本文的上下文中，计 算机可读存储介质可以是任何包含或存储程序的有形介质，该程序 被指令执行系统、装置或者设备使用或者与其结合使用。

可以以一种或多种程序设计语言的任意组合来编写用于执行本 发明的多个方面的操作的计算机程序代码，所述程序设计语言包括 面向对象的程序设计语言-诸如Java、Smalltalk、C++等，还包括常 规的过程式程序设计语言-诸如“C”或类似的程序设计语言。程序代 码可以完全地在用户计算机上执行、部分地在用户计算机上执行、 作为一个独立的软件包执行、部分在用户计算机上执行。下面将参 照根据本发明示例实施例的方法、装置(系统)和计算机程序产品 的流程图和/或框图描述本发明。应当理解，流程图和/或框图的每个 方框以及流程图和/或框图中各方框的组合，都可以由计算机程序指 令实现。这些计算机程序指令可以提供给通用计算机、专用计算机 或其它可编程数据处理装置的处理器，从而生产出一种机器，使得 这些计算机程序指令在通过计算机或其它可编程数据处理装置的处 理器执行时，产生用于实现流程图和/或框图中的一个或多个方框中 规定的功能/动作的装置。

也可以把这些计算机程序指令存储在计算机可读介质中，这些 指令使得计算机、其它可编程数据处理装置、或其他设备以特定方 式工作，从而，存储在计算机可读介质中的指令就产生出包括实现 流程图和/或框图中的一个或多个方框中规定的功能/动作的指令的 制造品(article of manufacture)。

也可以把计算机程序指令加载到计算机、其它可编程数据处理 装置、或其它设备上，使得将在计算机、其它可编程装置或其它设 备上执行一系列操作步骤，以产生计算机实现的过程，从而使得在 计算机或其它可编程装置上执行的指令提供用于实现流程图和/或框 图中的一个或多个方框中规定的功能/动作的过程。

附图中的流程图和框图显示了根据本发明的各种实施例的系 统、方法和计算机程序产品的可能实现的体系架构、功能和操作。 在这点上，流程图或框图中的每个方框可以代表一个模块、程序段 或代码的一部分，所述模块、程序段或代码的一部分包含一个或多 个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些替 换实现中，方框中所标注的功能也可以以不同于附图中所标注的顺 序发生。例如，被连续示出的两个方框实际上可以基本并行地执行， 或者，方框有时也可以按相反的顺序执行，这依所涉及的功能而定。 也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程 图中的方框的组合，可以用执行规定的功能或动作的专用的基于硬 件的系统来实现，或者可以用专用硬件与计算机指令的组合来实现。

这里所用术语仅为了描述具体实施例的目的，而并非旨在于限 制本发明。如这里所用，除非上下文另有明示，单数形式“一个”和“该” 旨在于也包括复数形式。还将理解术语“包括”在说明书中使用时指 定存在陈述的特征、整件、步骤、操作、单元和/或部件、但是未排 除存在或者添加一个或者多个其它特征、整件、步骤、操作、单元、 部件和/或其组。

所附权利要求中的所有装置或者步骤加上功能要素的对应结 构、材料、动作和等效物旨在于包括用于与如具体要求保护的其它 权利要求要素组合执行功能的任何结构、材料或者动作。已经出于 示例和描述的目的而呈现本公开内容的描述，但是该描述未旨在于 穷举本发明或者使本发明限于公开的形式。许多修改和变化将对于 本领域普通技术人员显而易见而未脱离公开内容的范围和精神实 质。选择和描述实施例以便最好地说明本发明的原理和实际应用， 并且使本领域其他普通技术人员能够对于具有与设想的特定使用相 配的各种修改的各种实施例理解本发明。

社交网络是由称为“节点”的动作者(或者组织)组成的社交结构， 这些节点由一个或者多个具体类型的相互依耐性、比如朋友关系、 亲属关系、共同利益、金融交易、嫌恶、性关系、或者信仰、知识 或者声望关系连结(连接)。社交网络还可以包括在线聊天信使服 务中的消息，或者它可以包括电子邮件网络，在该电子邮件网络中 在成对节点之间发送消息。

许多感兴趣的问题在这样的社交网络中出现，因为它们是动态 的并且与流中的网络结构关联。每个节点代表社交网络中的动作者， 并且在社交网络中发送的每个消息是与社交网络中的边缘关联的文 本内容。显然，可以随时间在相同一对节点之间发送多个消息。在 这一情况下，文档的主题内容、它们的时间分布、和动态交互网络 的图形结构可以用来检测感兴趣的事件及其演变。在紧密地编织的 一组节点之间发送的消息可以比从结构观点来看更分散地相关的消 息集合更能指示社交兴趣的特定事件。在社交网络被视为图形时， 这样的消息可以在结构上良好的连接，该图形具有与在实体之间发 送的消息对应的边缘。这与团体检测问题有关，在该团体检测中， 关键问题是发现社交网络的在结构上连接的区域。同时，文档的内 容和主题也应当在事件检测过程中发挥强大作用。

事件的网络局部性可以在它的意义中发挥关键作用。例如专属 于特定大学的大事件可以主要对应于在该大学的学生和员工成员内 的消息，而更全局事件、比如中东动荡可以对应于与具有更大的社 交网络局部性的内容有关的消息。在前一种情况下，通信可能在更 密切地连接的一组实体之间出现，而在后一种情况下，消息可以更 全局，而偏向与中东对应的社交网络的局部性。在繁多和大规模社 交网络中检测在动态网络中具有不同局部性和范围的这样的不同事 件极有挑战性。

在流式场景中的关键问题是假设由于用于处理这样的大量流的 存储器和存储限制而不能在盘上存储数据用于重复的处理。换而言 之，必须在一次通过流式假设下执行所有分割或者事件检测算法， 在该假设中仅可以从传入流提取(存储受约束的)摘要数据，此后 丢失原始流。另外，算法必须快速，因为它应当能够从社交网络流 的繁多流中实时检测事件。因此，对于社交流中的事件检测的关键 挑战如下：(a)有能力将交互的内容和(图形)结构二者用于事件 检测。(b)有能力在事件检测中使用时间信息。从结构和内容观点 来看，在更早时尚未被遇到的密切地有关的文本文档的新趋势可以 对应于社交流中的新事件。(c)有能力在流式场景的一次通过约束 之下处理很大量和繁多的文本文档。

确定流中的事件的问题与流分割问题密切地有关，对于后者已 经针对不同种类的数据提出多种方法。在社交网络的情境中，这样 的流的内容是文本。在这样的文本流中的事件实质上是活动的新模 式的开始，其可以被建模为数据中的新聚类的起点。文本挖掘界已 经在主题检测和跟踪情境中提出许多这样的方法。这也与动态文本 流中的分割和主题建模问题有关。

然而在社交网络中，有在确定网络中的关键事件时可用的丰富 数量的结构。例如与中东动荡对应的事件可以经常对应于在基于地 理邻近而相互密切地链接的成员之间交换的文本流。尽管社交联网 界已经广泛研究链接的使用以便确定聚类和模式，但是这些方法通 常被设计用于静态网络。一些分割方法最近也已经被设计用于动态 网络，但是它们未将下层网络的内容用于挖掘过程。另一方面，用 于网络中的模式发现的一些最近的方法使用内容和结构二者，但是 这些方法未被定义用于时间场景中的事件检测问题。因此，设计一 种能够以整体方式使用内容、结构和时间信息以便检测社交流中的 相关聚类和事件的方法，其中该方法可以解决确定网络中的关键事 件这样的独特挑战。

图1图示流程图，该流程图包括根据本发明的一个实施例的方 法步骤。在步骤101，从社交网络接收社交流，其中社交流包括至少 一个对象。如以上提到的那样，社交网络是由称为“节点”的动作者 (或者组织)组成的社交结构，这些节点由一个或者多个具体类型 的相互依赖性、比如朋友关系、亲属关系、共同利益、金融交易、 嫌恶、性关系、或者信仰、知识或者声望关系连结(连接)。社交 网络还可以包括在线聊天信使服务中的消息，或者它可以包括电子 邮件网络，在该电子邮件网络中在成对节点之间发送消息。社交网 络生成社交流，其中社交流包括对象S_i...S_r...的连续和时间序列，从而 每个对象S_i对应于在社交实体之间的、基于内容的交互，并且包含 实体之间的显式内容信息和链接信息，对象S_i包括与社交网络中的 实体与一个或者多个其它实体的交互的内容对应的文本文档T_i。对象 S_i还包括始发节点q_i∈N，该始发节点是到其它节点的消息T_i的发送 方。对象S_i最后包括一个或者多个接收方节点的集合，这些接 收方节点对应于来自节点q_i的消息T_i的所有接收方。因此，从始发节 点q_i向每个节点r∈R_i发送消息T_i。假设每个边(q_i，r)属于集合A。

在步骤101中，对象、即S_i由元组(q_i，R_i，T_i)表示。应当注意社交 流的以上定义捕获在不同类型的社交网络中的多个不同自然场景。 例如在Twitter社交网络中，文档T_i对应于tweet的内容，并且节点q_i对应于tweet动作者。集合R_i对应于tweet的接收方。电子邮件交互 网络也可以被视为具有与以上完全相似的解释的社交网络。相似主 张适用于聊天交互网络。在这些情况中的许多情况下，接收方集合R_i可以包含仅一个节点，作为这种情况的结果，有基于内容的边交换 的流。最后在许多社交网络中，一个动作者在墙上对另一动作者的 布告对应于边，而文档T_i对应于布告的内容。

社交流在步骤101中通常包含关于趋势的丰富信息，该趋势可 以造成交互可以在其中出现的网络的内容和结构局部性二者的改 变。本发明的实施例从描述用于事件检测的不经监督的技术开始， 该不经监督的技术以聚类的形式连续地表征传入的交互，并且利用 它们以便报告数据流中的事件。

在从社交网络接收社交流之后，图1中的步骤102执行接收的 社交流的分割，其中稍后将描述步骤102的进一步细节。来自社交 流S_i...S_r的对象被连续地分割成k个聚类C_i...C_k，从而每个对象S_i属于聚 类C_r中的至多一个聚类。另外，使用相似度值来将对象指配到不同 聚类，该相似度值捕获交换的消息的内容，以及不同消息暗示的动 态社交网络结构。将在图4中进一步具体提供相似度值的计算。

通过利用内容和链接信息二者来创建聚类。由于动态创建聚类， 所以它们可以随着流演变以及新点被添加到聚类而随时间明显改 变。另外，在一些情况下，传入对象可以与当前聚类充分不同。在 该情况下，它可以被放入它自己的聚类中，并且当前聚类之一可以 被从集合C_i...C_k中去除。这样的事件可能是令人感兴趣的事件，尤其 是如果新创建的聚类开始新活动模式时，在该新活动模式中更多流 对象被随后添加。同时，在一些情况下，事件不能全新、但是可以 对应于到达对象的模式在它们到聚类的相对分布方面的显著改变。

在步骤103，在聚类中的至少一个聚类中监测聚类的改变。在本 发明的本实施例中，有两个类型的新事件，将这两个类型的新事件 称为新颖事件和演变事件以便描述这些不同场景。如果数据点S_i被作 为新创建的聚类C_i内的单个点放置，则其到达被视为新颖事件。聚 类C_i的创建时间由t(C_i)表示。事件在这一情况下是在数据点S_i下面的 故事或者主题，而不是数据点本身。

新事件的出现可以作为新颖事件而产生，但是该出现也可以影 响现有数据点在不同聚类中的相对存在。例如，“中东动荡”事件可 以作为新聚类的创建而产生，或者作为向与这一主题最密切有关的 聚类显著添加新数据点而产生。这是因为先前存在的聚类经常有可 能与特定主题有关的对象的突然猝发密切地匹配。事件中的对象的 突然猝发将被定义为演变事件。演变事件被局限于具体时间范围并 且表示该特定聚类的相对活动的改变。

为了确定新事件是否为新颖事件或者演变事件，步骤103利用 分数聚类存在函数。聚类C_i在时间段(t₁，t₂)中的分数聚类存在是来自在 时间段(t₁，t₂)期间到达的社交流的属于聚类C_i的记录的百分比。这一分 数存在由F(t₁，t₂，C_i)表示。这一突然猝发由聚类中的数据点的分数存在 的改变来表征，并且这样的猝发将定义演变事件。

步骤103确定更高速率，与其它数据点甚至在H之前的到达比较， 在长度为H的先前时间窗中数据点已经以该更高速率到达聚类。参数 α也用作第一门限值，以便测量这一演变速率。参数α可以是预定值， 并且可以由于用户配置。如果聚类C_i中的点在范围(t_c-H，t_c)内的相对 存在与在时间t_c-H之前的相对存在的比值大于第一门限值α，则在当 前时间t_c、在范围H内的演变事件被视为已经以聚类C_i的第一门限值 α出现。提供以下等式以便更好理解：

等式1：$\frac{F(t_c-H,t_c,C_i)}{F(t\left(C_i\right),t_c-H,C_i)}\ge \alpha$

在等式1中，假设t_c-2·H≥t(C_i)，其中值t_c-2·H大于聚类创建时 间t(C_i)，以便定义前述演变比值。这保证在步骤103期间在这一比值 的分母的计算中使用至少H个时间单位。

在步骤104中，在聚类中的至少一个聚类的改变超过第一门限 值时触发警报。第一门限值在本发明的实施例中被表达为参数α，该 参数可以是预定值，并且可以由用户配置。如前文讨论的那样，事 件检测算法使用时间范围H作为用于事件检测过程的输入。为了执行 事件检测，并且每当用于C_i的比值超过门限α时都触发 警报。这提示下层社交流的显著改变，该改变通过向不同聚类指配 的流对象的比值的显著改变来检测。

图2示出根据本发明的实施例的、用于从社交流中检测事件的 系统。系统200包括接收社交流210的接收模块220，其中社交流包 对象S_i...S_r...的连续和时间序列，从而每个对象S_i对应于社交实体之间 的基于内容的交互，并且包含实体之间的显式内容信息和链接信息。

在图2中所示实施例中，系统200也包括将来自社交流S_i...S_r...的 对象连续地分割成k个聚类C_i...C_k、从而每个对象S_i属于聚类C_r中的至 多一个聚类的聚类模块230。如以上提到的那样，通过利用内容和链 接信息二者来创建聚类。由于动态创建聚类，所以它们可以随着流 演变以及新点被添加到聚类而随时间明显改变。另外，在一些情况 下，传入对象可以与当前聚类充分不同。在该情况下，它可以被放 入它自己的聚类中，并且当前聚类之一可以从集合C_i...C_k中被去除。

在图2中所示实施例中，系统200也包括监测聚类的改变的监 测模块240。监测模块也通过利用如以上描述的分数聚类存在函数来 确定新事件是否为新颖事件或者演变事件。系统最后包括触发模块 250，其中在聚类中的至少一个聚类的改变超过第一门限值时，触发 模块250触发警报。第一门限值可以是预定值并且可以由用户设置。

图3图示实施和/或执行本发明的实施例的计算系统1600(例如 接收模块202、聚类模块203、监测模块204、触发模块205)的硬 件配置。计算系统1600可以包括本发明的实施例中的图2中的所有 模块。硬件配置优选地具有至少一个处理器或者中央处理单元 (CPU)1611。CPU1611经由系统总线1612互连到随机存取存储器 (RAM)1614、只读存储器(ROM)1616、输入/输出(I/O)适配 器1618(用于将外围设备、比如盘单元1621和带驱动1640连接到 总线1612)、用户接口适配器1622(用于将键盘1624、鼠标1626、 扬声器1628、麦克风1632和/或其它用户接口设备连接到总线1612)、 用于将系统1600连接到数据处理网络、因特网、内部网、个人区域 网络(PAN)等的通信适配器1634，和用于将总线1612连接到显示 设备1638和/或打印机1639(例如数字打印机等)的显示适配器1636。

在又一实施例中，接收模块202、聚类模块203、监测模块204、 触发模块205被使用硬件描述语言(Verilog、VHDL、Handel-C或 者系统C)实施为可重新配置硬件、例如FPGA(现场可编程门阵列) 或者CPLD(复杂可编程逻辑器件)上的硬件。在另一实施例中，主 题建模模块140、链接建模模块150和团体建模模块160使用半定制 设计方法、即使用标准单元和硬件描述语言来设计芯片而被实施于 半导体芯片、例如ASIC(专用集成电路)上。

在又一实施例中，接收模块202、聚类模块203、监测模块204、 触发模块205被使用一个或者多个编程语言、例如C、C++、 Java、.NET、Perl、Python等实施为软件。在一个实施例中，接收模 块202、聚类模块203、监测模块204、触发模块205被记录于计算 机可读介质、例如CD(紧致盘)、DVD(数字万用盘)、HDD(硬 盘驱动)、SSD(固态驱动)上，作为由处理器、例如Power执行的指令、例如机器语言或 者汇编语言。

图4具体图示根据本发明的一个优选实施例的用于在分割步骤 102期间将对象指配到现有聚类或者创建新聚类的方法。图4包括以 下步骤：如果在所述对象与现有聚类之间的相似度值大于第二门限 值，则将所述对象指配到所述现有聚类；如果在所述对象与所述现 有聚类之间的所述相似度值小于第二门限值，则用所述对象创建新 聚类；并且用所述新聚类替换旧聚类。

在图4的步骤410中，做出在对象与现有聚类之间的相似度值 是否大于第二门限值的确定。在对象S_i与聚类C_r之间的相似度值 (Sim(S_i，C_r))根据结构分量SimS(S_i,C_r)和内容分量SimC(S_i，C_r)二者来计算。 内容分量使用在文本文档T_i与单词摘要W_r之间的基于tf-idf的相似 度，该文本文档T_i与社交网络中的实体与S_i的交互的内容对应。结构 分量通过利用社交流中的节点摘要V_r和节点R_i∪{q_i}来计算。节点摘要 V_r是与聚类C_i关联的节点集合，并且包括节点j_i1，j_i2...j_is以及由 v_i1，v_i2...v_is表示的节点频率。q_i是始发节点，q_i∈N，该始发节点是到其它 节点的消息T_i的发送方。R_i是一个或者多个接收方节点的集合， 这些接收方节点对应于来自节点q_i的消息T_i的所有接收方。首先， 被表示作为R_i∪{q_i}的比特矢量表示，该比特矢量表示具 有针对V_r中的每个节点的比特。如果对应节点被包括在R_i∪{q_i}中，则 比特值是1，否则它是0。在等式2中定义了对象S_i与聚类C_r的频率 加权节点集合之间的结构相似度：

等式2：$\mathrm{SimS}(S_i,C_r)=\frac{{\Sigma }_{t=1}^{S_r}{b}_t·v_{\mathrm{rt}}}{\sqrt{\left|\right|R_i\cup \left\{q_i\right\}\left|\right|·}\left({\Sigma }_{t=1}^{S_r}{v}_{\mathrm{rt}}\right)}$

对于等式2，与L₂范数的正常使用对照，分母中的节点-频率矢量 的L₁范数被使用，以便惩罚太大的聚类的创建。这将产生更平衡的聚 类。

在计算结构分量SimS(S_i，C_r)和内容分量SimC(S_i，C_r)之后，相似度值 Sim(S_i，C_r)被计算为基于结构和内容的相似度值的线性组合。等式3举 例说明用于相似度值Sim(S_i，C_r)的以上计算：

等式3：Sim(S_i，C_r)＝λ·SimS(S_i，C_r)+(1-λ)·SimC(S_i，C_r)

对于等式3，参数λ是落在范围(0，1)中的平衡参数。参数λ由 用户定义。

继续图4的步骤410，在计算在对象与现有聚类之间的相似度值 (Sim(S_i，C_r))时，确定相似度值是否大于第二门限值。第二门限值可 以是由用户预定的值，或者可以是值μ-3·σ，其中μ是平均值并且σ是 传入的流对象(S₁...S_r...)与聚类摘要的所有相似度值的标准偏差，其中 稍后将描述聚类摘要的细节。在图4的步骤420中，如果最近聚类 的相似度值在第二门限值以上，则传入的流对象S_i被指配到它的最近 聚类质心。在另一方面，在图4的步骤430中，如果S_i的相似度小于 第二门限值，则创建仅包含对象S_i和对应聚类摘要统计量的单独聚 类。图4的步骤440通过用新单独聚类来替换来自当前汇集C_i...C_k中 的最旧聚类而继续。最旧聚类被定义为最少更新的聚类。在空聚类 存在(从未被更新)的情况下，它自动被视为最旧聚类。随机断开 任何连结。

图5图示流程图，该流程图图示维护聚类的改变作为社交流的 历史数据的方法。图5的步骤530举例说明将通过使用聚类算法来 维护的聚类改变。假设聚类算法使用聚类数目k作为输入，并且以聚 类中的节点和单词频率的形式维护下层聚类中的结构和内容信息。 聚类由C_i...C_k表示。与聚类C_i关联的节点集合由V_i表示，并且与它关联 的单词集合由W_i表示。集合V_i称为节点摘要，而集合W_i称为单词摘要。 摘要表征可以用于将传入流对象指配到聚类，稍后将描述这一点。 集合V_i包括节点j_i1，j_i2...j_is以及由v_i1，v_i2...v_is表示的节点频率。单 词集合W_i包括单词标识符l_i1，l_i2...l_is以及由φ_i1，φ_i2...φ_is表示的单词频率。

传入社交流对象S_i与每个聚类摘要ψ_i(C_i)一起维护。聚类摘要ψ_i(C_i) 包括节点摘要和内容摘要。节点摘要包括表示为V_i＝{j_i1，j_i2...j_is}的节点 集合和表示为η_i＝v_i1，v_i2...v_is的对应节点频率的集合，其中假设节点集 合V_i包括S_i节点。内容摘要包括表示为W_i＝{l_i1，l_i2...l_is}的单词标识符集合 和表示为Φ_i＝φ_i1，φ_i2...φ_iu的对应单词频率的集合，其中假设W_i包含u_i个单 词。因此，聚类摘要ψ_i(C_i)被表示为ψ_i(C_i)＝(V_i，η_i，W_i，Φ_i)。在本发明的优选 实施例中，聚类C_i...C_k的集合与聚类摘要ψ₁(C₁)...ψ_k(C_k)一起被维护。随 着新社交流对象到达，连续地更新和维护聚类。同时，连续地跟踪 和维护下层聚类的改变以便提出新事件的警报。

一旦对象S_i被指配给它的最近聚类质心C_r，更新对应聚类摘要 ψ_r(C_r)。具体而言，S_i中的尚未在节点摘要V_r中包括的任何新节点被添 加到V_r，并且在V_r中包括的S_i的节点的频率被递增1。注意S_i中的节点 对应于源节点q_i和目的地节点R_i二者。换而言之，集合R_i∪{q_i}被用来 更新集合V_r及其成员频率。利用单词在社交流对象S_i中的使用，相同 方式被应用于W_i中的单词。在这一情况下的仅有的不同是单词的频率 并非仅被递增1、而是被递增它们在下层文档中的存在频率。

图5的步骤530也维护传入对象与聚类的(最近)相似度值的 平均值和标准偏差作为历史数据。出于这一目的，本实施例连续地 维护最近相似度值的零阶、一阶和二阶矩量M₀、M₁和M₂。这些值可 以在流场景中容易地维护，因为它们可以在数据流内添加地维护。 可以按照这些矩量将平均值μ和标准偏差σ表达如下：

等式4：μ＝M₁/M₀，$\sigma =\sqrt{M_2/M_0-{(M_1/M_0)}^2}$

在图6中图示用于聚类维护的详细总体算法。可以在图1的步 骤103中所示的监测聚类中的至少一个聚类的改变时使用历史数据。 还可以根据图4中所示的向现有聚类指配对象或者创建新聚类的结 果来创建和维护历史数据。可以在经监督的事件检测中使用历史数 据，在该经监督的事件检测中，历史数据变得可用以便指导事件检 测过程。

在经监督的事件检测的情况下，假设有对流的以往历史的访问， 在该以往历史中已经知道事件ε已经出现。此外，还有关于与这一特 定事件相关的社交流tweet的至少子集的信息。这是可以用于更准确 事件检测的基础事实。

为了执行经监督的事件检测，也有对算法的聚类部分的改变。 一个主要改变是在新传入点未自然地在任何聚类中相配时不允许替 换旧聚类或者创建新聚类。实际上，它总是被指配给它的最近聚类 而随机断开任何连结。这样做是为了向聚类特性提供稳定性，并且 是相对于下层数据中的聚类随时间以一致方式表征事件所必需的。

事件专属流对象到聚类的相对分布被用作专属于事件的签名。 可以使用这些以便实时执行检测。在经监督的情况下的假设是关于 与事件有关的社交流对象的训练数据在历史训练数据中可用。事件ε 的签名被定义为事件签名或者范围签名。

社交流的事件签名是k维矢量V(ε)，该k维矢量包含事件专属流对 象到聚类的(平均)相对分布。换而言之，V(ε)的第i个分量是指配 聚类i的事件专属(训练)流对象的百分比。

事件签名提供在有显著性的事件期间的相对主题分布的有用表 征。例如在中东动荡(事件ε)时段期间，一些聚类可能比其它聚类 活跃得多，并且这可以在矢量V(ε)中被捕获，只要基础事实可用于这 样做。可以比较事件签名与范围签名，这些范围签名实质上以与事 件签名相同的方式来定义，除了它们在长度为H的最新近时间范围 (t_c-H，t_c)内被定义之外。

作为事件的另一类型的签名，在最后时间段(t_c-H，t_c)内的范围签 名是k维矢量V(ε)，该k维矢量包含已经在时段(t_c-H，t_c)中到达的社交 流对象到聚类的相对分布。

为了执行经监督的事件检测，计算范围签名与已知事件签名(按 照基础事实来计算)的点积，并且与这一个值相等的报警水平输出。 在误判与漏判之间的折衷由被选择用于判决这样的事件何时实际出 现的门限确定。

这一算法的主要挑战是基于节点的统计量可能相当大。作为结 果，对应相似度计算和维护可能繁琐。例如V_r中的节点数目可以是千 万级，并且这可能使算法极为缓慢。因此，涉及了一种基于略图 (sketch)的技术以便加速计算。

基于略图的技术是一种用于压缩下层数据中的计数信息、从而 可以用空间高效方式维护主导计数的广泛特性的方法。在本发明的 这一实施例中，应用计数最小值略图用于维护下层聚类中的节点计 数。在计数最小值略图中，利用哈希方式以便保持下层数据流中的 节点计数的跟踪。函数w＝[ln(1/δ)]是按对使用的独立哈希函数。独立哈 希函数中的每个独立哈希函数映射到在范围h＝[0，el∈]中的均匀随机整 数，其中e是自然对数的底数。数据结构包括长度为h并且宽度为w的 具有w，h个单元的二维数组。每个哈希函数对应于各自具有h个单元的 w个1维数组之一。在计数-最小值略图的标准应用中，使用哈希函 数以便更新在这一2维数据结构中的不同单元的计数。例如考虑具 有从繁多域值集合抽取的元素的1维数据流。例如在本发明的实施 例中，值的域对应于社交网络中的不同节点标识符。在接收数据流 的新元素时，应用w个哈希函数中的每个哈希函数以映射到在[0...h-1] 中的数上。w个单元的集合的每个单元的计数被递增1。为了估计项 目的计数，确定w个哈希函数中的每个哈希函数映射到的w个单元的 集合，并且计算在所有这些单元之中的最小值。令c_t为被估计的计数 的真实值。注意被估计的计数至少等于c_t，因为仅处理非负计数，并 且由于在哈希单元之间的冲突而可能有过度估计。不言而喻，也可 以确定对于估计的概率上界。已经表明对于具有T个到达的数据流， 估计至多为c_t+∈·T而概率至少为1-δ。

为了将计数-最小值略图用于改进节点计数估计过程，维护数据 中的每个聚类的略图表。略图表被用于维护传入的数据流中的节点 的频率计数。具体而言，第j个聚类的略图表由U_j表示。如果希望， 则可以将w个哈希函数的相同集合用于不同聚类。主要条件是该集合 的w个哈希函数应当相互独立。对于每个传入的对象S_i，更新用于聚 类的略图表，其中基于相似度测量向略图表指配聚类。w个不同哈希 算法被应用于R_i∪{q_i}中的节点(的标识符的串表示)，并且向对应单 元的计数加1。因此对于传入的对象R_i，需要哈希函数中的每个哈希 函数应用于不同的|R_i|＝1个节点，并且更新对应单元。这对应于应用 (|R_i|+1)·w个哈希函数实例和对应单元更新。

此外，基于略图的结构也可以用来有效估计相似度值SimS(S_i，C_r)。 注意需要对于每个聚类C_r及其对应略图表U_r执行这一相似度值计算， 以便基于复合相似度测量来确定对于传入对象的最近聚类。可以确 切地估计SimS(S_i，C_r)的分母，因为对象S_i已知，因此也可以确定的 值。也可以确定的值，因为该值等于针对w个哈希函数中的任何 哈希函数的U_r中的略图表单元中的所有值之和。因此，可以通过将 针对哈希函数中的任何特定哈希函数的h个单元求和来确切地获得 这一个值。在另一方面，需要近似地估计分子。注意分子实质上由 在R_i∪{q_i}中包括的节点的频率的估计值之和来定义。

可以估计每个这样的节点的频率。具体而言，对于在R_i∪{q_i}中包 括的每个节点，可以通过将哈希函数应用于每个节点的标识符来获 得节点的对应聚类专属频率。注意对应哈希单元的值将由于在到相 同哈希单元的不同节点标识符之间的冲突而总是被过度估计。因此， 跨越w个不同哈希函数的这些值的最小值也将是过度估计，但是由 于使用不同哈希函数它将严密得多并且更健壮。在R_i∪{q_i}中的不同节 点上将这些估计的频率值求和。这实质上是分子的估计。分子的这 一估计可以与关于不同分母值的确切知识结合使用，以便创建 SimS(S_i，C_r)的估计。令EstSimS(S_i，C_r)表示使用基于略图的方式时S_i与C_r的估 计的相似性。然后可以示出以下结果：

引理1：如果使用具有长度h和宽度w的略图表，则对于某个小值 相似度的估计值EstSimS(S_i，C_r)被以至少为的概率限 于以下范围：

等式5：SimS(S_i，C_r)≤EstSimS(S_i，C_r)≤SimS(S_i，C_r)+∈

证明：如在等式2中之前讨论的那样，结构相似度由以下等式 给定：

等式6：$\mathrm{SimS}(S_i,C_r)=\frac{{\Sigma }_{t=1}^{S_r}{b}_t·v_{\mathrm{rt}}}{\sqrt{\left|\right|R_i\cup \left\{q_i\right\}|·}\left({\Sigma }_{t=1}^{S_r}{v}_{\mathrm{rt}}\right)}$

注意分子是被使用基于略图的过程近似地(过度)估计的，而 分母可以确切地已知。显然，由于分子的过度估计， SimS(S_i，C_r)≤EstSimS(S_i，C_r)。仍然示出以至少为的概率 EstSimS(S_i，C_r)≤SimS(S_i，C_r)+∈。

令SimSN(S_i，C_r)和EstSimSN(S_i，C_r)为使用基于略图的方式对分子的估 计。然后由于可以确切地计算分母，所以有：

等式7：$\mathrm{EstSimS}(S_i,C_r)=\frac{\mathrm{EstSimSN}(S_i,C_r)}{\sqrt{\left|R_i\right|+1}·\left({\Sigma }_{t=1}^{S_r}{v}_{\mathrm{rt}}\right)}$

另外有：

等式8：$\mathrm{SimS}(S_i,C_r)=\frac{\mathrm{SimSN}(S_i,C_r)}{\sqrt{\left|R_i\right|+1}·\left({\Sigma }_{t=1}^{S_r}{v}_{\mathrm{rt}}\right)}$

因此，为了证明引理中的结果，需要证明分子中的近似的界限。 具体而言，需要证明以下等式以至少为概率成立。

等式9：$\mathrm{EstSimSN}(S_i,C_r)\le \mathrm{SimSN}(S_i,C_r)+E·\sqrt{\left|R_i\right|+1}·\left(\underset{t=1}{\overset{S_r}{\Sigma }}{v}_{\mathrm{rt}}\right)$

令等式9的被替换为B。与等式9一样，需要表明对 用于如下条件的概率的以上界限：

等式10：EstSimSN(S_i，C_r)-SimSN(S_r，C_r)≤B

利用任何特定哈希函数对EstSimSN(S_i，C_r)-SimSN(S_i，C_r)的预计值是 这一结果之所以出现是因为需要在|R_i|+1个不同频率 估计上对误差求和，并且对于这些基于单元的估计中的任何基于单 元的估计的预计冲突数目是然后可以使用马尔科夫不等式 以使用概率至多为的1个哈希函数来表明违反等式10 中的条件的概率。可以将这一概率推广至w个独立哈希函数至多为 因此，等式10中的条件以至少的概率 成立。通过在以上等式中代入B的值，可以获得期望的结果。

以上结果提示可以使用略图表的适度存储器要求很准确地估计 相似度的值。例如考虑具有|R|＝100和相似度估计界限∈＝0.001的tweet。 如果使用具有h＝200,000和w＝5(典型值)的略图表，则它将需要仅100 万个单元的存储，这是兆字节级。相似度估计以至少为1-(1/20)⁵＞1-10^-6概率落在真实值的∈＝0.001内。在实践中，由于这些理论界限很宽松， 所以估计好得多。

以下段落将讨论本发明的实施例的有效性和效率。两个实际数 据集被用作示例以评估本发明的实施例的有效性。

在以下两个数据集上测试算法。第一集合是社交流，该 社交流是从社交网络抓取(crawled)的tweet流。每个社交 对象包含tweet中的网络结构和内容。具体而言，每个对象包括tweet 的文本以及tweet的发送方和接收方。在2011年5月9日05:00GMT 与2011年5月10日18:30GMT之间的时段收集tweet。使用橡胶软管流式API来提取tweet，该API是使用Twitter4j库 (http://dev.twitter.com/docs/twitter-libraries)而可用的。流包含在共计47,351,520个 节点内分布的共计1,628,779个tweet。在广播消息的情况下节点包括以 来自发送方或者他们的跟随者的直接提述的形式的发送方和接收 方。在提取跟随者之时，实验仅包括跟随少于1,000个其他人并且具有 少于1,000个跟随者的用户。Kwak等人指示在具有这一范围以外的社 交图形程度的用户之中的行为急剧变化；这样的用户可以是营销者、 具有专业宣传者的名流、新闻媒体源，并且因此是一般人群的非典 型者。实验也消除用于接收的tweet中的每个tweet的短URL、停用 词和情绪。平均而言，每个流对象包含每tweet约84个节点。

第二示例集合是Enron电子邮件流，该电子邮件流是使用电子邮 件中的时间戳信息而转换成流的Enron电子邮件数据集。每个对象 包含电子邮件的文本、以及与发送方和接收方对应的网络结构。在 这种意义上，电子邮件的网络结构与具有单个发送方和多个接收方 的tweet很相似。Enron电子邮件数据流包含共计517,432个电子邮 件。示例消除了无有效发送方和接收方电子邮件标识符的电子邮件。 示例也滤除在每个电子邮件的底部的日历邀请、重复电子邮件和电 子邮件历史。在过滤过程之后的全部电子邮件是349,911，其中电子邮 件分布于共计29,083个个体。平均而言，每个电子邮件包含3.62个接 收方。

对于聚类和事件检测方法测试两个数据集，并且对于有效性进 一步测试两个数据集。对于效率情况，仅使用聚类方法，因为事件 检测的时间的大多数被用于聚类过程中。为了测试有效性，实验使 用与社交流中的对象关联的多个类标签。对于流，这些类 标签是与tweet关联的哈希标签。流中的最频繁的哈希标签经常对应 于流中的事件、比如日本地震，并且表示应该被聚类在一起的下层 对象的有意义的特性。这些哈希标签也经常表示流中的有意义事件。 注意并非每个tweet可以包含哈希标签，并且哈希标签仅与tweet的 子集关联。对于Enron电子邮件流的情况，类标签由主题行中的最 频繁出现的标记(token)定义。这些标记如下：

会面、协定、天然气、能量、功率、报告、更新、请求、会议、信 件、交易、信用、加利福尼亚、贸易、合同、项目、演示、休斯顿、 通报

在主题行中包含以上标记中的任何标记的所有电子邮件都被用 对应的类标签来标注。因此对于两个数据流，流对象的子集被用类 标签来标注。显然地，高质量的聚类将倾向于将具有相似标签的对 象放在相同聚类中。因此，计算每个聚类的主导类纯度。每个聚类 被用最高存在来标注，并且计算属于该标签的(标注的)聚类对象 的百分比。这一个值以加权方式在不同聚类中被平均，其中聚类的 权值与在它中的(标注的)对象数目成比例。

也测试社交流聚类过程的效率。为了测试效率，计算每单位时 间处理的社交流对象数目，并且呈现针对不同算法的数目。

测试事件检测算法的有效性。对于涉及到不经监督的算法的情 况，呈现案例研究以举例说明该技术所发现的感兴趣的事件。这提 供关于该技术的有效性的直观思想。在另一方面，经监督的算法需 要生成基础事实。出于这一目的，在Twitter流中使用哈希标签以便 生成与事件何时实际出现对应的0-1比特流。使用与#japan对应的哈 希标签以便生成Twitter数据流中的事件。具体而言，在每个时间戳， 在长度为h的以往窗监测、并且对该窗中的特定哈希标签的出现数目 进行计数。如果哈希标签的出现数目至少为3，则生成在该时间戳的 比特1，以指示事件已经确实出现。

经监督的事件检测算法生成连续警报水平。有可能使用关于这 一连续报警水平的门限t，以便生成与事件何时已经出现的算法预测 对应的0-1比特流。通过使用关于这一警报水平的不同门限t，可以 获得在精确度(precision)与查全率(recall)之间的不同折衷。令S_F(t)为 时间戳集合，警报在这些时间戳处使用关于实际警报水平的门限值t 来生成。令S_G为时间戳的基础事实集合，事件在这些时间戳真实地 出现。然后可以计算Precision(t)和Recall(t)如下：

等式11：$\mathrm{Precisiont}\left(t\right)=\frac{|S_F\left(t\right)\cap S_G|}{S_F\left(t\right)}$

等式12：$\mathrm{Recall}\left(t\right)=\frac{S_F\left(t\right)\cap S_G}{S_G}$

通过变化t的值、并且使用关于生成的警报水平的不同门限来探 究在精确度与查全率之间的折衷而绘制在精确度与查全率之间的绘 图。曲线越高，结果的质量就越好。

测试不同算法设置，以确定内容和网络结构对准确度和效率的 影响。通过将λ设置成极端值0和1，可以测试算法性能有多么好。 可以对于聚类过程测试仅网络算法或者仅文本算法的性能回顾。也 测试组合方案，在该组合方案中，λ的值被设置成0.5。以上提到的 方案在聚类和事件检测过程中向文本和内容提供相等权值。对于组 合方案，测试利用略图技术和未利用略图技术的算法，以便估计略 图使用对方案的准确度和效率影响。因此，变化也用作良好基线， 因为使用纯文本内容在这一结合点是用于这一问题的仅有自然备 选。

图7图示聚类算法在聚类纯度方面的有效性结果。利用增加的 聚类数目进一步测试该方式的有效性。分别在图7(a)和7(b)中图示 Twitter和Enron流的结果。对于Twitter社交流，略图表长度h被设 置262,213，而略图表宽度w被设置成2，并且这些值对于Enron数据 流被设置成16,369和2。在每种情况下，图示在X轴上的聚类数目和 在Y轴上的聚类纯度。

在不同算法的相对性能方面对于两个数据集观察趋势。在所有 情况下，仅使用文本的算法在所有算法之中性能最差。在纯基于网 络的方式与组合方式之间的趋势依赖于执行聚类的粒度水平。对于 两个数据流，发现在使用小数目的聚类时，基于网络的方式是优异 的。在使用更大数目的聚类时，组合方法性能超过纯基于网络的方 式。这是因为在粒度相对粗略时网络局部性信息足以有效分割聚类。 在这样的情况下，添加文本未提高下层聚类的质量，并且甚至可能 对聚类质量有害。然而在聚类数目增加时，组合方法往往性能更好， 因为聚类的粒度高得多，并且作为结果，可能需要更多属性以在不 同聚类之间区分。这在Enron数据流的情况下特别明显，在该数据 流中，在组合方式与纯基于网络的方式之间的差距相当大。在所有 情况下，发现使用略图造成一些准确度损失。然而这一准确度损失 不是很显著，尤其在考虑到基于略图的方式显著地更快时。也重要 的是注意纯基于文本的方式(该方式是基线)在所有场景中表现最 差。

这些结果也似乎提示，与文本信息比较，社交流中的网络信息 提供用于聚类的强大得多的信息。这对于来源、比如Twitter数据流 而言未特别让人惊讶，在该数据流中文本相当有噪声并且经常包含 非标准缩略词或者难以用有意义的方式使用的其它文本。然而发现 有些让人感兴趣和惊讶的是，这些趋势对于比如Enron数据流的源 也成立，在该数据流中文本相对地干净并且通常对于下层类标签很 有信息量。

也利用流的进展来图示聚类纯度。这提供在流本身的进展期间 聚类过程表现如何的动态思想。图7(c)和7(d)示出针对Twitter和 Enron数据流的结果。聚类数目被固定为750。对于Twitter数据流， 略图表长度h被固定成262,213，并且对于Enron，略图表长度被设 置成16,369。略图表宽度w在两种情况下被固定成2。X轴图示对 于每处理的1000个对象的流的进展，并且Y轴图示在1小时的最后 时间窗内的聚类纯度。在不同方法之间的相对趋势与之前的观察相 似，但是主要观察是聚类纯度一般随着流的进展而降低。原因是由 于流中的类标签数目一般随着流的进展在遇到新类、标签和事件时 增加。作为结果，聚类纯度一般随着流进展而降低。

最后，图7(e)和7(f)用略图表长度和宽度测试该方式的灵敏度。 分别在图7(e)和7(f)中图示针对Twitter和Enron数据流的略图表长 度增加时的灵敏度结果。在X轴上图示略图表长度，而在Y轴上图 示聚类纯度。聚类数目在这一情况下被设置成500，并且略图表宽度 被设置成2。为了提供并入略图结构的相对有效性的基线，也在相同 图中示出针对未使用略图的方法的结果。清楚的是聚类纯度随着略 图表长度增加而增加。这是因为更大略图表长度减少略图表中的冲 突数目，并且因此它提高总体准确度。此外，在充分增加略图表长 度时，基于略图表的方式的准确度接近未使用略图表的方法的准确 度。在这样的情况下，冲突被充分减少至由于略图表使用而准确度 减少的点。

图7(g)和7(h)测试和示出针对Twitter和Enron数据流的、在略 图表宽度增加时的灵敏度结果。聚类数目被设置成500，并且略图表 长度分别对于Twitter数据流被设置成262,213而对于Enron数据流 设置成16,369。虽然有效性结果随着略图表宽度增加而提高，但是 纯度结果与略图表长度相比对略图表宽度不那么灵敏。这是因为虽 然哈希函数数目增加提供附加的健壮性，但是它未明显减少在不同 条目之间的冲突数目。

图8示出聚类方式随着聚类数目增加的效率。参数设置与有效 性结果的参数设置相同。图8(a)和(b)也示出针对Twitter和Enron数 据流的有效性结果。X轴表示聚类数目，而Y轴表示每小时处理的 流对象数目。结果表明基于网络的方式比基于文本的方式更慢。这 是因为需要由基于文本的方式处理大量相异节点。然而基于略图的 方式在两个数据流中显著增加速度，因为通过略图表示相似度计算 中的操作数目得以减少。此外，处理速率未必随着聚类数目增加而 减少，因为更大聚类数目(其造成在每个聚类中有更少数目的对象 的更稀疏聚类)表现在传入对象与下层聚类之间的更快的相似度计 算。

图8(a)和8(d)示出随着流进展的效率的结果。在X轴上图示流 进展，并且在Y轴上图示处理速率。图8(c)和8(d)图示，对于所有 不同方式，处理速率随着流进展而降低，因为聚类随着流的进展而 包含更大数目的对象。这增加相似度计算的复杂性，因为每个聚类 中的属性数目(在文本单词或者节点数目方面)也增加。然而该方 法的减缓在某点之后随着每个聚类中的属性数目稳定而变平。

图8(e)、8(f)、8(g)和8(h)示出该方式关于哈希表长度和宽度的 灵敏度。在图8(e)、8(f)、8(g)和8(h)中也图示针对两个数据流的关 于哈希表长度和宽度的灵敏度结果。从图中显而易见的是运行时间 对哈希表长度不很灵敏，并且变化中的多数变化实际上是随机变化。 在另一方面，哈希表宽度影响需要计算的哈希函数数目。因此，运 行时间一般随着哈希表宽度增加而减少。这些结果看来提示更大哈 希表宽度并不特别有用，因为它不大影响纯度，但是它明显影响效 率。因此，附加存储器应当被用于增加哈希表长度而不是为了宽度 使用附加存储器。

此外，提供不经监督的事件检测问题的案例研究。利用这一方 式的使用来检测演变事件和新颖事件。通常，这样的事件与特定新 闻、国家、语言或者情绪关联。

第一事件与日本核危机有关。具体而言，社交流的相关段对应 于如下情况，其中日本首相请求中部电力公司关停滨冈核电站。这 一事件在社交流中生成相当多的谈论，其中下层动作者在讨论这一 命令的正面和负面。社交流的对应部分包含结构节点，这些在地理 上偏向日本并且一般基于下层网络和内容信息创建它们自己的聚 类。在这些聚类中的频繁文本内容包括以下单词：

核、滨冈、电厂、顾虑、困境、天然气流体、细线、暂停、关闭、 沉重、日本、忽略、运营(1.152)

算法的一个令人感兴趣的方面是它能够检测事件，针对这些事 件的内容是以外语的形式。这一点的原因是事件检测算法不使用任 何专属于英语的方法，并且网络结构的使用对于不考虑具体语言的 使用。例如，印度尼西亚财政部长于2011年5月9日发布命令购买 PT Newmont Nusa Tenggara公司7％的股份。这在twitter中触发讨论 线程，该讨论线程由于它们的有关内容和网络结构而被捕获。在与 这一事件最相关的聚类中关联的频繁文本内容如下：

keputusan，menkeu，beli，newmont，saham，wapres，didukung， challenge，minskade，metro，jak，kimiad，menos，minskade(0.9964)

在前述示例中，在这一事件中的整个文本内容由外语单词构成。

如以上所见，不经监督的事件检测方式能够发现下层社交流中 的感兴趣的和新颖事件。这样的推断在诊断与实际事件有关的重要 社交情绪时可以非常有用。

图9图示经监督的事件检测方法对Twitter流的结果。为了创建 经监督的事件，将范围设置成5分钟，并且确定与日本核危机对应 的事件在数据流中出现的时段。在每种情况下，将聚类数目设定为 750以检测下层事件。图9详细图示在精度和查全率之间的折中。查 全率在X-轴图示，而精度在Y-轴图示。在每种情况下，事件检测算 法已经用算法的不同变化来实施。清楚的是仅使用文本提供比在事 件检测过程中使用网络结构的所有方法更低准确度的事件检测。具 体而言，使用网络结构和文本内容二者的方法提供最准确结果。略 图的使用在某个程度上降低检测的准确度，但是该方式仍然比涉及 到纯文本的事件检测更准确。同样显然的是精确度和查全率的绝对 值相当高。例如在日本核危机的情况下，在使用网络和文本二者时 在近似0.62的查全率点获得0.525的精确度。在另一方面，仅使用 文本或者网络的方案在约0.6的查全率点实现约0.3的精确度。

因此，网络和文本的组合的使用大大提高事件检测算法的准确 度。这些结果看来提示组合网络和文本内容的、用于聚类和事件检 测的方式可以在广泛多种场景中提供有用并且准确的结果。