Taxonomy-driven lumping for sequence mining Export

@article{citeulike:5282786, abstract = {Abstract\ \ Given a taxonomy of events and a dataset of sequences of these events, we study the problem of finding efficient and effective ways to produce a compact representation of the sequences. We model sequences with Markov models whose states correspond to nodes in the provided taxonomy, and each state represents the events in the subtree under the corresponding node. By lumping observed events to states that correspond to internal nodes in the taxonomy, we allow more compact models that are easier to understand and visualize, at the expense of a decrease in the data likelihood. We formally define and characterize our problem, and we propose a scalable search method for finding a good trade-off between two conflicting goals: maximizing the data likelihood, and minimizing the model complexity. We implement these ideas in Taxomo,\ a taxonomy-driven modeler, which we apply in two different domains, query-log mining and mining of moving-object trajectories. The empirical evaluation confirms the feasibility and usefulness of our approach.}, author = {Bonchi, Francesco and Castillo, Carlos and Donato, Debora and Gionis, Aristides}, citeulike-article-id = {5282786}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/s10618-009-0141-6}, citeulike-linkout-1 = {http://www.springerlink.com/content/09512060677r059n}, day = {1}, doi = {10.1007/s10618-009-0141-6}, journal = {Data Mining and Knowledge Discovery}, keywords = {clustering, sequence}, month = {October}, number = {2}, pages = {227--244}, posted-at = {2009-09-07 10:12:57}, priority = {0}, title = {Taxonomy-driven lumping for sequence mining}, url = {http://dx.doi.org/10.1007/s10618-009-0141-6}, volume = {19}, year = {2009} }

TY - JOUR ID - citeulike:5282786 L3 - citeulike-article-id:5282786 N2 - Abstract  Given a taxonomy of events and a dataset of sequences of these events, we study the problem of finding efficient and effective ways to produce a compact representation of the sequences. We model sequences with Markov models whose states correspond to nodes in the provided taxonomy, and each state represents the events in the subtree under the corresponding node. By lumping observed events to states that correspond to internal nodes in the taxonomy, we allow more compact models that are easier to understand and visualize, at the expense of a decrease in the data likelihood. We formally define and characterize our problem, and we propose a scalable search method for finding a good trade-off between two conflicting goals: maximizing the data likelihood, and minimizing the model complexity. We implement these ideas in Taxomo, a taxonomy-driven modeler, which we apply in two different domains, query-log mining and mining of moving-object trajectories. The empirical evaluation confirms the feasibility and usefulness of our approach. IS - 2 JF - Data Mining and Knowledge Discovery EP - 244 TI - Taxonomy-driven lumping for sequence mining VL - 19 SP - 227 KW - clustering KW - sequence AU - Bonchi, Francesco AU - Castillo, Carlos AU - Donato, Debora AU - Gionis, Aristides PY - 2009/10/01/ UR - http://dx.doi.org/10.1007/s10618-009-0141-6 ER -