Question for the experienced data miners out there:
Given this scenario:
- There are N shopping carts
- Each shopping cart is filled with an arbitrary number of M items from an infinitely large set (with the current amount of data I have, that arbitrary number can hit numbers around 1500)
- The order in which each cart is filled is significant
- There are other attributes such as geolocation of shopper, but these can be (and currently are) thrown out in favor of making the algorithm simpler
I need to:
- At a particular point in time, given only the ordered sets of items in each cart, identify 'similar' carts without prior knowledge of class labels
- After a certain amount of data has been collected and a drudge works through the data and assigns labels, create a classifier that can work quickly with future unseen data
- So far, my approach has been focused on the first point. My method uses k-means clustering and handles the sequential nature of the data by using a distance matrix generated by calculating the Hamming distance between carts. In this way, [apple, banana, pear] is different from [pear, apple, banana], but [apple, banana, pear] is less different from [apple, banana, antelope]. The appropriate value of k is determined through investigation of the silhouette coefficient. The clusters generated from this seem to make sense, but the runtime of my method will definitely be prohibitive as my dataset scales.
- Would anyone happen to have any suggestions for a novice data miner for this problem?
Edits with more info:
- I've found suggestions that consider using n-gram features and comparing them pair-wise. A concern I have about this is order: will the order of the sequences be maintained if n-gram models are used? Also, I see performance issues being a larger possibility with this method.