Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #78207 > unrolled thread
| Started by | Miki Tebeka <miki.tebeka@gmail.com> |
|---|---|
| First post | 2014-09-23 05:34 -0700 |
| Last post | 2014-09-26 09:20 -0700 |
| Articles | 15 — 9 participants |
Back to article view | Back to comp.lang.python
"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
| From | Miki Tebeka <miki.tebeka@gmail.com> |
|---|---|
| Date | 2014-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]
| From | Peter Otten <__peter__@web.de> |
|---|---|
| Date | 2014-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]
| From | Miki Tebeka <miki.tebeka@gmail.com> |
|---|---|
| Date | 2014-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]
| From | random832@fastmail.us |
|---|---|
| Date | 2014-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]
| From | Tim Chase <python.list@tim.thechases.com> |
|---|---|
| Date | 2014-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]
| From | Rob Gaddi <rgaddi@technologyhighland.invalid> |
|---|---|
| Date | 2014-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]
| From | Chris Angelico <rosuav@gmail.com> |
|---|---|
| Date | 2014-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]
| From | Miki Tebeka <miki.tebeka@gmail.com> |
|---|---|
| Date | 2014-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]
| From | Ian Kelly <ian.g.kelly@gmail.com> |
|---|---|
| Date | 2014-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]
| From | Steven D'Aprano <steve+comp.lang.python@pearwood.info> |
|---|---|
| Date | 2014-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]
| From | Miki Tebeka <miki.tebeka@gmail.com> |
|---|---|
| Date | 2014-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]
| From | Rob Gaddi <rgaddi@technologyhighland.invalid> |
|---|---|
| Date | 2014-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]
| From | random832@fastmail.us |
|---|---|
| Date | 2014-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]
| From | Rob Gaddi <rgaddi@technologyhighland.invalid> |
|---|---|
| Date | 2014-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]
| From | Ethan Furman <ethan@stoneleaf.us> |
|---|---|
| Date | 2014-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