데이터 마이닝 분야 중 하나인 순차 패턴(sequential pattern)은 데이터에 공통으로 나타나는 순차적인 항목의 조합을 찾는 문제다. 순차 패턴 마이닝의 대상이 되는 데이터는 시퀀스(sequence)로 관측치가 이산형이며 변수 간 순서가 중요한 데이터를 시퀀스라고 한다. 최근 제조공정 내 불량을 야기하는 공정 설비를 찾는 문제, 의료분야에서 환자들의 패턴을 분석하는 문제 등의 시퀀스 데이터에서 원인이 되는 조합을 찾는 연구의 필요성이 증가하고 있다. 그 원인이 되는 조합을 찾기 위해 필요한 기법이 순차패턴분석(sequential pattern mining) 기법이다. 본 세미나에서는 순차패턴분석의 대표적인 알고리즘 두가지 GSP(Generalized Sequential Pattern), PrefixSPAN을 소개하였다.

GSP, PrefixSpan 두 알고리즘 모두 '지지도(support)'라는 척도를 기준으로 순차패턴을 탐색한다. 지지도는 데이터 내 특정 항목이 얼마나 빈번하게 나타났는지 표현하는 지수다. 예를 들어 10개의 시퀀스 중 'A'라는 항목이 10번 나타났다면 'A'의 지지도는 100%이다. GSP는 '너비기반 탐색(breadth based search)'알고리즘으로 길이가 가장 긴 순차패턴을 찾는다. 먼저 GSP는 사용자가 설정하는 최소지지도(minimum support)를 만족하는 길이가 1인 패턴을 찾는다.이후 단계적으로 길이를 늘려가며 찾는 방식으로 이루어진다. 즉, 길이가 k인 순차패턴을 Fk, 후보패턴을 Ck라고 했을 때, F1->C2->F2->...->Fk 순으로 탐색하는 것이다. 하지만 데이터 셋이 증가함에 따라 후보군을 만들기 위한 조합의 수가 급격히 늘어나기 때문에 시간비용이 큰 단점을 갖는다. 이러한 단점을 개선한 것이 PrefixSPAN 알고리즘이다. PrefixSPAN는 '깊이기반 탐색(depth based search)' 알고리즘으로 후보패턴을 만들지 않고 suffix데이터를 만들어가며 순차패턴을 찾는 기법이다. PrefixSPAN 역시 길이가 1인 패턴부터 찾고 가장 긴 순차패턴을 탐색하고자 하는 것이 목적이다. 여기서 GSP와 다른 prefix라는 개념이 등장한다. prefix는 길이가 K인 패턴 중 최소 지지도를 만족하는 패턴들이 있을 때 관측치마다 그 패턴 이전에 나타난 항목들을 전부 제외하고, 이후에 나타난 항목들에 대해서만 탐색하는 방법이다. 최소 지지도를 만족하는 길이 1 패턴이 최종 순차패턴이 되는 시작점인 것이다. 길이 k를 node의 깊이, 패턴을 node로 보고 트리 형태로 나타낸 것이 prefixSpan tree 이며 트리 노드 순서대로 계속 탐색을 이어나간다. 여기서 깊이기반 탐색 기법이라고 말할 수 있는 것이다.

본 세미나에서는 대표적인 순차패턴탐색 알고리즘 GSP, PrefixSpan을 소개하였다. 또한, 소개한 알고리즘에서 확장된 SPADE, SPIRIT 등의 기법들이 있으며, 순차패턴 이외 데이터를 그래프로 표현할 수 있을 때, 그래프 패턴마이닝 분야도 있다는 점을 소개하였다.

세미나를 진행하며 순차패턴마이닝 기법이 필요한 상황을 먼저 상기시키고 자세한 알고리즘을 설명하는 방식으로 소개했다면 좀더 청중들이 이해하기 편했을 것이라는 아쉬움이 남는다. 본 세미나로부터 전반적인 패턴마이닝에 대한 컨셉과 패턴을 탐색하는 기준, 또 응용분야와 각 알고리즘의 장단점을 알고 추후 분석에 활용할 때 도움이 되길 바란다.

​

