# Which 1D graphical pattern recognition algorithm can I use to find similar, fuzzy patterns?

I have data in form of a grayscale bitmaps. The x axis represents different instances and the y axis represents time. For example each pixel's gray value could represent the number of bytes transferred during one second by a computer (and every column in this bitmap is a different computer). Now I want to identify all columns, which have similar patterns and see what these patterns look like.

The patterns...

• are not previously known
• will have very different starting points in time/are shifted
• are not exactly the same (data points of a pattern might have slightly different distances or values)
• are covered by noise
• might occur multiple times in one dataset (most likely different patterns)

This is an example bitmap with 255 (white) meaning "no bytes transferred" and 0 (black) meaning "many bytes transferred". The x axis represents different data sets and the y axis is time:

The real datasets are thousands of pixels long.

I was thinking about using FFTs to identify certain frequency patterns, but believe there could be easier approaches which also can help sort patterns by similarity.

If possible I appreciate answers pointing me to python implementations covering my requirements.

• Welcome to CV. You may not get an answer specific to Python as this is not intended to be a site for addressing specific software questions. Jan 14, 2016 at 14:32
• @DJohnson Thank you, I am aware of this, which is why I said "if possible I appreciate" Jan 14, 2016 at 14:40

In my opinion, FFT wouldn't be an appropriate approach for analyzing the asynchronous, irregular data you've described since FFT is intended to capture sinusoidal-like regularities.

There is an approach that might work and for which R modules are available. Translation into Python would be entirely possible. I'm referring to Andreas Brandmaier's Permutation Distribution Clustering (PDC). Brandmaier describes his method as follows:

Permutation Distribution Clustering is a clustering method for time series. Dissimilarity of time series is formalized as the divergence between their permutation distributions. The permutation distribution was proposed as measure of the complexity of a time series.

Here's a link describing the R modules:

https://cran.r-project.org/web/packages/pdc/pdc.pdf

The CRAN modules are here:

https://cran.r-project.org/web/packages/pdc/index.html