Matching Patterns

Patterns in historical data are the lifeblood of business intelligence and knowledge

By Girish Keshav Palshikar

Continued from Page 2

Describing the Patterns

For most users of temporal data, it would be useful to have assistance from a system that performs inferences and reasoning, and queries, automatically identifies, and states patterns in a qualitative temporal pattern language that is easily understood.

ALWAYS X at ti = (X at ti) AND (X at ti+1) AND ... AND (X at tN) 
EVENTUALLY X at ti = (X at ti) OR (X at ti+1) OR ... OR (X at tN)
X WITHIN n at ti = (X at ti) OR (X at ti+1) OR ... OR (X at ti+n)

But first, how do you formally describe a pattern for comparison with the databases and its detected instances? We decided that the answer was mathematical temporal logic.

If you assume that you have a finite, linear-ordered sequence of not necessarily equally separated time instants TIME = t0, t1, ..., tN, where N+1 is the number of time instants, each ti is a time instant (0 £ i £ N) and ti < tj if i < j, for all 0 £ i, j £ N. The instants could be timestamps, dates, or date-time strings; you can then appropriately define the ordering <,>, = and so on between pairs of instants.

We assume that a declarative fuzzy proposition can define each concept in the user's domain. Each such fuzzy proposition can have a truth-value from the range [0, 1]; thus it need not be fully true or fully false. In general, a fuzzy proposition has a different truth-value over the instants in time. Thus, each fuzzy proposition defines a time-dependent concept in the user's domain. In the AR example mentioned earlier, some fuzzy propositions that you can define are "collection is high," collection is low," "collection is improving," and "collection is slow." The values of these fuzzy propositions vary over time and come from the sales and AR databases.

You can now use the standard logical connectives AND, OR, NOT, IF-THEN and so forth to construct more complex fuzzy formulae from the fuzzy propositions. The truth-value of a complex formula at any instant i is computed from the truth-values of its constituent fuzzy propositions at the instant i. In addition, you can define temporal connectives FORNEXT, ALWAYS, AVG_ALWAYS, AVG_FORNEXT, EVENTUALLY, WITHIN, UNTIL, SINCE, BEFORE, AFTER, and so on. Table 1 shows the informal meaning of these connectives. Note that these temporal connectives are future-oriented; we can analogously define past-oriented connectives.

Here's an example: Let cool, humid, and raining respectively denote the fuzzy propositions that the weather is cool, humid, or raining. Then at a particular instant, truth-values of cool, humid, and raining may be 0.9, 0.4, and 0.1; meaning that the weather is very cold and somewhat humid, with very little rain at that instant. These truth-values may vary over the instants (note that instants are not necessarily adjacent instants, but say daily, hourly, or even weekly readings). You can detect a pattern of how s truth-values such as cool vary over time. However, you can construct more complex and interesting weather patterns using the logical and temporal connectives. Here are some examples of weather patterns described in natural language and also as temporal formulae. I may use special-purpose fuzzy connectives like heavy, fairly, low, high, very, and so on to emphasize the degree of truth.

• It will always eventually rain within five instants if the weather is fairly cool and very humid.

   ALWAYS (IF fairly cool AND very humid 
  THEN (rain WITHIN 5) )

• A heavy rain always reduces to drizzle before stopping.

   ALWAYS (IF heavy rain THEN 
  EVENTUALLY (very low rain BEFORE 
  NOT rain) )

Detecting the Patterns

Given fuzzy truth-values x and y (as real numbers between 0 to 1), the standard method to define the meaning of the fuzzy logical connectives is as follows:

 x AND y = min(x, y), x OR y = max(x, y),
NOT x = 1 - x, IF x THEN y = max(1-x, y).

See the sidebar, "Truth and Time."

In Table 2, the first column shows the time instants and the next three columns show the value of the three fuzzy propositions (cool, humid, and rain) at each instant. You ignore the method used to compute the truth-values for the fuzzy propositions at each instant. For example, you can compute the degree of truth of the fuzzy proposition, cool, from the given temperature (T) using the following formula (when T = 9 degreesC, cool = 1.0, when T = 30 degreesC, cool = 0.0 and when T = 20 degreesC, cool = 0.33):

 cool(T) = 1.0 if T £ 10 degreesC
= 0.0 if T greater than or equal to 25 degreesC
= 1 - [(T - 10)/ 25 - 10)]
if 10 < T < 25

The truth-values of the formulas fairly cool and very humid are shown in the next two columns. The last column shows the truth-value of the formula IF (fairly cool AND very humid) THEN (rain WITHIN 5), denoted by F.

In another example, Figure 1, shows the price and number of shares traded for a specific company (on the y-axis) over time (on the x-axis). A common normal trading pattern, in natural language, is "the volume traded is low when the price is very high or very low," which is represented as the fuzzy temporal formula IF (high_price OR low_price) THEN low_ volume. The fuzzy propositions are appropriately computed from the data about the company's price and volume. Figure 2 depicts the truth-value of this formula (on the y-axis) over time (on the x-axis). Note that the formula shows a very high match (truth-value greater than or equal to 0.8) most of the time, meaning that you can consider the trading in this company over the observation period as normal. You can detect early warnings for any exceptions to the pattern by low truth-values for the pattern over a sustained period of time.

Logical Patterns

In this article, I presented one approach to define the meaning of a pattern and described a fuzzy temporal logic where a formula has a truth-value at each instant in time (computed from the given underlying temporal databases). This logic can describe conceptual, high-level, approximate patterns that characterize time-dependent phenomena in various domains and applications. You can define simple algorithms to extract the time intervals where a given fuzzy temporal formula shows a significant presence. To facilitate the easy expression of more types of expert knowledge, you can add interval-based meta-temporal facilities to describe relationships between various time intervals of interest (DURING, OVERLAP, and so on). Clearly, such pattern detection tools can be useful in a number of different applications such as trading surveillance in the stock market, manufacturing, process control, aerospace (diagnostic fault patterns in telemetry data), banking and finance (operational risk monitoring), insurance, and military defense.

I would like to thank Prof. Mathai Joseph and Dr. Manasse Palshikar for their support.

Rate This Article Rating: 1 (best) 2 3 4 5 (worst) Comments: Optional e-mail address:

Girish Keshav Palshikar (girishp@pune.tcs.co.in) is a scientist at Tata Research Development and Design Centre (TRDDC) in Pune, India. TRDDC is the R&D Division of Tata Consultancy Services, India's largest software company. His areas of work include theory and applications of artificial intelligence.