CUTS: CUrvature-Based Development Pattern Analysis

and Segmentation for Blogs and other Text Streams

Tempe, AZ 85287 yan.qi@asu.edu

(a) Long vs. short segment

(b) More vs. less change

(c) High vs. low con- centration

Figure 1: Visualizing topic development differences between consecutive segments; all three cases show two consecutive segments: in (a) the first segment is longer than the second one; in (b) the first segment diverges faster than the second; and in (c) the first segment is more concentrated than the second

where there is no development structure, more traditional, keyword-based search [2, 3] is generally sufficient. However, many weblogs (such as news commentaries and education sites) where there is a correlation between materials in blogs and real world events, it is important to understand the development of structure of the blog. Since blogs are not structured in a particular way but time, it is generally not possible to navigate among entries in a given collection of blog entries in an informed manner. Thus, our primary goal is to segment the sequence of entries in a filter-type blog on the basis of the topic development patterns.

Example 1.1 (Visualizing Topic Segments). A ma- jor motivation of our work is to enable indexing as well as ease of navigation of the blogs. Therefore, the various topic development patterns need to be visualized in a convenient manner to the user. In Figure 1, we depict one way to achieve this in a compact and easy to use manner. In this scheme, a gradient is used to denote a topic segment. The length of the gradient visualizes how long the topic segment lasts; its height denotes how fast the topic segment changes, and the saturation of the gradient measures how concentrated the topic segment is.

Figure 2 shows an example of the visualization scheme introduced in Figure 1. Figure 2 is a visualization of the topic development patterns for the weblog (Talking Point Memo [4]) from January, 2005 to October, 2005. There are three layers in the visualization. The top layer depicts the highest level topic segmentation. The segments on the lower layers are clustered under the higher level segments. A tri- angle shows the location and duration of an interrupt, i.e. a temporary, but significant change in content. The content for each topic segment can also be quickly explored though a mouse cursor, i.e., clicks on a segment would guide the user to the relevant entries.

Note that there are other visualization schemes as well. In this paper, we do not focus on any specific scheme, rather we concentrate on extraction of topic development patterns with the goal of enabling effectively visualization schemes.

Based on the above example, there are three topic develop- ment patterns that are of primary interest to us for indexing and navigation purposes:

• Dominated: there is one (or more) dominant topic(s) in a given sequence of entries. • Drifting: the content of the segment is gradually tran- sitioning from one topic to an other. • Interrupted: a different, significant but temporary, topic emerges and disappears during the natural (concen- trated or drifting) flow of the blog.

In addition to these patterns, how concentrated a given seg- ment is in terms of its content and how fast it changes are

Jul 31st – Aug 21st :

corruption; contract

Figure 2: An example visualization scheme for a blog archive. The visualization interface not only presents a hierarchy of dominant topics, but also how fast topics develop and change and when signif- icant interrupts occur. This interface is intended for experts who are interested in understanding and ex- ploring the development patterns through blog anal- ysis. Although we do not focus on a particular visu- alization or indexing scheme, CUTS is intended to enable development of this or similar tools

important pieces of information needed both for visualiza- tion and indexing. The section 2-4 will discuss these issues in detail.

1.2 Related Work One method often used in text segmentation is text tiling, which makes use of patterns of lexical co-occurrence to sub- divide texts into multi-paragraph units that represent pas- sages or subtopics [14]. In [20], Reynar provides an extensive discussion of algorithms for topic segmentation, including compression, optimization, and word frequency algorithms. All of these make use of topic shift indicators as cues for topic segmentation. Typical indicators include repetitions of character sequences, patterns of word and word n-gram repetition, word frequency, and the presence of certain key phrases. A probabilistic latent semantic analysis model is used in [11] for segmenting a document. Blei et al. [8] used partially unsupervised topic segmentation on unstructured text by means of a hidden Markov model. In [13], Fung et al. constructed a model with a hyper-geometric distribu- tion to detect bursty events. The advantage of this model is the fact that it does not need tuning or estimating any of parameters.

A related research domain is topic detection and track- ing (TDT) [5, 10, 27], which mainly focuses on detecting and tracking events in streaming news data. Most TDT systems compare a new document with the past documents and make a decision regarding the novelty of the story based on the content-based similarity values. In contrast, the naturally evolving nature of blogs and the need for fine- granularity segment boundary identification make the prob- lem of topic segmentation in blogs significantly harder than the new-event detection problem addressed by the TDT technologies. In [15], Plaunt et al. exploit the idea of curve analysis to assist text segmentation. More recently, An- drews et. al also exploited a similar scheme [6]. The basic idea behind these approaches is as the following: A text is split into small pieces using a sliding window; a weighted keyword vector represents each piece. Then, the similar- ity between consecutive entries is measured using an ap- propriate similarity measure to obtain the sequence: T = (s1,2, . . . , si,i+1, . . . , sm−1,m), where si,i+1 is the similarity between the ith entry and the (i + 1)th entry. In a sense, T tracks how drastically the content of the input stream of

