Market Basket Evaluation Utilizing Excessive Utility Itemset Mining | by Laurin Brechter | Sep, 2024

Discovering high-value patterns in transactions

On this submit, I’ll give a substitute for standard methods in market basket evaluation that may assist practitioners discover high-value patterns reasonably than simply essentially the most frequent ones. We’ll acquire some instinct into completely different sample mining issues and take a look at a real-world instance. The total code could be discovered right here. All pictures are created by the writer.

I’ve written a extra introductory article about sample mining already; when you’re not acquainted with among the ideas that come up right here, be at liberty to test that one out first.

Briefly, sample mining tries to search out patterns in information (duuh). More often than not, this information comes within the type of (multi-)units or sequences. In my final article, for instance, I regarded on the sequence of actions {that a} person performs on a web site. On this case, we would care in regards to the ordering of the objects.

In different circumstances, such because the one we are going to focus on beneath, we don’t care in regards to the ordering of the objects. We solely listing all of the objects that had been within the transaction and the way typically they appeared.

So for instance, transaction 1 contained 🥪 3 instances and 🍎 as soon as. As we see, we lose details about the ordering of the objects, however in lots of situations (because the one we are going to focus on beneath), there isn’t any logical ordering of the objects. That is just like a bag of phrases in NLP.

Market Basket Evaluation (MBA) is an information evaluation approach generally utilized in retail and advertising and marketing to uncover relationships between merchandise that clients have a tendency to buy collectively. It goals to establish patterns in clients’ buying baskets or transactions by analyzing their buying conduct. The central thought is to know the co-occurrence of things in buying transactions, which helps companies optimize their methods for product placement, cross-selling, and focused advertising and marketing campaigns.

Frequent Itemset Mining (FIM) is the method of discovering frequent patterns in transaction databases. We are able to take a look at the frequency of a sample (i.e. a set of things) by calculating its assist. In different phrases, the assist of a sample X is the variety of transactions T that include X (and are within the database D). That’s, we’re merely how typically the sample X seems within the database.

In FIM, we then need to discover all of the sequences which have a assist larger than some threshold (typically known as minsup). If the assist of a sequence is greater than minsup, it’s thought of frequent.

Limitations

In FIM, we solely take a look at the existence of an merchandise in a sequence. That’s, whether or not an merchandise seems two instances or 200 instances doesn’t matter, we merely symbolize it as a one. However we regularly have circumstances (akin to MBA), the place not solely the existence of an merchandise in a transaction is related but additionally what number of instances it appeared within the transaction.

One other downside is that frequency doesn’t all the time indicate relevance. In that sense, FIM assumes that every one objects within the transaction are equally necessary. Nevertheless, it’s affordable to imagine that somebody shopping for caviar is likely to be extra necessary for a enterprise than somebody shopping for bread, as caviar is probably a excessive ROI/revenue merchandise.

These limitations immediately convey us to Excessive Utility Itemset Mining (HUIM) and Excessive Utility Quantitative Itemset Mining (HUQIM) that are generalizations of FIM that attempt to tackle among the issues of regular FIM.

Our first generalization is that objects can seem greater than as soon as in a transaction (i.e. we have now a multiset as a substitute of a easy set). As stated earlier than, in regular itemset mining, we remodel the transaction right into a set and solely take a look at whether or not the merchandise exists within the transaction or not. So for instance the 2 transactions beneath would have the identical illustration.

t1 = [a,a,a,a,a,b] # repr. as {a,b} in FIM
t2 = [a,b] # repr. as {a,b} in FIM

Above, each these two transactions could be represented as [a,b] in common FIM. We shortly see that, in some circumstances, we may miss necessary particulars. For instance, if a and b had been some objects in a buyer’s buying cart, it could matter so much whether or not we have now a (e.g. a loaf of bread) 5 instances or solely as soon as. Due to this fact, we symbolize the transaction as a multiset by which we write down, what number of instances every merchandise appeared.

# multiset illustration
t1_ms = {(a,5),(b,1)}
t2_ms = {(a,1),(b,1)}

That is additionally environment friendly if the objects can seem in numerous objects (e.g. 100 or 1000 instances). In that case, we want not write down all of the a’s or b’s however merely how typically they seem.

The generalization that each the quantitative and non-quantitative strategies make, is to assign each merchandise within the transaction a utility (e.g. revenue or time). Under, we have now a desk that assigns each attainable merchandise a unit revenue.

We are able to then calculate the utility of a particular sample akin to {🥪, 🍎} by summing up the utility of these objects within the transactions that include them. In our instance we might have:

(3🥪 * $1 + 1🍎 * $2) +

(1 🥪 * $1 + 2🍎 * $2) = $10

