Packages

  • package root

    High level Smile operators in Scala.

    High level Smile operators in Scala.

    Definition Classes
    root
  • package smile
    Definition Classes
    root
  • package association

    Frequent item set mining and association rule mining.

    Frequent item set mining and association rule mining. Association rule learning is a popular and well researched method for discovering interesting relations between variables in large databases. Let I = {i1, i2,..., in} be a set of n binary attributes called items. Let D = {t1, t2,..., tm} be a set of transactions called the database. Each transaction in D has a unique transaction ID and contains a subset of the items in I. An association rule is defined as an implication of the form X ⇒ Y where X, Y ⊆ I and X ∩ Y = Ø. The item sets X and Y are called antecedent (left-hand-side or LHS) and consequent (right-hand-side or RHS) of the rule, respectively. The support supp(X) of an item set X is defined as the proportion of transactions in the database which contain the item set. Note that the support of an association rule X ⇒ Y is supp(X ∪ Y). The confidence of a rule is defined conf(X ⇒ Y) = supp(X ∪ Y) / supp(X). Confidence can be interpreted as an estimate of the probability P(Y | X), the probability of finding the RHS of the rule in transactions under the condition that these transactions also contain the LHS.

    For example, the rule {onions, potatoes} ⇒ {burger} found in the sales data of a supermarket would indicate that if a customer buys onions and potatoes together, he or she is likely to also buy burger. Such information can be used as the basis for decisions about marketing activities such as promotional pricing or product placements.

    Association rules are usually required to satisfy a user-specified minimum support and a user-specified minimum confidence at the same time. Association rule generation is usually split up into two separate steps:

    • First, minimum support is applied to find all frequent item sets in a database (i.e. frequent item set mining).
    • Second, these frequent item sets and the minimum confidence constraint are used to form rules.

    Finding all frequent item sets in a database is difficult since it involves searching all possible item sets (item combinations). The set of possible item sets is the power set over I (the set of items) and has size 2n - 1 (excluding the empty set which is not a valid item set). Although the size of the power set grows exponentially in the number of items n in I, efficient search is possible using the downward-closure property of support (also called anti-monotonicity) which guarantees that for a frequent item set also all its subsets are frequent and thus for an infrequent item set, all its supersets must be infrequent.

    In practice, we may only consider the frequent item set that has the maximum number of items bypassing all the sub item sets. An item set is maximal frequent if none of its immediate supersets is frequent.

    For a maximal frequent item set, even though we know that all the sub item sets are frequent, we don't know the actual support of those sub item sets, which are very important to find the association rules within the item sets. If the final goal is association rule mining, we would like to discover closed frequent item sets. An item set is closed if none of its immediate supersets has the same support as the item set.

    Some well known algorithms of frequent item set mining are Apriori, Eclat and FP-Growth. Apriori is the best-known algorithm to mine association rules. It uses a breadth-first search strategy to counting the support of item sets and uses a candidate generation function which exploits the downward closure property of support. Eclat is a depth-first search algorithm using set intersection.

    FP-growth (frequent pattern growth) uses an extended prefix-tree (FP-tree) structure to store the database in a compressed form. FP-growth adopts a divide-and-conquer approach to decompose both the mining tasks and the databases. It uses a pattern fragment growth method to avoid the costly process of candidate generation and testing used by Apriori.

    References:
    • R. Agrawal, T. Imielinski and A. Swami. Mining Association Rules Between Sets of Items in Large Databases, SIGMOD, 207-216, 1993.
    • Rakesh Agrawal and Ramakrishnan Srikant. Fast algorithms for mining association rules in large databases. VLDB, 487-499, 1994.
    • Mohammed J. Zaki. Scalable algorithms for association mining. IEEE Transactions on Knowledge and Data Engineering, 12(3):372-390, 2000.
    • Jiawei Han, Jian Pei, Yiwen Yin, and Runying Mao. Mining frequent patterns without candidate generation. Data Mining and Knowledge Discovery 8:53-87, 2004.
    Definition Classes
    smile
  • Operators
t

smile.association

Operators

trait Operators extends AnyRef

High level association rule operators.

Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. Operators
  2. AnyRef
  3. Any
