Иерархическая кластеризация для битовых последовательностей - PullRequest
Новая
       31

Иерархическая кластеризация для битовых последовательностей

0 голосов
/ 15 ноября 2011

Это проблема с домашним заданием, и я сталкиваюсь с некоторыми трудностями, чтобы понять это. Вопрос о домашней работе 

    Cluster the following bitsequences using hierarchical clustering. If d(:,:) defines the
distace between two bitsequences a and b, d(a,b) = Hamming-Distance(a,b) . If C1 and C2 are 
two clusters, the distance between C1 and C2 is d(C1,C2) = 1/|C1||C2| Summation(a belongs C1, b belongs C2) d(a,b). 
Show the cluster hierarchchy with all the intermediate steps.

1   10001011
2   11010111
3   00101010
4   00011110
5   10101110
6   11100001

Я прочитал в книге, что сначала я должен рассматривать их как кластеры, а затем начинаю объединять самые близкие. Новый кластер будет сформирован. Теперь мне нужно найти ближайший кластер к этому вновь сформированному кластеру, вычислив расстояние между этим новым кластером и другими кластерами путем усреднения расстояния между каждым элементом в обоих кластерах, как сказано в вопросе.

Мое решение: Я найду расстояние Хэмминга между всеми парами и выберу ту, наименьшей из которых является C3 и C5 (расстояние Хэмминга равно 2). Теперь это можно объединить в новый кластер.

Меня беспокоит, что именно подразумевается под слиянием здесь? Как мне это сделать? Или просто я оставляю их такими, какие они есть, и называю это новым кластером?

А как мне найти среднее расстояние между каждым элементом нового кластера с другими кластерами?

Также для вычисления среднего приведенная формула говорит, что нужно разделить на | C1 | и | C2 |. Итак, значит ли это, что я должен разделить здесь количество элементов (то есть 8 на одну группу, умноженное на кластер, в который он входит?)

Любая помощь очень ценится. Спасибо.

1 Ответ

2 голосов
/ 16 ноября 2011

Звучит так, как будто вы хотите восходящие кластеры. Идея состоит в том, чтобы начать с некоторых наборов синглтона 

{1} {2} {3} {4} {5} {6}

Пока есть два или более комплектов, выберите ближайшую пару и замените их их объединением. Я сделаю это несколько произвольно. 

{1, 2} {3} {4} {5} {6}
{1, 2} {3, 6} {4} {5}
{1, 2} {3, 4, 6} {5}
{1, 2, 5} {3, 4, 6}
{1, 2, 3, 4, 5, 6}

Иерархическая кластеризация состоит из всех наборов, которые когда-либо существовали в алгоритме. Их можно представить в виде дерева, где, если X является потомком Y, то X является подмножеством Y. 

           {1,2,3,4,5,6}
           /           \
          /             \
         /               \
     {1,2,5}           {3,4,6}
     /     \           /     \
  {1,2}     \       {3,6}     \
  /   \      \      /   \      \
{1}   {2}    {5}  {3}   {6}    {4}

Среднее расстояние вычисляется по заданной формуле; | C1 | и | C2 | количество последовательностей в кластерах 1 и 2 соответственно. Длина последовательностей важна только при расчете расстояния Хэмминга для одной пары. Например, расстояние между кластерами {1, 2} и {3, 4, 6} составляет (d (1,3) + d (1,4) + d (1,6) + d (2,3) + D (2,4) + D (2,6)) / 6.

...