Adaptive Cluster Based Discovery of High Utility Itemsets

Abstract

Utility Itemset Mining (UIM) is a key analysis technique for data which is modeled by the Transactional data model. While improving the computational time and space efficiency of the mining of itemsets is important, it is also critically important to predict future itemsets accurately. In today’s time, when both scientific and business competitive edge is commonly derived from first access to knowledge via advanced predictive ability, this problem becomes increasingly relevant. We established in our most recent work that having prior knowledge of approximate cluster structure of the dataset and using it implicitly in the mining process, can lend itself to accurate prediction of future itemsets. We evaluate the individual strength of each transaction while focusing on itemset prediction, and reshape the transaction utilities based on that. We extend our work by identifying that such reshaping of transaction utilities should be adaptive to the anticipated cluster structure, if there is a specific intended prediction window. We define novel concepts for making such an anticipation and integrate Time Series Forecasting into the evaluation. We perform additional illustrative experiments to demonstrate the application of our improved technique and also discuss future direction for this work.

Appendix

C is the set of all given clusters. A cluster $C_k \in C$ is essentially a subset of transactions from D.

$$\begin{aligned} C_k = \{T_1, T_2 \ldots T_k |T_i \in D \} \end{aligned}$$

(23)

$$\begin{aligned} I_{C_k}=\{a_i|a_i\in T_j\wedge T_j\in C_k \}=\text {item types in } C_k \end{aligned}$$

(24)

Cluster utility (CU), relative utility (ru) of a category type in a cluster and the affinity between clusters have the following definitions:

$$\begin{aligned} CU(C_k)=\sum _{T_j\in C_k }TU(T_j)=\text {Cluster utility of } C_k \end{aligned}$$

(25)

CU is an overall measure of importance of a cluster, since it is the sum of utilities of all transactions in it.

$$\begin{aligned} \forall a_i\in I_{C_k}, ru(a_i, C_k)=\frac{\sum _{a_i\in I_{C_k}\wedge T_j\in C_k}au(a_i, T_j)}{CU(C_k)} \end{aligned}$$

(26)

ru is the relative importance (since utility is a unit of importance) given to $a_i$ among all $I_{C_k}$ in $C_k$.

For clusters $C_i$ and $C_j$:

$$\begin{aligned} affinity(C_i, C_j)=\sum _{a\in I_{C_k}\wedge a\in I_{C_j}}min(ru(a,C_i),ru(a,C_j)) \end{aligned}$$

(27)

It is the sum of shared utility of common category types among two clusters. $min_{aff}$ and $min_{uty}$ are tunable parameters of the algorithm. $min_{aff}$ decides the termination criterion of the clustering and $min_{uty}$ decides the final selection criterion for the clusters.