Discovering high-value patterns in transactions
On this publish, I’ll give a substitute for in style strategies in market basket evaluation that may assist practitioners discover high-value patterns slightly than simply essentially the most frequent ones. We are going to acquire some instinct into completely different sample mining issues and take a look at a real-world instance. The total code may be discovered right here. All photos are created by the writer.
I’ve written a extra introductory article about sample mining already; in the event you’re not aware of a number of the ideas that come up right here, be at liberty to verify that one out first.
Briefly, sample mining tries to seek 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 seemed on the sequence of actions {that a} consumer performs on a web site. On this case, we would care concerning the ordering of the gadgets.
In different circumstances, such because the one we are going to focus on under, we don’t care concerning the ordering of the gadgets. We solely listing all of the gadgets that have been within the transaction and the way usually 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 gadgets, however in lots of situations (because the one we are going to focus on under), there isn’t a logical ordering of the gadgets. That is much 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 concept 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 will 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 taking a look at how usually the sample X seems within the database.
In FIM, we then wish to discover all of the sequences which have a assist greater than some threshold (usually referred to 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 characterize it as a one. However we frequently have circumstances (similar 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 suggest relevance. In that sense, FIM assumes that each one gadgets within the transaction are equally essential. Nonetheless, it’s cheap to imagine that somebody shopping for caviar may be extra essential for a enterprise than somebody shopping for bread, as caviar is probably a excessive ROI/revenue merchandise.
These limitations straight convey us to Excessive Utility Itemset Mining (HUIM) and Excessive Utility Quantitative Itemset Mining (HUQIM) that are generalizations of FIM that attempt to deal with a number of the issues of regular FIM.
Our first generalization is that gadgets can seem greater than as soon as in a transaction (i.e. we now have 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 under 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 can be represented as [a,b] in common FIM. We rapidly see that, in some circumstances, we may miss essential particulars. For instance, if a and b have been some gadgets in a buyer’s buying cart, it will matter quite a bit whether or not we now have a (e.g. a loaf of bread) 5 instances or solely as soon as. Subsequently, we characterize the transaction as a multiset during 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 gadgets can seem in a lot of gadgets (e.g. 100 or 1000 instances). In that case, we’d like not write down all of the a’s or b’s however merely how usually 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 now have a desk that assigns each doable merchandise a unit revenue.
We will then calculate the utility of a selected sample similar to {🥪, 🍎} by summing up the utility of these gadgets 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 now have to seek out patterns with excessive utility. That is primarily as a result of we assume that frequency doesn’t suggest 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 gadgets within the transaction. For our transaction 3 within the database, this is able to be
1🥪 * $1 + 2🦞*$10 + 2🍎*$2 = $25
Observe that fixing this downside and discovering all high-utility gadgets is harder than common FPM. It’s because the utility doesn’t comply with 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 have to be a minimum of as huge as Y’s.
Because of this if a subset of Y is rare, Y itself have to be rare because it will need to have a smaller assist. Let’s say we now have X = {a} and Y = {a,b}. If Y seems 4 instances in our database, then X should seem a minimum of 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 eradicate them from the search area [3].
This property doesn’t maintain after we are speaking about utility. A superset Y of transaction X may have kind of utility. If we take the instance from above, {🥪} has a utility of $4. However this doesn’t imply we can not take a look at supersets of this sample. For instance, the superset we checked out {🥪, 🍎} has a better utility of $10. On the identical time, a superset of a sample gained’t all the time have extra utility because it may be that this superset simply doesn’t seem fairly often within the DB.
Thought Behind HUIM
Since we will’t use the apriori property for HUIM straight, we now have to give you another higher certain for narrowing down the search area. One such certain 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 a better 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 similar to {🥪 🦞 🍎} we will see that there isn’t a method it will have extra utility since all transactions which have Y in them even have X in them.
There at the moment are numerous algorithms for fixing HUIM. All of them obtain a minimal utility and produce the patterns which have a minimum of 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 complete of round 19,500 transactions with a mean transaction worth of $526 and 26 distinct gadgets per transaction. In complete, there are round 4000 distinctive gadgets. We will additionally make an ABC evaluation the place we put gadgets into completely different buckets relying on their share of complete income. We will see that round 500 of the 4000 gadgets make up round 70% of the income (A-items). We then have an extended right-tail of things (round 2250) that make up round 5% of the income (C-items).
Preprocessing
The preliminary information is in an extended 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 gadgets w/o utilitytransaction_db = information.groupby('BillNo').agg(
gadgets=('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 will then apply the EFIM algorithm.
import PAMI.highUtilityPattern.fundamental.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 a listing of patterns that meet this minimal utility criterion.