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

Initial approach:

  • 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.
  • $\begingroup$ Interesting question, but probably better suited for stats.stackexchange.com $\endgroup$ Apr 29 '11 at 15:49
  • $\begingroup$ I originally submitted this to stats.stackexchange.com and am viewing it from there...is this showing up elsewhere? $\endgroup$
    – don
    Apr 29 '11 at 16:45
  • $\begingroup$ Oh, man, it has been a long week. I habitually open a bunch of StackOverflow and CrossValidated questions in adjacent tabs, and this was at the end of a string of StackOverflow questions. Then, when I flagged for attention, it gave me the option to suggest that it move to stats.stackexchange - except that was actually META.stats.stackexchange. I should probably go to bed now. $\endgroup$ Apr 29 '11 at 18:20
  • $\begingroup$ you don't sound like a novice data miner to me. $\endgroup$
    – rolando2
    Apr 30 '11 at 16:39
  • $\begingroup$ @rolando2: I suppose it's all relative, heh. I still feel like I've only scraped the surface of the subject... $\endgroup$
    – don
    Apr 30 '11 at 16:55

I am a novice data miner as well, but may I suggest that exploratory data analysis is always a good first step? I would see if items can be assigned some sort of 'priority value' which can serve to predict how early they appear in the cart, as such a result may allow you to use simpler models. Something as simple as a linear regression on (#order in cart/#number of items in cart) for all carts possessing item X will give you an idea of whether this is possible. Suppose you find that a certain proportion of items always appear early, or later, and some seem to be completely random: this would guide you in your later model-building.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.