Matlab: Как настроить код кластеризации для многоступенчатой ​​кластеризации?

Question

Я хочу объединить огромное количество записей данных. Данные, с которыми я имею дело, имеют строковый тип. Процесс кластеризации занимает много времени.
Давайте предположим, что я хочу кластеризовать набор записей данных электронной почты в кластер, где электронные письма, написанные одним и тем же человеком, размещаются в одном кластере (принимая во внимание, что человек может написать свое имя по-разному).
Я хочу выполнить многоступенчатую кластеризацию:

• Первая стадия кластеризации на основе имени, если расстояние между именами между записями меньше порога, мы считаем эти кластеры иначе...
• Записи данных поступают на второй этап кластеризации на основе других атрибутов (кроме имени).

Попарное расстояние рассчитывается. Сейчас я в фазе кластеризации. Я хочу использовать следующий код для dbscan кластеризация:

function [IDX, isnoise] = dbscan_strings(X,epsilon,MinPts)
C = 0;
n = size(X,1); 
IDX = zeros(n,1);
D = pdist2(X,X,@intersection);
visited = false(n,1);
isnoise = false(n,1);
for i = 1:n
    if ~visited(i)
        visited(i) = true;
        Neighbors = RegionQuery(i);
        if numel(Neighbors)<MinPts
            % X(i,:) is NOISE
            isnoise(i) = true;
        else
            C = C+1;
            ExpandCluster(i,Neighbors,C);
        end
    end
end

function ExpandCluster(i,Neighbors,C)
    IDX(i) = C;
    k = 1;
    while true
        j = Neighbors(k);
        if ~visited(j)
            visited(j) = true;
            Neighbors2 = RegionQuery(j);
            if numel(Neighbors2)>=MinPts
                Neighbors = [Neighbors Neighbors2];   %#ok
            end
        end
        if IDX(j)==0
            IDX(j) = C;
        end
        k = k + 1;
        if k > numel(Neighbors)
            break;
        end
    end
end

function Neighbors = RegionQuery(i)
    Neighbors = find(D(i,:)<=epsilon);
end
end

Мне нужна помощь в превращении следующего процесса кластеризации в многоступенчатый процесс, где X содержит записи данных со всеми атрибутами. Давайте предположим, что X{:,1} это записи данных с атрибутом name, так как имя содержится в первом столбце.

ПРИМЕЧАНИЕ: я дам награду в 50 баллов за того, кто мне помогает.

Answer 1

Не делай все сразу!

Вы вычисляете много вещей, которые вам никогда не нужны, что замедляет работу. Например, хороший DBSCAN использует не функцию расстояния, а индекс.

Для имен работайте только с уникальными именами! Якобы у вас много одинаковых имен, но вы снова и снова вычисляете одни и те же расстояния.

Итак, прежде всего, создайте набор только уникальных имен. Выполните сопоставление сходства с этим (однако я бы предложил использовать для этого OpenRefine, а не Matlab!). После того как вы определили имена для объединения, создайте новую матрицу данных для каждой группы имен. Затем запустите любую кластеризацию, какую захотите. Хорошими кандидатами, вероятно, являются HDBSCAN и OPTICSXi (взгляните на алгоритмы кластеризации, доступные в ELKI, который, вероятно, имеет самый широкий выбор на выбор). Может быть, начать только со среднего общего имени, чтобы почувствовать параметры для алгоритма. Не кластеризуйте все подмножества одновременно.