What is a good way to cluster a variable length sequence data I have a dataset consisting of variable length sequences: There are about 5000 instances. Each instance is a variable length sequence. The shortest sequence has a length of 2 and the longest sequence has a length of 64.
An example sequence looks something like this: ["31A354", "42C164", "39A200", "33B126", "33A443"]. This sequence has a length of 5. Each element of this sequence represents a step in a manufacturing process. The complete sequence thus represents a product. I am tring to do a cluster analysis so that similar processes are grouped together. Thus each cluster would represent a unique product.
An important detail to note is that the order of the elements in the sequence is crucial. If the order of the elements (the steps in manufacturing process) is altered, it would produce a different product. The total number of unique process steps in the dataset is 300.
Based on all these details, I used Sequence Graph Transform to convert the variable length sequences into constant length vectors. This technique preserves the positional and order information of the sequences:

*

*Since all the elements in the sequences are strings, I converted them to integers. Each element was mapped to an integer between 1 and 300.

*I applied Sequence Graph Transform on the integer sequences to obtain fixed lenght vectors.

*The result was a sparse array of dimension 5000x90000 (5000 instances and 90000 features).

After obtaining constant length for all the instances, I applied Principal Component Analysis to bring down the number of features from 90000 to 3 (Maybe this is where I need to do something else). After obtaining the 3 dimensional feature set, I did cluster analysis but did not get any intuitive results.
Could anyone advise any improvements on the steps that I've done or any other techniques to perform the cluster analysis?
 A: The TraMineR R package proposes several dissimilarity measures (See seqdist function) between categorical sequences, most of them (Optimal matching, which is Needlman-Wunsch, and its variants, number of matching subsequences, ...) applying to sequences of different length. Function seqdist proposes also different normalization options of the distances.
Function seqdist returns the matrix of pairwise dissimilarities between sequences, which can then be inputted to any clustering function based on a pairwise distance matrix. The WeightedCluster package, for example, offers efficient PAM (partitioning around medoids) functions for clustering sequences.
The approach above should work with your data. Nevertheless, it will not tell you if it makes sense to compare a sequence of length 2 with one of length 64. (The distance between two such sequences would essentially be their difference in length.) To give more sense to your analysis, I would suggest to restrict the set of sequences by excluding those with extremes lengths, e.g., such that the shortest sequences have at least half the length of the longest ones.