Implicitly
  1. by any2stringadd
  2. by StringFormat
  3. by Ensuring
  4. by ArrowAssoc
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Value Members

  1. final def !=(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  2. final def ##(): Int
    Definition Classes
    AnyRef → Any
  3. def +(other: String): String
    Implicit
    This member is added by an implicit conversion from Operators to any2stringadd[Operators] performed by method any2stringadd in scala.Predef.
    Definition Classes
    any2stringadd
  4. def ->[B](y: B): (Operators, B)
    Implicit
    This member is added by an implicit conversion from Operators to ArrowAssoc[Operators] performed by method ArrowAssoc in scala.Predef.
    Definition Classes
    ArrowAssoc
    Annotations
    @inline()
  5. final def ==(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  6. def arm(file: String, minSupport: Int, confidence: Double, output: String): Long

    Association Rule Mining.

    Association Rule Mining. This method scans data twice. We first scan the database to obtains the frequency of single items. Then we scan the data again to construct the FP-Tree, which is a compressed form of data. In this way, we don't need load the whole database into the main memory. In the data, the item identifiers have to be in [0, n), where n is the number of items.

    file

    the input file of item sets. Each row is a item set, which may have different length. The item identifiers have to be in [0, n), where n is the number of items.

    minSupport

    the required minimum support of item sets in terms of frequency.

    confidence

    the confidence threshold for association rules.

    output

    the output file.

    returns

    the number of discovered association rules.

  7. def arm(file: String, minSupport: Int, confidence: Double, output: PrintStream): Long

    Association Rule Mining.

    Association Rule Mining. This method scans data twice. We first scan the database to obtains the frequency of single items. Then we scan the data again to construct the FP-Tree, which is a compressed form of data. In this way, we don't need load the whole database into the main memory. In the data, the item identifiers have to be in [0, n), where n is the number of items.

    file

    the input file. Each row is a item set, which may have different length. The item identifiers have to be in [0, n), where n is the number of items. Item set should NOT contain duplicated items. Note that it is reordered after the call.

    minSupport

    the required minimum support of item sets in terms of frequency.

    confidence

    the confidence threshold for association rules.

    output

    a print stream for output of association rules.

    returns

    the number of discovered association rules.

  8. def arm(itemsets: Array[Array[Int]], minSupport: Int, confidence: Double, output: String): Long

    Association Rule Mining.

    Association Rule Mining. Usually the algorithm generates too many data to fit in the memory. This alternative prints the results to a stream directly without storing them in the memory.

    itemsets

    the item set database. Each row is a item set, which may have different length. The item identifiers have to be in [0, n), where n is the number of items. Item set should NOT contain duplicated items. Note that it is reordered after the call.

    minSupport

    the required minimum support of item sets in terms of frequency.

    confidence

    the confidence threshold for association rules.

    output

    the output file.

    returns

    the number of discovered association rules.

  9. def arm(itemsets: Array[Array[Int]], minSupport: Int, confidence: Double, output: PrintStream): Long

    Association Rule Mining.

    Association Rule Mining. Usually the algorithm generates too many data to fit in the memory. This alternative prints the results to a stream directly without storing them in the memory.

    itemsets

    the item set database. Each row is a item set, which may have different length. The item identifiers have to be in [0, n), where n is the number of items. Item set should NOT contain duplicated items. Note that it is reordered after the call.

    minSupport

    the required minimum support of item sets in terms of frequency.

    confidence

    the confidence threshold for association rules.

    output

    a print stream for output of association rules.

    returns

    the number of discovered association rules.

  10. def arm(itemsets: Array[Array[Int]], minSupport: Int, confidence: Double): Buffer[AssociationRule]

    Association Rule Mining.

    Association Rule Mining. Let I = {i1, i2,..., in} be a set of n binary attributes called items. Let D = {t1, t2,..., tm} be a set of transactions called the database. Each transaction in D has a unique transaction ID and contains a subset of the items in I. An association rule is defined as an implication of the form X ⇒ Y where X, Y ⊆ I and X ∩ Y = Ø. The item sets X and Y are called antecedent (left-hand-side or LHS) and consequent (right-hand-side or RHS) of the rule, respectively. The support supp(X) of an item set X is defined as the proportion of transactions in the database which contain the item set. Note that the support of an association rule X ⇒ Y is supp(X ∪ Y). The confidence of a rule is defined conf(X ⇒ Y) = supp(X ∪ Y) / supp(X). Confidence can be interpreted as an estimate of the probability P(Y | X), the probability of finding the RHS of the rule in transactions under the condition that these transactions also contain the LHS. Association rules are usually required to satisfy a user-specified minimum support and a user-specified minimum confidence at the same time.

    itemsets

    the item set database. Each row is a item set, which may have different length. The item identifiers have to be in [0, n), where n is the number of items. Item set should NOT contain duplicated items. Note that it is reordered after the call.

    minSupport

    the required minimum support of item sets in terms of frequency.

    confidence

    the confidence threshold for association rules.

    returns

    the number of discovered association rules.

  11. final def asInstanceOf[T0]: T0
    Definition Classes
    Any
  12. def clone(): AnyRef
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  13. def ensuring(cond: (Operators) ⇒ Boolean, msg: ⇒ Any): Operators
    Implicit
    This member is added by an implicit conversion from Operators to Ensuring[Operators] performed by method Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  14. def ensuring(cond: (Operators) ⇒ Boolean): Operators
    Implicit
    This member is added by an implicit conversion from Operators to Ensuring[Operators] performed by method Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  15. def ensuring(cond: Boolean, msg: ⇒ Any): Operators
    Implicit
    This member is added by an implicit conversion from Operators to Ensuring[Operators] performed by method Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  16. def ensuring(cond: Boolean): Operators
    Implicit
    This member is added by an implicit conversion from Operators to Ensuring[Operators] performed by method Ensuring in scala.Predef.
    Definition Classes
    Ensuring
  17. final def eq(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  18. def equals(arg0: Any): Boolean
    Definition Classes
    AnyRef → Any
  19. def finalize(): Unit
    Attributes
    protected[java.lang]
    Definition Classes
    AnyRef
    Annotations
    @throws( classOf[java.lang.Throwable] )
  20. def formatted(fmtstr: String): String
    Implicit
    This member is added by an implicit conversion from Operators to StringFormat[Operators] performed by method StringFormat in scala.Predef.
    Definition Classes
    StringFormat
    Annotations
    @inline()
  21. def fpgrowth(file: String, minSupport: Int, output: String): Long

    Frequent item set mining based on the FP-growth (frequent pattern growth) algorithm.

    Frequent item set mining based on the FP-growth (frequent pattern growth) algorithm. This is for mining frequent item sets by scanning data twice. We first scan the database to obtains the frequency of single items. Then we scan the data again to construct the FP-Tree, which is a compressed form of data. In this way, we don't need load the whole database into the main memory. In the data, the item identifiers have to be in [0, n), where n is the number of items.

    file

    the input file of item sets. Each row is a item set, which may have different length. The item identifiers have to be in [0, n), where n is the number of items.

    minSupport

    the required minimum support of item sets in terms of frequency.

    output

    the output file.

    returns

    the number of discovered frequent item sets.

  22. def fpgrowth(file: String, minSupport: Int, output: PrintStream): Long

    Frequent item set mining based on the FP-growth (frequent pattern growth) algorithm.

    Frequent item set mining based on the FP-growth (frequent pattern growth) algorithm. This is for mining frequent item sets by scanning data twice. We first scan the database to obtains the frequency of single items. Then we scan the data again to construct the FP-Tree, which is a compressed form of data. In this way, we don't need load the whole database into the main memory. In the data, the item identifiers have to be in [0, n), where n is the number of items.

    file

    the input file of item sets. Each row is a item set, which may have different length. The item identifiers have to be in [0, n), where n is the number of items.

    minSupport

    the required minimum support of item sets in terms of frequency.

    output

    a print stream for output of frequent item sets.

    returns

    the number of discovered frequent item sets.

  23. def fpgrowth(itemsets: Array[Array[Int]], minSupport: Int, output: String): Long

    Frequent item set mining based on the FP-growth (frequent pattern growth) algorithm.

    Frequent item set mining based on the FP-growth (frequent pattern growth) algorithm. Usually the algorithm generates too many data to fit in the memory. This alternative prints the results to a stream directly without storing them in the memory.

    itemsets

    the item set database. Each row is a item set, which may have different length. The item identifiers have to be in [0, n), where n is the number of items. Item set should NOT contain duplicated items. Note that it is reordered after the call.

    minSupport

    the required minimum support of item sets in terms of frequency.

    output

    the output file.

    returns

    the number of discovered frequent item sets.

  24. def fpgrowth(itemsets: Array[Array[Int]], minSupport: Int, output: PrintStream): Long

    Frequent item set mining based on the FP-growth (frequent pattern growth) algorithm.

    Frequent item set mining based on the FP-growth (frequent pattern growth) algorithm. Usually the algorithm generates too many data to fit in the memory. This alternative prints the results to a stream directly without storing them in the memory.

    itemsets

    the item set database. Each row is a item set, which may have different length. The item identifiers have to be in [0, n), where n is the number of items. Item set should NOT contain duplicated items. Note that it is reordered after the call.

    minSupport

    the required minimum support of item sets in terms of frequency.

    output

    a print stream for output of frequent item sets.

    returns

    the number of discovered frequent item sets.

  25. def fpgrowth(itemsets: Array[Array[Int]], minSupport: Int): Buffer[ItemSet]

    Frequent item set mining based on the FP-growth (frequent pattern growth) algorithm, which employs an extended prefix-tree (FP-tree) structure to store the database in a compressed form.

    Frequent item set mining based on the FP-growth (frequent pattern growth) algorithm, which employs an extended prefix-tree (FP-tree) structure to store the database in a compressed form. The FP-growth algorithm is currently one of the fastest approaches to discover frequent item sets. FP-growth adopts a divide-and-conquer approach to decompose both the mining tasks and the databases. It uses a pattern fragment growth method to avoid the costly process of candidate generation and testing used by Apriori.

    The basic idea of the FP-growth algorithm can be described as a recursive elimination scheme: in a preprocessing step delete all items from the transactions that are not frequent individually, i.e., do not appear in a user-specified minimum number of transactions. Then select all transactions that contain the least frequent item (least frequent among those that are frequent) and delete this item from them. Recurse to process the obtained reduced (also known as projected) database, remembering that the item sets found in the recursion share the deleted item as a prefix. On return, remove the processed item from the database of all transactions and start over, i.e., process the second frequent item etc. In these processing steps the prefix tree, which is enhanced by links between the branches, is exploited to quickly find the transactions containing a given item and also to remove this item from the transactions after it has been processed.

    itemsets

    the item set database. Each row is a item set, which may have different length. The item identifiers have to be in [0, n), where n is the number of items. Item set should NOT contain duplicated items. Note that it is reordered after the call.

    minSupport

    the required minimum support of item sets in terms of frequency.

    returns

    the list of frequent item sets.

  26. final def getClass(): Class[_]
    Definition Classes
    AnyRef → Any
  27. def hashCode(): Int
    Definition Classes
    AnyRef → Any
  28. final def isInstanceOf[T0]: Boolean
    Definition Classes
    Any
  29. final def ne(arg0: AnyRef): Boolean
    Definition Classes
    AnyRef
  30. final def notify(): Unit
    Definition Classes
    AnyRef
  31. final def notifyAll(): Unit
    Definition Classes
    AnyRef
  32. final def synchronized[T0](arg0: ⇒ T0): T0
    Definition Classes
    AnyRef
  33. def toString(): String
    Definition Classes
    AnyRef → Any
  34. final def wait(): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  35. final def wait(arg0: Long, arg1: Int): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  36. final def wait(arg0: Long): Unit
    Definition Classes
    AnyRef
    Annotations
    @throws( ... )
  37. def →[B](y: B): (Operators, B)
    Implicit
    This member is added by an implicit conversion from Operators to ArrowAssoc[Operators] performed by method ArrowAssoc in scala.Predef.
    Definition Classes
    ArrowAssoc

Inherited from AnyRef

Inherited from Any

Inherited by implicit conversion any2stringadd from Operators to any2stringadd[Operators]

Inherited by implicit conversion StringFormat from Operators to StringFormat[Operators]

Inherited by implicit conversion Ensuring from Operators to Ensuring[Operators]

Inherited by implicit conversion ArrowAssoc from Operators to ArrowAssoc[Operators]

Ungrouped