Кіріспе

Матрицаның жолдары мен бағаналарын бір мезгілде кластерлеуге арналған деректерді өндіру әдісі. Бикластерлеу, блок кластерлеу, ко-кластерлеу немесе екі режимді кластерлеу – бұл матрицаның жолдары мен бағаналарын бір уақытта кластерлеуге мүмкіндік беретін деректерді өндіру әдісі. Бұл термин алғаш рет Борис Миркин көп жылдар бұрын енгізілген әдісті атау үшін қолданылды.

Егер үлгілер жиынтығы өлшемдік белгілер векторы арқылы көрсетілсе, онда бүкіл деректер жиынтығын жолдармен бағандарда көрсетуге болады (яғни, матрица). Бикластерлеу алгоритмі бикластерлерді құрайды. Бикластер – бұл бағандардың белгілі бір жиынтығы бойынша ұқсас мінез-құлық көрсететін жолдардың жиынтығы, немесе керісінше.

Даму

Бикластерлеуді алғаш рет 1972 жылы Джон А. Хартиган енгізді. "Бикластеринг" термині кейін Борис Г. Миркин қолданды және жетілдірді. Бұл алгоритм 2000 жылға дейін жалпыланбады, сол кезде Y. Ченг пен Джордж М. Черч орташа квадраттық қалдық көрсеткішіне (MSR) негізделген бикластерлеу алгоритмін ұсынды және оны биологиялық гендік экспрессия деректеріне қолданды. 2001 және 2003 жылдары И. С. Дхилон файлдар мен сөздерге бикластерлеуді қолданатын екі алгоритм жариялады. Бір нұсқа екі бөлікті спектрлік графты бөлуге негізделген, ал екіншісі – ақпарат теориясына. Дхилон бикластерлеу кезінде өзара ақпараттың жоғалуы P және Q арасындағы Kullback–Leibler қашықтығына (KL қашықтығы) тең деп болжады. Мұнда P – бикластерлеуден бұрынғы файлдар мен ерекше сөздердің таралуын, ал Q – бикластерлеуден кейінгі таралуын білдіреді. KL қашықтығы екі кездейсоқ таралым арасындағы айырманы өлшеуге арналған. Егер екі таралым бірдей болса, KL = 0, ал айырмашылық артқан сайын KL да өседі. Осылайша, алгоритмнің мақсаты P мен Q арасындағы ең төмен KL қашықтығын табу болды. 2004 жылы Ариндам Банерджи KL қашықтығының орнына салмақталған Брегман қашықтығын қолданып, KL қашықтығынан айырмаша, кез келген матрицаға сәйкес келетін бикластерлеу алгоритмін жасады. 2005 жылы Беккерман Дхилон теоремасындағы өзара ақпаратты екі нысан түрінен артық нысан түрлерін кластерлеу үшін бір жұптан бірнеше жұпқа дейін кеңейтті.

Күрделілігі

Бикластерлеу мәселесінің күрделілігі нақты мәселе тұжырымдамасына және әсіресе берілген бикластердің сапасын бағалау үшін қолданылатын өлшем функциясына байланысты. Дегенмен, осы мәселенің ең қызықты түрлері NP-толық. NP-толықтығы екі шартқа негізделген. Екілік матрица A-да тек 0 немесе 1 элементтері болған жағдайда, бикластер тиісті екі бөлікті графтың бикликіне тең. Бикластердің максималды мөлшері екі бөлікті графтың максималды жиектік биклигімен сәйкес келеді. Күрделі жағдайда, матрица A-дағы элементтер берілген бикластердің сапасын есептеу үшін және мәселенің шектеулі түрін шешу үшін қолданылады. Бұл үлкен есептеу ресурстарын қажет етеді немесе есептеуді жеңілдету үшін шамалы қателіктерге жол беретін эвристикалық әдістерді пайдалануды талап етеді.