Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.lang.python > #78207 > unrolled thread

"Fuzzy" Counter?

Started byMiki Tebeka <miki.tebeka@gmail.com>
First post2014-09-23 05:34 -0700
Last post2014-09-26 09:20 -0700
Articles 15 — 9 participants

Back to article view | Back to comp.lang.python


Contents

  "Fuzzy" Counter? Miki Tebeka <miki.tebeka@gmail.com> - 2014-09-23 05:34 -0700
    Re: "Fuzzy" Counter? Peter Otten <__peter__@web.de> - 2014-09-23 15:36 +0200
      Re: "Fuzzy" Counter? Miki Tebeka <miki.tebeka@gmail.com> - 2014-09-23 21:57 -0700
        Re: "Fuzzy" Counter? random832@fastmail.us - 2014-09-26 13:57 -0400
    Re: "Fuzzy" Counter? Tim Chase <python.list@tim.thechases.com> - 2014-09-23 08:42 -0500
    Re: "Fuzzy" Counter? Rob Gaddi <rgaddi@technologyhighland.invalid> - 2014-09-23 09:32 -0700
      Re: "Fuzzy" Counter? Chris Angelico <rosuav@gmail.com> - 2014-09-24 02:41 +1000
      Re: "Fuzzy" Counter? Miki Tebeka <miki.tebeka@gmail.com> - 2014-09-23 22:01 -0700
        Re: "Fuzzy" Counter? Ian Kelly <ian.g.kelly@gmail.com> - 2014-09-24 08:56 -0600
          Re: "Fuzzy" Counter? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2014-09-26 16:45 +1000
          Re: "Fuzzy" Counter? Miki Tebeka <miki.tebeka@gmail.com> - 2014-09-26 01:23 -0700
        Re: "Fuzzy" Counter? Rob Gaddi <rgaddi@technologyhighland.invalid> - 2014-09-26 11:30 -0700
          Re: "Fuzzy" Counter? random832@fastmail.us - 2014-09-26 15:10 -0400
            Re: "Fuzzy" Counter? Rob Gaddi <rgaddi@technologyhighland.invalid> - 2014-09-26 12:36 -0700
      Re: "Fuzzy" Counter? Ethan Furman <ethan@stoneleaf.us> - 2014-09-26 09:20 -0700

#78207 — "Fuzzy" Counter?

FromMiki Tebeka <miki.tebeka@gmail.com>
Date2014-09-23 05:34 -0700
Subject"Fuzzy" Counter?
Message-ID<0d28ee82-2240-4f10-9db9-e966c0e62a13@googlegroups.com>
Greetings,

Before I start writing my own. Is there something like collections.Counter (fore frequencies) that does "fuzzy" matching?

Meaning x is considered equal to y if abs(x - y) < epsilon. (x, y and my case will be numpy.array).

Thanks,
--
Miki

[toc] | [next] | [standalone]


#78210

FromPeter Otten <__peter__@web.de>
Date2014-09-23 15:36 +0200
Message-ID<mailman.14259.1411479409.18130.python-list@python.org>
In reply to#78207
Miki Tebeka wrote:

> Before I start writing my own. Is there something like collections.Counter
> (fore frequencies) that does "fuzzy" matching?
> 
> Meaning x is considered equal to y if abs(x - y) < epsilon. (x, y and my
> case will be numpy.array).

The problem I see with that description is that for x, y, z, assumming 

x eq y 
y eq z
not (x eq z)

where eq is the test given above -- should x, y, and z land in the same bin?

I'm not really qualified here, but k-means clustering may be a direction to 
investigate:

<http://docs.scipy.org/doc/scipy/reference/generated/scipy.cluster.vq.kmeans.html>

[toc] | [prev] | [next] | [standalone]


#78265

