Кластеризация с пользовательской метрикой расстояния в склеарне - PullRequest
Новая
       20

Кластеризация с пользовательской метрикой расстояния в склеарне

0 голосов
/ 20 сентября 2019

Я пытаюсь реализовать пользовательскую метрику расстояния для кластеризации.Фрагмент кода выглядит следующим образом: 

import numpy as np
from sklearn.cluster import KMeans, DBSCAN, MeanShift

def distance(x, y):
    # print(x, y) -> This x and y aren't one-hot vectors and is the source of this question
    match_count = 0.
    for xi, yi in zip(x, y):
        if float(xi) == 1. and xi == yi:
            match_count += 1
    return match_count

def custom_metric(x, y):
    # x, y are two vectors
    # distance(.,.) calculates count of elements when both xi and yi are True
    return distance(x, y)


vectorized_text = np.stack([[1, 0, 0, 1] * 100,
                            [1, 1, 1, 0] * 100,
                            [0, 1, 1, 0] * 100,
                            [0, 0, 0, 1] * 100] * 100)

dbscan = DBSCAN(min_samples=2, metric=custom_metric, eps=3, p=1).fit(vectorized_text)

* vectorized_text - это матрица функций с кодированием в одну горячую строку размером n_sample x n_features.Но когда вызывается custom_metric, один из x или y оказывается реальным вектором, а другой остается горячим вектором.Как и ожидалось, и x, и y должны были быть одним горячим вектором.Это приводит к тому, что custom_metric возвращает неправильные результаты во время выполнения и, следовательно, кластеризация не так правильна.

Пример x и y в distance(x, y) методе: 

x = [0.5 0.5 0.5 ... 0.5 0.5]
y = [0. 0. 0. 1. 0. 0. ... 1. 0.]

Оба должны были быть горячими векторами.

У кого-нибудь есть идеи по поводу этой ситуации?

Ответы [ 3 ]

1 голос
/ 21 сентября 2019

Прежде всего, ваше расстояние неверно.

Расстояния должны возвращать значения small для похожих векторов.Вы определили сходство , а не расстояние.

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

Это, ваше расстояние, вероятно, должно выглядеть так: 

def distance(x, y):
  return x.shape[0] - np.dot(x,y)

ИлиКакую бы дистанцию ​​ трансформацию вы намеревались использовать.

Теперь для вашей реальной проблемы: я предполагаю, что sklearn пытается ускорить ваше расстояние с помощью дерева шаров.Это не сильно поможет из-за плохой производительности обратных вызовов интерпретатора Python (на самом деле, вы, вероятно, должны предварительно вычислить всю матрицу расстояний в одной векторизованной операции - что-то вроде dist = dim - X.transpose().dot(X)?из уравнения).Другие языки, такие как Java (например, инструмент ELKI), гораздо лучше расширить таким образом, потому что JIT-компилятор горячей точки может оптимизировать и встраивать такие вызовы везде.

Чтобы проверить гипотезу о том, что sklearn ball-дерево является причиной для нечетных значений, которые вы наблюдаете, попробуйте установить method="brute" или около того (см. документацию), чтобы отключить дерево шаров.Но в конце вы захотите либо предварительно вычислить всю матрицу расстояний (если вы можете позволить себе затраты O (n²)), либо перейти на другой язык программирования (например, реализация расстояния в Cython помогает, но вы все равноскорее всего, данные внезапно станут массивами с плавающей точкой).

1 голос
/ 20 сентября 2019

Я не получу ваш вопрос, если у меня есть: 

x = [1, 0, 1]
y = [0, 0, 1]

и я использую: 

def distance(x, y):
    # print(x, y) -> This x and y aren't one-hot vectors and is the source of this question
    match_count = 0.
    for xi, yi in zip(x, y):
        if float(xi) == 1. and xi == yi:
            match_count += 1
    return match_count

print(distance(x, y))
 1.0

и сверху, если вы печатаете x, y сейчас: 

x
[1, 0, 1]
y
[0, 0, 1]

так работает?

0 голосов
/ 21 сентября 2019

Я воспроизвел твой код и получил твою ошибку.Я объясню это лучше здесь:

У него есть переменная vectorized_text ( np.stack ), которая имитирует набор функций One Hot Encoded (содержит только 0 и 1).А в модели DBSCAN он использует функцию custom_metric для вычисления расстояния.Ожидается, что при запуске модели пользовательская метрическая функция принимает в качестве параметров пары наблюдений в том виде, в каком они есть: одно горячее закодированное значение, но вместо этого при печати этих значений внутри функции distance берется только однокак есть, а другой выглядит как список реальных значений, как он описал в вопросе:

x = [0.5 0.5 0.5 ... 0.5 0.5] y = [0. 0. 0. 1. 0. 0. ... 1. 0.]

В любом случае, когда я передаю списки параметру fit,Функция получает значения в том виде, как они есть: 

from sklearn.cluster import KMeans, DBSCAN, MeanShift

x = [1, 0, 1]
y = [0, 0, 1]
feature_set = [x*5]*5
def distance(x, y):
    # Printing here the values. Should be 0s and 1s
    print(x, y)
    match_count = 0.
    for xi, yi in zip(x, y):
        if float(xi) == 1. and xi == yi:
            match_count += 1
    return match_count

def custom_metric(x, y):
    # x, y are two vectors
    # distance(.,.) calculates count of elements when both xi and yi are True
    return distance(x, y)

dbscan = DBSCAN(min_samples=2, metric=custom_metric, eps=3, p=1).fit(feature_set)`

Результат: 

[1. 0. 1. 1. 0. 1. 1. 0. 1. 1. 0. 1. 1. 0. 1.] ... [1. 0. 1. 1. 0.1. 1. 0. 1. 1. 0. 1. 1. 0. 1.]
[1. 0. 1. 1. 0. 1. 1. 0. 1. 1. 0. 1. 1. 0. 1.] ... [1. 0. 1. 1. 0.1. 1. 0. 1. 1. 0. 1. 1. 0. 1.]

Я предлагаю вам использовать pandas DataFrame или какой-либо другой тип значения и посмотретьесли это работает.

...