Re: help in algorithm

2005-08-11 Thread Bill Mill
On 10 Aug 2005 12:46:08 -0700, gene tani <[EMAIL PROTECTED]> wrote:
> this sounds like LSI / singular value decomposition (?)

Why do you think so? I don't see it, but you might see something I
don't. LSI can be used to cluster things, but I see no reason to
believe that he's using LSI for his clustering.

I ask because I've done some LSI [1], and could help him out with that
if he is doing it.

While I'm on the subject, is there any general interest in my python LSI code?

[1] http://llimllib.f2o.org/files/lsi_paper.pdf

Peace
Bill Mill
-- 
http://mail.python.org/mailman/listinfo/python-list


Re: help in algorithm

2005-08-11 Thread Paolino
Bengt Richter wrote:
> On Wed, 10 Aug 2005 16:51:55 +0200, Paolino <[EMAIL PROTECTED]> wrote:
> 
> 
>>I have  a self organizing net which aim is clustering words.
>>Let's think the clustering is about their 2-grams set.
>>Words then are instances of this class.
>>
>>class clusterable(str):
>>  def __abs__(self):# the set of q-grams (to be calculated only once)
>>return set([(self+self[0])[n:n+2] for n in range(len(self))])
>>  def __sub__(self,other): # the q-grams distance between 2 words
>>set1=abs(self)
>>set2=abs(other)
>>return len(set1|set2)-len(set1&set2)
>>
>>I'm looking  for the medium  of a set of words, as the word  which 
>>minimizes the sum of the distances from those words.
>>
>>Aka:sum([medium-word for word in words])
>>
>>
>>Thanks for ideas, Paolino
>>
> 
> Just wondering if this is a desired result:
> 
>  >>> clusterable('banana')-clusterable('bananana')
>  0

Yes, the clustering is the main filter,it's good (I hope) to cut the 
space of words down one or two magnitudes.
Final choices must be done with the expensive Levenstain distance, or 
other edit-type distance.

Now I'm using an empirical solution where I suppose the best set has 
lenght L equal the medium of the lenghts.Then I choose from the 
frequency distribution of 2-grams the first L 2-grams.

I have no clue this is the right set and I'm sure that set is not a word 
as there is no chance to chain those 2-grams to form a word.

Thanks for comments

Paolino
-- 
http://mail.python.org/mailman/listinfo/python-list


Re: help in algorithm

2005-08-11 Thread Bengt Richter
On Wed, 10 Aug 2005 16:51:55 +0200, Paolino <[EMAIL PROTECTED]> wrote:

>I have  a self organizing net which aim is clustering words.
>Let's think the clustering is about their 2-grams set.
>Words then are instances of this class.
>
>class clusterable(str):
>   def __abs__(self):# the set of q-grams (to be calculated only once)
> return set([(self+self[0])[n:n+2] for n in range(len(self))])
>   def __sub__(self,other): # the q-grams distance between 2 words
> set1=abs(self)
> set2=abs(other)
> return len(set1|set2)-len(set1&set2)
>
>I'm looking  for the medium  of a set of words, as the word  which 
>minimizes the sum of the distances from those words.
>
>Aka:sum([medium-word for word in words])
>
>
>Thanks for ideas, Paolino
>
Just wondering if this is a desired result:

 >>> clusterable('banana')-clusterable('bananana')
 0

i.e., resulting from

 >>> abs(clusterable('banana'))-abs(clusterable('bananana'))
 set([])
 >>> abs(clusterable('banana'))
 set(['na', 'ab', 'ba', 'an'])
 >>> abs(clusterable('bananana'))
 set(['na', 'ab', 'ba', 'an'])

Regards,
Bengt Richter
-- 
http://mail.python.org/mailman/listinfo/python-list


Re: help in algorithm

2005-08-11 Thread Tom Anderson
On Wed, 10 Aug 2005, Paolino wrote:

> I have a self organizing net which aim is clustering words. Let's think 
> the clustering is about their 2-grams set. Words then are instances of 
> this class.
>
> class clusterable(str):
>  def __abs__(self):# the set of q-grams (to be calculated only once)
>return set([(self+self[0])[n:n+2] for n in range(len(self))])
>  def __sub__(self,other): # the q-grams distance between 2 words
>set1=abs(self)
>set2=abs(other)
>return len(set1|set2)-len(set1&set2)