Figure 3: An existing text segmentation method which uses a similarities-curve[6]: the curve tracks how drastically the content of the input stream of entries changes between consecutive entries and the segment boundaries are chosen at the local minima of the curve

entries changes between consecutive entries (Figure 3). The main idea underlying these approaches is that topic shift occurs at local minima of the curve: low value of similarity between entries means little relationship, and boundaries are likely to be located where consecutive entries are not related to each other. In the example shown in Figure 3, the local minima-based approach presented in [15, 6] leads to four boundaries.

This curvature-based approach is quite simple and effec- tive, especially when the topic boundaries are indeed marked with drastic changes in the similarities of consecutive en- tries. However, as we will see, this usually is not the case. Furthermore, since these approaches ignore all other infor- mation except the relationship between consecutive entries, they do not capture richer content development patterns. In [25], Wong et al. combines techniques of both data min- ing and data visualization to explore sequential patterns in large text corpora. They focus on correlations between dif- ferent specific items, not topic development patterns.

1.3 Proposed Approach and Contributions of this Paper In this paper, we present a novel algorithm, CUTS(CUrvature- based development pattern analysis and segmentation for blogs and other Text Streams) to topic segmentation of text streams and blogs. A key output of CUTS is the set of topic development patterns inherent in the sequence of en- tries. This knowledge helps in constructing properly anno- tated navigational helps, such as tables-of-contents, as well as proper segment indexes for context-aware search.

As in [15, 6], CUTS relies on curvature analysis for iden- tifying boundaries. However, unlike the previous ap- proaches, CUTS does not apply curvature analysis on the similarities curve (illustrated in Figure 3). Instead, it pre- processes the content in a way that brings out various topic development patterns as different curvature signatures. CUTS is composed of three phases:

(a) analysis of the content in the blog entries and gener-

ation of a representative signature (an appropriately weighted keyword vector) for each entry;

(b) mapping of the sequence of entries onto a curve which

brings out various topic development patterns; and

(c) analysis of the resulting curve to identify topic seg-

ments and topic development patterns.

In the following sections, we discuss these three phases in detail. The structure of the paper is as follows. Section 2 briefly describes the data representation we use for indi- vidual blog entries. Section 3 discusses how CUTS maps blog entries onto a curve in a way that highlights topic de- velopment patterns. Section 4 provides an overview of the curve segmentation algorithms we rely on and discusses how to produce base topic segments and identify topic develop- ment patterns based on the output generated with these curve segmentation mechanisms. Section 5 experimentally verifies the performance of our approach.

REPRESENTATION OF THE BLOG EN- TRIES CUTS represents each blog entry using a conventional TF- IDF based scheme. For each entry, we construct a vector of weights, Pi = {wi,1, wi,2, . . . , wi,n}, where n is the number of keywords in all entries concerned and i ∈[1, N] , N is the number of entries in the blog. When extracting keywords from the text, stop words are removed and a stemmer is employed. The TF-IDF weight, wi,j, of a keyword j in en- try i is then computed. Given these keyword weights, the similarity, si,j, between two entries, i and j, is defined as

n 

wi,k · wj,k.

si,j =

k=1

Finally a dissimilarity matrix D is generated for all of en- tries concerned in the blog. In D, each value represents the dissimilarity (di,j = 1−si,j) between a given pair of entries.

⎡

⎤

d1,1 d1,2 . . . d1,N d2,1 d2,2 . . . d2,N ...

⎢⎢⎣

⎥⎥⎦

D =

... dN,1 dN,2 . . . dN,N

... di,j

Note that given the similarity values, it is possible to mine for independent topics in the collection using a latent seman- tic indexing (LSI)-based method [17]. LSI, however, would not consider the temporal correlation between entries, thus would miss an important dimension in topic development in blogs. Nevertheless, singular valued decomposition (which forms the basis of the LSI technique) can also be exploited in CUTS to reduce the number features to be considered for dissimilarity matrix construction.

We also note that the keyword weight (wi,k) can also in- corporate additional domain knowledge. For example, when there are multiple related blogs, the keyword weights can re- flect importance of the words across related (in time or by reference) entries in different blogs. For simplicity and clar- ity, in this paper we do not focus on the co-segmentation of correlated blogs. We also do not consider links in the blog entries. However it is easy to extend CUTS to analysis of multiple correlated blogs and this will be part of our future work.

MATERIALIZING TOPIC DEVELOPMENT PATTERNS THROUGH A CUTS-CURVE As discussed in the related work section, similarity curves are used in the literature for analyzing the content of text streams [15, 6]. Our main observation in this paper is that the similarity curves used in the literature for curvature