So, we get that this sample has a utility of $10. With FIM, we had the duty of discovering frequent patterns. Now, we have now to search out patterns with excessive utility. That is primarily as a result of we assume that frequency doesn’t indicate significance. In common FIM, we would have missed uncommon (rare) patterns that present a excessive utility (e.g. the diamond), which isn’t true with HUIM.

We additionally must outline the notion of a transaction utility. That is merely the sum of the utility of all of the objects within the transaction. For our transaction 3 within the database, this could be

1🥪 * $1 + 2🦞*$10 + 2🍎*$2 = $25

Be aware that fixing this downside and discovering all high-utility objects is tougher than common FPM. It is because the utility doesn’t observe the Apriori property.

The Apriori Property

Let X and Y be two patterns occurring in a transaction database D. The apriori property says that if X is a subset of Y, then the assist of X should be at the least as huge as Y’s.

Which means that if a subset of Y is rare, Y itself should be rare because it should have a smaller assist. Let’s say we have now X = {a} and Y = {a,b}. If Y seems 4 instances in our database, then X should seem at the least 4 instances, since X is a subset of Y. This is sensible since we’re making the sample much less basic / extra particular by including an merchandise which suggests that it’ll match much less transactions. This property is utilized in most algorithms because it implies that if {a} is rare all supersets are additionally rare and we will remove them from the search area [3].

This property doesn’t maintain once we are speaking about utility. A superset Y of transaction X may have roughly utility. If we take the instance from above, {🥪} has a utility of $4. However this doesn’t imply we can’t take a look at supersets of this sample. For instance, the superset we checked out {🥪, 🍎} has the next utility of $10. On the similar time, a superset of a sample gained’t all the time have extra utility because it is likely to be that this superset simply doesn’t seem fairly often within the DB.

Concept Behind HUIM

Since we will’t use the apriori property for HUIM immediately, we have now to provide you with another higher sure for narrowing down the search area. One such sure is named Transaction-Weighted Utilization (TWU). To calculate it, we sum up the transaction utility of the transactions that include the sample X of curiosity. Any superset Y of X can’t have the next utility than the TWU. Let’s make this clearer with an instance. The TWU of {🥪,🍎} is $30 ($5 from transaction 1 and $5 from transaction 3). After we take a look at a superset sample Y akin to {🥪 🦞 🍎} we will see that there isn’t any approach it could have extra utility since all transactions which have Y in them even have X in them.

There at the moment are varied algorithms for fixing HUIM. All of them obtain a minimal utility and produce the patterns which have at the least that utility as their output. On this case, I’ve used the EFIM algorithm since it’s quick and reminiscence environment friendly.

For this text, I’ll work with the Market Basket Evaluation dataset from Kaggle (used with permission from the unique dataset writer).

Above, we will see the distribution of transaction values discovered within the information. There’s a whole of round 19,500 transactions with a median transaction worth of $526 and 26 distinct objects per transaction. In whole, there are round 4000 distinctive objects. We are able to additionally make an ABC evaluation the place we put objects into completely different buckets relying on their share of whole income. We are able to see that round 500 of the 4000 objects make up round 70% of the income (A-items). We then have a protracted right-tail of things (round 2250) that make up round 5% of the income (C-items).

Preprocessing

The preliminary information is in a protracted format the place every row is a line merchandise inside a invoice. From the BillNo we will see to which transaction the merchandise belongs.

After some preprocessing, we get the info into the format required by PAMI which is the Python library we’re going to use for making use of the EFIM algorithm.

information['item_id'] = pd.factorize(information.Itemname)[0].astype(str) # map merchandise names to id
information["Value_Int"] = information["Value"].astype(int).astype(str)
information = information.loc[data.Value_Int != '0'] # exclude objects w/o utility
transaction_db = information.groupby('BillNo').agg(
objects=('item_id', lambda x: ' '.be part of(listing(x))),
total_value=('Worth', lambda x: int(x.sum())),
values=('Value_Int', lambda x: ' '.be part of(listing(x))),
)
# filter out lengthy transactions, solely use subset of transactions
transaction_db = transaction_db.loc[transaction_db.num_items < 10].iloc[:1000]

We are able to then apply the EFIM algorithm.

import PAMI.highUtilityPattern.primary.EFIM as efim 
obj = efim.EFIM('tdb.csv', minUtil=1000, sep=' ') 
obj.startMine()                       #begin the mining course of 
obj.save('out.txt')               #retailer the patterns in file 
outcomes = obj.getPatternsAsDataFrame()     #Get the patterns found right into a dataframe 
obj.printResults()   

The algorithm then returns an inventory of patterns that meet this minimal utility criterion.