sampling items from a nested list

[Steven Bethard]

So, I have a list of lists, where the items in each sublist are of
basically the same form. It looks something like:

py> data = [[('a', 0),
.... ('b', 1),
.... ('c', 2)],
....
.... [('d', 2),
.... ('e', 0)],
....
.... [('f', 0),
.... ('g', 2),
.... ('h', 1),
.... ('i', 0),
.... ('j', 0)]]

Now, I'd like to sample down the number of items in each sublist in the
following manner. I need to count the occurrences of each 'label' (the
second item in each tuple) in all the items of all the sublists, and
randomly remove some items until the number of occurrences of each
'label' is equal. So, given the data above, one possible resampling
would be:

[[('b', 1),
('c', 2)],

[('e', 0)],

[('g', 2),
('h', 1),
('i', 0)]]

Note that there are now only 2 examples of each label. I have code that
does this, but it's a little complicated:

py> import random
py> def resample(data):
.... # determine which indices are associated with each label
.... label_indices = {}
.... for i, group in enumerate(data) :
.... for j, (item, label) in enumerate(group ):
.... label_indices.s etdefault(label , []).append((i, j))
.... # sample each set of indices down
.... min_count = min(len(indices )
.... for indices in label_indices.i tervalues())
.... for label, indices in label_indices.i teritems():
.... label_indices[label] = random.sample(i ndices, min_count)
.... # return the resampled data
.... return [[(item, label)
.... for j, (item, label) in enumerate(group )
.... if (i, j) in label_indices[label]]
.... for i, group in enumerate(data)]
....
py>
py> resample(data)
[[('b', 1), ('c', 2)], [('d', 2), ('e', 0)], [('h', 1), ('i', 0)]]
py> resample(data)
[[('b', 1), ('c', 2)], [('d', 2)], [('f', 0), ('h', 1), ('j', 0)]]

Can anyone see a simpler way of doing this?

Steve

[Michael Spencer]

Re: sampling items from a nested list

Steven Bethard wrote:[color=blue]
> So, I have a list of lists, where the items in each sublist are of
> basically the same form. It looks something like:
>[/color]
....[color=blue]
>
> Can anyone see a simpler way of doing this?
>
> Steve[/color]

You just make these up to keep us amused, don't you? ;-)

