There are numerous clustering applications such as s a set of documents, citation networks, web graphs, and so on. Most clustering algorithms are only for 2-dimensional matrix data. However, many real-world datasets have more than three entities which require at least 3-dimensional matrix data.
Focusing on the clustering algorithm known as cross-association, we extend the algorithm to deal with a 3-dimensional matrix. Our proposed method has the same advantages as 2-dimensional cross-association such as fully automated and simultaneously discovering clusters of both row and column groups. To evaluate our method, we experimented with synthetic data and real-world data. With synthetic data, our algorithm works well for finding clusters and regrouping. With real-world data, the algorithm is also able to handle real-world data. Through the proposed method, useful information can be obtained even from sparse datasets.
데이터 마이닝 영역에서 다양한 형태의 데이터로부터 비슷한 집합, 또는 일정한 유형을 찾는 문제는 많은 연구가 이루어져 왔다. 다량의 무질서해 보이는 데이터를 분석하기 쉽도록 특정 기준으로 모으거나 그 중에서 특정 유형을 추출해 내는 기술은 많은 영역에서 사용할 수 있다. 그 중 2차원의 행렬로서 표현 및 분석 가능한 데이터를 중점적으로 보면, 그 예로 위에서 언급하였던 장바구니 분석을 들 수 있다. 각 차원을 구매자-물건 으로서 표현할 수 있다. 또한 문서 집합과 각 문서에서 사용한 단어의 집합도 마찬가지로 2차원 행렬로서 표현할 수 있다. 이 외에도 주어진 그래프에서 집합군을 찾는 문제나 분할하는 문제, 웹 페이지의 연결관계를 분석, 네트워크 상의 기기들 간의 연결관계 분석 등 다양한 영역에서 행렬 분석을 사용할 수 있다. 하지만, 실제세계의 데이터는 단순히 2차원, 즉 2개 요소들 간의 상관관계 그 이상의 요소들 간의 관계가 엮여 있다. 구매자와 물품 사이의 구매 패턴을 연구하는 예에서는 `어디에서` 구매하였는지에 대한 정보를 추가적으로 사용할 수 있다. 다른 예로, 영화와 이를 본 관객들을 분석하여 각 관객들의 성향을 파악하는 문제에서는 관객-영화 사이의 정보 뿐만이 아니라 각 영화의 등장 배우, 영화 제작 국가 등을 추가 정보로서 활용하여 관객의 성향을 다각도로 분석할 수 있다. 그리고 실제 데이터는 구성하는 요소들의 크기가 매우 크지만, 요소들 사이의 관계 정보는 전체 행렬에서 극히 일부만을 채우고 있을 정도로 대부분이 매우 성기다
구성 요소들 간의 집합을 찾는 것은 주어진 데이터를 압축한다는 것과 비슷한 문제를 해결한다고 볼 수 있다. 데이터에서 적절한 집합군을 전부 찾으면, 해당 집합들로만으로 전체 데이터를 대표하여 설명할 수 있다. 역으로 데이터를 압축하였다는 것은 곧 압축된 그 결과가 원래 데이터에 있는 요소들을 대표적으로 표현한다고 볼 수 있다. 본 논문에서는 실제 데이터에서 의미 있는 데이터들 간을 묶음으로서 여러 패턴 또는 유형을 찾아내고자 한다. 그러기 위해 본 논문에서는 다차원의 정보 중 3차원의 데이터를 사용하여 의미를 분석하고자 한다. 3개 요소들 간의 관계를 군집화를 거침으로서 데이터를 기존보다 조밀하게 묶는 과정을 거친다. 제시하고자 하는 알고리즘은 기존의 군집화 알고리즘과는 다르게 변수를 일절 쓰지 않는다. 대다수의 군집화 알고리즘은 군집의 개수와 기타 알고리즘에 필요한 변수를 입력받아야 하지만, 본 논문의 알고리즘은 3개 이상의 요소들 간의 정보 군집을 군집 개수와 같은 변수를 필요로 하지 않고 자동적으로 찾는다. 찾은 군집을 3차원 이상의 행렬 내에서 재 정렬함으로서 기존의 성긴 행렬을 보다 조밀하게 압축하는 효과를 보일 수 있다.