We investigate if the mapping between text and time series data is feasible such that relevant data mining problems in text can find their counterparts in time series (and vice versa). As a preliminary work, we present the T3 (T ext T o T ime series) framework that utilizes different combinations of granularity (e.g., character or word level) and n-grams (e.g., unigram or bigram). To assign appropriate numeric values to each character, T3 adopts different space-filling curves (e.g., linear, Hilbert, Z orders) based on the keyboard layout. When we applied T3 approach to the “record linkage” problem, despite the lossy transformation, T3 achieved comparable accuracy with considerable speed-up.
Despite significant advancement in each area, data mining research in textual data (e.g., web pages of search engines, citations of digital libraries, relationship data in social networks) and time series data (e.g., network traffic observations, daily fluctuations of stock prices) have not been developed in a close synchronization. New techniques developed in one area do not easily get carried over to the other area. This is partly due to the fact that although both deal with many similar problems such as defining appropriate distance functions or finding interesting patterns, their subject domains are different – i.e., alphabetical strings vs. numerical signals. Therefore, toward this lack of connection between the emerging time series and the traditional text mining approaches, in this paper, we investigate if there exists feasible transformation between two data types such that relevant data mining problems in one data type can find their counterparts in the other type. We are interested in whether and to what extent the performance of mining solutions developed in one domain can be improved over the solutions in the other domain.
Toward this objective, as a preliminary work, we present the T3 (T ext T o T ime series) framework to map text data to time series data. During the transformation of the entire text corpus, T3 utilizes different combinations of granularity (i.e., character level or word level) to extract text units from strings. Furthermore, T3 utilizes n-grams (i.e., unigram, bigram or trigram) to form subsequences of text units. In order to assign appropriate numeric values to each character, T3 adopts different space-filling curves (i.e., linear, Hilbert, Z orders) based on the keyboard layout. In addition, to associate real values to each token, T3 uses the tf-idf weight of the traditional weighting scheme from information ? Partially supported by IBM and Microsoft gifts. retrieval and text mining. We apply the T3 framework to the Record Linkage problem, one of the traditional data mining problems, to determine whether or not two entities represented as relational records are approximately the same. Through extensive experiments using both real and synthetic data sets, the efficacy of our proposed schemes is experimentally validated. To the best of our knowledge, this is one of the first attempts to solve a text mining problem in time series domain. Our experiments reveal that T3 shows comparable accuracy (despite the lossy transformation in T3) when compared to a popular distance measure (e.g., Levenshtein distance) in text domain. However, T3 also achieves much improved speed-up thanks to the numerical data of time series domain. 2
Time series data mining has received tremendous attention in the data mining
community during the last decade. Many time series representation methods such
as Discrete Fourier Transformation (DFT) [
On the other hand, the
gene8kr]n,aolmwliennrkgaaesg-perupercrgooerbdl[e1m0li]n,hkcaaistgaebtei[oe2nn, eKKDt-Nocmc…NeCalnusstering dRaSteatrcbionargsde 132R...eRRRseeeecccaooorrrrcdddhICCPnlldruaoessbxtseliienfrimigcnagstion Text
matching [
The T3 Framework The basic idea of T3 is illustrated in Figure 1. Instead of solving data mining problems on string/text data, we first scan the string database using the proposed transformation schemes in T3. After the string database is mapped to a new time series database, we then employ dimension reduction and symbolization techniques directly on the real values of time series. In general, T3 serves as a convenient bridge to connect two subject domains: numerical signals and alphabetical strings. Therefore, our approach can be considered as a novel complement to existing text mining algorithms which were solely built for generic use based on string manipulation. We illustrate our idea using a simple example in Figure 2. The first two records are referring to the same person and the third record belongs to a different person. We can easily see that the time series of the first two records preserve similar shapes in real-value domain (with some shifting) while the time series of the third record has a rather different shape. Given any sequence s from a database of textual sequences D, T3 utilizes different combinations of granularity, n-grams and score assignments to convert strings to time series as follows.
Granularity. Each record or document in text domain can be viewed as a sequence of characters or word tokens. To transform text data into time series, T3 can use different units of text data: (1) character level : An alphabet letter is regarded as a single text unit. In the transformation, ignoring upper/lower cases, we consider 64 (= 26 + 10 + 28) cases – i.e., 26 cases for 26 English alphabets, 10 cases for 10 numbers (e.g., 0 to 9), and 28 cases for all special characters such as @, #, $. We do distinguish among special characters since some of special characters in record strings appear in our data sets; and (2) word level : At this granularity, an English word (also called “token”) is regarded as a single text unit and T3 simply extracts each token from sequences and then assign appropriate values to each token based on the weighting scheme.
N-grams. In statistical natural language processing, an n-gram is a
subsequence of n consecutive items from a given sequence. These items could be
symbols, letters, or words according to the application. As mentioned above, in
our T3 framework, we treat either a character or a token as the single unit of
sequences. Therefore, an n-gram in T3 is a sub-sequence of n consecutive
“characters” at character level and a sub-sequence of n consecutive “tokens” at word
level. In particular, T3 adopts three sizes of n-grams – unigram, bigram and
trigram. Table 1 shows an example of how to transform the record “time series
data mining” based on different combinations of granularity level and n-grams.
Score Assignment. At this stage,
T3 assigns appropriate numeric val- Record #1: Steve Allen 15201-B Burbank Bl. Van Nuys CA
ues in order to actually convert strings Record #2: Allen, S., 15201 Burbank Blvd Van Nuys California
to time series. Based on different lev- Record #3: Woody Allen 930 5th Ave. New York NY
els of granularity, T3 adopts different (a) Original string records
swceoirgehstitnogssucbhseemquesenicnesorodfertetxot ausnsiitgsn. 00..86 Record #1
At character level, first, T3 uses the 0.4
QWERTY keyboard layout to allo- 0.020 5 10 15 20Record #225 30 35 40 45
cate each text unit (i.e., alphabets, 0.8
numbers or special alphabets) into equal- 00..46
length or varying-length bins within 0.2
the range of [
At word level, second, T3 uses the tf-idf (term frequency-inverse document frequency) weight of the traditional IR weighting scheme. The tf-idf weight is a statistical measure to estimate how important a token in a string record is within a record database such that it increases proportionally to the number of times that the token occurs in the string but is offset by its frequency in the database. Each token of a record string is assigned an importance weight using the tf-idf weight such that the whole string can be converted into a time series. Discussion. Note that the Coding Transformation three dimensions of approaches char + unigram {t,i,m,e,s,e,r,i,e,s,d,a,t,a,m,i,n,i,n,g} (i.e., granularity, n-gram, and char + bigram {ti,im,me,es,se,er,ri,ie,es, score assignment) in T3 are sd,da,at,ta,am,mi,in,ni,in,ng} not exhaustive at all. One can char + trigram {tim,ime,mes,ese,ser,eri,rie,ies,esd,sda, easily devise more sophisticated word + unigram da{t,taimtae,t,asmer,iaems,i,dmatina,,inmi,inniinn,gin}g} transformation schemes from word + bigram {time series, series data, data mining} text strings to numeric time word + trigram {time series data, series data mining} series. For instance, as to the score assignment dimension, Table 1. Examples of T3 transformation. in addition to the keyboard layout based assignment for the character level or weighting based assignment for the word level, one may use Linguistic characteristic (e.g., while a character-level bigram “on” occurs frequently, another bigram “xz” rarely occurs in English) to assign different assignment scores. Similarly, domain-specific characteristics of text data can be adopted. For instance, instead of character-level or word-level, one may use phrase-level or paragraphlevel summary as the basic text unit when dealing with documents. Since the immediate goal of this paper is first to evaluate the validity of T3 framework to show that “there exist some reasonable information-lossy conversion schemes from text domain to time series domain so that text-based data mining problems can be solved in time series domain”, we rather leave the development of more sophisticated conversion schemes in T3 framework to the future work. 4
In order to validate our proposed T3 framework, we use the record linkage problem. In a nutshell, once we transform all textual records into time series data using T3 framework, for a given query time series q, we attempt to retrieve q’s true duplicate time series. Then, we compare the performance of T3 with that of a traditional record linkage solution that uses the text string as input. If the performance of T3 in solving the record linkage problem in time series domain is comparable to that of a traditional record linkage solution, then it shows the validity of our proposed T3 framework. Since the transformation schemes in T3 “lose” some information of original text string (i.e., lossy conversion), we expect the accuracy of T3 framework to drop slightly, compared to the accuracy of a traditional record linkage solution. However, what we are more interested in these experimentations is the comparison among different schemes in T3 framework and any possible benefits of those schemes.
Set-Up. Table 2 shows the summary of data sets that we used in our experiments. The first five data sets map, bird, business, census, and university are real data sets1 which contain real string data and real errors. The data
Name map bird business census university
cora restaurant celebrity dblp dbgen
Data Error real real real real real real real real real real real real real real real real real synthetic synthetic synthetic
Domain # of records Max # of duplicates # of queries # of targets map name 337 2 19 19 bird name 982 2 67 67 business name 2,139 2 279 279 census info. 841 2 326 326 university name 116 16 15 15
citation 1,326 5 98 194 restaurant info. 864 2 111 111 celebrity address 2615 2 276 276
citation 5359 5 1,369 3,991 mailing list 9,947 19 960 8,987
Table 2. Summary of data sets.
Name bird business restaurant celebrity dblp dbgen
Sample Data “Gavia stellata Red-throated Loon”
“3Com Corporation” “cassells 3266 w sixth st la 213 480 8668 hamburgers” “ANDRE AGASSI 8921 ANDRE DR. LAS VEGAS NV 89113” “Bell Data Modelling of Scientific Simulation Proams SIGMOD Conference 1982” “Colbri P Beer 478 Naftel St 6j2 Rio Blanco PR 00744”
Table 3. Examples of some data sets.
sets cora, restaurant2, and celebrity3 are also real data sets containing real
string data and real errors. We pre-processed each data set to delete some of
the duplicates which were incorrectly labeled. The citation data set dblp was
generated using real citation records from similar venues of DBLP. We randomly
selected ten venues from similar research domains such as SIGMOD, PODS, and
EDBT, and again randomly selected citations published in those venues. Then,
we generated duplicates by injecting typographical errors. Using the data
generation tool, DBGen [
As for distance measures, we use the Levenshtein Distance (LD) in text
domain and Euclidean Distance (ED) and Dynamic Time Warping (DTW) in
time series domain. All measures are known to work well for order-conscious
text or time series data [
3 Provided by Ned Porter at US Census Bureau. precision= |S∩T | and recall= |S∩T | . We will use the precision-recall (PR) graph |S| |T | to present the accuracy.
Comparison of Transformation Schemes in T3. We first compare the performance of different combinations of granularity, n-grams and score assignment in T3. In this comparison, we choose one distance function (i.e, either ED or DTW) and then perform tests of all major coding schemes using the same distance measure. Figures 3(a) and (b) present the precision of the record linkage task using ED and DTW, respectively. Among data sets, the results of tests on celebrity, restaurant, and cora are presented. In Figure 3(a) with ED, note that both Hilbert and Z order based schemes outperform the others with respect to the precision. This is reasonable because both Hilbert and Z order have a good locality-preserving behavior such that alphabets in the neighborhood in the keyboard have the similar real values during the score assignment. Therefore, this can reduce a number of false positives in cases when true duplicates have some dissimilar characters caused by typos or data entry errors. Between these two orders, Hilbert order performs slightly better than Z order scheme, but not significantly. Figure 3(b) shows the similar results when DTW is adopted as the distance function in the experiment.
Another interesting finding is that the word-level transformation schemes using tf-idf weighting as scores do not show a significantly better precision, although they can find true duplicates faster because of the shorter time series generated. The reason is that using the word-level schemes based on tf-idf weights, the resulting time series is entirely determined by the tf-idf weight of each token. To some extent, we lose the lexical information of tokens. For instance, there might exist a situation where two tokens are completely different but happen to carry equal or similar tf-idf weights. This can affect the shapes of time series and hence generate false positives.
Also note that from Figures 3(a) and (b), we do not see much difference between unigram and bigram schemes (trigram schemes have similar patterns and not shown for limited space). This is partially because our record linkage solutions are obtained in real-value domain after record stings are converted to time series, and higher-gram techniques may not be as effective as in the case of string manipulation in text domain. Overall, the transformation scheme based on the combination of character-level granularity, unigram and Hilbert order appears to be the best scheme. Therefore, we adopt this scheme (denoted as char-uni-hilbert) in the following experiments.
Comparison of Distance Functions with Baseline. Next, we compare the performance of different distance functions in our proposed T3 framework. In this comparison, we fix the transformation scheme to char-uni-hilbert and then compare among ED and DTW (in time series domain), and LD (in text domain) as the baseline. Figures 3(c) and (d) show the precision and running time of three distance measures in the context of record linkage problem. The results of tests on map, bird, business, restaurant and celebrity are presented. In these data sets, each query string has exactly one duplicate. Therefore record linkage on these data sets is straightforward and aims to find the other duplicate for each of the query records.
In Figure 3(c), note that LD consistently produces better precision than ED and DTW, except map data set. This is as expected because LD directly operates on the original record strings in text domain without the loss of any information. What we are more interested is: as a complementary approach for solving the record linkage problem in time series domain, how good is the performance of T3 techniques compared to the baseline? Figure 3(c) shows that T3 with ED and DTW can yield comparable precision on four data sets (and better precision on one data set). Since the various transformation schemes in T3 tend to lose some information from original text strings during the conversion, we expect to lose some degree of accuracy in T3, when compared to LD. Therefore, although there appears to be degraded accuracy in T3, since it is comparable to the baseline without using T3, we believe that the result is still promising. Also note that the overall precision of either our proposed schemes or the baseline is around 0.6 across all the data sets in Figure 3(c). This is due to the characteristics of our data sets. As shown in Table 3, our data sets are real data sets which contain a lot of mis-spelling errors and mis-alignments. Therefore, we expect low degree of accuracy of matching similar records. More research is needed so that one can transform text to time series while maintaining or improving the accuracy. Another interesting finding is that DTW mostly performs better than ED (i.e., in map, restaurant, and celebrity data sets) and the difference increases as
Recal (a) cora 0.4
Recal
(b) dblp
0
0.2
0.4
0.6
0.8
1
0
the size of data sets and lengths of record strings increase. This is reasonable
as DTW is usually regarded as a much more robust distance measure for time
series [
The precision-recall (PR) graphs in Figure 4 are generated with both precision and recall of the ED, DTW and LD methods by increasing k, which is the number of answers returned by an algorithm to solve the record linkage task. The value of k changes from 1 to 30. At each point, corresponding precision and recall values are measured and plotted. The PR graphs of three large data sets, cora, dblp and dbgen, are presented. As we can see from Figure 4, DTW and the baseline LD outperform ED by a large margin. Furthermore, DTW produces PR curves that are comparable to the baseline. This is consistent with what we found in Figure 3(c). In addition, note that both LD and DTW run much faster than LD (in Figure 5), again consistent with Figure 3(d). 14 12 10 ()s 8 e iTm6 4 2 0 500 1000 2000 3000 4000 5000 10k 20k 50k 100k
1000 2000 4000 6000 8000 10k 20k 50k 100k (a) Scalability on dblp (b) Scalability on dbgen With these data sets and the fixed transformation scheme of char-uni-hilbert, we measure the running time as the data size increases.
Figure 5 shows the results. In general, Figures 5(a) and (b) show similar patterns. As the size of data sets increases, the running time per query increases linearly for both ED and DTW. However, the running time for LD increases more rapidly compared to that of our approaches. This indicates that our record linkage solution is more scalable to handle a large amount of data. Furthermore, ED consistently outperforms DTW in terms of speed. This is as expected because DTW involves a procedure of dynamic programming in calculating the distance, which decreases the overall speed as the size of data increases. But as we mentioned earlier, DTW method has better precision in terms of accuracy of record linkage. 5
In this paper, we present our preliminary design of the T3 framework to transform text to time series data. We propose two variations of granularity, three variations of n-grams, and four variations of score assignments based on spacefilling curve techniques for characters or tf-idf weighting technique for tokens. We adopt two similarity measures, Euclidean Distance (ED) and Dynamic Time Warping (DTW), to calculate the distance between two time series and show the efficacy of our proposed schemes using both real and synthetic data sets.
In terms of record linkage, our schemes in the T3 framework show promising results with good combination of speed and accuracy, compared to conventional string matching methods such as Levenshtein Distance (LD). In particular, Hilbert space-filling technique at character-level granularity is the best variation of transformation schemes while DTW is a better distance measure regarding precision and ED outperforms regarding running time. With respect to accuracy and speed, the experimental results confirm that our T3 framework can generate precision-recall curves comparable to the baseline LD. We believe our approach can shed new insights in both areas of text mining and time series mining.
Many future research directions are ahead. First, we plan to extend T3 framework to other text mining areas such as document clustering and classification. The sizes and dimensions of the data increase dramatically when documents are considered. Second, more sophisticated transformation schemes and advanced similarity functions need to be devised to provide comparable accuracy using time series data to their counterpart using text data.
The implementations and test data sets used in this paper are publicly available at: http://pike.psu.edu/download/amw09/