Figure 4: Topic development patterns highlighted by CUTS-curve

6.5

6.5

Value of Entries

Value of Entries

Value of Entries

5.5

5.5

4.5

4.5

3.5

3.5

0 2 4 6 8 10 12 14 16 18 20 3

0 2 4 6 8 10 12 14 16 18 20 5

Sequence Number of Entries

Sequence Number of Entries

(a) Dominated

(b) Drifting

analysis cannot capture anything but pairwise relationships of the neighbors. On the other hand, segments in a naviga- tion structure need to capture the global structure of a large body of entries. Furthermore, identifying general develop- ment patterns (such as dominated, drifting, and interrupted introduced in Section 1.1) requires more knowledge than the relationship between immediate neighbors.

Thus, instead of using the similarity curves as in [15, 6], CUTS creates a curve which brings the underlying struc- ture and development patterns into light. For this purpose, CUTS relies on multi-dimensional scaling (MDS) [24]. MDS is a class of search techniques for mapping data into a multi- dimensional space based on a given list of distance values be- tween data elements. The mapping is such that the distances between points in the space best match the dissimilarities between the corresponding objects [12]. In this paper, we exploit this property of MDS. In particular,

(a) CUTS first maps all entries to a 1-dimensional space

based on their dissimilarities (using the matrix D);

(b) CUTS then extends the space with the corresponding

time dimension: i.e., CUTS maps the entries onto a 2- dimensional space, where the x-axis denotes the time (or the sequence number of the entries in the blog archive) and the y-axis denotes the MDS-computed dissimilarity dimension.

In the resulting two dimensional space, the consecutive en- tries form a curve (referred to as the CUTS-curve), on which various topic development patterns emerge:

• Dominated: In dominated segments, there is one or more stable topics in the given sequence of entries. In the CUTS-curve, such segments have the horizontal pattern shown in Figure 4(a): all points in this pat- tern are similar to each other (i.e., they form a clique where the distances between the entries are close to each other). Once this clique is mapped into a 1- dimensional space through MDS, the entries are nat- urally mapped close to each other and when they are plotted against time, a horizontal pattern emerges. In the example shown in Figure 5, such a dominated be- havior is visible in the segment a, relatively horizontal, part of the curve.

• Drifting: In drifting segments, the content is in the way of transition from one topic to the other. When all entries are plotted in a CUTS-curve, we obtain the pattern shown in Figure 4(b). Although consecutive

8.5

7.5

Value of Entries

6.5

5.5

4.5

0 2 4 6 8 10 12 14 16 18 3

0 2 4 6 8 10 12 14 16 18 3.5

Sequence Number of Entries

Sequence Number of Entries

(c) Interrupted (case 1)

(d) Interrupted (case 2)

0.5

0.4

0.3

a

0.2

Value of Entries

0.1

b

−0.1

−0.2

−0.3

0 10 20 30 40 50 60 70 80 −0.4

Sequence Number of Entries

Figure 5: A CUTS-curve of a sequence of blog en- tires; the x-axis represents the sequence number of entries and the y-axis represents the position of each entry in the 1-dimensional space mapped by MDS

entries are similar to each other, MDS forces a place- ment, such that there is a significant difference be- tween the entries in the beginning of the pattern and those entries in the end of the pattern (essentially, the end-points correspond to two different topics). Fur- thermore, the slope of the curve reflects the speed with which the topic evolves from one to the other. A drifting segment b is visible immediately after the first dominated segment a. The example shows in Fig- ure 5.

• Interrupted: In an interrupted segment, a signifi- cant, but temporary, topic emerges while one topic or a topic developing pattern is presented. When the en- tries are plotted in a CUTS-curve, we see two cases (Figure 4(c) and Figure 4(d)) of interruptions, corre- sponding to interruption of dominated or drifting pat- terns, respectively. The shapes of the interrupted pat- terns are usually of the form “∨” or “∧”. In fact, this pattern is usually composed of two opposite drifting patterns. However, unlike two independent drifting patterns, this class of segments usually have aligned (and similar) end-points; thus it is more reasonable to combine them.

Thus, given the dissimilarity matrix D as input, CUTS obtains a vector ˜Y = (y1,1, y2,1, . . . , yn,1) through MDS. ˜Y represents the structural relationships of the entries in the blog. Finally, we extend the entries in ˜Y with time (the sequence numbers of the entries) to obtain a 2-dimensional CUTS-curve, C (as in Figure 5), where the x-axis denotes time and y-axis denotes the position of the entries in the 1-dimensional space mapped by MDS.

As discussed next, we then segment this CUTS-curve to identify the various segments and their temporal develop- ment patterns.

