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$
  • 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 '17 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$ – Homunculus Reticulli Feb 9 '17 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 '17 at 19:25
  • $\begingroup$ I meant to say: ... lets say a pattern fits in a ... $\endgroup$ – spdrnl Feb 9 '17 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$ – Homunculus Reticulli Feb 10 '17 at 0:32
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.)

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Homunculus Reticulli Feb 11 '17 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$ – Homunculus Reticulli Feb 11 '17 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 '17 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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.