# Presentation: 480228

## 
Bolin Ding and Jiawei Han
bding3@uiuc.edu and hanj@cs.uiuc.edu 
Event Cube Research Group, UIUC

- Bolin Ding and Jiawei Han
- _[bding3@uiuc.edu](mailto:bding3@uiuc.edu)_ and _[hanj@cs.uiuc.edu](mailto:hanj@cs.uiuc.edu)_
- Event Cube Research Group, UIUC

## ASRS Database

- After each commercial flight
- Anomaly: some of the 62 anomalies observed
- Narrative: a report is written to describe the observed anomalies (and related activities)

| ACN | Date | ... ... | Event - Anomaly | Report - Narrative |
| --- | --- | --- | --- | --- |
| 101063 | 1989/01 | ... ... | aircraft equipment problem | TKOF LAX LNDG GEAR WOULD NOT RETRACT, GEAR HANDLE WOULD NOT GO PAST MID POS ... |
| 101066 | 1989/01 | ... ... | other  anomaly | PVT PLT FLT TEST IN WHICH I WAS ACTING AS EXAMINER. FIRST TKOF WAS A PLANNED AND ... |
| 101151 | 1989/01 | ... ... | spatial deviation | CLRED FOR ILS APCH, GIVEN A HDG TO INTERCEPT ILS 23L AT RDU. NAVAID WAS IDENTED (ILS ... |
| ... ... | ... ... | ... ... | ... ... | ... ... |

## The Problem 

- Challenges
- A large number of narratives
- Human-written narratives are unstructured
- Our proposal
- Step 1: Finding frequent sequence patterns – finished and presented in this poster
- Step 2: Experts analyzing these patterns
- Step 3: Using these patterns as features (selecting discriminative ones) – ongoing work
- Step 4: Clustering / Classification using features

- What’s the reasons for the observed anomaly?
- What’s the common reasons for different anomalies?
- Is there any anomaly missed?

- Narratives to describe the anomaly

- Anomaly:
- aircraft equipment problem

## Sequences and Patterns

- A Sequence S:
- An ordered list of words
- An ASRS report’s narrative
- Database DB = {S1, S2, ..., Sn}:
- A set of sequences
- A set of narratives
- Gapped Subsequence (or simply “subsequence”)
- Subsequence with gaps
- Pattern (Repetitive Gapped Subsequence) P:
- A sequence of words, repeating as subsequences (called instances) in one or multiple sequences of database DB
- Support of a pattern sup(P):
- How many instances a pattern has
- How frequently a pattern repeats in database DB
- Frequent Patterns: Patterns with high supports (≥ min_sup) in DB

- LAX LNDG GEAR WOULD NOT RETRACT, GEAR HANDLE WOULD NOT GO PAST MID POS AND GEAR DID NOT RETRACT...

- Pattern: GEAR NOT RETRACT

## Repetitive Subsequences

- Differences from Sequential Pattern [AgrawalS95]
- Counting the instances within a sequence
- Important word sequences may appear frequently even within one narrative
- Counting non-overlapping instances
- Instances in different sequences
- Instances in the same sequence, but do not overlaps
- Avoid over-estimating the frequency: in A A A A B B B B C C C C,
- 	43 occurrences of A B C, and 4 non-overlapping ones
- Definition of support sup(P)
- Deferent ways to embed instances
- Maximum number of instances satisfying 1 and 2

## Repetitive Subsequences

- Mining Closed Patterns
- P is a closed pattern iff there is no super-pattern P’ s.t. sup(P) = sup(P’)
- No information loss
- Easier to be browsed or applied in other algorithms (like clustering and classification)
- Mining patterns with Gap Constraint
- The gap between two words in the instance of a pattern ≤ max_gap
- To make the instances meaningful

## Elements in Solution

- Computing the support of a pattern
- Maximize the number of non-overlapping instances
- Polynomial-time solvable: pick the leftmost instance one by one
- Depth-first pattern growth for mining all frequent patterns
- Restrict gap ≤ max_gap
- Apriori property
- Pruning strategy for mining closed patterns

## Experimental Study

- Advantages of mining closed patterns
- 5k sequences, average length 20, 10k distinct words

- Shorter mining time

- Less frequent patterns

## Experimental Study

- A preliminary study on the mined patterns (statistics)
- Pre-processing: stemming, remove stop words
- Post-processing
- Select patterns with length ≥ 2
- Select patterns with 50% distinct words
- Parameter: min_sup = 10, max_gap = 5
- Anomaly1 = aircraft equipment problem : critical
- 273 reports  -> 415 patterns
- Anomaly2 = inflight encounter : weather
- 266 reports -> 285 patterns
- Anomaly3 = conflict : nmac
- 469 reports -> 1393 patterns

## Experimental Study

- A preliminary study on the mined patterns (some discriminative patterns)

| Pattern | Support |  |  |
| --- | --- | --- | --- |
|  | Anomaly1 | Anomaly2 | Anomaly3  |
| LNDG UNEVENTFUL | 11 | 0 | 0 |
| LANDED WITHOUT INCIDENT | 12 | 0 | 0 |
| SHUT DOWN ENG | 12 | 0 | 0 |
| VISIBILITY FOG | 0 | 13 | 0 |
| CEILING VISIBILITY | 0 | 15 | 0 |
| DOWNWIND RWY | 0 | 0 | 12 |
| SAW OTHER ACFT | 0 | 0 | 10 |
| CLRED FOR RWY | 0 | 0 | 44 |
| TOOK EVASIVE ACTION | 0 | 0 | 44 |
| SUPPLEMENTAL FROM | 17 | 10 | 31 |
| CALLBACK WITH REVEALED FOLLOWING | 37 | 13 | 24 |
| CALLBACK WITH REVEALED FOLLOWING HAT | 13 | 0 | 0 |

## Experimental Study

- A preliminary study on the mined patterns (some examples)

## Conclusion

- Modeling narratives as sequences of words
- Mining (closed) frequent gapped subsequences
- Used to explain the reasons of certain anomalies
- Used as features for clustering / classification
- A generic approach
- Can be also applied in other kinds of “sequences”, like cockpit switch sequences