금일 세미나는 '순차패턴분석'이라는 주제에 관한 내용이었다. 나는 순차패턴분석이라는 주제를 보고 시계열 데이터와 관련이 있을 것이라 예측하였지만, 잘못된 예측이었다. 순차패턴이 보이는 것은 마트에서 물건을 구매하는 것과 같은 예가 있다. 주식, 각종 연도별 데이터에 대해서만 해당되는것이 아니었다.

발표자는 특히 연관규칙을 분석하는 3가지의 확률을 이용한 지표와 2가지 알고리즘에 대하여 설명하였다. 예를 들어, A를 물건 A를 사는 경우라 하고, B를 물건 B를 사는 경우라 하자. 우선 지지도는 P(A와 B의 교집합)을 의미하고, 신뢰도의 경우는 P(B|A)를 의미하고, 향상도는 [지지도/{P(A)*P(B)}]를 의미하는 지표였다. 연관규칙분석은 실험자가 임의로 지정한 최소 지지도보다 큰 지지도를 보이며, 이 상황에서 높은 신뢰도와 향상도를 보이는 규칙을 찾는 방법이었다. 여기에서 순서의 개념이 들어간 경우, 순차패턴분석이라 불린다. 위에서 언급한 물건을 사는 경우를 보면, 연관규칙분석에서는 'A와 B를 구매하였다.'라는 사실이 중요하였지만, 순차패턴분석에서는 A가 발생하고 B가 발생하였다는 순서가 존재하였다. 이러한 순서가 존재하는지를 탐색하는 방법에는 GSP(Generalized Sequential Pattern)과 Prefix Span(Prefix-projected Sequential Pattern Mining) 두가지 방법을 주로 언급하였다. GSP는 각 항목별로 지지도를 계산하여, 최소 지지도를 만족하는 항목들을 뽑아 후보군을 만들고 여기서 파생하여 다음 항목들을 선정해나가면 순서패턴을 찾아 나가는 방법이다. Prefix Span은 가지고 있는 데이터 상에서 지지도를 계산하여, 일종의 Tree를 만들어 나가는 방법이다. 두가지 방법 모두 의미있는 순서패턴을 찾고자 할 때 사용된다.

금일 세미나를 들으면서 느낀 점은 순서가 있는 데이터에 대해 추상적으로만 알고 있었지만 이를 실제적으로 순서를 찾아 나아가고 이를 응용하여 접목한 부분은 처음으로 접해 보았다. 위에서 언급한 분석방법들은 이산형 순서 데이터에 적합한 방법이지만, 연속형 순서 데이터에 적합한 분석방법에도 많은 것들이 있었다. 이러한 부분들에 대해서는 추후에 살펴보면 유용하게 사용 할 수 있을듯 하다. 나에게 새로운 분야를 소개해준 윤상이에게 감사를 표한다.

오늘 세미나의 주제는 Sequential Pattern Mining Algorithms 에 관한 내용이었다.

연관분석은 데이터마이닝의 한 종류로 '조건-결과' 식으로 표현되는 패턴 , 즉 연관규칙을 발견하는 분석이다.

기준으로는 지지도와 신뢰도, 향상도가 있는데 이번 발표에서 지지도를 기준으로 사용되는 알고리즘 Generalized Sequential Pattern과 Prefixspan에 대해 알아보았다. GSP algorithm은 넓이 우선 탐색으로 후보패턴(Ck)와 빈번한 패턴(Fk)을 고려하여 분석한다. 만일 Fk를 통해 더이상 Ck를 만들 수 없을 때 algorithm은 종료된다. GSP는 후보패턴을 만들며 사용하기 때문에 시간이 많이 걸린다는 단점이 있다. 이를 개선하기 위한 algorithm이 PrefixSpan이다. PrefixSpan은 깊이 우선 탐색으로 Tree를 만들어가며 빈번한 패턴을 탐색하는 방법이다. 데이터의 sequence에서 노드에 해당하는 데이터가 모두 존재하는 경우를 prefix라 하고, 이를 제거한 데이터를 projected DB라 한다. Tree에서 각 노드의 projected DB에서 빈번한 패턴을 탐색하고 데이터의 null값이 나올 경우 분석을 멈추게 된다.

