--- title: "Categorical data; sequential, sub-graph patterns" subject: "Data Mining" chapter: 4 key: "semester_7/data_mining:categorical-sequential-subgraph-patterns" source: https://www.bctengineer.com/q/semester_7/data_mining/categorical-sequential-subgraph-patterns site: BCT Engineering --- # Categorical data; sequential, sub-graph patterns Data Mining · Chapter 4: Association Analysis - Asked in: year not given - Video: [#16 Sequential Pattern Mining ( SPM ) |DM|](https://www.youtube.com/watch?v=vWuVbQ_NKcY) — Trouble- Free - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/data_mining/categorical-sequential-subgraph-patterns - Whole chapter: https://www.bctengineer.com/md/semester_7/data_mining/chapter-4 ## Question Describe the issues related to categorical data. Explain Sequential, Sub-graph and infrequent patterns. ## Short answer Categorical data issues: binarisation creates many items, low-frequency values cause sparsity, and same-attribute items cannot co-occur. Sequential patterns are ordered subsequences with min_sup. Sub-graph patterns are frequent subgraphs in graph data. Infrequent patterns include negative and negatively correlated patterns, important for rare events. ## Answer #### Issues related to categorical (non-binary) data Association analysis was designed for asymmetric binary items. Categorical and continuous attributes, such as {Gender = Male, Education = Graduate, State = Bagmati}, must first be converted: - **Binarisation**: each (attribute, value) pair becomes an item; continuous attributes are discretised. - **Issues**: (1) too many items from attributes with many values; (2) attribute values with low frequency make rules infrequent, and skewed values (e.g. 95% "No") produce spurious patterns; (3) redundant rules because of concept hierarchies and relations between attributes; (4) loss of information in discretisation; (5) items from the same attribute must not appear together in one rule. - **Solutions**: group rare values into "Other", use concept hierarchies (multilevel association), and use a lower support for rarer items. #### Sequential patterns A **sequence** is an ordered list of itemsets (events), e.g. ⟨{Laptop}, {Mouse, Bag}⟩. A **sequential pattern** is a subsequence that appears in at least min_sup data sequences (customers). *Example*: customers who buy a camera later buy a memory card within a month. Support is the fraction of sequences containing the pattern; timing constraints (maxgap, mingap, window) can be added. Algorithms: GSP, SPADE, PrefixSpan. #### Sub-graph patterns Data such as chemical compounds, web links or social networks are graphs. A **frequent sub-graph** is a subgraph that appears in at least min_sup graphs of the data set. Candidate subgraphs are generated by adding a vertex or an edge (Apriori-like FSG, or pattern-growth gSpan), with checks for graph isomorphism. Uses: finding common substructures of molecules, web communities. #### Infrequent patterns An **infrequent pattern** is an itemset whose support is below minsup; most are uninteresting, but some are still important. - **Negative patterns**: itemsets that involve the absence of items (negated items), e.g. {Coffee, ¬Tea}: customers who buy coffee but not tea. - **Negatively correlated patterns**: itemsets whose support is much lower than expected if the items were independent: s(X ∪ Y) < s(X)·s(Y), e.g. coffee and tea are rarely bought together. - Use: finding rare but important events such as fraud, system faults and rare diseases. Mining uses a very low support or methods based on expected support. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is categorical data prepared for association analysis? A. Each (attribute, value) pair becomes a binary item; continuous attributes are discretised B. Values are averaged into a single numeric item C. Only the most frequent value of each attribute is kept D. Attributes are converted to graphs Answer: A. Standard algorithms expect asymmetric binary items. (Key point: Binarisation) 2. What is a sequential pattern? A. An unordered set of frequent items B. A subsequence of ordered itemsets appearing in at least min_sup data sequences C. A subgraph in many graphs D. An itemset with negative correlation Answer: B. Order matters in sequences, e.g. camera then memory card. (Key point: Sequential pattern) 3. A frequent sub-graph is one that... A. has the most vertices B. has no cycles C. appears in at least min_sup graphs of the data set D. appears in every graph Answer: C. Frequency is counted across graphs; isomorphism checks are needed. (Key point: Frequent subgraph) 4. Which describes a negatively correlated infrequent pattern? A. s(X union Y) > s(X)s(Y) B. s(X union Y) = s(X) C. s(X) = s(Y) D. s(X union Y) < s(X)s(Y) Answer: D. Joint support is much lower than expected from individual supports. (Key point: Infrequent pattern) ## Related in Data Mining - [Association mining on varied data types](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Aassoc-categorical-sequential-stream) — Data Mining, chapter 4 - [Sequential covering for rule induction](https://www.bctengineer.com/question.md?key=semester_7%2Fdata_mining%3Asequential-covering) — Data Mining, chapter 3 ## Related in other subjects - [Pycnometer data, water content, γsub](https://www.bctengineer.com/question.md?key=semester_4%2Fsoil_mechanics%3Apycnometer-water-content-submerged) — Soil Mechanics, chapter 2 - [Regulatory issues in wireless communication](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Aregulatory-issues) — Wireless Communication, chapter 1, asked 6× - [Centralized vs distributed; design issues](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Acentralized-vs-distributed) — Distributed System, chapter 1 - [NLP issues with example](https://www.bctengineer.com/question.md?key=semester_6%2Fartificial_intelligence%3Anlp-issues) — Artificial Intelligence, chapter 7