1
$\begingroup$

I have an interesting real world problem that can be abstracted and decomposed into a pattern recognition problem - specifically, recognising "known configurations" from within a 2D plane.

The problem can be described as follows:

  1. Given an MxN matrix (see image on left in the figure below)
  2. Given that each cell in the MxN matrix above contains one or more tuples
  3. A tuple consists of: i. A non zero integer variable ii. A categorical variable
  4. There are known, labelled configurations of cells (i.e. patterns) (see image on right in the figure below).

My question is, given all of the above, which would be the most appropriate machine learning algorithm to identify and extract patterns from a given MxN matrix?

The picture below provides a visual representation of the problem:

MxN matrix patterns

Note1: It is required that a pattern should be "recognised" regardless of where it is located within the grid.

Note2: In practice, patterns could "overlap" and a cell could hold tuples relating to different patterns. The algorithm needs to be able to discriminate between patterns - even in cases of "overlap" such as that described.

$\endgroup$
8
  • 1
    $\begingroup$ If the patterns are known, why not just scan for these? Throw the counts in a vector and apply further methods as appropriate? $\endgroup$
    – spdrnl
    Feb 9, 2017 at 17:01
  • $\begingroup$ @spdrnl Good idea (intuitively, that's the most 'obvious' thing to do) - but how do I "just scan" for the patterns? Care to elaborate? $\endgroup$ Feb 9, 2017 at 18:52
  • $\begingroup$ Like the answer below, it is basically a convolution. Lets say a filter fits in a k * l square. Then one would slide such a square from left to right and top till bottom, and check conformance to a pattern. This is also t the basis of deep learning conv nets. In your case it could be a set of if then statement instead of a numerical filter. $\endgroup$
    – spdrnl
    Feb 9, 2017 at 19:25
  • $\begingroup$ I meant to say: ... lets say a pattern fits in a ... $\endgroup$
    – spdrnl
    Feb 9, 2017 at 22:19
  • $\begingroup$ @spdrnl If I may be so bold as to prod you further; I'd be really grateful if you could put your response into an answer (ideally, with some pseudocode thrown in to further explain the concept). Intuitively, this is closest to what I know I'm doing when I eyeball the grid - but (although I'm a programmer), I lack the ML/statistical know how. Thanks $\endgroup$ Feb 10, 2017 at 0:32

2 Answers 2

2
$\begingroup$

Following up on the comments, this is more a general CS approach than an ML approach. It might not be what you want, since the suggestion is really trivial.

Given an MxN matrix and a known pattern that fits in a x b subsection, one can scan for the presence of that pattern as follows:

counts = np.zeros(len(patterns))
for index, pattern in enumerate(patterns):
    for i in range(M-a):
        for j in range(N-b):
            subsection = matrix[i+a, j+b]
            if matches(subsection, pattern): counts[index] += 1

Now use any algorithm to the set of counts vectors (clustering, knn, etc.)

$\endgroup$
3
  • $\begingroup$ Fantastic! this is very intuitive - and kind of what I was wanting to do, but not quite able to articulate it. Now, rather than "roll my own" matching algorithm, are there any well known algorithms for comparing two equal sized (axb) matrices containing a predefined pattern?. It would be great if there was a greplike language for matching 2D spatial patterns. $\endgroup$ Feb 11, 2017 at 11:07
  • $\begingroup$ Actually, I just came up with a way to use grep for the pattern matching - but I'll wait to hear from you first. Perhaps there is a more established way of doing it. $\endgroup$ Feb 11, 2017 at 11:18
  • $\begingroup$ Matching arrays is just tedious work I guess. Depending on the values in the matrices one could create a summary of values in a matrix to make a quick check if a fit is likely at all. i.e. if a pattern requires a 5.0 and that value does not occur in a matrix, then a scan is useless. $\endgroup$
    – spdrnl
    Feb 12, 2017 at 14:41
0
$\begingroup$

In Computer Vision exists something that is called convolution with a filter. See https://en.wikipedia.org/wiki/Kernel_(image_processing). For a single tuple per cell that gives you the pattern search algorithm that you need. Further you could adapt it to the case where more tuples are present inside a cell.

$\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.