How do I group objects by similiar items that they contain?

user_17208851 0
Viewed 64

I have 10,000 baskets. In each basket, I have 10 food objects, no repetitions.

I need to group baskets in groups where all baskets in the group have >=6 of the same objects within them, with no repetitions in any group. Basically, if a group has basket1, basket2, basket33, basket 123, then no other groups will have them.

When I try to do it with combinations, I end up with many redundant groups.

from typing import Generic, TypeVar, List
import random
from uuid import uuid4
import attr

T = TypeVar("T")

food = ['apple', 'banana','grapes','orange','potato','kiwi','pomegranate','blueberry','strawberry','cantalope','honeydew','papaya','mango','raspberry',
        'celery','carrot','potato','raddish','lettuce','tomato','garlic','onion','cabbage','corn','shallot','peas','squash','broccoli','spinach']
        #'pasta','sugar','flour','honey','salt','pepper','corn starch','baking soda','cinnamon','paprika','butter','cream','chocolate']

@attr.dataclass
class Basket(Generic[T]):
    items: List[T]
    volume: int
    id: str = attr.ib(factory=lambda: str(uuid4()))


#Generate baskets
basket_names = [f"basket{i}" for i in range(1, 10001)]
baskets: List[Basket[str]] = [
    Basket(items=random.sample(food, 10), volume=random.randint(0, 1000), id=name)
    for name in basket_names
]
algorithm python
1 Answers

Here is a solution using scikit-learn.

  • sklearn.preprocessing.MultiLabelBinarizer to transform each basket into a 0-1 vector with one coordinate per food type;
  • sklearn.cluster.AgglomerativeClustering to make clusters, with baskets in the same cluster if they differ by at most 8 food types (8 = 2 * 4 = 2 * (10 - 6), so if two baskets have exactly 6 food types in common, then their vectors will differ by 8 coordinates)
  • AgglomerativeClustering().fit_predict() returns a list of numbers: number x at index i in the list means that the ith basket is in the xth cluster.
  • itertools.groupby with zip can be used to get the clusters as a list of lists of baskets.
import random
from sklearn.cluster import AgglomerativeClustering
from sklearn.preprocessing import MultiLabelBinarizer
from itertools import groupby
from operator import itemgetter

n_baskets = 10000
n_foodperbasket = 10
n_samefoodpercluster = 6
max_volume = 1000

food = sorted(['apple', 'banana','grapes','orange','potato','kiwi','pomegranate','blueberry',
 'strawberry','cantalope','honeydew','papaya','mango','raspberry', 'celery','carrot',
 'raddish','lettuce','tomato','garlic','onion','cabbage','corn','shallot',
 'peas','squash','broccoli','spinach']) # removed your duplicate 'potato'

baskets = [(random.sample(food, n_foodperbasket), random.randint(0,max_volume), i) for i in range(n_baskets)]

vectorbaskets = MultiLabelBinarizer(classes=food).fit_transform([b[0] for b in baskets])

clustering = AgglomerativeClustering(n_clusters=None, distance_threshold=2*(n_foodperbasket - n_samefoodpercluster))
clusters = clustering.fit_predict(vectorbaskets)

groups = [list(g) for k,g in groupby(sorted(zip(clusters, baskets)), key=itemgetter(0))]

print(groups)
user_30807230
Related