TOPIC SEGMENTATION AND PATTERN IDENTIFICATION BY CUTS In the context of image processing, curve segmentation is a widely used technique for analyzing dominant visual features, such as shapes and outlines [18]. Curve segmenta- tion helps detect critical boundary points (such as minima, maxima, zero-crossings, and discontinuities) which are im- portant in understanding these features. In this work, we exploit curve segmentation for understanding the underly- ing patterns in the CUTS curve obtained as described in the previous section.

4.1 Adaptive Curve Segmentation [19] Given a curve C = {xi, yi}N

i=1, the goal of curve segmen- tation algorithms is to find the subset of dominant points D = {xi, yi}M

i=1 (where M ≤N and D ⊆C), such that each resulting curve segment has uniform features. There are two major categories of approaches to curve segmenta- tion. The first approach is segmentation through polygonal approximation. In this approach, a curve is approximated and then segmented into a series of simple straight lines. In [21], various of approaches of this category are discussed and assessed. The second (more general) approach is to treat the given curve as if it is made up of straight lines as well as arcs. Therefore, the goal becomes to find not only the subset of dominant points D = {xi, yi}M

i=1, but also a set S = {αi}M−1

i=1 where αi represents the curvature between point i and point i + 1 in the set D. In this paper, we rely on the first approach, where a curve is split into a series of straight lines. The use of the second approach for more descriptive development patterns is part of our future work.

Segmenting a curve into straight lines is not straightfor- ward. For instance, a simple thresholding mechanism for determining boundaries is not appropriate, as the curve may behave differently at different parts and a single threshold may not be able to capture the temporal variations in the curve behavior. Thus, it is essential to use a scheme which can adapt to local changes in the curve behavior. In this paper, we build on [19]: in its first phase, [19] divides the points in the curve and constructs a binary tree; the second phase traverses the binary tree and decides the best representation of the curve with a series of straight lines.

For a detailed example, let us consider the curve in Fig- ure 6. In the figure, the curve is approximated by a series of straight lines, through four iterations. First, the line e1 is used to approximate the entire curve. The associated break- point is identified as b1. The line e1 is placed as the root of the binary tree in Figure 6(e). Then the part of the curve af- ter (or to the right of) b1 is considered. This curve gives the line e2 and the breakaway point b2. This process is repeated until the number of points in any given segment is at most a certain number, called MinSpan. At the end of the process, the resulting curve segment are organized as a binary tree where each node represents a straight line. Each level in the binary tree approximates the curve with a different granu- larity. Figure 6(e) shows the binary tree which represents the lines obtained from Figure 6(a) to Figure 6(d).

In order to get the optimal series of lines, the algorithm

b1

b1

e2

e3

b2

b3

b2 b3

s1

e1

e4

- - -

{e1} {e2} {e3} {e4} (a) Binary tree

(b) Curve segments

Figure 7: An example for over-segmentation: e2 and e3 should be replaced by s1 because one topic is fo- cused in this part rather than two

traverses the binary tree in a bottom-up manner. At each node, the significance of the line is compared with the sig- nificances of its children. If the significance of any of its two children is larger than that of the node, then the par- ent is removed from consideration; in a sense the children get upgraded, taking the place of their parent in the tree. The darker shaded nodes in Figure 6(e) illustrate the curve segments chosen through this process.

4.2 EliminationofOver-SegmentationandIden- tification of Topic Development Patterns The curve segmentation scheme [19] described above has a number of desirable features in the context of topic seg- mentation:

• Most parameters (except MinSpan) used in the algo- rithm do not require to be set by the user. There is no need for error tolerances or noise estimations.

• The measure of significance is based on a (pseudo-) psychological measure of perceptual significance: the longer the feature primitive, the greater the maximum deviation tolerated [22]. Thus, long lines will be kept for their stronger perceptual basis. This feature can reduce negative influence of local extremes when seg- menting the curve.

In topic segmentation, a line composed of a sequence of entries can represent a pattern. When longer patterns are preferred, this feature can help ignore or tolerate possible minor and very short term divergences in the development of a topic.

• The algorithm has scale invariance. That means, it will find the same structures without regards to the sizes of the curves. The feature makes it possible for us to effectively focus on a detailed analysis of parts of a curve, or study it at a higher level.

We on the other hand note that although this algorithm is adaptive and works well for curve segmentation tasks and has various advantages as stated above, it unfortunately does not immediately provide topic segments.

4.2.1 Reasons for Oversegmentation The curve segmentation algorithm in [19], or any other curve segmentation algorithm which relies on curvature anal- ysis is likely to oversegment topics, especially when there are frequent topic interrupts: sudden but temporary interrupts can also cause segmentation if the algorithm of adaptive curve segmentation in [19] is used naively.

Figure 6: Adaptive curve segmentation by [19]

e1

e2

b2 b3

e 6

e7

b1 (a) Step 1

b1

b4 (c) Step 3

e3

(b) Step 2