전반적인 algorithm에 대해서는 이해가 갔지만 수면 이벤트 시퀀스 데이터 부분에서의 그래프를 보았을 때 이해가 힘든 부분이 있었다. 이 부분에 대해서는 오늘 토론한 내용을 떠올리면서 다시 이해할 필요가 있다고 생각했다. 오늘 배운 내용에 대해서는 다양한 산업 분야나, 비즈니스 영역에서 활용이 되고, 조금 더 연구를 한다면 재미있는 분야가 될 것 같다는 생각이 들었다.

금일 진행된 세미나는 ‘Sequential Pattern Mining Algorithm’이라는 주제로 진행되었다. Sequential Pattern Mining이란 순서가 있는 데이터에서 순서를 고려해 빈번히 발생하는 특정 Pattern들을 찾아주는 데이터 마이닝 분야 중 하나이다. 다양한 방법론 중 오늘은 지지도 기준으로 탐색하여 Sequential Pattern을 정의하는 알고리즘에 대한 설명과 더불어 이를 적용시킨 응용연구까지 접해보았다. 먼저 특정 Pattern을 정의하기 위해서는 기준이 필요하며 대표적으로 지지도, 신뢰도, 향상도가 있다. 지지도는 전체 관측치 중 특정 항목이 동시에 포함되는 관측치의 비율을 의미하며, 최소지지도를 정의하여 빈번히 발생하는 항목을 기준으로 탐색을 할 수 있다. 이산형 데이터의 Sequential Pattern Mining은 ‘너비 우선 탐색’과 ‘깊이 우선 탐색’으로 나눌 수 있는데, 지지도를 기준으로 탐색하는 너비우선탐색의 경우 대표적인 예로 GSP algorithm이 있으며 후보패턴을 생성하고 빈번패턴을 정의하기 때문에 상당히 많은 시간을 필요로 하다는 단점이 있다. 대용량 데이터의 경우 후보패턴을 생성하지 않는 깊이우선탐색이 효과적이며 대표적인 예로 PerfixSpan방식이 있다. 지지도가 높은 항목을 기준으로 트리의 노드를 정의하고, 해당 항목을 하나씩 제거한 Sequence에서 지지도가 높은 항목을 기준으로 다음 hierarchy 노드를 정의하는 방식이다. 따라서 한 hierarchy 노드들의 Sequence를 Pattern으로 정의하는 것이다. 추가적으로 설명해주신 응용사례에서는 수면 이벤트 시퀀스 데이터를 PerfixSpan에 적용시킨 결과를 볼 수 있었는데 데이터 전처리 상에서 해당 데이터의 시간 간격을 고려하지 않고 발생하는 항목의 순서를 패턴으로 가정하였다. 이 부분에 대해 다같이 고민해보는 시간을 가졌는데 해당 데이터의 경우 Pattern을 정의하는데 있어서 시간간격 또한 고려하는 것이 정상, 이상을 판별하기 위한 분석에 더욱 적합할 것 같다는 의견이 있었다. 평소 데이터를 Sequential한 관점에서 생각해보지 않아 sequence data와 time series data의 개념에 혼동이 있었는데 수면데이터의 응용사례를 통해 개념을 정리해볼 수 있어 유익했고, 앞으로 데이터를 새로운 관점으로 해석해볼 수 있을 것 같다.