FromMiki Tebeka <miki.tebeka@gmail.com>
Date2014-09-23 21:57 -0700
Message-ID<599ba7b9-1df3-44d4-bceb-fb477ae5cb10@googlegroups.com>
In reply to#78210
On Tuesday, September 23, 2014 4:37:10 PM UTC+3, Peter Otten wrote:
> x eq y 
> y eq z
> not (x eq z)
> 
> where eq is the test given above -- should x, y, and z land in the same bin?
Yeah, I know the counting depends on the order of items. But I'm OK with that.

[toc] | [prev] | [next] | [standalone]


#78386

Fromrandom832@fastmail.us
Date2014-09-26 13:57 -0400
Message-ID<mailman.14401.1411754254.18130.python-list@python.org>
In reply to#78265
On Wed, Sep 24, 2014, at 00:57, Miki Tebeka wrote:
> On Tuesday, September 23, 2014 4:37:10 PM UTC+3, Peter Otten wrote:
> > x eq y 
> > y eq z
> > not (x eq z)
> > 
> > where eq is the test given above -- should x, y, and z land in the same bin?
> Yeah, I know the counting depends on the order of items. But I'm OK with
> that.

It doesn't just depend on the order. If you put x and z in first
(creating two "bins"), then which one does y go in after?

[toc] | [prev] | [next] | [standalone]


#78211

FromTim Chase <python.list@tim.thechases.com>
Date2014-09-23 08:42 -0500
Message-ID<mailman.14260.1411480271.18130.python-list@python.org>
In reply to#78207
On 2014-09-23 05:34, Miki Tebeka wrote:
> Before I start writing my own. Is there something like
> collections.Counter (fore frequencies) that does "fuzzy" matching?
> 
> Meaning x is considered equal to y if abs(x - y) < epsilon. (x, y
> and my case will be numpy.array).

Not that I know of -- the performance characteristics would differ
radically from the O(1) expectations that Counter() gives you since
you'd have to compare your value against *every* value in the
container[*], and you have the possibility that two items in the
container are equidistant yet within EPSILON:

  EPSILON = 0.51
  my_counter[1.0] += 1
  my_counter[2.0] += 1
  my_counter[1.5] += 1  # which one should be incremented?

-tkc


[*]
This could be mitigated if you had some constraints on your inputs
and wanted to do some sort of bucket-hashing, limiting it to a subset
of the possible keys




[toc] | [prev] | [next] | [standalone]


#78223

FromRob Gaddi <rgaddi@technologyhighland.invalid>
Date2014-09-23 09:32 -0700
Message-ID<20140923093244.066bb10b@rg.highlandtechnology.com>
In reply to#78207
On Tue, 23 Sep 2014 05:34:19 -0700 (PDT)
Miki Tebeka <miki.tebeka@gmail.com> wrote:

> Greetings,
> 
> Before I start writing my own. Is there something like collections.Counter (fore frequencies) that does "fuzzy" matching?
> 
> Meaning x is considered equal to y if abs(x - y) < epsilon. (x, y and my case will be numpy.array).
> 
> Thanks,
> --
> Miki

You'll probably have to write that yourself.  While you're at it, think
long and hard about that definition of fuzziness.  If you can make it
closer to the concept of histogram "bins" you'll get much better
performance.  If, for instance, you can live with 1.anything being one
bin, and 2.anything being the next (even though this puts 1.999 and
2.000 into separate bins) then you can just floor() the number and use
the result as the key.

If you really need the continuous fuzziness you'll probably have to
keep the potential keys sorted and run a binary search against the list
of them to find the nearest.  This will still run you into some
problems based on ordering.  For instance, with an epsilon of 0.1,
you'd put 2.0 into a bin, then 1.9 into the same bin, then 2.1 into the
same bin.  If however you put 1.9 into that bin first, then 2.0 would
go into that bin, but 2.1 would go into a different one.

TL;DR you need to think very hard about your problem definition and
what you want to happen before you actually try to implement this.

-- 
Rob Gaddi, Highland Technology -- www.highlandtechnology.com
Email address domain is currently out of order.  See above to fix.

[toc] | [prev] | [next] | [standalone]


#78226