Furthermore, the curve segmentation algorithm in [19] has a greedy nature, which may cause over-segmentation of a given CUTS-curve. This is illustrated in Figure 7. In this example, segments e2 and e3 are placed into two different subtrees by the curve segmentation algorithm (due to the greedy nature of the first split). However, slopes of these two segments are similar; thus from a topic development perspective they should belong to the same topic segment.

Therefore, curve segments obtained through an applica- tion of curve segmentation algorithms are not suitable to be used directly as topic segments, as this may reduce the overall precision. Therefore, to identify actual (potentially more complex) topic segments, we need to combine appro- priate curve segments into larger topic segments, based on available contextual information.

4.2.2 Curve Segments to Base Topic Segments Let us denote a 4-tuple gi = (ki, σi, (xstart, ystart)i, (xend, yend)i) to represent each line segment in S:

• ki is the slope of the corresponding line segment; this describes the divergence speed of the topics in the seg- ment;

• σi is the average of distances from original points in this segment to the line approximating these points. This parameter measures the concentration of the en- tries around the dominant development pattern1; in other words, a large σi means that the curve is jagged (or saw-tooth shaped); i.e., there is a diverse set of topics being covered. For example, in Figure 9, the segment e1 and e2 are more concentrated than e3.

• the pairs, (xstart, ystart)i and (xend, yend)i, denote the end points of a segment.

A base topic segment is composed of one or more consecutive curve segments, representing one topic or reflecting changes of topics. In particular, given two consecutive curve seg- ments, gi and gi+1 in S, these segments can be combined into a single base topic segment if the development of two curve segments is relatively homogeneous in terms of their topic evolution speeds and concentrations:

(|ki −ki+1| < λdrifting) ∧ (|σi −σi+1| < (σi + σi+1)/2) . (1)

Here λdrifting is a parameter which determines the algo- rithms sensitivity to differences in topic evolution speeds;

1We use this average-based measure, rather than the maximum-deviation based significance value returned by the curve segmentation algorithm to identify the concentration of topics.

{e1}

b1

{e3} {e2}

b3 b2

e5

e5

-

b4 -

{e7}

b2 b3

b2 b3

e 6

{e4}

{e5} {e6}

e 4

e 4

e 8

-

b1

b1

e 9

b4 (d) Step 4

{e8} {e9}

(e) Resulting tree

b

d2

a

d1

θ θ

c

t

Figure 8: Angles between segments can not reflect the amount of drift correctly: b and c have the same difference of angles from a, but not same amount of drift.

Curve Segm ent:e1 Curve Segm ent:e2 Curve Segm ent:e3

Figure 9: Combining curve segments: e1 and e2 can be combined because their slope (k) and concentra- tion (σ) parameters are both relatively similar; how- ever, although e2 and e3 have similar slopes, they can not be combined because of their very different concentrations

its value is computed as a percentage of the overall change in the data. As shown in Figure 8, angles between segments can not correctly capture the degrees of topic changes. Thus, λdrifting is described in terms of the difference of slopes of the curves as opposed to simple difference between their an- gles. When combining curve segments, we also require the difference of σs to be small. This process is illustrated in Figure 9.

After two curve segments are combined, the k and σ of the new segment are recalculated. In particular, the slope is recomputed based on the end-points of the combined base topic segments. The new σ value is the average of distances from the points in both segments to the new line connecting end-points of the combined base topic segments.

Given a sequence S = {gi}M

i=1 of curve segments, we visit the pairs of segments in the chronological order of the under- lying entries (i.e., in the increasing order of i) and combine the similar segments as described above. This gives us a new, reduced, sequence S′ = {g′

i}M′

i=1 of base topic segments, where a segment g′

i corresponds to one or more segments in S. The base topic segments, B = {bh}M′

h=1 are then the elements of the reduced segment set; i.e., B = S′.

e4

e4

s1

e3 s1

e1

e3

e1

e2

e2

(a) interrupted pattern

(b) not an interrupted pat- tern

Figure 10: Deciding interrupted patterns: the change of slopes between e1, e4 and s1 needs to be small for identification of an interrupted pattern

4.2.3 Annotating Base Topic Segments with Patterns of Topic Development Once the base topic segments, B, are identified, they need to be annotated with the topic development patterns: dom- inated, drifting, or interrupted. Foremost, a base topic seg- ment, bh = (kh, σh, (xstart, ystart)h, (xend, yend)h), is

• dominated, if |ki| < λdrifting, or

• drifting, if |ki| ≥λdrifting

where λdrifting is used to identify significant speeds of topic changes. However, this is not enough. As we mentioned earlier, when there are long-running dominant topics, which are interrupted with a short running topic, we need to differ- entiate these from simple topic drifts. Given two base topic segments, bh and bh+1, they can be combined into an

• interrupted segment if

(|kh| ≥λdrifting) ∧ (|kh+1| ≥λdrifting) ∧ (kh × kh+1 < 0) ∧ k′

