Discovery of optimal factors in binary data via a novel method of matrix decomposition

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989592%3A15310%2F10%3A00010968" target="_blank" >RIV/61989592:15310/10:00010968 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Discovery of optimal factors in binary data via a novel method of matrix decomposition

Popis výsledku v původním jazyce

We present a novel method of decomposition of an n xm binary matrix I into a Boolean product A x B of an n x k binary matrix A and a k x m binary matrix B with k as small as possible. Attempts to solve this problem are known from Boolean factor analysiswhere I is interpreted as an object?attribute matrix, A and B are interpreted as object?factor and factor?attribute matrices, and the aim is to find a decomposition with a small number k of factors. The method presented here is based on a theorem provedin this paper. It says that optimal decompositions, i.e. those with the least number of factors possible, are those where factors are formal concepts in the sense of formal concept analysis. Finding an optimal decomposition is an NP-hard problem. However, we present an approximation algorithm for finding optimal decompositions which is based on the insight provided by the theorem. The algorithm avoids the need to compute all formal concepts and significantly outperforms a greedy approxim

Název v anglickém jazyce

Discovery of optimal factors in binary data via a novel method of matrix decomposition

Popis výsledku anglicky

We present a novel method of decomposition of an n xm binary matrix I into a Boolean product A x B of an n x k binary matrix A and a k x m binary matrix B with k as small as possible. Attempts to solve this problem are known from Boolean factor analysiswhere I is interpreted as an object?attribute matrix, A and B are interpreted as object?factor and factor?attribute matrices, and the aim is to find a decomposition with a small number k of factors. The method presented here is based on a theorem provedin this paper. It says that optimal decompositions, i.e. those with the least number of factors possible, are those where factors are formal concepts in the sense of formal concept analysis. Finding an optimal decomposition is an NP-hard problem. However, we present an approximation algorithm for finding optimal decompositions which is based on the insight provided by the theorem. The algorithm avoids the need to compute all formal concepts and significantly outperforms a greedy approxim

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BD - Teorie informace

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2010

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Computer and System Sciences

ISSN

0888-613X

e-ISSN

—

Svazek periodika

76

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

18

Strana od-do

—

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—