Как определить, идентичны ли два раздела (кластеризации) точек данных?
я имею n точки данных в некотором произвольном пространстве, и я их кластеризирую.
Результатом моего алгоритма кластеризации является раздел, представленный вектором int l длины n присвоение каждой точки кластеру. Значения l колеблется от 0 до (возможно) n-1,
Пример:
l_1 = [ 1 1 1 0 0 2 6 ]
Это раздел n=7 точки в 4 кластера: первые три точки сгруппированы вместе, четвертая и пятая вместе, а последние две точки образуют два отдельных одноэлементных кластера.
Мой вопрос:
Предположим, у меня есть два раздела l_1 а также l_2 как я могу продуктивно определить, представляют ли они одинаковые разделы?
Пример:
l_2 = [ 2 2 2 9 9 3 1 ]
идентично l_1 поскольку он представляет одинаковые разбиения точек (несмотря на то, что «цифры» / «метки» кластеров не идентичны).
С другой стороны
l_3 = [ 2 2 2 9 9 3 3 ]
больше не идентичен, так как он группирует последние два пункта.
Я ищу решение на C ++, Python или Matlab.
Нежелательное направление
Наивным подходом будет сравнение матрицы совпадений
c1 = bsxfun( @eq, l_1, l_1' );
c2 = bsxfun( @eq, l_2, l_2' );
l_1_l_2_are_identical = all( c1(:)==c2(:) );
Матрица совместного появления c1 имеет размер nИксn с true если очки k а также m находятся в одном кластере и false в противном случае (независимо от кластера «номер» / «метка»).
Поэтому, если матрицы совмещения c1 а также c2 идентичны тогда l_1 а также l_2 представлять идентичные разделы.
Тем не менее, так как количество очков, n, может быть довольно большим, я хотел бы избежать O (n^2) решения …
Есть идеи?
Спасибо!
Решение
Когда два раздела идентичны?
Вероятно, если у них есть точно такие же члены.
Поэтому, если вы просто хотите проверить личность, вы можете сделать следующее:
Замените каждый идентификатор раздела на наименьшее Идентификатор объекта в разделе.
Тогда два разбиения идентичны тогда и только тогда, когда это представление идентично.
В приведенном выше примере предположим, что индекс вектора 1 .. 7 является идентификатором вашего объекта. Тогда я бы получил каноническую форму
[ 1 1 1 4 4 6 7 ]
^ first occurrence at pos 1 of 1 in l_1 / 2 in l_2
^ first occurrence at pos 4
для l_1 и l_2, тогда как l_3 канонизирует
[ 1 1 1 4 4 6 6 ]
Чтобы сделать это более понятным, вот еще один пример:
l_4 = [ A B 0 D 0 B A ]
канонизирует
[ 1 2 3 4 3 2 1 ]
поскольку первый случай кластера «А» находится в положении 1, «В» в положении 2 и т. д.
Если вы хотите измерить, как аналогичный две кластеризации, хороший подход состоит в том, чтобы посмотреть на точность / возврат / f1 пар объектов, где пара (a, b) существует тогда и только тогда, когда a и b принадлежат одному кластеру.
Обновить: Поскольку было заявлено, что это квадратичный, я уточню.
Чтобы создать каноническую форму, используйте следующий подход (фактический код Python):
def canonical_form(li):
""" Note, this implementation overwrites li """first = dict()
for i in range(len(li)):
v = first.get(li[i])
if v is None:
first[li[i]] = i
v = i
li[i] = v
return li
print canonical_form([ 1, 1, 1, 0, 0, 2, 6 ])
# [0, 0, 0, 3, 3, 5, 6]
print canonical_form([ 2, 2, 2, 9, 9, 3, 1 ])
# [0, 0, 0, 3, 3, 5, 6]
print canonical_form([ 2, 2, 2, 9, 9, 3, 3 ])
# [0, 0, 0, 3, 3, 5, 5]
print canonical_form(['A','B',0,'D',0,'B','A'])
# [0, 1, 2, 3, 2, 1, 0]
print canonical_form([1,1,1,0,0,2,6]) == canonical_form([2,2,2,9,9,3,1])
# True
print canonical_form([1,1,1,0,0,2,6]) == canonical_form([2,2,2,9,9,3,3])
# False
Другие решения
Если вы собираетесь перемаркировать свои разделы, как было предложено ранее, вам, возможно, понадобится выполнить поиск по n меткам для каждого из n элементов. То есть решения O (n ^ 2).
Вот моя идея: сканировать оба списка одновременно, поддерживая счетчик для каждой метки раздела в каждом списке.
Вам нужно будет иметь возможность сопоставить метки разделов с номерами счетчиков.
Если счетчики для каждого списка не совпадают, то разделы не совпадают.
Это было бы O (n).
Вот подтверждение концепции в Python:
l_1 = [ 1, 1, 1, 0, 0, 2, 6 ]
l_2 = [ 2, 2, 2, 9, 9, 3, 1 ]
l_3 = [ 2, 2, 2, 9, 9, 3, 3 ]
d1 = dict()
d2 = dict()
c1 = []
c2 = []
# assume lists same length
match = True
for i in range(len(l_1)):
if l_1[i] not in d1:
x1 = len(c1)
d1[l_1[i]] = x1
c1.append(1)
else:
x1 = d1[l_1[i]]
c1[x1] += 1
if l_2[i] not in d2:
x2 = len(c2)
d2[l_2[i]] = x2
c2.append(1)
else:
x2 = d2[l_2[i]]
c2[x2] += 1
if x1 != x2 or c1[x1] != c2[x2]:
match = False
print "match = {}".format(match)
В матлабе:
function tf = isIdenticalClust( l_1, l_2 )
%
% checks if partitions l_1 and l_2 are identical or not
%
tf = all( accumarray( {l_1} , l_2 , [],@(x) all( x == x(1) ) ) == 1 ) &&...
all( accumarray( {l_2} , l_1 , [],@(x) all( x == x(1) ) ) == 1 );
Что это делает:
группирует все элементы l_1 согласно разделу l_2 и проверяет, все ли элементы l_1 у каждого кластера все одинаковые. Повторяя то же самое для разбиения l_2 в соответствии с l_1,
Если обе группировки дают однородные кластеры — они идентичны.