Tracking the Evolution of News Events
Tracking the Evolution of News Events
Christopher C. Yang
Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong
yang@se.cuhk.edu.hk
Xiaodong Shi
Department of Systems Engineering and Engineering Management
The Chinese University of Hong Kong
xdshi@se.cuhk.edu.hk
Abstract
In topic detection and tracking, news stories are monitored and automatic techniques are used to spot new events and track the progress of previously spotted events. However, the traditional document clustering techniques only organize news stories into a flat hierarchical structure like uncorrelated clusters that represent news events or topics. Such an organization is not capable of presenting the complex relationships between news events. Users are unable to capture how the events start, evolve and end without a graphical evolution presentation. An event evolution graph is effective in presenting the rich underlying structure of events and allows efficient and meaningful information browsing. As a result, users are not only able to retrieve news stories of the same topic but also able to capture their evolution.
In this paper, we define three rules of event evolution relationships. The event evolution includes event threading and event joining, where an event may evolve to several events or an event may be evolved from several events. The events and event evolution relationship will be presented in an event evolution graph. The construction of event evolution graph has two phases, (i) event clustering, and (ii) event evolution relationship identification. In this paper, we focus on the second phase. Several techniques are investigated and examples are presented.
Keywords: Event evolution, Event threading, Topic detection, Tracking
1. Introduction
Due to the popularity of the Internet and electronic commerce, news documents are available at the news information providers’ Web sites. Users can easily go to any newswires such as CNN, BBC, CBS, etc. to download the news articles any time and anywhere. There are infomediaries available to search across multiple newswires for any queries made by users. For example, users may make a query of “Hurricane Katrina” at Google. Several hundred thousands of news articles from a few dozens of newswires will be returned as result in less than a second (Figure 1). It is extremely convenience for users to retrieve documents for a particular query; however, the tremendous volume of news documents makes it impossible for the users to capture the flow of the stories (i.e. evolution of events) efficiently and effectively.
[pic]
Figure 1 Searching news documents related to “Hurricane Katrina” at Google News.
Research in topic detection and tracking (TDT) supports the monitoring of news stories and automatically spots new events and tracks the progress of previously spotted events. The tasks in TDT [4] include
• Story segmentation
• Topic detection
• First story detection
• Link detection
• Topic tracking
Story segmentation determines the boundaries for cohesive text fragments. It is used for segmenting stories obtained form audio sources but it is not required for newswire sources. Topic detection clusters stories of the same topic. First story detection determines if the new document reports a new topic that has not been reported yet in the current identified topics. Link detection determines if two documents are of the same topic. Topic tracking tracks the topic to find all following stories. Allan et al. [5, 6] and Yang et al. [14, 15, 16] have investigated several techniques such as group-average clustering, single-pass clustering, kNN, and natural language processing. However, TDT only organize news stories in a flat hierarchical structure like uncorrelated clusters that represent news events of the same topics. As a result, users are only given lists of news stories belonging to different events of the news topic. Users are unable to capture how events start, evolve and end in a news topic. It is difficult to capture the underlying complex structure of news events within a news topic without identifying the evolution relationship between events.
[pic]
Figure 2 Flat hierarchical structure of organization of documents in TDT.
Temporal text mining (TTM) is a research area concern with the discovery of temporal patterns in text information over time based on the time stamps of the text streams. Mei and Zhai [11] has proposed a new approach to discover the evolutionary theme patterns of news stream and present the result as a them evolution graph. A theme is defined as a probabilistic distribution of words that characterizes a semantically coherent topic or subtopic. The text stream is partitioned into n non-overlapping sliced intervals. The theme of each interval is identified and the evolution of theme between successive intervals is extracted. An example of a theme evolution graph is given in Figure 3. However, such theme evolution graph only presents the transition of themes across successive time intervals. It does not capture the events of the news topic nor extract the event evolution relationship among the events. Users can only obtain the information about the theme for a predefined interval and realize if there is a theme transition between consecutive time intervals.
[pic]
Figure 3 An example of a theme evolution graph.
Event evolution is a concept developed recently. Makkonen [10] was the first to conduct investigation on event evolution as a subtopic of TDT. The news documents within a topic are temporally linearly ordered. A narrative begins when the first story of the topic is detected. A seminal event may lead to several other events. The events at the beginning may have more influence on the events coming immediately after than the events at the later time. As we go through the event in the temporal order, we may see the evolution of events within a topic. For example, the out break of a war may evolve to the economic crisis and then evolve to the problem of refugees. The events and the event evolution relationship can be represented as a graph structure (Figure 4). Nallapati et al. [12] has investigated the dependencies among events and developed a few simple models to determine the event threading relationships. However, the existing model is rather too simple to capture the complex relationships among the events in a large collection of documents within a topic. The concept of event evolution has not been well defined. In this work, we formally define the event evolution by three logical rules. We also introduce some techniques to capture the complicated event threading and event joining relationships.
[pic]
Figure 4 An example of event evolution graph.
2. Definitions
The definition of event evolution is based on the definitions of story, event, and topic in TDT. Without a clear understanding of story, event and topic, there will be many possible interpretations of event evolution. In this section, we shall revisit the definitions of story, event and topic with some modifications to support the definition of event evolution.
Story – A story is a news article delivering some information to users (i.e. reporting a particular event).
Each news document describes a unique story and each story discusses a single event. As a result, a story is the smallest atomic unit in the hierarchy of [topic / event / story]. Practically, each story is a news document downloaded from the newswire. Each story includes a few components such as title, timestamp, source, abstract, full text, and images.
Event – An event is something that happens at some specific time but may or may not be at a specific place.
In the previous definitions of event, it always specifies a place that the event occurs. It is true for most cases. However, there are some events that do not have any specific location. For example, the event about the reaction of the people after the event of the death of the Pope John XII describes the mourning of the people all around the world. It does not have any specific location of the event. Each event is composed of a set of stories. Practically, there is usually more than one story from the newswire that is describing an event. For example, a story may describe the mourning of the people in New York while another story may describe the mourning of the people in Italy. The stories within an event are semantically coherent.
Topic – A topic is a set of events that are strongly interconnected with each other.
In general, a topic is started by a novel seminal event that is followed by other related events.
Event evolution is a concept that is developed recently. Makkonen [10] described event evolution as the changing nature of a topic. Nallapati et al. [12] defined event threading as detecting events within a topic and capturing the dependencies among the events. In general, the evolution of events is describing some kinds of relationships (or dependencies) between the events within a topic where these relationships are narrating the changes of events from the seminal events to the final events along the timeline. There are variations of the interpretations of event evolution although there are some initial techniques to determine the relationships between events. Without a formal definition of event evolution, it is impossible to determine the objectives and evaluate and benchmark the proposing techniques. In this work, we define the event evolution as follow.
Event Evolution – When an event evolves to another event within a topic, there is an event evolution relationship between these two events.
In addition, we formally define the event evolution relationship with three rules.
Event Evolution Relationship – An event evolution relationship is the directional logical dependencies or relatedness between two events within a topic. The event evolution relationship from event A to event B must follow the three rules in below.
1. Event A must temporally precede event B.
2. Event A must be the necessary and/or the sufficient condition of event B.
3. The event evolution relationship must coincide with the user information needs.
The event evolution relationship must be directional. There must be a starting event and an ending event. The event evolution relationship between any two events is not symmetric. “Hurricane Katrina hits New Orleans” evolves to “Flooding caused severe damage in New Orleans” but “Flooding caused severe damage in New Orleans” cannot evolve to “Hurricane Katrina hits New Orleans”.
The above three rules describe the conditions to validate the existence of the event evolution relationships. In the first rule, it describes the constraint of the temporal order between event A and event if event A evolves to event B. Event A must occur before event B. In the next section, we shall further discuss the temporal preceding relationship in terms of event timestamp and Allen’s temporal relationships [8].
In the second rule, when event A evolves to event B, there are some necessary and/or sufficient conditions that event A possesses so that event B to occur. In some cases, event B will not occur unless event A occurs. In these situations, event A is considered as the necessary condition for event B to occur. In some other cases, event A occurs, and therefore, event B or other events may occur. In this satiation, event A is considered as a sufficient condition for event B to occur. The dependences between event A and event B can be a causal relationship or corollary relationship. For example, “Columbia space shuttle crash” evolving to “NASA conducted investigations into the shuttle crash” is a casual relationship. “Columbia space shuttle crash” can be considered as the necessary condition for “NASA conducted investigations into the shuttle crash”. NASA will not conduct any investigations unless there is a shuttle crash. Considering another example, “Yasser Arafat passed away” evolves “The new leader of Palestinian Liberation Organization was elected”. “Yasser Arafat passed away” is a sufficient condition of “The new leader of Palestinian Liberation Organization was elect”. Election of a new leader is a natural consequence of the death of the current leader; however, it is not a necessary condition. Election of a new leader can also be the consequence of other events, for example, the term of the current leader is ended.
In the third rule, it eliminates any unrelated relationship according to the information needs of users. In some situations, two events may follow the first two rules of event evolution relationship. However, the dependency between theses events does not provide any information value for the users to understand the evolution of the events within the news topic. Including such relationship will only create excessive information overheads but it is not helpful to the users.
3. Temporal Relationships
Event timestamps are used to determine the temporal relationships of the corresponding events. The event timestamp of an event can be determined from the stories that the event contains. Event timestamp is implemented as a time interval, which is the duration of time between two spot times along a linear timeline with one ahead or equal to another. The anterior spot time is the start time (s) and the posterior spot time is the end time (e) of the timestamp (t). The temporal distance between two timestamps, t1 = [s1,e1] and t2 = [s2,e2], is denoted as d(t1,t2). d(t1,t2) is computed as the difference between e1 and s2 if e1 is before or equal to s2; otherwise, d(t1,t2) equals to 0. The computation of temporal distance is illustrated in Figure 5.
Allen [3] has presented 13 possible temporal relationships. These relationships are presented and illustrated in Table 1. According to the first rule of our definition on event evolution relationship, “Event A must temporarily precede event B if event A evolves to event B”, there are only 8 temporal relationships in Table 1 obey this rule if the timestamps of event A and event B are t1 and t2 respectively. These temporal relationships are t1 < t2, t1 m t2, t1 o t2, t1 di t2, t1 s t2, t1 si t2, t1 fi t2, and t1 = t2.
[pic]
Figure 5. Computation of temporal distance between t1 and t2.
Table 1. Allen’s Temporal Relationships
| |Temporal Relationships |Illustration |Obey 1st rule of event evolution |
| | | |relationship? |
|1 |t1 < t2 (t1 before t2) | s1 e1 s2 e2 |Yes |
|2 |t1 > t2 (t1 after t2) | s2 e2 s1 e1 |No |
|3 |t1 m t2 (t1 meets t2) |s1 e1 |Yes |
| | |s2 e2 | |
|4 |t1 mi t2 (t1 met by t2) | s1 e1 |No |
| | |s2 e2 | |
|5 |t1 o t2 (t1 overlaps t2) |s1 e1 |Yes |
| | |s2 e2 | |
|6 |t1 oi t2 (t1 overlapped t2) | s1 e1 |No |
| | |s2 e2 | |
|7 |t1 d t2 (t1 during t2) | s1 e1 |No |
| | |s2 e2 | |
|8 |t1 di t2 (t1 contains t2) | s1 e1 |Yes |
| | |s2 e2 | |
|9 |t1 s t2 (t1 starts t2) | s1 e1 |Yes |
| | |s2 e2 | |
|10 |t1 si t2 (t1 started by t2) | s1 e1 |Yes |
| | |s2 e2 | |
|11 |t1 f t2 (t1 finishes t2) | s1 e1 |No |
| | |s2 e2 | |
|12 |t1 fi t2 (t1 finished by t2) | s1 e1 |Yes |
| | |s2 e2 | |
|13 |t1 = t2 (t1 equal to t2) | s1 e1 |Yes |
| | |s2 e2 | |
The other 5 temporal relationships will be utilized to filter those pairs of events that have invalid event evolution relationships.
4. Event Similarity
After filtering the pairs of evens that do not follow the first rule of event evolution relationship, we make use of the event similarity to identify the pairs of events that follow the second and third rules of event evolution relationship. When there are some types of dependency between two events, the content of these events usually have certain level of similarity. For example, the persons involved in these events are most likely the same. The location where these events occur is the same. The stories contained in the second event usually describe briefly what has happened in the event that it evolves from. On the other hand, if two events are independent from each other, their similarity is usually low. As a result, we utilize the event similarity to determine if there is an event evolution relationship between any two events.
In this work, we utilize the cosine similarity of terms spaces that are representing two events to measure the event similarity. A k-term feature vector, ωi = {ωi1, ωi2, …, ωik}, is used to represent a story i. The traditional TF-IDF function is utilized to compute ωik.
[pic]
where tfik is the frequency of term k in story i. N is the total number of documents in that topic and dfk is the number of stories which contains term k in that topic.
We compute the event term vector of event j using the average of the document term vectors of stories that belong to event j. We define the event term vector for event j as ω’j = {ω’j1, ω’j2, …, ω’jk} where,
[pic]
where nj is the number of stories in S that belongs to event j.
The event content similarity is computed as follow:
[pic]
5. Event Evolution Graph
Given the temporal relationships and event similarity, we build an event evolution graph to provide a graphical presentation of how events evolve within a news topic to the users. An event evolution graph is a directed acyclic graph, G, consisting of events as the nodes and event evolution relationships as the directed edges between nodes.
Given a set of n distinct news stories S = {s1, s2, ∙∙∙, sn} on a given news topic, we have a set of m events E = {e1, e2, ∙∙∙, em} and their event timestamps T = {t1, t2, ∙∙∙, tm}. We can build a one-to-one mapping function τ that maps each event to its corresponding event timestamp:
τ(ek) = tk (1 ≤ k ≤ m)
Each of the n stories is assigned to one of the m events.
ƒ(si) = ek iff si[pic]ek (1 ≤ i ≤ n, 1 ≤ k ≤ m)
We denote the event evolution relationship from event ei to ej, if existing and valid, as (ei, ej) (i ≠ j). A directed edge from vertex ei to ej is created in the event evolution graph accordingly. Event ei the parent of event ej and event ej is the child of event ei.
The set of valid event evolution relationships between m events is represented a set of directed edges L = {(ei, ej)} in the event evolution graph where ei, ej[pic]E. Combining the set of m events E as the nodes and the set of event evolution relationships L as the directed edges between the nodes, we have a directed acyclic graph G = {E, L}.
There are two steps in verifying the validity of an event evolution relationship between any pair of events, ei and ej, in E.
1. ei evolves to ej if and only if ei and ej follow any one of the eight temporal relationships as described in Section 0. i.e. ti < tj, ti m tj, ti o tj, ti di tj, ti s tj, ti si tj, ti fi tj, and ti = tj.
2. ei evolves to ej if and only if cos_sim(ei,ej) > threshold.
6. Examples
In this section, we use two examples to illustrate the construction of event evolution graphs.
Example 1
We use the topic “NBA player Kobe Bryant charged with sexual assault” as the first example. In this topic, there are totally 82 documents and 16 events. In each document, title, timestamp, headline, text, summary, etc. are marked up in XML format as illustrated in Figure 6.
[pic]
Figure 6 News document in XML format.
[pic]
Figure 7. The user interface to view the events and documents.
Table 2 gives the details of the 16 events in this topic. The number of documents, the start time and end time of each event are given. There are 5.1 documents per event on average. Event 11 and Event 12 have the largest number of documents. These events describe the hearing and court trial between December 14, 2003 and August 18, 2004.
The event evolution graph is generated by a professional annotator. In the first step, the professional annotator read through the news stories several times and formed a general picture of event evolution graph. In the second step, he was asked to identify the events and assigned each story to one of the events. Given the events, the annotator identified the evolution relationship based on the three rules as defined in Section 0. The annotator reviewed and revised the event evolution graph until no further revision could be made.
Figure 8 presents the event evolution graph of “NBA player Kobe Bryant charged with sexual assault” news topic. The numbers adjacent to the nodes are the event number of the corresponding nodes. The blue nodes are events that only have out-going links but no in-coming links. In this case, it is the first event. The red nodes are events that have only in-coming links but no out-going links. Event 2, 4, 7, 10, and 16 are events that do not evolve to any other events. In particular, Event 16 is the last event. Event 1 and Event 5 have the largest number of out-going links. These are the seminal events that have impact on many other events.
Table 2 Events in “NBA player Kobe Bryant charged with sexual assault”
|Event no. |Label |Number of |Start time |End time |
| | |doc. | | |
|1 |Kobe Bryant is arrested and charged for sexual assault crime |6 |2003-07-07 05:28|2003-07-19 |
| | | | |10:02 |
|2 |Kobe denies the sexual assault charge and the accuser responds |2 |2003-07-21 11:09|2003-07-21 |
| | | | |15:28 |
|3 |Judge orders to limit public comments and keep private information and |6 |2003-07-25 03:21|2003-08-06 |
| |arguments emerge about the judge’s order | | |16:38 |
|4 |Bryant case D.A. office says it received threats |1 |2003-07-26 10:46|2003-07-26 |
| | | | |10:46 |
|5 |The first hearing for charging Kobe sexual assault is conducted |7 |2003-07-31 09:21|2003-08-06 |
| | | | |17:34 |
|6 |Kobe Bryant sexual assault case documents and details unsealed |3 |2003-08-19 16:13|2003-08-28 |
| | | | |18:45 |
|7 |Kobe fans and supporters threaten to kill Kobe accuser |3 |2003-08-20 21:07|2003-09-22 |
| | | | |18:51 |
|8 |Kobe’s lawyers fight for the medical records of the accuser |3 |2003-09-05 07:08|2004-01-23 |
| | | | |10:52 |
|9 |The second hearing for Kobe case is held and Judge decides that Kobe |8 |2003-10-02 10:47|2003-10-20 |
| |must stand trial | | |12:11 |
|10 |Analysis of the effects of Colorado rape laws upon Kobe case |3 |2003-10-15 09:37|2003-10-28 |
| | | | |14:49 |
|11 |The hearing and court defense for Kobe case continues and defense argues|14 |2003-12-14 22:43|2004-05-06 |
| |accuser’s medical records and history | | |16:46 |
|12 |The court trial for Kobe case and Kobe was declared to be innocent |15 |2004-06-10 21:00|2004-08-18 |
| | | | |22:36 |
|13 |Kobe accuser files civil lawsuit against Kobe Bryant |2 |2004-08-11 17:10|2004-08-23 |
| | | | |19:32 |
|14 |Final trial for Kobe case and Kobe was declared to be innocent |5 |2004-08-24 22:57|2004-09-02 |
| | | | |02:08 |
|15 |Kobe Bryant apologizes publicly to the accuser |1 |2004-09-02 02:33|2004-09-02 |
| | | | |02:33 |
|16 |Kobe accuser’s lawyers and analysts talk about Kobe case |3 |2004-09-07 14:27|2004-09-07 |
| | | | |16:22 |
[pic]
Figure 8 Event evolution graph of “NBA player Kobe Bryant charged with sexual assault” news topic.
Figure 9 presents the event evolution graphs that are generated automatically by using the temporal relationships and event similarity as described in Section 0 to Section 0. The event evolution graph in Figure 9 (a) uses a threshold of 0.50 in event similarity. The event evolution graph in Figure 9 (b) uses a threshold of 0.57. The red links are the correct event evolution relationships identified by the system. The black links are the incorrect event evolution relationships identified by the system. The green links are the evolution relationships missed by the system.
Using a lower threshold of 0.50 as shown in Figure 9 (a), the system identifies 19 correct and 10 incorrect event evolution relationships and misses 4 event evolution relationships. (The professional annotator identified 23 event evolution relationships.) The precision is 0.66 and the recall is 0.83. With a higher threshold of 0.57 as shown in Figure 9 (b), the system identifies 15 correct and 5 incorrect event evolution relationships but misses 8 event evolution relationships. The precision is 0.75 and the recall is 0.65. Increasing the threshold of event similarity make the precision increase but make the recall decrease.
[pic] [pic]
(a) threshold = 0.50 (b) threshold = 0.57
Figure 9. Event evolution graphs generated automatically by system with thresholds of 0.50 and 0.57.
Table 3 Event evolution relationships in Figure 8 and Figure 9 (a).
|Event Evolution Relationship in |Correct Event Evolution |Missed Event Evolution |Incorrect Event Evolution |
|Figure 8 |Relationship in Figure 9 (a) |Relationship in Figure 9 (a) |Relationship in Figure 9 (a) |
|Event 1 ( Event 2 |✔ | | |
|Event 1 ( Event 3 |✔ | | |
|Event 1 ( Event 4 | |✔ | |
|Event 1 ( Event 5 |✔ | | |
|Event 3 ( Event 5 |✔ | | |
|Event 3 ( Event 6 |✔ | | |
|Event 5 ( Event 6 |✔ | | |
|Event 5 ( Event 7 | |✔ | |
|Event 5 ( Event 8 |✔ | | |
|Event 5 ( Event 9 |✔ | | |
|Event 6 ( Event 9 |✔ | | |
|Event 8 ( Event 9 |✔ | | |
|Event 8 ( Event 11 |✔ | | |
|Event 8 ( Event 12 |✔ | | |
|Event 9 ( Event 10 | |✔ | |
|Event 9 ( Event 11 |✔ | | |
|Event 11 ( Event 12 |✔ | | |
|Event 12 ( Event 13 |✔ | | |
|Event 12 ( Event 14 |✔ | | |
|Event 13 ( Event 14 |✔ | | |
|Event 14 ( Event 15 | |✔ | |
|Event 14 ( Event 16 |✔ | | |
|Event 15 ( Event 16 |✔ | | |
| | | |Event 2 ( Event 4 |
| | | |Event 3 ( Event 8 |
| | | |Event 3 ( Event 9 |
| | | |Event 3 ( Event 11 |
| | | |Event 5 ( Event 11 |
| | | |Event 6 ( Event 8 |
| | | |Event 6 ( Event 11 |
| | | |Event 11 ( Event 14 |
| | | |Event 12 ( Event 16 |
| | | |Event 13 ( Event 16 |
Table 4. Event Evolution Relationships in Figure 8 and Figure 9 (b).
|Event Evolution Relationship in |Correct Event Evolution |Missed Event Evolution |Incorrect Event Evolution |
|Figure 8 |Relationship in Figure 9 (b) |Relationship in Figure 9 (b) |Relationship in Figure 9 (b) |
|Event 1 ( Event 2 |✔ | | |
|Event 1 ( Event 3 |✔ | | |
|Event 1 ( Event 4 | |✔ | |
|Event 1 ( Event 5 |✔ | | |
|Event 3 ( Event 5 |✔ | | |
|Event 3 ( Event 6 |✔ | | |
|Event 5 ( Event 6 |✔ | | |
|Event 5 ( Event 7 | |✔ | |
|Event 5 ( Event 8 | |✔ | |
|Event 5 ( Event 9 |✔ | | |
|Event 6 ( Event 9 |✔ | | |
|Event 8 ( Event 9 |✔ | | |
|Event 8 ( Event 11 |✔ | | |
|Event 8 ( Event 12 | |✔ | |
|Event 9 ( Event 10 | |✔ | |
|Event 9 ( Event 11 |✔ | | |
|Event 11 ( Event 12 |✔ | | |
|Event 12 ( Event 13 |✔ | | |
|Event 12 ( Event 14 |✔ | | |
|Event 13 ( Event 14 | |✔ | |
|Event 14 ( Event 15 | |✔ | |
|Event 14 ( Event 16 |✔ | | |
|Event 15 ( Event 16 | |✔ | |
| | | |Event 3 ( Event 8 |
| | | |Event 3 ( Event 9 |
| | | |Event 11 ( Event 14 |
| | | |Event 12 ( Event 16 |
| | | |Event 13 ( Event 16 |
Example 2
In the second example, we use the topic of “Death of Arafat”. There are totally 38 documents and 11 events. Table 5 gives the details of the events. There are 3.5 documents per event on average.
Table 5. Events in “Death of Arafat”.
|Event no. |Label |Number of |Start time |End time |
| | |doc. | | |
|1 |Arafat was allowed by Israel to leave compound for hospital |1 |2004-10-25 21:41|2004-10-25 21:41|
|2 |Arafat entered Paris hospital and underwent medical tests |7 |2004-10-28 19:07|2004-11-05 10:16|
|3 |Rumors about Arafat’s health and Palestine’s future |5 |2004-10-31 01:45|2004-11-10 14:42|
|4 |Palestinian police planned security in case of Arafat’s death |1 |2004-11-07 04:23|2004-11-07 04:23|
|5 |Palestinian officials visited Arafat in Paris hospital |2 |2004-11-08 04:24|2004-11-08 22:07|
|6 |Arafat was in deep coma and finally passed by |2 |2004-11-10 02:40|2004-11-11 09:01|
|7 |Agreement on Arafat’s funeral was reached and preparations started |5 |2004-11-11 02:29|2004-11-11 17:25|
|8 |Reactions on Arafat’s funeral was reached and preparations started |3 |2004-11-11 12:18|2004-11-12 14:10|
|9 |Abbas was elected PLO leader as the successor of Arafat |3 |2004-11-11 18:09|2004-11-17 19:06|
|10 |Arafat’s burial was done and people around the world mourn Arafat’s |6 |2004-11-12 02:58|2004-11-13 23:58|
| |burial | | | |
|11 |Arafat’s nephew as a Palestinian official checked Arafat’s medical |3 |2004-11-18 19:17|2004-11- 24:18 |
| |records | | | |
Figure 10 presents the event evolution graph generated by the profession annotator. There are totally 18 event evolution relationships. Event 2 and Event 6 have 5 out-links. These are the seminal events that cause a sequence of events. Event 2 describes Arafat entering to hospital and Event 6 describes Arafat passing away.
Figure 11 presents the event evolution graph generated automatically by the system using a threshold of 0.65 in event similarity. It identifies 15 correct event evolution relationships and 3 incorrect event evolution relationships. It misses 3 event evolution relationships. The precision is 0.83 and the recall is 0.83. Event 2 is a seminal event; however, the event evolution relationship between Event 2 and Event 4 and the event evolution relationship between Event 2 and Event 7 are missed in the automatic event evolution graph in Figure 11. Event 4 describes the police was planning security which is less relevant to Arafat’s hospitalization although it is caused by Event 2. The temporal distance between Event 2 and Event 7 and the temporal distance between Event 6 and Event 11 are large. Therefore, the event evolution relationships are not as obvious as the others. On the other hand, the event evolution relationship between Event 3 and Event 9 and the event evolution relationship between Event 3 and Event 10 are incorrectly identified by the system because there are similarities in the description of the events. However, the rumors of Arafat’s death have nothing to do with the election and the mourning of the people.
[pic]
Figure 10. Event evolution graph of “Death of Arafat”.
[pic]
Figure 11. Event evolution graph generated automatically by system with threshold of 0.65.
Table 6 Event evolution relationships in Figure 10 and Figure 11
|Event Evolution Relationship in |Correct Event Evolution |Missed Event Evolution |Incorrect Event Evolution |
|Figure 10 |Relationship in Figure 11 |Relationship in Figure 11 |Relationship in Figure 11 |
|Event 1 ( Event 2 |✔ | | |
|Event 2 ( Event 3 |✔ | | |
|Event 2 ( Event 4 | |✔ | |
|Event 2 ( Event 5 |✔ | | |
|Event 2 ( Event 6 |✔ | | |
|Event 2 ( Event 7 | |✔ | |
|Event 3 ( Event 5 |✔ | | |
|Event 3 ( Event 6 |✔ | | |
|Event 3 ( Event 7 |✔ | | |
|Event 5 ( Event 6 |✔ | | |
|Event 5 ( Event 7 |✔ | | |
|Event 6 ( Event 7 |✔ | | |
|Event 6 ( Event 8 |✔ | | |
|Event 6 ( Event 9 |✔ | | |
|Event 6 ( Event 10 |✔ | | |
|Event 6 ( Event 11 | |✔ | |
|Event 7 ( Event 10 |✔ | | |
|Event 8 ( Event 10 |✔ | | |
| | | |Event 3 ( Event 9 |
| | | |Event 3 ( Event 10 |
| | | |Event 9 ( Event 10 |
7. Conclusion
Event evolution is a new and important concept in topic detection and tracking. In the traditional work, we only focus on the detection of new event or topic and determine if a new story belongs to any of the identified events or a new event. However, the limitation of the previous work is not being able to present the evolution of events. Users are required to browse through the events according to their temporal order to understand how the events are developed within a news topic. In this work, we formally define event evolution with three rules based on the events’ temporal order, necessary and/or sufficient condition and user information needs. Temporal relationships and event similarity are utilized to extract the event evolution relationship. We use the event evolution graph to present the events and event evolution relationships. Such graphical presentation facilitates the user navigation of event evolution. Users can easily capture the underlying structure of events within a news topic.
References
Aixin Sun and Ee-Peng Lim. Hierarchical text classification and evaluation. In Proceedings of the 2001 IEEE International Conference on Data Mining, pages 521–528. IEEE Computer Society, 2001.
Chris Ding, Xiaofeng He. K-means Clustering via Principal Component Analysis. In Proceedings of the 21 st International Conference on Machine Learning, Article No. 29, 2004.
James Allan. Detection as Multi-Topic Tracking. Information Retrieval, vol. 5, pp. 139-157, 2002.
James Allan, editor. Topic Detection and Tracking: Event based Information Organization. Kluwer Academic Publishers, 2000.
James Allan, Jaime Carbonell, George Doddington, Jonathan Yamron, Yiming Yang. Topic Detection and Tracking Pilot Study Final Report. In Proceedings of the Broadcast News Transcription and Understranding Workshop, 1998.
James Allan, Ron Papka, and Victor Lavrenko. On-line new event detection and tracking. In Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, ACM Press, pages 37–45, 1998
James Allan, Rahul Gupta, and Vikas Khandelwal. Temporal summaries of new topics. In Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, pages 10–18. ACM Press, 2001.
James F. Allen. Maintaining knowledge about temporal intervals. In Communications of the ACM, Volume 26, Issue 11, pages 832–843, 1983.
J. Carthy. Lexical Chains for Topic Detection. Technical Report in Department of Computer Science: National University of Dublin, 2002
Juha Makkonen. Investigations on event evolution in TDT. In Proceedings of HLT-NAACL 2003 Student Workshop, pages 43–48, 2004.
Qiaozhu Mei, Chengxiang Zhai. Discovering evolutionary theme patterns from text: an exploration of temporal text mining. In Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 198-207, 2005.
Ramesh Nallapati, Ao Feng, Fuchun Peng, James Allan. Event threading within news topics. In Proceedings of the 2004 Thirteenth ACM conference on Information and knowledge management. pages 446-453, 2004.
Yiming Yang, Tom Pierce, Jaime Carbonell. A Study on Retrospective and On-Line Event Detection. In Proceedings of SIGIR-98, 21st ACM International Conference on Research and Development in Information Retrieval, 1998.
Yiming Yang, Jaime Carbonell, Ralf Brown, Thomas Pierce, Brian T. Archibald, and Xin Liu. Learning approaches for detecting and tracking news events. In IEEE Intelligent Systems Special Issue on Applications of Intelligent Information Retrieval, volume 14 (4), pages 32–43, 1999.
Y. Yang, T. Ault, T. Pierce, and C. W. Lattimer. Improving text categorization methods for event tracking. In Proceedings of the 23rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval., Athens, Greece, 2000.
Y. Yang, J. Carbonell, R. Brown, J. Lafferty, T. Pierce, and T. Ault. Multi-Strategy Learning for TDT. In Topic Detection and Tracking: Event-based Information Organization, J. Allan, Ed. Norvell: Kluwer Academic Publishers, 2002, pp. 85-114.
Y. Yang, J. Zhang, J. Carbonell, and C. Jin. Topic-conditioned novelty detection. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2002.
-----------------------
Theme 1
Theme 2
Theme 3
Theme 4
Theme 5
Theme 5
Theme 4
Theme 3
Theme 2
Theme 1
Theme 5
Theme 4
Theme 3
Theme 2
Theme 1
Theme 5
Theme 4
Theme 3
Theme 2
Theme 1
Theme 5
Theme 4
Theme 3
Theme 2
Theme 1
Source
Topic 1
Topic 2
Topic 3
Topic 4
…
Event 1
Event 1
Event 2
Event 3
…
Story 3
Story 2
Story 1
Event 1
…
Event 1
Event 2
Event 3
Event 4
Event 5
d(t1,t2) = 0
e2
s2
e1
s1
d(t1,t2)
3
2
1
16
s1
e1
s2
e2
4
t
t
5
6
7
8
9
10
11
12
13
14
15
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
11
10
9
8
7
6
5
4
3
2
1
11
10
9
8
7
6
5
4
3
2
1
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- the evolution of surgery
- major news events of 2019
- major news events of 2010
- the evolution of humans
- the evolution of humans timeline
- the evolution of earth
- the evolution of life
- the evolution of slavery
- the evolution of the airplane
- the evolution of cameras timeline
- timeline the evolution of life
- the evolution of technology