Firstly:

- What do you mean by "to be calculated only once"? The code in __abs__ 
will run every time anyone calls abs() on the object. Do you mean that 
clients should avoid calling abs more than once? If so, how about 
memoising the function, or computing the 2-gram set up front, so clients 
don't need to worry about it?

- Could i suggest frozenset instead of set, since the 2-gram set of a 
string can't change?

- How about making the last line "return len(set1 ^ set2)"?

> I'm looking for the medium of a set of words, as the word which 
> minimizes the sum of the distances from those words.

I think i understand. Does the word have to be drawn from the set of words 
you're looking at? You can do that straightforwardly like this:

def distance(w, ws):
return sum([w - x for x in ws])

def medium(ws):
return min([(distance(w, ws), w) for w in ws])[1]

However, this is not terribly efficient - it's O(N**2) if you're counting 
calls to __sub__.

If you want a more efficient algorithm, well, that's tricky. Luckily, i am 
one of the most brilliant hackers alive, so here is an O(N) solution:



def distance_(w, counts, h, n):
"Returns the total distance from the word to the words in the set; the 
set is specified by its digram counts, horizon and size."
return h + sum([(n - (2 * counts[digram])) for digram in abs(w)])

def horizon(counts):
return sum(counts.itervalues())

def countdigrams(ws):
"Returns a map from digram to the number of words in which that digram 
appears."
counts = {}
for w in ws:
for digram in abs(w):
counts[digram] = counts.get(digram, 0) + 1
return counts

def distance(w, ws):
"Returns the total distance from the word to the words in the set."
counts = countdigrams(ws)
return distance_(w, counts, horizon(counts), len(ws))

def medium(ws):
"Returns the word in the set with the least total distance to the other 
words."
counts = countdigrams(ws)
h = horizon(counts)
n = len(ws)
return min([(distance_(w, counts, h, n), w) for w in ws])[1]



Note that this code calls abs a lot, so you'll want to memoise it. Also, 
all of those list comprehensions could be replaced by generator 
expressions, which would probably be faster - they certainly wouldn't 
allocate as much memory; i'm on 2.3 at the moment, so i don't have 
genexps.

I am ashamed to admit that i don't really understand how this code works. 
I had a flash of insight into how the problem could be solved, wrote the 
skeleton, then set to the details; by the time i'd finished with the 
details, i'd forgotten the fundamental idea! I think it's something like 
using the counts to represent the ensemble properties of the population of 
words, which means measuring the total distance for each word is O(1).

> Aka:sum([medium-word for word in words])

I have no idea what you're trying to do here!

tom

-- 
I sometimes think that the IETF is one of the crown jewels in all of 
western civilization. -- Tim O'Reilly
-- 
http://mail.python.org/mailman/listinfo/python-list


Re: help in algorithm

2005-08-10 Thread gene tani
this sounds like LSI / singular value decomposition (?)

http://javelina.cet.middlebury.edu/lsa/out/lsa_explanation.htm

-- 
http://mail.python.org/mailman/listinfo/python-list


help in algorithm

2005-08-10 Thread Paolino
I have  a self organizing net which aim is clustering words.
Let's think the clustering is about their 2-grams set.
Words then are instances of this class.

class clusterable(str):
   def __abs__(self):# the set of q-grams (to be calculated only once)
 return set([(self+self[0])[n:n+2] for n in range(len(self))])
   def __sub__(self,other): # the q-grams distance between 2 words
 set1=abs(self)
 set2=abs(other)
 return len(set1|set2)-len(set1&set2)

I'm looking  for the medium  of a set of words, as the word  which 
minimizes the sum of the distances from those words.

Aka:sum([medium-word for word in words])


Thanks for ideas, Paolino







___ 
Yahoo! Mail: gratis 1GB per i messaggi e allegati da 10MB 
http://mail.yahoo.it
-- 
http://mail.python.org/mailman/listinfo/python-list