Методы бикластеризации для анализа интернет-данных

     чиабатта |   

Классификация методов бикластеризации


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

Таблица 1.3:

Сравнительная таблица алгоритмов бикластеризации



Алгоритм Тип бикластера Структура Порождение Стратегия поиска
Block Clustering [37] Constant f One Set at a Time Div-and-Conq

-biclusters [25]

Coherent Values i One at a Time Greedy
FLOC [84,85] Coherent Values i Simultaneous Greedy
pClusters [81] Coherent Values g Simultaneous Exh-Enum
Plaid Models [51] Coherent Values i One at a Time Dist-Ident
PRMs [66,67] Coherent Values i Simultaneous Dist-Ident
CTWC [34] Constant Columns i One Set at a Time Clust-Comb
ITWC [78] Coherent Values d,e One Set at a Time Clust-Comb
DCC [23] Constant b,c Simultaneous Clust-Comb

-Patterns [24]

Constant Rows i Simultaneous Greedy
Spectral [45] Coherent Values c Simultaneous Greedy
Gibbs [68] Constant Columns d,e One at a Time Dist-Ident
OPSMs [16] Coherent Evolution a,i One at a Time Greedy
SAMBA [77] Coherent Evolution i Simultaneous Exh-Enum
xMOTIFs [58] [19] Coherent Evolution a,i Simultaneous Greedy
OP-Clusters [53] Coherent Evolution i Simultaneous Exh-Enum

Мы используем решеточную таксономию алгоритмов, так как она лишена недостатков древесной, когда наследование свойств от различных надклассов невозможно для одного и того же подкласса. Данная таксономия построена средствами ФАП, а исходная таблица 1.3 посредством шкалирования сведена к объектно-признаковому представлению в виде бинарной матрицы.

Рис. 1.1. Таксономия алгоритмов бикластеризации


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

Для пополнения таксономии объектами мы предлагаем включить алгоритмы, используемые в ФАП для поиска формальных понятий, алгоритмы поиска частых (замкнутых) множеств признаков, алгоритм аддитивной бокс-кластеризации, DR-miner и D-miner из области DataMining, BiMax — разработанный для анализа генетических данных. Перечисленные алгоритмы, за исключением бокс-кластеризации, работают только с 0/1 данными, поэтому в таксономии им соответствует подрешетка, порожденная признаком

"


-данные".


Содержание раздела