sklearn BallTree дает неожиданные результаты

Question

Что я делаю неправильно?

Я пытаюсь использовать BallTree от sklearn, чтобы создать похожие коллекции, а затем создать некоторые предложения по элементам, которые могут отсутствовать в данной коллекции.

import random 
from sklearn.neighbors import BallTree 
import numpy 

collections = [] # 10k sample collections of between 
        # 7 and 15 (of a possible 300...) items 

for sample in range(0, 10000): # build sample data 
    items = random.sample(range(1, 300), random.randint(7, 15)) 
    collections.append(items)  

darray = numpy.zeros((len(collections), max(map(len, collections)))) # 10k x 15 matrix 

for c_cnt, items in enumerate(collections): # populate matrix 
    for cnt, i in enumerate(sorted(items)): 
     darray[C_cnt][cnt] = i 

query = BallTree(darray).query(darray[0], k=15) 

nearest_neighbors = query[1][0] 

# test the results against the first item! 

all_sets = [set(darray[0]) & set(darray[item]) for item in nearest_neighbors] 
for item in all_sets: 
    print item # intersection of the neighbor 

Я получаю следующие результаты:

set([0.0, 130.0, 167.0, 290.0, 162.0, 144.0, 17.0, 214.0]) # Nearest neighbor is itself! Awesome! 
set([0.0]) # WTF? The second closest item shares only 1 item? 
set([0.0, 290.0]) 
set([0.0, 17.0]) 
set([0.0, 130.0]) 
set([0.0]) 
set([0.0]) 
set([0.0]) 
set([0.0]) 
set([0.0]) 
set([0.0]) 
set([0.0]) 
set([0.0, 162.0]) 
set([0.0, 144.0, 162.0]) # uhh okay, i would expect this to be higher up 
set([0.0, 144.0, 17.0]) 

Я наблюдаю, что выше предложенные элементы, как правило, имеют одинаковую длину ненулевых значений в качестве массива я пытающийся сравнить. Есть ли какая-то подготовка, которую я могу сделать с моими данными, чтобы исправить это?

Answer 1

По умолчанию BallTree вычисляет евклидово расстояние между вашими векторами и поэтому не подходит для типа вычислений, который вы имеете в виду.

В качестве простого примера, представьте, что вы имеете следующие два набора:

collections[0] = [1, 3] 
collections[1] = [1, 2, 3] 

При преобразовании их векторов в darray, как вы сделали выше, они стали это:

darray[0] = [1, 3, 0] 
darray[1] = [1, 2, 3] 

Евклидовое расстояние между ними не отражает количество похожих записей в наборе, поэтому результаты не то, что вы ожидали.

Вместо евклидова расстояния, метрика расстояния, которую вы ищете, вероятно, это Jaccard distance, которая измеряет сходство между множествами. BallTree реализует это для булевых представлений множеств; то есть, для приведенных выше данных векторы станут

darray[0] = [True, False, True] 
darray[1] = [True, True, True] 

где первая запись указывает, если 1 находится в наборе, вторая запись указывает на то, если 2 находится в наборе, и так далее. Это версия «однострунной кодировки».

Для данных образца вы предоставили, вы можете вычислить результаты таким образом:

import numpy as np 
from sklearn.neighbors import BallTree 
from sklearn.feature_extraction import DictVectorizer 

# for replicability 
np.random.seed(0) 

# Compute the collections using a more efficient method 
collections = [np.random.choice(300, replace=False, 
           size=np.random.randint(7, 15)) 
       for _ in range(10000)] 

# Use DictVectorizer to compute binary representation of collections 
dicts = [dict(zip(c, np.ones_like(c))) for c in collections] 
darray = DictVectorizer(sparse=False, dtype=bool).fit_transform(dicts) 

# Compute 15 nearest neighbors for the first collection 
dist, ind = BallTree(darray, metric='jaccard').query(darray[0], k=15) 
for i in ind[0]: 
    print(set(collections[0]) & set(collections[i])) 

я получаю следующие результаты:

{225, 226, 261, 166, 296, 52, 150, 246, 215, 221, 223} 
{52, 261, 221, 215} 
{225, 226, 166, 150} 
{223, 150, 215} 
{225, 261, 166, 221} 
{226, 261, 223} 
{261, 150, 221} 
{223, 52, 166, 215} 
{296, 226, 166, 223} 
{296, 221, 150} 
{223, 52, 215} 
{52, 261, 246} 
{296, 225, 52} 
{296, 225, 221} 
{225, 150, 223} 

Следует отметить, что сходство Jaccard это не просто размер пересечение, но этот размер нормализуется по размеру объединения. Размер одного пересечения не имеет свойств метрики расстояния и поэтому не может быть вычислен непосредственно с помощью BallTree.

Редактировать: Я должен добавить, что если у вас много записей в наборах, этот метод становится несостоятельным, потому что булева матрица кодирования становится слишком большой. Лучший способ вычислить очень многомерные поиски соседей с расстоянием Jaccard - это, вероятно, с помощью Locality Sensitive Hashing, хотя я не знаю простой в использовании реализации Python, подходящей для этой проблемы.