[Python] Find the largest itemset in agroup of itemsets with the same support efficiently

I have a spark-DataFrame with two columns, ID and Items. Items is a list of strings.

My goal is to find frequent subsets of the itemsets in my data. I am familiar with apriori and fp-growth and used the latter to find frequent subsets. But I have one more requirement, in cases where multiple itemsets along a path in the fp-tree have the same support, I only want to keep the largest itemset. In my example, ["a"] has the same support as ["a", "b"]. Thus I am only interested in keeping the latter.

Even that is in principal not a problem, simplest solution is grouping itemsets by support, selecting the one with the most items in it and delete all subsets of that set. My problem is that the number of possible combinations is extremly large. I have 60 different items and itemsets of up to 50 items.

So my question is, is there anyway to make this more efficient?

Here is a basic example of what I am initially doing:

from pyspark.ml.fpm import FPGrowth
from pyspark.sql import functions as F
from pyspark.sql.functions import explode, udf
from pyspark.sql.types import ArrayType, IntegerType, StructType, StructField


basic_data = {100: [['a', 'b']],
101: [['a', 'b', 'c']],
102: [['a', 'b', 'c', 'd']],
103: [['a', 'b', 'c']],
104: [['a', 'b']],
105: [['a', 'b']],
106: [['c', 'e']],
107: [['c', 'e']],
108: [[ 'c', 'e']],
}

data = [(key, value[0]) for key, value in basic_data.items()]
schema = ['id', 'items']
df = spark.createDataFrame(data, schema=schema)

fpGrowth = FPGrowth(itemsCol = 'items', minSupport=0.3)
model = fpGrowth.fit(df)

# Display frequent itemsets
frequentItemsets = model.freqItemsets
frequentItemsets.show()


Which gives me this result:

+---------+----+
| items|freq|
+---------+----+
| [a]| 6|
| | 6|
| [b, a]| 6|
| [c]| 6|
| [c, b]| 3|
|[c, b, a]| 3|
| [c, a]| 3|
| [e]| 3|
| [e, c]| 3|
+---------+----+


I then group the data by frequency:

df = frequentItemsets.groupBy('freq').agg(F.collect_list('items').alias('items_list'))
df.show(truncate=False)

+----+----------------------------------------+
|freq|items_list |
+----+----------------------------------------+
|6 |[, [b, a], [a], [c]] |
|3 |[[c, b], [c, b, a], [c, a], [e], [e, c]]|
+----+----------------------------------------+


Next for each frequency I remove all itemsets that are subsets of another itemset with the same frequency. So for instance I remove and [a] from the first row, because they are both subsets of [a,b]. My code for this is not the best, but I hope you get the idea:

def getlongestitem(itemlist:list)->int:
longestlen = 0
longestitem_index = -1
for i in range(len(itemlist)):
if len(itemlist) > longestlen:
longestlen = len(itemlist)
longestitem_index = i
return longestitem_index


def find_subsets(itemlist:list, index:int)->list:
'''
Find all subsets of itemlist that are subsets of itemlist[index]
Return a list of indexes of the subsets
'''
subset_indexes = []
longestitem = itemlist[index]
for i in range(len(itemlist)):
if all(element in longestitem for element in itemlist):
subset_indexes.append(i)
return subset_indexes


def extract_items(itemlist:list)->list:
'''
Find the largest item in itemlist and find all subsets of itemlist that are subsets of the largest item.
Remove the largest item and all its subsets from itemlist. Repeat until itemlist is empty.
Return a list of the largest items.
'''
items = []
processed_indices = set() # Track indices of processed items

while len(processed_indices) < len(itemlist):
longestitem_index = getlongestitem(itemlist)

while longestitem_index in processed_indices:
itemlist[longestitem_index] = []
longestitem_index = getlongestitem(itemlist)

subset_indexes = find_subsets(itemlist, longestitem_index)
items.append(itemlist[longestitem_index])

processed_indices.update(subset_indexes)

return items


extract_items_udf = udf(extract_items, ArrayType(ArrayType(StringType())))

df_with_items = df.withColumn("extracted_items", extract_items_udf(df["items_list"]))

result_df = df_with_items.select(df_with_items["freq"], explode(df_with_items["extracted_items"]).alias("items"))

result_df.show(truncate=False)


The results then looks like this:

+----+---------+
|freq|items |
+----+---------+
|3 |[c, b, a]|
|3 |[e, c] |
|6 |[b, a] |
|6 |[c] |
+----+---------+


Now that is all fine and runs - on a small dataset. But my issue is that the number of items I have is around 60 and thus the number of combinations is extremly large. fpgrowth delivered results but the next step, removing those subsets crashes because I run out of memory. I tried batching this by looking at one frequency at a time but even then I have the problem that there are so many itemsets with the same frequency that I can not process this well.

Continue reading...