(2)

+

k′

< λdrifting

h−1 −˜kh

h+2 −˜kh

where k′

h−1 and k′

h+2 are the slopes of base topic seg- ments just before bh and after bh+1 respectively, and

˜kh = |(ystart)h −(yend)h+1|

In other words, an interrupted pattern is composed of two (or more) consecutive drifting base topic segments which have slopes with opposite directions and which interrupt a dominated or drifting pattern. Based on the Equation 2, the context provided by the segments before and after the wedge shaped formation will decide whether a combination should happen. Examples are shown in Figure 10.

When an interrupted pattern is identified, the slope (k) and the concentration (σ) of the new base topic segment are recalculated. In order to keep the interrupted feature, we use the maximum of σi and σi+1 as the σ for the new segment. Thus, interrupted pattern segments are (properly annotated and) replaced with the dominated or drifting base topic segments respectively for further processing.

Note that identification of an interrupt causes a number of base segments to be combined into a single (interrupted) seg- ment. Therefore, the process of combining segments should be repeated until all segments (over-)split due to interrupts are identified and merged.

4.2.4 Elimination of Topic Oversegmentations The previous steps of CUTS identify and classify topic segments and their development patterns. Note that, after the process ends, it is possible to have a number of con- secutive dominated segments, each with a small drift but with significantly different concentrations, as shown in Fig- ure 9. Since these segments are dominated (i.e., are con- centrated around the same horizontal line), these segments are similar to each other in content; i.e., they have the same topic in focus. On the other hand, the different degrees of concentrations of the individual topic segments highlight that each segment has a different degree of focus around this common topic. We note that, for effective topic-based indexing and visualization, splitting consecutive segments concentrated around the same topic (because their degrees of concentrations around this common topic are different) may be unnecessary. Therefore, to enable proper labeling of a sequence of consecutive segments concentrated around the same common topic, CUTS merges such consecutive dom- inated patterns and places the segment boundaries only at the end-points of the merged segment.

4.2.5 Constructing A Hierarchy of Topic Segments The above steps provide a sequence of segment boundaries and topic development patterns for each segment. However, in reality, these segments form the lowest layer of a hierarchy of segments. To discover the overall hierarchy, we reiterate the above steps with the boundaries that are already dis- covered:

(a) We first combine the entries in each segment into a

single processing unit;

(b) We then apply the topic segmentation and develop-

ment pattern analysis algorithm to the new sequence of units

These steps are repeated (bottom-up) until no new topic segments can be discovered. A hierarchical index or naviga- tion structure can be constructed on the basis of these levels of segments.

EXPERIMENTS In this section, we present experiments we carried out to evaluate the proposed segmentation and topic develop- ment analysis algorithms. The experimental evaluation is composed of two parts. In the first part, we use a blog as data source to verify our approach. In the second part, as a comparison for blog segmentation, a book (with a known ta- ble of contents) is taken as input. These experiments show the characteristic differences between the two text stream classes, blogs and book pages.

5.1 TopicSegmentationandAnnotationofBlogs

Source Data. To evaluate the performance of the proposed approach, we used entries from popular political commen- tary weblog (Talking Point Memo [4]) as the data source. For the experiments presented here, we are using a 40-week sample (from January, 2005 to October, 2005) of entries from this source. For ease of analysis of the results, in this experiment, we unify the set of entries in one week into a single text unit. For the experiments presented here, we do not use any other supporting topic analysis method (such

0.5

0.4

0.3

0.2

Value of Entries

0.1

29 31 34

−0.1

−0.2

−0.3

0 5 10 15 20 25 30 35 40 −0.4

Sequence Number of Entries

Figure 11: Topic segmentation for the blog entries. The numbers in the plot represent topic boundaries; the two circles denote the end-points of an interrup- tion identified by the algorithm

0.35

Value of Similarities of Consecutive Entries

0.3

0.25

0.2

0.15

0 5 10 15 20 25 30 35 40 0.1

Sequence Number of Pairs of Consecutive Entries

Figure 12: Similarities-curve based topic segmenta- tion by [6]. The numbers denote the topic bound- aries identified by that approach

Table 1: Base (lowest level) topic segments for the blog entries taken from [4], from January 02 to Oc- tober 05

Seg#

Weeks

Pattern

Length

Var.(σ)

Slope(K)

. . 3

0.0010

0.0158

dominated

. . 5

0.0347

-0.0380

dominated

. . 7

0.0096

0.0661

drifting

0.0000

-0.0719

drifting

. . 11

0.0022

0.0610

drifting

0.0000

-0.0727

drifting

. . 21

0.0047

0.0148

dominated

0.0000

-0.0797

drifting

0.0000

0.5122

drifting

. . 25

0.0120

-0.0927

drifting

0.0000

0.1626

drifting

. . 28

0.0116

-0.1723

drifting

. . 40

0.2424

0.0028

dom/interrupt.

as LSI) to reduce the noise in the data. In other words, the difference matrix used for analysis is simply the keyword vectors of the weekly collections of blog entries from [4].