FromChris Angelico <rosuav@gmail.com>
Date2014-09-24 02:41 +1000
Message-ID<mailman.14273.1411490468.18130.python-list@python.org>
In reply to#78223
On Wed, Sep 24, 2014 at 2:32 AM, Rob Gaddi
<rgaddi@technologyhighland.invalid> wrote:
> You'll probably have to write that yourself.  While you're at it, think
> long and hard about that definition of fuzziness.  If you can make it
> closer to the concept of histogram "bins" you'll get much better
> performance.  If, for instance, you can live with 1.anything being one
> bin, and 2.anything being the next (even though this puts 1.999 and
> 2.000 into separate bins) then you can just floor() the number and use
> the result as the key.

Or even check three bins based on that - the floor(), floor()+1, and
floor()-1 bins. That way, you're not running into problems at any
boundaries, and you still limit the exponential growth of the
comparisons.

But it's still fundamentally problematic.

ChrisA

[toc] | [prev] | [next] | [standalone]


#78266

FromMiki Tebeka <miki.tebeka@gmail.com>
Date2014-09-23 22:01 -0700
Message-ID<1a63fb8d-e0b8-4385-acbc-ddb6bf1f0f7d@googlegroups.com>
In reply to#78223
On Tuesday, September 23, 2014 7:33:06 PM UTC+3, Rob Gaddi wrote:

> While you're at it, think
> long and hard about that definition of fuzziness.  If you can make it
> closer to the concept of histogram "bins" you'll get much better
> performance.  
The problem for me here is that I can't determine the number of bins in advance. I'd like to get frequencies. I guess every "new" (don't have any previous equal item) can be a bin.

> TL;DR you need to think very hard about your problem definition and
> what you want to happen before you actually try to implement this.
Always a good advice :) I'm actually implementing algorithm for someone else (in the bio world where I know very little about).

[toc] | [prev] | [next] | [standalone]


#78293

FromIan Kelly <ian.g.kelly@gmail.com>
Date2014-09-24 08:56 -0600
Message-ID<mailman.14318.1411570620.18130.python-list@python.org>
In reply to#78266
On Tue, Sep 23, 2014 at 11:01 PM, Miki Tebeka <miki.tebeka@gmail.com> wrote:
> On Tuesday, September 23, 2014 7:33:06 PM UTC+3, Rob Gaddi wrote:
>
>> While you're at it, think
>> long and hard about that definition of fuzziness.  If you can make it
>> closer to the concept of histogram "bins" you'll get much better
>> performance.
> The problem for me here is that I can't determine the number of bins in advance. I'd like to get frequencies. I guess every "new" (don't have any previous equal item) can be a bin.

Then your result depends on the order of your input, which is usually
not a good thing.

Why would you need to determine the *number* of bins in advance? You
just need to determine where they start and stop. If for example your
epsilon is 0.5, you could determine the bins to be at [-0.5, 0.5);
[0.5, 1.5); [1.5, 2.5); ad infinitum. Then for each actual value you
encounter, you could calculate the appropriate bin, creating it first
if it doesn't already exist.

[toc] | [prev] | [next] | [standalone]


#78359

FromSteven D'Aprano <steve+comp.lang.python@pearwood.info>
Date2014-09-26 16:45 +1000
Message-ID<54250b73$0$12983$c3e8da3$5496439d@news.astraweb.com>
In reply to#78293
Ian Kelly wrote:

> On Tue, Sep 23, 2014 at 11:01 PM, Miki Tebeka <miki.tebeka@gmail.com>
> wrote:
>> On Tuesday, September 23, 2014 7:33:06 PM UTC+3, Rob Gaddi wrote:
>>
>>> While you're at it, think
>>> long and hard about that definition of fuzziness.  If you can make it
>>> closer to the concept of histogram "bins" you'll get much better
>>> performance.
>> The problem for me here is that I can't determine the number of bins in
>> advance. I'd like to get frequencies. I guess every "new" (don't have any
>> previous equal item) can be a bin.
> 
> Then your result depends on the order of your input, which is usually
> not a good thing.
> 
> Why would you need to determine the *number* of bins in advance? You
> just need to determine where they start and stop. If for example your
> epsilon is 0.5, you could determine the bins to be at [-0.5, 0.5);
> [0.5, 1.5); [1.5, 2.5); ad infinitum. Then for each actual value you
> encounter, you could calculate the appropriate bin, creating it first
> if it doesn't already exist.

