Scipy Negative Distance? ¿Qué?

Question

que tienen un archivo de entrada que contiene números de punto flotante a cabo el 4 decimales:

i.e. 13359 0.0000 0.0000 0.0001 0.0001 0.0002` 0.0003 0.0007 ... 

(el primero es el id). Mi clase usa el método loadVectorsFromFile que lo multiplica por 10000 y luego int() estos números. Además de eso, también recorro cada vector para asegurarme de que no haya valores negativos en el interior. Sin embargo, cuando realizo _hclustering, continuamente veo el error, "Linkage Z contains negative values".

serio que esto es un error, porque:

1. Revisé mis valores,
2. los valores son en ninguna parte lo suficientemente pequeño o lo suficientemente grande como para acercarse a los límites de los números de punto flotante y
3. la fórmula que usé para derivar los valores en el archivo usa valor absoluto (mi entrada es DEFINITIVAMENTE correcta).

¿Alguien me puede aclarar por qué estoy viendo este raro error? ¿Qué está pasando que está causando este error de distancia negativa?

=====

def loadVectorsFromFile(self, limit, loc, assertAllPositive=True, inflate=True): 
    """Inflate to prevent "negative" distance, we use 4 decimal points, so *10000 
    """ 
    vectors = {} 
    self.winfo("Each vector is set to have %d limit in length" % limit) 
    with open(loc) as inf: 
     for line in filter(None, inf.read().split('\n')): 
      l = line.split('\t') 
      if limit: 
       scores = map(float, l[1:limit+1]) 
      else: 
       scores = map(float, l[1:]) 

      if inflate:   
       vectors[ l[0]] = map(lambda x: int(x*10000), scores)  #int might save space 
      else: 
       vectors[ l[0]] = scores       

    if assertAllPositive: 
     #Assert that it has no negative value 
     for dirID, l in vectors.iteritems(): 
      if reduce(operator.or_, map(lambda x: x < 0, l)): 
       self.werror("Vector %s has negative values!" % dirID) 
    return vectors 

def main(self, inputDir, outputDir, limit=0, 
     inFname="data.vectors.all", mappingFname='all.id.features.group.intermediate'): 
    """ 
    Loads vector from a file and start clustering 
    INPUT 
     vectors is { featureID: tfidfVector (list), } 
    """ 
    IDFeatureDic = loadIdFeatureGroupDicFromIntermediate(pjoin(self.configDir, mappingFname)) 
    if not os.path.exists(outputDir): 
     os.makedirs(outputDir) 

    vectors = self.loadVectorsFromFile(limit, pjoin(inputDir, inFname)) 
    for threshold in map(lambda x:float(x)/30, range(20,30)): 
     clusters = self._hclustering(threshold, vectors) 
     if clusters: 
      outputLoc = pjoin(outputDir, "threshold.%s.result" % str(threshold)) 
      with open(outputLoc, 'w') as outf: 
       for clusterNo, cluster in clusters.iteritems(): 
        outf.write('%s\n' % str(clusterNo)) 
        for featureID in cluster: 
         feature, group = IDFeatureDic[featureID] 
         outline = "%s\t%s\n" % (feature, group) 
         outf.write(outline.encode('utf-8')) 
        outf.write("\n") 
     else: 
      continue 

def _hclustering(self, threshold, vectors): 
    """function which you should call to vary the threshold 
    vectors: { featureID: [ tfidf scores, tfidf score, .. ] 
    """ 
    clusters = defaultdict(list) 
    if len(vectors) > 1: 
     try: 
      results = hierarchy.fclusterdata(vectors.values(), threshold, metric='cosine') 
     except ValueError, e: 
      self.werror("_hclustering: %s" % str(e)) 
      return False 

     for i, featureID in enumerate(vectors.keys()): 

Answer 1

estoy bastante seguro de que esto se debe a que está utilizando la métrica del coseno al que está llamando fclusterdata. Pruebe usar euclidiano y vea si el error desaparece.

La métrica del coseno puede ser negativa si el producto escalar de dos vectores en su conjunto es mayor que 1. Dado que usa números muy grandes y los normaliza, estoy bastante seguro de que los productos de puntos son mayores que 1 a gran parte del tiempo en su conjunto de datos. Si desea utilizar la métrica de coseno, necesitará normalizar sus datos de modo que el producto escalar de dos vectores nunca sea mayor que 1. Consulte la fórmula en this page para ver qué se define en el indicador coseno en Scipy.

Editar:

Bueno, de mirar el código fuente creo que la fórmula que aparece en esa página no es realmente la fórmula que SciPy usos (lo cual es bueno porque el código fuente parece que es usando la fórmula de distancia de coseno normal y correcta). Sin embargo, para el momento en que crea el enlace, hay claramente algunos valores negativos en el enlace por la razón que sea. Intente encontrar la distancia entre sus vectores con scipy.spatial.distance.pdist() con method = 'cosine' y verifique si hay valores negativos. Si no hay ninguno, tiene que ver con cómo se forma el enlace utilizando los valores de distancia.

Answer 2

No soy capaz de mejorar la respuesta de Justin, pero otro punto a tener en cuenta es el manejo de datos.

Diga que hace algo como int(float("0.0003") * 10000) para leer los datos. Pero si lo hace, no obtendrá 3 sino 2.9999999999999996. Eso es porque las imprecisiones del punto flotante se multiplican.

Una mejor, o al menos más precisa. forma sería haciendo la multiplicación en la cadena. Es decir, usando la manipulación de cadena para obtener desde 0.0003 hasta 3.0 y así sucesivamente.

Tal vez incluso hay una extensión de tipo de datos Python en alguna parte que puede leer en este tipo de datos sin pérdida de precisión en la que puede realizar la multiplicación antes de la conversión. No estoy en casa en SciPy/numerics, así que no sé.

EDITAR

Justin comentó que hay una acumulación de tipo decimal en pitón. Y eso puede interpretar cadenas, multiplicar con enteros y convertir a float (lo probé). Siendo ese el caso, recomendaría actualizar su lógica como:

factor = 1 
if inflate: 
    factor = 10000 
scores = map(lambda x: float(decimal.Decimal(x) * factor), l[1:]) 

Eso reduciría un poco sus problemas de redondeo.

Answer 3

Esto se debe a la imprecisión de coma flotante, por lo que algunas distancias entre sus vectores, en lugar de ser 0, son por ejemplo -0.000000000000000002. Use la función scipy.clip() para corregir el problema. Si su matriz de distancia es dmatr, use numpy.clip(dmatr,0,1,dmatr) y debería estar bien.

Answer 4

"La conexión Z contiene valores negativos". Este error también se produce en el proceso de agrupamiento jerárquico scipy cuando a cualquier índice de clúster de vinculación en la matriz de vinculación se le asigna -1.

Según mis observaciones, cualquier índice de clúster de enlaces se asigna -1 durante los procesos de combinación, cuando la distancia entre todos los pares de clústeres o puntos para combinar, resulta ser menos infinito. Así que la función de vinculación combina clusters incluso si la distancia de enlace entre ellos es infinita. Y asignar uno de los cluster o índice negativo punto

Resumen Así que el punto es, si está utilizando cosine distance como métrica y si la norma o magnitud de cualquier punto de datos es cero, entonces este error se produce

Answer 5

Tuve el mismo problema. Lo que puedes hacer es reescribir la función del coseno. Por ejemplo:

from sklearn.metrics.pairwise import cosine_similarity 
def mycosine(x1, x2): 
    x1 = x1.reshape(1,-1) 
    x2 = x2.reshape(1,-1) 
    ans = 1 - cosine_similarity(x1, x2) 
    return max(ans[0][0], 0) 

...

clusters = hierarchy.fclusterdata(data, threshold, criterion='distance', metric=mycosine, method='average')