Comparison of Segmentation by CUTS versus [6]. When implementing CUTS, we used a MinSpan of 5% of the total number of units (i.e., about 2). Similarly, λdrifting is set to be 5% of the range of difference values in the curve. Table 1 contains the base segments obtained through Sec- tion 4.1. Figure 11 shows the corresponding topic segments obtained by processing these base segments. In this figure, the horizontal axis represents the sequence number of weeks

in a chronological order; the vertical axis represents the MDS assigned values for each week of entries (Section 3). The plot contains both the original curve and the result of topic seg- mentation process: the line segments in the figure are the identified topic segments. The numbers on the curve de- note the topic segment boundaries. According to Figure 11, there are eleven topic boundaries in this sequence of entries: (6, 8, 9, 12, 13, 22, 23, 24, 26, 27, 29).

For comparison purposes, we also use [6] to get topic boundaries for the same data set. The result is shown in Figure 12. The horizontal axis depicts the sequence num- ber of pairs of consecutive weeks; the vertical axis shows the similarity value between consecutive weeks. This approach identifies only three topic boundaries, (14, 22, 31) using the local minima as shown in Figure 12.

Interpretation of the Results. The analysis of results from CUTS (and comparisons with the similarity curve based segmentation approach suggested in [6]) leads to the follow- ing observations supporting the proposed hierarchical topic development pattern identification mechanism:

(a) At the highest level, there is an almost constant-slope

topic drifting of content in the blog entries depicted in Figure 11. Such a pattern is not visible in Figure 12, which de- picts the alternative similarities curve based method which relies on only the similarities between neighbor- ing weeks.

(b) At the lowest level, the proposed segmentation ap-

proach provides 12 segments for the 40-week period; thus the average length of topic segments is about 3-4 weeks. However, there are two long segments (one 9 weeks long and the other 12 weeks long) where the con- tent does not change much. Excluding these, the aver- age segment length is around 2 weeks. In other words, at the lowest level, the proposed approach visualizes the short-term shifts in the content development. [6], on the other hand, provides only four segments for the entire period of 40 weeks.

(c) There are two notable jumps in Figure 11. One is at week 24, and the other is at week 33. After both jumps, after a few weeks, the content development pat- tern reverts back to its normal constant-slope pattern. At the lowest-level (Table 1), the second jump is rec- ognized as an interrupt (between weeks 31 and 34) in a 12-week long segment. Note that such topic devel- opment patterns are not visible with the alternative segmentation technique [6]:

Example 5.1. The analysis of the blog content shows that during the week of the first jump, news of a politi- cian suspected of a corrupt transaction emerges and dominates the discussions for a few weeks. The sec- ond jump is also related to the news of the same po- litical corruption case. Note that, the fact that these two jumps are related can easily be seen by analyzing the curve: the tops of both jumps are more or less at the same level (since MDS places them closer to each other, before the temporal dimension is considered). Such related clusters of jumps can easily be recognized by the proposed approach, by simply analyzing the y- axis of the curve.

0.4

68 75

0.3

0.2

60 64

0.1

Value of Pages

−0.1

−0.2

−0.3

−0.4

0 10 20 30 40 50 60 70 −0.5

Sequence Number of Pages

Figure 13: Topic segmentation results for the input book by CUTS.

0.65

0.6

0.55

Value of Similarity

0.5

0.45

0.4

0.35

0.3

0.25

0 10 20 30 40 50 60 70 0.2

Sequence Number of Pair of Consecutive Pages

Figure 14: Similarities-curve based topic segmenta- tion [6]

5.2 Topic Segmentation and Annotation of the Edited Material

Source Data. In order to (a) observe the differences be- tween segmenting dynamically (and freely) growing weblog entries and edited material (such as books) and (b) re- validate the performance of the proposed segmentation algo- rithm against a material which already has a table of content (i.e., ground truth), we used a book [7] as the data source for segmentation and analysis.

In the experiments, we selected a number of sections as input (from page 31 to page 100) and treat each page as a separate entry. Moreover, we omitted the non-text ma- terial, such as figures, tables, etc. Naturally, since our aim is to measure the performance of segmentation and analysis mechanisms when there are no available table of contents, we ignored the tell-tale signs of segment boundaries, such as chapter, section, and subsection titles and headings.

Comparison of Segmentation by CUTS versus [6], and Ground Truth. Figure 13 shows the results of the curve segmentation. Once again, the plot contains both the original curve and the result of topic segmentation process: the line segments in the figure are the identified topic seg- ments. Further analysis of the pages (Section 4.2) provides a total of 15 topic segment boundaries in the data: (43, 45, 58, 60, 64, 66, 68, 75, 76, 77, 80, 83, 91, 95, 96).