That has the unfortunate implication that:

0.500000001 and 1.499999999 (delta = 0.999999998)

are considered equal, but:

1.500000001 and 1.499999999 (delta = 0.000000002)

are considered unequal.



-- 
Steven

[toc] | [prev] | [next] | [standalone]


#78372

FromMiki Tebeka <miki.tebeka@gmail.com>
Date2014-09-26 01:23 -0700
Message-ID<a50acf2d-a80d-47ef-80cc-0a681a7b3428@googlegroups.com>
In reply to#78293
Greetings,

On Wednesday, September 24, 2014 5:57:15 PM UTC+3, Ian wrote:
> Then your result depends on the order of your input, which is usually
> not a good thing.
As stated in previous reply - I'm OK with that.

> Why would you need to determine the *number* of bins in advance? You
> just need to determine where they start and stop. If for example your
> epsilon is 0.5, you could determine the bins to be at [-0.5, 0.5);
> [0.5, 1.5); [1.5, 2.5); ad infinitum. Then for each actual value you
> encounter, you could calculate the appropriate bin, creating it first
> if it doesn't already exist.
I see what you mean. I thought you mean histogram like bins where you usually state the number of bins in advance.

[toc] | [prev] | [next] | [standalone]


#78388

FromRob Gaddi <rgaddi@technologyhighland.invalid>
Date2014-09-26 11:30 -0700
Message-ID<20140926113016.3f6a7628@rg.highlandtechnology.com>
In reply to#78266
On Tue, 23 Sep 2014 22:01:51 -0700 (PDT)
Miki Tebeka <miki.tebeka@gmail.com> wrote:

> On Tuesday, September 23, 2014 7:33:06 PM UTC+3, Rob Gaddi wrote:
> 
> > While you're at it, think
> > long and hard about that definition of fuzziness.  If you can make it
> > closer to the concept of histogram "bins" you'll get much better
> > performance.  
> The problem for me here is that I can't determine the number of bins in advance. I'd like to get frequencies. I guess every "new" (don't have any previous equal item) can be a bin.
> 
> > TL;DR you need to think very hard about your problem definition and
> > what you want to happen before you actually try to implement this.
> Always a good advice :) I'm actually implementing algorithm for someone else (in the bio world where I know very little about).

See, THERE's your problem.  You've got a scientist trying to make
prescriptions for an engineering problem.  He's given you a fuzzy
description of the sort of thing he's trying to do.  Your job is to
turn that fuzzy description into a concrete, actual algorithm
before you even write a single line of code, which means understanding
what the data is, and what the desired result of that data is.  Because
the thing you keep trying to do, with all of its order dependencies
fundamentally CANNOT be right, regardless of what the squishy scientist
tells you.

The "histogram" bin solution that everyone keeps trying to steer you
towards is almost certainly what you really want.  Epsilon is your
resolution.  You cannot resolve any information below your resolution
limit.  Yes, 1.49 and 1.51 wind up in different bins, whereas 1.51 and
2.49 are in the same one, but that's what it means to have a resolution
of 1; you can't say anything about whether any given count in the "2,
plus or minus a bit" bin is very nearly 1 or very nearly 3.

This doesn't require you to know the number of bins in advance, you can
just create and fill them as needed.  That said, you're trying to solve
a physical problem, and so it has physical limits.  Your biologist
should be able to give you an order of magnitude estimate of how many
"bins" you're expecting, and what the ultimate shape is expected to
look like.  Normally distributed?  Wildly bimodal?  Is the overall span
of data going to span 10 epsilon or 10,000 epsilon?  If there are going
to be a ton of bins, you may be better served by putting 1/3 of a count
into bins n-1, n, and n+1 rather than just in bin n; it's the
equivalent of squinting a bit when you look at the bins.

