.

if all the sequences of the same type have the same length (all A sequences have length La, all B sequences have length Lb and so on) and if all these sequences have a priori the same importance, a simplistic approach would be to concatenate them into one large string and use any appropriate similarity between such strings (jaccard, or sum of the jaccard similarities per sequence, for instance) to cluster the users.

but this is maybe too simplistic for your application ...

.

even then if the sequences having different lengths you could find the common sequence by using LONGEST LENGTH COMMON SEQUENCE using dynamic programming.after that you could go for S3M method to cluster the sequences

Yes, the sequences have different lengths. If I use the sequence such as (1,3)(7,2)...(1000,8)... for each sequence, may I apply dynamic programming? Thanks all.

Yes you can apply dynamic programming to find the common subsequence

@Bindu Madhuri: Thank you very much.

Yes, dynamic programming is useful. In classical time series analysis this is reffered as DTW (dynamic time warping) . You can find ready to use code in MATLAB bioinformatics toolbox.

Yes, I am doing about time series data. It makes me tired now. I read many papers about Similarity Function. Now I want to write all codes by myself. I would like to use Hierarchical Clustering in this case. DTW ...erm let me see.

Thanks all.

Between pattern sequences and frequent pattern sequences which one is better for clustering?I think frequent is better, right?because my data is very huge. Thanks!

.

the downside of frequent patterns or frequent sequences (unsure of the vocabulary ; in ABC, "AC" is a pattern, "AB" is a sequence (and a pattern !)) is that you won't see the similarity of individuals sharing "not so frequent" patterns or sequences (sensitivity of the clustering to the frequency threshold) but it is certainly a very reasonable first step with large data sets since, after recoding the series on the set of frequent pattern, it reduces the problem to some kind of document (individual) / word (frequent pattern) clustering problem

.

so, it is better for me to choose the frequent pattern. Thanks a lot.

I don't understand or don't know a point.

E.g, a simple clustering

Object Feature 1 Feature 2

A 1.0 1.0

B 1.0 1.0

C 1.0 1.0

D 1.0 1.0

E 1.0 1.0

.....

If I apply Euclidean, I can save distance value into a matrix.

BUT when a object have many sequences and each sequence is multidimensional.

e.g,

Object Sequence 1 sequence 2 ........

A 111000 00010101

B 111000 00010101

C 111000 00010101

D 111000 00010101

How can I store the similarities into a matrix or any where?

Thanks for your time.

.

a possible approach would be

- for each sequence, extract frequent patterns

- recode all individuals on the basis of the frequent patterns

you are back to a document / word co-clustering problem

modifying your example :

A 111010 1001

B 111001 0101

C 111100 0011

D 111000 0001

for the first sequence, 111, 10, 00 are frequent with frequency threshold at 3 (maybe others, i did not count, i'm just trying to explain ...)

for the second sequence, 01 is frequent

vocabulary is therefore : {S1_111, S1_10, S1_00, S2_01}

(of course it is necessary to prefix a frequent pattern by the sequence from which it originates !)

and the recoded data set is (coded as a sparse matrix with "document; word; number of occurrences of word in document" on a line, zeros are not coded) :

A S1_111 1

A S1_10 2

A S2_01 1

B S1_111 1

B S1_10 1

B S1_00 1

B S2_01 2

etc

from there, you could simply apply LDA or your favourite co-clustering algorithm.

warning : this is just a possible approach ; depending on your application it may (or not !) make sense !

Thanks for your great idea!

I always think that each object is only in 1 line as normal clustering.

If each object is in many line, how can we calculate the similarities value among objects?(maybe this is a stupid question but I really need to know.)

As your idea, I can recoded data set as your example. Thanks a lot.

.

"one object, many lines" may have several meanings !

small database formalization : assume a star schema with a central table of "individuals" ("objects" for you) with just a single column of identifiers and several fact tables around linked to the central table with a 0:n link (hence, an id of the central table can be linked to zero, one or several records of the side tables ; different individuals can be linked to different numbers of lines, of course).

assume that the side tables describe uncommensurable facets of the individuals (say, their e-mails usage on one side and their favourite books on the other) ; in this case, you can try to define a similarity for each side table (see below) and build an agregate similarity with a weighted sum of the similarities of each table. The task of finding the "good" set of weights is all yours and remember that there is not such thing as a "best" clustering "per se" : your "best" clustering is the one that fits your needs best, helps you understand your data in the best way ... and there may be many such "best" clusterings !

So setting the weights is a trial and error process where you may at one point decide that the current clustering gives too much importance to one of the table and therefore decrease its weights just to see what happens. Exploratory data analysis is not as much a science as some kind advanced handicraft !

now, we're left with the problem of building a similarity from one fact table with a 0:n link to the central table. The simplistic approach is to select a set of relevant agregates for the domain described by the fact table and compute those agregates for each individual from the possibly many lines of the fact table ; we end up with a reduced agregate table with a 1:1 link to the central table. Agregates will depend on the domain : for sequences, frequent patterns or subsequences can be used, for numerical data (say, the side table is the table of all the customers invoice), mean, std, quantiles and so on may be appropriate ...

research in the area focuses on avoiding such simplistic methods as outlined above (simplistic ... but quite efficient in practice, however !). You can google for "clustering multi-relational data" for more information.

.

Many thanks.hihi

I'm curious to see what would happen if you perhaps applied a quantization and vectorization scheme meant for free text. Have you looked into treating your binary sequences as words? and your users as documents? I'd be very interested to see what would happen if you used a TF-IDF( http://en.wikipedia.org/wiki/Tf%E2%80%93idf ) scheme to vectorize your users for clustering by Euclidean Distance.

The thought occurred to me because the TF-IDF measurement is simple enough that it may actually prove useful in measuring similarities amongst your users.

If you choose this path there are many tool sets that will tokenize your data and vectorize your "documents" for you and save you the step of writing the transformation code by hand..

So, if I look into treating patterns as words and users as documents, I can apply TF-IDF in this situation? each document will become a vector?How can I do that? Could you give me some papers or key words about this method!

The main point of research is clustering documents (users).

e.g: cluster 1: doc 1, doc 2.....

cluster 2: doc 1, doc 3,.....

one document can be in many clusters.

BTW, what algorithm should I choose for this method?

Thank you so much!

.

you can apply "Latent Dirichlet Allocation" directly on the sparse matrix of counts (no tf-idf preprocessing)

http://en.wikipedia.org/wiki/Latent_Dirichlet_allocation‎

if you use tf-idf preprocessing you can simply go for a k-means on the resulting representation or to a fuzzy k-means if you _really_ want (need) to have multiple membership ... which mainly adds confusion, but that's just my opinion!

.

I would agree with Clerot in that you should avoid multiple membership in your clusters if you can avoid it.

You may or may not find your cluster results skewed by very commonly occurring patterns. In text mining we account for this with large lists of stop words to automatically ignore(amongst other preprocessing steps). In your case you may have to manually compile a list of extremely common patterns to ignore if your results are skewed.

Here is an overview of k-means clustering of text documents with python:

https://www.youtube.com/watch?v=Zd5dfooZWG4

heres more about how the preprocessors, TF-IDF among others listed , work under the sklearn suite

http://scikit-learn.org/stable/modules/feature_extraction.html#text-feature-extraction

I believe that it is explained much better there than in most papers I've read.

You may notice that I'm promoting python and the Scikit learn library, there are other libraries that do exactly the same thing but Scikit-learn is the easiest to use that I've found.