오늘 세미나는 순차 패턴 분석에 관한 내용이었다. 그 설명에 앞서 연관분석 연관규칙에 대한 의미를 먼저 이해하는 것이 필요하다. 둘의 차이를 장바구니 분석의 예로 이해해보자면 연관분석은 한 구매자의 한번의 구매행동시 구매품목들이 한 관측치가 된다. 순차 패턴 분석은 한 구매자의 지금까지 모든 구매헹동의 구매 품목들이 하나의 관측치가 된다. 따라서 연관규칙은 한구매행동 내에서 어떤 구매품목들의 조합(규칙)이 유의미한 의미를 갖는가를 확인할 수 있는 반면 순차패턴분석은 어떤 구매품목을 산 이후 다른 구매품목을 사더라라는 순서를 고려한 패턴을 확인할 수 있다. 오늘은 이산형의 시퀀스 데이터의 순차패턴분석 알고리즘 두가지에 대한 자세한 설명을 들을 수 있었다. 한가지는 너비 우선 탐색(Breath-First Style)의 GSP(Generalized Sequential Pattern) 알고리즘이다. 모든 시점 길이마다 모든 후보 순차 패턴을 만들고 후보 패턴들 가운데 사용자가 지정해놓은 지지도 값보다 높은 지지도 값을 갖는 순차 패턴들이 빈발 패턴으로 산출된다. 다음 시점의 후보 순차 패턴을 현 시점의 빈발 순차 패턴으로부터 만들어진다. GSP는 후보패턴을 만드는데 매우 오랜 시간이 걸리게 되어 효율성이 떨어지게된다. 또다른 알고리즘은 깊이 우선 탐색(Depth-First Style)의 PrefixSpan이다. PrefixSpan은 후보 패턴을 만들지 않으면서 Tree를 만들어가며 빈번한 패턴을 탐색하므로 GSP의 단점을 보완한다. Tree의 노드는 최소지지도를 넘는 대상으로 만들어지며 노드가 결정되는 이 노드가 prefix가 되고 이 노드에 해당되는suffix = projected DB가 만들어진다. 다음 노드는 projected DB내에서 최소지지도를 만족하는 대상으로 선정되고 따라서 Tree는 projected DB내에 더이상 최소지지도를 만족하는 대상이 나타나지 않을 때까지 깊어지게 된다. 이를 발표자는 수면이벤트 시퀀스 데이터에 적용하였다. 수면이벤트 시퀀스 데이터는 각 사람의 수면상태(W, N1,N2,N3,R)의 sequence가 하나의 관측치가 된다. 사람은 정상인과 수면질환 환자 두 종류가 있다. 따라서 정상인들의 관측치와 수면질환 환자들 관측치 따로 PrefixSpan 알고리즘을 적용하여 각각의 빈발 순차패턴을 확인하고 두 빈발순차패턴들의 차이가 분명할 것이라는 가정내에 실행되었다. 하지만 효율적라고 알려진 prefixspan 알고리즘마저도 해당 데이터에 적용하기위해 수시간이라는 엄청난 시간이 소요되었다고 한다. 아직까지도 아무리 훌륭한 알고리즘이라 하더라도 정해진 메모리와 시간 내에 결과를 내지 못한다면 결국 현실적으로 데이터에 적용불가능한 경우가 많은 것 같고 생각이 들었다. 유익한 세미나를 준비해준 윤상오빠게 감사를 표한다.

오늘 세미나는 순차 패턴 분석에 대해 다루었다. 순차 패턴 분석을 이해하기 위해서는 먼저 연관 분석에 대해 알아야 한다. 연관 분석은 ‘조건-결과’ 형태로 표현되는 유용한 패턴으로 이러한 규칙을 발견하는 것을 연관 분석이라고 하며, 월마트의 장바구니 분석으로 대중에 잘 알려져 있다. 측정 지표로는 지지도, 신뢰도, 향상도 등이 있는데 주로 전체 관측치 중 특정 항목들이 동시에 포함되는 관측치 비율인 지지도를 기준으로 패턴을 뽑아낸다. 이 같은 연관 분석의 연장선에서 순서가 있는 데이터를 다루는 것을 순차 패턴 분석이라 한다. 순차 패턴 분석에서는 순서를 고려하여 빈번하게 나타나는 패턴을 찾아내는 것이 특징이다. 세미나 시간에는 순차 패턴 분석에서 대표적인 알고리즘 두 가지를 소개했다. 첫번째는 Generalized sequential pattern algorithm(GSP)이고 두번째는 PrefixSpan이다. GSP는 지지도 기반 너비 우선 탐색으로 길이가 k인 후보 패턴 중에서 가장 빈번한 패턴을 찾아가는 방식이다. 후보 패턴을 만드는데 시간이 오래 걸린다는 단점이 있다. Prefix는 지지도 기반 깊이 우선 탐색 방법으로 GSP의 단점을 극복하기 위해 후보 패턴을 만들지 않는다. 지지도를 기준으로 가장 높은 대상을 찾은 뒤에 그 대상 뒤에 따라오는 패턴을 보는 방식으로 작동한다. 발표자가 앞에서 어떤 컨셉이나 알고리즘에 대하여 설명할 때 쉬운 예시를 들어주어 이해하기가 편했다. 다만 알고리즘에 대해 설명한 뒤에 PrefixSpan을 적용한 실제 사례에 대해 간단히 설명을 하였는데 사용한 raw data에 대해 먼저 설명을 하고 어떻게 적용하였는지 좀더 자세히 설명했다면 재미있었을 것 같다.