But you have to understand the problem to solve it.

-- 
Rob Gaddi, Highland Technology -- www.highlandtechnology.com
Email address domain is currently out of order.  See above to fix.

[toc] | [prev] | [next] | [standalone]


#78390

Fromrandom832@fastmail.us
Date2014-09-26 15:10 -0400
Message-ID<mailman.14404.1411758648.18130.python-list@python.org>
In reply to#78388
On Fri, Sep 26, 2014, at 14:30, Rob Gaddi wrote:
> The "histogram" bin solution that everyone keeps trying to steer you
> towards is almost certainly what you really want.  Epsilon is your
> resolution.  You cannot resolve any information below your resolution
> limit.  Yes, 1.49 and 1.51 wind up in different bins, whereas 1.51 and
> 2.49 are in the same one, but that's what it means to have a resolution
> of 1; you can't say anything about whether any given count in the "2,
> plus or minus a bit" bin is very nearly 1 or very nearly 3.

You could "antialias" the values, though. 1.49 results in a value that
is 51% in the "1" bin, and 49% in the "2" bin. count[1] += 0.51,
count[2] += 0.49. You could even spread each value across a larger
number of smaller bins.

[toc] | [prev] | [next] | [standalone]


#78391

FromRob Gaddi <rgaddi@technologyhighland.invalid>
Date2014-09-26 12:36 -0700
Message-ID<20140926123646.57aa9288@rg.highlandtechnology.com>
In reply to#78390
On Fri, 26 Sep 2014 15:10:43 -0400
random832@fastmail.us wrote:

> On Fri, Sep 26, 2014, at 14:30, Rob Gaddi wrote:
> > The "histogram" bin solution that everyone keeps trying to steer you
> > towards is almost certainly what you really want.  Epsilon is your
> > resolution.  You cannot resolve any information below your resolution
> > limit.  Yes, 1.49 and 1.51 wind up in different bins, whereas 1.51 and
> > 2.49 are in the same one, but that's what it means to have a resolution
> > of 1; you can't say anything about whether any given count in the "2,
> > plus or minus a bit" bin is very nearly 1 or very nearly 3.
> 
> You could "antialias" the values, though. 1.49 results in a value that
> is 51% in the "1" bin, and 49% in the "2" bin. count[1] += 0.51,
> count[2] += 0.49. You could even spread each value across a larger
> number of smaller bins.

Right, but there's still that stateless determination of which bin (or
bins) 1.49 goes in.  The history of the bins is irrelevant, which is
the important part.

-- 
Rob Gaddi, Highland Technology -- www.highlandtechnology.com
Email address domain is currently out of order.  See above to fix.

[toc] | [prev] | [next] | [standalone]


#78384

FromEthan Furman <ethan@stoneleaf.us>
Date2014-09-26 09:20 -0700
Message-ID<mailman.14399.1411748416.18130.python-list@python.org>
In reply to#78223
On 09/23/2014 09:32 AM, Rob Gaddi wrote:
> On Tue, 23 Sep 2014 05:34:19 -0700 (PDT) Miki Tebeka wrote:
>>
>> Before I start writing my own. Is there something like collections.Counter (fore frequencies) that does "fuzzy" matching?
>>
>> Meaning x is considered equal to y if abs(x - y) < epsilon. (x, y and my case will be numpy.array).
>
> You'll probably have to write that yourself.  While you're at it, think
> long and hard about that definition of fuzziness.  If you can make it
> closer to the concept of histogram "bins" you'll get much better
> performance.

You might want to take a look at the reference implementation for PEP 455 [1].  If you can decide on a method to 
transform your keys (such as taking the floor, or the half, or something like that), then that should work as is.

--
~Ethan~


[1] http://legacy.python.org/dev/peps/pep-0455/

[toc] | [prev] | [standalone]


Back to top | Article view | comp.lang.python


csiph-web