For comparison, we also segmented the book using the similarity curve based method method presented in [6] (and discussed in Section 1.2). The resulting similarity curve is shown in Figure 14. Using the local minima, this approach provides 6 segment boundaries: (36, 46, 59, 65, 81, 97).

Table 2: Comparison of two approaches, [6] and CUTS, in terms of their edit distance from the ground truth provided by the table of content; we also present the edit distance values for random seg- mentation (RND) to show that edit distance mea- sure correctly reflects quality of segmentation re- sults

Cost per Edit Oper.

Edit Distance

No

Ins

Del

Sub

RND

[6]

CUTS

C1-1-1

C2-2-1

C4-2-1

C5-5-1

Finally, in order to measure the accuracy of the result, we used the table of content of the book as the ground truth, by identifying the lowest-level topic boundaries:

(43, 45, 49, 55, 57, 58, 61, 63, 69, 80, 84, 91, 94, 99).

Evaluation Measure. To quantify the precision of a seg- mentation approach, we computed the edit distance between the strings formed by the topic segment boundaries [23]. The edit operations include insertion of segment boundaries, deletion of boundaries, and substitution of one boundary with the other. Insertion makes up for the absence of bound- aries missed by the segmentation algorithm. Deletion filters out boundaries resulting from over-segmentation. Substitu- tion accounts for misplaced segmentation boundaries. Each operation has a cost; in particular, the cost of substitution measures the cost of the replacement (of one boundary with another) in terms of the page differences between the de- tected and correct boundary. Naturally, a result which has a small edit distance with the actual table of content is more desirable.

The edit distance results are shown in Table 2. For inser- tion or deletion, the value in the table represents the cost per operation. However, for substitution, the value is a mul- tiplicative factor. For example, if we substitute a boundary at page 23 with a boundary at 32, the total substitution cost would be the product of the substitution factor in the table (i.e., 1) and the substitution page difference (i.e.,9). In a sense, the insertion and deletion costs in Table 2 measure the penalties associated with over- and under-segmentation, relative to mis-segmentation of the content by a single page.

Validation of the Evaluation Measure. Table 2 also contains edit distance values for random segmentations (av- eraged over 100 random iterations) to show that edit dis- tance function we use in this paper properly measures the qualities of segmentation results. By comparing the edits distance values under the column RND against the columns titled [6] and CUTS, we can see that the edit distance val- ues for random segmentation results are %100−%300 times higher than the edit distance values for the segmentation results returned by [6] and our technique, CUTS. In other words, higher edit distance values reflect uninformed (more random) segmentations, while lower edit distance values re- flect less-random (more informed) segmentation.

Interpretation of the Results. The analysis of the Fig- ures 13 and 14 and Table 2, provides the following observa- tions, supporting the proposed approach:

(a) At the highest level, Figure 13 shows the content con-

centration and divergences. There are two major topic

concentrations (pages 31-57 and 68-100) , which are connected by an intermediary segment (pages 58-67).

Such topic development patterns are not visible in the similarities curve based approach (Figure 14).

(b) The similarities curve based approach [6] significantly

under-segments the material. When such under- seg- mentations are not penalized (C1-1-1) or lightly pe- nalized (C2-2-1) the two approaches provide compara- ble results (Table 2), though the proposed scheme still performs better.

When on the other hand, the missing segment bound- aries are probably penalized (C-4-2-1 and C-5-5-1), the advantage of the proposed approach relative to alter- natives becomes clear.

Finally, note that, when compared with results of the blog, there are more dominated patterns in the the book. We omit the detailed table of the 15 segments due to space con- straints, but the difference in topic development patterns is visible in Figures 11 and 13. The first has a constantly drift- ing shape (highlighted with the almost constant slope of the curve), but the second one has two more or less flat sections, with a clear jump from one to the other. This difference is due to the edited nature of the content in the book.

CONCLUSIONS With the goal of constructing navigational tools and ap- propriate index structures for blogs, we developed a novel topic segmentation method, CUTS, which enables us to iden- tify the topic development patterns in text streams. CUTS use multi-dimensional scaling to map entries in the blog into a curve which materializes the various patterns of interest. An adaptive, hierarchical curve segmentation technique is used for identifying topic segments and classifying them into different topic development patterns. Thus, unlike exist- ing methods, CUTS has the advantage of not only better precision in segmentation, but also of providing topic de- velopment patterns, useful in annotating and indexing the returned segments. We experimentally showed that CUTS achieves a better performance than recently proposed meth- ods for topic segmentation. As mentioned in Section 2, it’s possible to make topic development analysis when multiple blogs with similar content structure is available. In the fu- ture work, we will explore benefiting from such knowledge.