금일 세미나는 순차 패턴 분석에 대해 몇 가지 알고리즘을 설명하는 시간이었다. 순차 패턴을 지니는 데이터를 분석하기에 보통 많은 시간과 CPU 사용이 불가피하다. 따라서 이를 줄이기 위해 다양한 자료구조와 방법론들이 도출되었는데, 이 중 발표자는 연관 분석(Association Mining)을 접목한 순차 패턴 분석 방법론을 소개했다. 연관 분석은 보통 지지도, 신뢰도, 향상도를 기반으로 규칙을 도출하여 변수 간의 관계를 정의 할 수 있도록 한다. 이 세 가지 중 지지도를 사용한 방법이 GSP(Generalized Sequential Pattern) 방법이며, 크기가 1인 후보 집합부터 시작해 빈번한 집합을 찾아가는 방식이다. 더 이상 후보 집합을 찾을 수 없을 때 탐색은 중단된다. 이 후보 집합군을 사용하지 않아도 되는 방법론은 Prefix Span인데, 상대적으로 GSP 보다 대용량 데이터에 적합하다고 알려져 있다. 이 이유는 PrefixSpan Tree를 만들어가며 빈번한 패턴을 탐색하는 형태이기 때문이다. 각 패턴 시퀀스에서 빈출 원소(prefix)를 빼고 패턴을 분석한다는 점에서 Gibbs sampling과 부분적으로 유사한 방법론이며 prefix를 더 이상 찾을 수 없을 때 탐색을 중단한다. 각각 지지도 기반이지만 너비와 깊이 우선 이라는 점에서 차이점을 보인다. 최근 여러 도메인에서 시퀀스 데이터 분석에 대한 수요가 많은데 유용하게 응용할 수 있는 방법론을 소개해주었다고 생각한다.

금일 세미나는 sequential pattern mining 알고리즘 중 빈도수 기반의 이산형 이벤트 subsequence를 탐색하는 GSP와 prefixspan 알고리즘에 대해 살펴보았다. 두 알고리즘은 연관분석시 기본 개념인 apriori 알고리즘에 기반하고 있으며, support, confidence의 score에 기반하여 subsequence의 탐색 방향을 결정한다. (관심 subsequence 기반의 탐색을 계속할지, 종료할지) 이러한 기법은 주어진 데이터에 어떠한 순서패턴이 있을지 탐구할 경우 유용하게 사용할 수 있지만, 학습모델이 아니다 보니 예측문제에 사용이 불가능하다. 특히 빈도수 기반이라는 특징 때문에 적은데이터에는 충분한 inference성능을 기대하기 힘들다. sequential pattern mining의 본질은 의미있는 subsequnces를 빠른 시간내 탐색하는데 있다. 또한 pattern-growth 방식과 divided-and-conquer problem에 해당할 경우에만 적용이 가능하다는 전제가 있다. 탐색의 효율성을 꾀하고자 하는 연구방향이다 보니 우리에게 친숙한 분야는 분명 아닌듯 싶다. 연관분석에서부터 순서패턴 알고리즘까지 잘 설명해준 윤상이에게 수고했다는 말을 전하고 싶다. 이와 관련된 좋은 연구성과를 내기를 바란다.

