Matching Patterns

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

By Girish Keshav Palshikar

UPS AND DOWNS

Patterns Reveal Connections Users in diverse domains often describe interesting patterns that they expect to see in the databases collected by their systems over time. They often use high-level domain concepts and various temporal and logical connectives to describe these patterns. Some examples of temporal patterns in end users' language include: Whenever the price of a stock is very high or very low, the stock is trading rather low. Large purchases of a stock within a short time interval lead to a sharp rise in the price. As the market price of a stock increases, so does the volume traded. The selling tendency increases whenever a stock price goes above the previous maximum. A failing bank has a large number of large nonperforming loans that eventually become loan losses. Large increases in total loans within a short time, along with only small changes in provision for loan losses, are followed by a period of high-net loan losses. Whenever the furnace temperature rises rapidly, the yield quality somewhat deteriorates.

A critical analysis and deep understanding of "historical databases" form a backbone of many special business-critical tasks: decision making, surveillance and monitoring, performance evaluation, risk analysis, fraud detection, resource management, diagnosis, planning, and forecasting. Automated business systems collect vast amounts of data over long periods of time in stock markets, banks, sales and finance departments, insurance companies, manufacturing industries, and so forth. The long-term data - perhaps from several years past - typically resides in a data warehouse and short-term data - the current year or immediate project - may be available in online databases.

Making significant business decisions requires extensive knowledge about your business and your collected data, which is often expressed in terms of patterns in the data and its relationship with business phenomena, activities, and decisions. After all, as Hegel said, "Those who do not understand history are condemned to repeat it." To say that detection, measurement, understanding, and effective use of patterns in historical data form a core of business intelligence and knowledge would not be an exaggeration. More fundamentally, the ability to detect, measure, and analyze patterns is a crucial human ability and the basis of perception, understanding, and learning.

For example, a manager may offer incentives such as discounts when stock levels gradually increase while demand rapidly dwindles. Or as another example, a surveillance manager in a stock exchange normally expects the trading in a particular security to be rather low during a period when its price is high, or very low when the price is relatively steady. The manager may be interested in a system to define such a pattern (at this level of abstraction, away from the database details) and that will generate an early warning about the exceptions to this normal trading pattern. Then the manager may use further data analysis to either confirm or eliminate the possibility that the detected exception to the pattern constitutes some suspicious activity.

Users need tools to express and detect patterns in given databases, particularly because the databases are often quite enormous and manual inspections of data are well-nigh impossible. Management information and decision-support systems in such applications often provide a range of services, typically in the form of canned queries, reports, visualizations, and special-purpose computational and analysis facilities (for example, based on time-series) so that the decision makers can make informed and intelligent decisions consistent with past observations.

The often unstated assumption is that these tools will only provide support to the IT experts to detect and understand the hidden patterns. Unfortunately, many of these tools do not really have a clear underlying notion of what patterns are or any special facilities for detecting and measuring them. But the primary responsibility lies with the database users and their skills.

In this article, I explore the notion of a pattern, particularly a temporal pattern, and suggest an approach for matching a known pattern against given databases. This approach derives from the research of my organization, Tata Research Development and Design Centre (TRDDC) and its practical applications. TRDDC is the research and development division of Tata Consultancy Services, a software company in India.

TIME FACTORS

Where Temporal Patterns Are Used Experts in many application domains describe and look for specific patterns in the time-stamped data collected by their systems. Examples of domains that use temporal patterns include: Stock market surveillance: patterns of price-volume variations and buying-selling activities Banking: patterns of loan disbursement or repayment activities Telephone billing: patterns of calls and bill payments Power distribution systems: patterns of power usage Manufacturing: patterns in ordering, production, inventory and delivery data Battlefield surveillance systems: patterns of object movements.

What Is a Pattern?

For the purpose of understanding historical databases, I define a pattern as a significant, high-level structure present in the data. A pattern condenses and summarizes vast amounts of numeric data. Detecting a pattern (and measuring its attributes) in a given source is a significant observation. You see where, when, and how strongly it occurred, variations from a standard reference pattern, repetitions, other measurements, and so forth. Clearly, a pattern is a valuable piece of knowledge. Describing and recognizing such patterns contributes to knowledge building and knowledge reuse within an intelligent enterprise.

If a pattern consists of nothing but a group of records, then queries and reports should be able to find it. If a pattern is a group of data values - for example, most guests who stay for more than three nights are men, corporate executives, and use air travel - then clustering algorithms are generally well equipped to detect them. Data mining algorithms often detect such associations of data values as well.

But what about patterns that are temporal in nature, like shapes in electrocardiogram (ECG) signals? Also, most experienced businesspeople know that leopards don't change their spots. That is, the experts often have a repository of well-understood patterns that they wish to compare with the current data. So how does one detect a pattern, which is known a priori and not an unknown pattern? What my company's researchers are saying is that often you may need to match a known pattern against given data, rather than automatically detect an unknown pattern.

For example, finance managers often describe the health of a company in approximate symbolic patterns. In the context of accounts receivables (AR), they may say "collection is high," "collection is slow," "collection is not improving," or various combinations like "collections are high, not slow, and improving." The last one indicates a healthy status, which may be described in more detail as, "The AR turnover is increasing and the days' sales outstanding (DSO) is well above the given norm and the average collection period (ACP) remains much higher than the credit terms." Here, AR turnover, DSO, and ACP are domain concepts; their values vary over time and can be computed from sales and AR databases. The pattern is clearly composed from smaller subpatterns.

As another example, you may look for periods in which "collections are high and slowing down." In the domain of manufacturing systems, experts often know the possible faults that can occur in the system, and they usually characterize these faults by means of inexact symbolic descriptions: If the temperature steadily increases and no sustained pressure builds up, then the out valve may be leaking. Finally, we at TRDDC ask a more general question: "Is there a way to characterize the patterns more logically to resemble their users' verbal informal description?"

Characteristics of Temporal Patterns

What then are the characteristics of temporal patterns? First and foremost, managers and other decision makers often describe a pattern in terms that are qualitative (nonnumeric or symbolic) in nature. (See the sidebar "Ups and Downs" for specific examples.) A temporal pattern is qualitative in that it typically does not specify actual numeric values, time instants, and intervals but deals with temporal relationships between events. (See the sidebar "Time Factors," page 50.) Symbolic descriptors like high, low, close, rapidly, and so on replace numeric values.

A pattern description deals with domain-specific concepts, rather than database columns. A decision maker's descriptions of temporal patterns are conceptually at a very high level of abstraction, removed from table structure, field types, keys, and so on.

Users often use inexact, approximate and probabilistic, or fuzzy terms in describing temporal patterns. A pattern is approximate in the sense that its instances may occur several times in a given source and they are usually similar but not identical. If you look at it another way, a pattern is not black and white; it is present in a graded way (described, for example, as a fuzzy degree of truth by a number between 0 and 100) rather than in a binary Boolean (true or false) fashion.

Interestingly, a pattern description is composed using smaller, more primitive patterns; typically, the composition operators are logical (AND, OR, NOT, IF-THEN) and temporal (BEFORE, UNTIL, SINCE, AFTER, WHENEVER, DURING, and so on). Such techniques let the experts focus on and reuse subpatterns, describe interrelationships between patterns, isolate variations among patterns, and so forth. An example of relations between instances of patterns is "Pattern A is strongly present within the period when patterns B or C are low." These temporal connectives let you express many more such relationships between patterns.

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.

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.