How to represent a set of sets as a vector

Question

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}}.

Answer 1

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.

Answer 2

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.