If you don't need to preserve the ordering, would the following work?:
[color=blue][color=green][color=darkred]
>>> data = [[('a', 0),[/color][/color][/color]
... ('b', 1),
... ('c', 2)],
...
... [('d', 2),
... ('e', 0)],
...
... [('f', 0),
... ('g', 2),
... ('h', 1),
... ('i', 0),
... ('j', 0)]]
...[color=blue][color=green][color=darkred]
>>> def resample2(data) :[/color][/color][/color]
... bag = {}
... random.shuffle( data)
... return [[(item, label)
... for item, label in group
... if bag.setdefault( label,[]).append(item)
... or len(bag[label]) < 3]
... for group in data if not random.shuffle( group)]
...[color=blue][color=green][color=darkred]
>>> resample2(data)[/color][/color][/color]
[[('a', 0), ('c', 2), ('b', 1)], [('h', 1), ('g', 2), ('i', 0)], []][color=blue][color=green][color=darkred]
>>> resample2(data)[/color][/color][/color]
[[('h', 1), ('f', 0), ('j', 0), ('g', 2)], [('b', 1), ('c', 2)], []][color=blue][color=green][color=darkred]
>>> resample2(data)[/color][/color][/color]
[[('e', 0), ('d', 2)], [('i', 0), ('h', 1), ('g', 2)], [('b', 1)]][color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

Michael

[Steven Bethard]

Re: sampling items from a nested list

Michael Spencer wrote:[color=blue]
> Steven Bethard wrote:
>[color=green]
>> So, I have a list of lists, where the items in each sublist are of
>> basically the same form. It looks something like:
>>[/color]
> ...[color=green]
>>
>> Can anyone see a simpler way of doing this?
>>
>> Steve[/color]
>
> You just make these up to keep us amused, don't you? ;-)[/color]

Heh heh. I wish. It's actually about resampling data read in the
Yamcha data format:

http://chasen.org/~taku/software/yamcha/

So each sublist is a "sentence" and each tuple is the feature vector for
a "word". The point is to even out the number of positive and negative
examples because support vector machines typically work better with
balanced data sets.
[color=blue]
> If you don't need to preserve the ordering, would the following work?:
>[/color]
[snip][color=blue]
>[color=green][color=darkred]
> >>> def resample2(data) :[/color][/color]
> ... bag = {}
> ... random.shuffle( data)
> ... return [[(item, label)
> ... for item, label in group
> ... if bag.setdefault( label,[]).append(item)
> ... or len(bag[label]) < 3]
> ... for group in data if not
> random.shuffle( group)][/color]

It would be preferable to preserve ordering, but it's not absolutely
crucial. Thanks for the suggestion!

STeVe

[Michael Spencer]

Re: sampling items from a nested list

Michael Spencer wrote:
[color=blue][color=green][color=darkred]
> >>> def resample2(data) :[/color][/color]
> ... bag = {}
> ... random.shuffle( data)
> ... return [[(item, label)
> ... for item, label in group
> ... if bag.setdefault( label,[]).append(item)
> ... or len(bag[label]) < 3]
> ... for group in data if not[/color]

....which failed to calculate the minimum count of labels, try this instead
(while I was at it, I removed the insance LC)
[color=blue][color=green][color=darkred]
>>> def resample3(data) :[/color][/color][/color]
... bag = {}
... sample = []
... labels = [label for group in data for item, label in group]
... min_count = min(labels.coun t(label) for label in set(labels))
... random.shuffle( data)
... for subgroup in data:
... random.shuffle( subgroup)
... subgroupsample = []
... for item, label in subgroup:
... bag.setdefault( label,[]).append(item)
... if len(bag[label]) <= min_count:
... subgroupsample. append((item,la bel))
... sample.append(s ubgroupsample)
... return sample
...[color=blue][color=green][color=darkred]
>>>[/color][/color][/color]

Cheers

Michael

[Michael Spencer]

Re: sampling items from a nested list

Steven Bethard wrote:[color=blue]
> Michael Spencer wrote:
>[color=green]
>> Steven Bethard wrote:
>>[color=darkred]
>>> So, I have a list of lists, where the items in each sublist are of
>>> basically the same form. It looks something like:
>>>[/color]
>> ...
>>[color=darkred]
>>>
>>> Can anyone see a simpler way of doing this?
>>>
>>> Steve[/color]
>>
>>
>> You just make these up to keep us amused, don't you? ;-)[/color]
>
>
> Heh heh. I wish. It's actually about resampling data read in the
> Yamcha data format:
>
> http://chasen.org/~taku/software/yamcha/
>
> So each sublist is a "sentence" and each tuple is the feature vector for
> a "word". The point is to even out the number of positive and negative
> examples because support vector machines typically work better with
> balanced data sets.
>[color=green]
>> If you don't need to preserve the ordering, would the following work?:
>>[/color]
> [snip]
>[color=green]
>>[color=darkred]
>> >>> def resample2(data) :[/color]
>> ... bag = {}
>> ... random.shuffle( data)
>> ... return [[(item, label)
>> ... for item, label in group
>> ... if bag.setdefault( label,[]).append(item)
>> ... or len(bag[label]) < 3]
>> ... for group in data if not
>> random.shuffle( group)][/color]
>
>
> It would be preferable to preserve ordering, but it's not absolutely
> crucial. Thanks for the suggestion!
>
> STeVe[/color]
Maybe combine this with a DSU pattern? Not sure whether the result would be
better than what you started with

Michael

[Felix Wiemann]

Re: sampling items from a nested list

Steven Bethard wrote:
[color=blue]
> py> data = [[('a', 0),
> ... ('b', 1),
> ... ('c', 2)],
> ...
> ... [('d', 2),
> ... ('e', 0)],
> ...
> ... [('f', 0),
> ... ('g', 2),
> ... ('h', 1),
> ... ('i', 0),
> ... ('j', 0)]]
>
> I need to count the occurrences of each 'label' (the second item in
> each tuple) in all the items of all the sublists, and randomly remove
> some items until the number of occurrences of each 'label' is equal.[/color]

If the tuples are "heavier" than this, you can avoid comparing them
using the following algorithm (which probably still leaves some room for
optimization, e.g. simpler return_list building [or returning a
generator instead of a list], or directly building the sample set
instead of converting a random.sample to a set):

def resample(data):
counts = {}
for i in data:
for j in i:
counts[j[1]] = counts.setdefau lt(j[1], 0) + 1

min_count = min(counts.iter values())

# Same keys, so we can reuse the counts dictionary.
indices = counts
for label, count in counts.iteritem s():
indices[label] = set(random.samp le(xrange(count ), min_count))

# Same thing with a generator expression, building a new dict (dunno
# what's faster).
#indices = dict(((label, set(random.samp le(xrange(count ), min_count)))
# for label, count in counts.iteritem s()))

# "done" maps labels to the number of tuples (with that label) which
# have been added to return_list.
done = {}
return_list = []
for i in data:
return_list.app end([])
for j in i:
if done.setdefault (j[1], 0) in indices[j[1]]:
return_list[-1].append(j)
done[j[1]] += 1
return return_list

--
Felix Wiemann -- http://www.ososo.de/