2
$\begingroup$

I'm pretty new to machine learning.

I know I can represent a set of discrete values as a vector of 0/1 values. For instance, in the set of features {a, b, c, d, e}, the subset containing {a, c} can be represented as [1, 0, 1, 0, 0] and the subset containing {c, d, e} can be represented as [0, 0, 1, 1, 1], meaning I have as many dimensions as elements, which is workable when you have a finite (and small) number of elements.

But now, for a clustering task, I want to represent sets of sets, like, for instance, representing the set {{a, c}, {c, d, e}}. How can I do that? Here, the basic 0/1 approach won't work, as I'll have 2^n possible combinations. What is the workaround, if any?

Edit: here is the transcription as a less abstract, more business problem. I want to find clusters of people according to the trips they made. A trip consists in a set of cities visited, and a set of transportation used. For instance, people might have visited cities in the set {Rabat, Alger, Marrakech, Tunis, Hammamet} with transportation such as {car, plane, train}. A trip could be {Rabat, Marrakech, plane} or {Alger, Marrakech, Tunis, car, train}. Note the order in which cities were visited, or the order in which vehicles were used, is not considered.

An example of the items I want to find clusters of could be a person having made those two trips, represented as p1 = {{Rabat, Marrakech, plane}, {Alger, Marrakech, Tunis, car, train}}.

$\endgroup$
5
  • $\begingroup$ To be sure I understand, for one observation you have a set of subsets as the observed data point? $\endgroup$
    – kbrose
    Mar 29, 2018 at 14:05
  • $\begingroup$ yes @kbrose, {{a, c}, {c, d, e}} is one of the datapoints I want to clusterize. $\endgroup$
    – Fabien
    Mar 29, 2018 at 14:41
  • $\begingroup$ You may benefit from a reformulation. What's the real, business problem? $\endgroup$
    – Emre
    Mar 29, 2018 at 16:07
  • $\begingroup$ Thanks for the suggestion @Emre, I just made a detailed example. $\endgroup$
    – Fabien
    Mar 30, 2018 at 8:36
  • $\begingroup$ And what would you do next? There is little benefit in just encoding the data, you need to be able to do meaningful computations, too. $\endgroup$ Apr 8, 2018 at 19:09

2 Answers 2

1
$\begingroup$

You are describing one-hot encoding. There is a slot for each element. If the element is present, the slot has a one, and if the element if not present, the slot has a zero.

Typically, people will encode orthogonal features in different dimensions. In your case, cities would be one dimension and transportation type would be another dimension. A given data point would be one-hot encoded in a matrix (a 2D collection of vectors). If you want to add people, you would another dimension. That would create a 3D tensor with each person in a row.

Another way to compress your data is to encode not the cities (nodes) but the path between the cities (edges). From that encoding, you can create a Laplacian matrix that sets up spectral clustering. Since you have multiple transportation methods for the routes, you can create clusters with multi-dimensional spectral clustering.

$\endgroup$
0
$\begingroup$

Since you do not have a similarity measure for trips, two trips are different if the sets that represent the trips are different. So you can simply represent different trips by different numbers and represent a person's trips by a set of those numbers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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