순차패턴마이닝 이라는 것에 대해서는 들어는 본적은 있으나, 이번 세미나와 같이 연관된 방법에 대해 들어본적은 처음이었던것 같다. 일반적인 연관규칙 분석을 시계열로 확대를 하게 된다면 크게 2가지 문제가 있다고 생각한다. 첫번째는 시간 = 변수, 시간이 흐름에 따라 변수의 개수가 증가한다. 따라서 단순히 연관규칙을 적용한다고 할때도 탐색 범위가 엄청나게 많이 증가하게 되고 이는 곧 계산시간의 증가로 나타난다. 두번째는 특정시간만큼을 측정한다고 하더라도 각 관측치 별로 그 길이가 상이하나는 점이다. 예를들어 오늘 세미나에서 다룬 고객 데이터의 경우 A고객은 3가지 상품만 구매한 반면, B는 10개의 상품을 구매하는 경우도 발생할 수 있다. 따라서 이를 동일 선상에 넣고 분석하는 것은 매우 어려운 일이다. 오늘 다뤘던 Prefixspan는 지지도를 활용하여 시계열 데이터에 연관규칙 분석을 적용한것으로 이해할 수 있다. 전체적인 시계열 데이터에서 일부 sub-sequence를 찾는 효율적인 방법일 뿐 전체적인 패턴을 고려한다고 보기는 어려울 것 같다는 생각이 들었다. 반대로 말해서 어려운 만큼 다양한 분야에서 사용될 여지가 있으므로, 새로운 연구분야로써 상당히 흥미 있는 분야라고 생각된다.

금일 세미나는 순차 패턴 분석을 주제로 진행 되었다. 연관 분석과 순차 패턴 분석에 대한 개념과 방법론을 학습하고 응용 사례를 통하여 개념에 대해 확실하게 이해할 수 있는 세미나였다. 연관 분석은 지지도, 신뢰도, 향상도를 기준으로 규칙을 도출하는 분석 기법이다. 지지도는 통계적 유의성을 신뢰도는 연관 규칙의 강도를, 향상도는 중요한 규칙을 나타내는 지표이다. 순차 패턴 분석은 각 원소 사이에 순서가 있는 시퀀스 데이터 베이스에서 순서를 고려하여 빈번하게 나타나는 패턴을 찾아주는 기술로 지지도를 기준으로 탐색한다. GSP Algorithm 은 지지도를 기반으로 길이가 가장 긴 빈번한 순차 패턴을 탐색하는 방법으로 후보 패턴을 생성하여 찾아가기 때문에 시간이 많이 걸리는 단점이 있다. PrefixSpan 은 PrefixSpan Tree 를 만들어가며 빈번한 패턴을 탐색하는 방식으로 후보패턴을 만들지 않아 상대적으로 대용량 데이터에 적합한 방법론이다. 이 외에도 SPIRIT 알고리즘이나, SPADE 알고리즘이 있다. 이런 순차 패턴 분석은 방대한 양의 데이터에서 의미있는 규칙을 찾는 방법으로 시간이 오래 걸리는 상황이라 다양한 자료구조에 맞는 방법론 연구가 지속적으로 진행되고 있는 분야이다. 제조 공정 데이터의 경우 반복적인 시퀀스를 나타내는 형태의 데이터가 많은데 오늘 학습한 방법론을 이용하여 문제를 단순하게 만드는 것도 좋을 것 같다.

금일 세미나는 윤상이가 순서가 있는 패턴 (순차패턴) 탐지 알고리즘에 대해서 발표했다. 순서가 없는 경우 우리가 아는 apriori 이 대표적인 기법이다. Apriori 알고리즘의 경우 순서를 고려하지 않기 때문에 순서를 반영하여 패턴을 찾아주는 기법으로 GSP(generalized Sequential Patttern), SPADE(Sequential PAttern Discovery using Equivalence Classes), PrefixSpan 등이 제안되었다. 이들 알고리즘도 apriori 알고리즘과 마찬가지로 학습을 하는 방식이 아니라 유의미한 패턴의 후보를 빠르게 찾는 알고리즘이다. 세미나 후반부에 현재 수행하고 있는 과제와 관련한 PrefixSpan을 적용한 응용 사례를 발표했는데 알고리즘의 특성이 데이터에서 발견하고자 하는 패턴을 찾을 수 있는 것인지 이 부분을 먼저 검증한 후 적용해야 할 것 같다.