Egloos | Log-in
YJ
YJ
데이터 마이닝 테크닉 - Apriori 알고리즘 / 클러스터링
유동하 (mozala@hufs.ac.kr) Apriori 알고리즘
연관 규칙을 찾아주는 알고리즘 중에서 가장 먼저 개발됐고 또 가장 많이 쓰이는 알고리즘은 Apriori 알고리즘입니다. 이 알고리즘은 두 가지 단계로 구성됩니다. 우선 첫 번째 단계에서는 최소 지지도 설정 값에 따라 빈도수가 높은 항목의 집합들을 찾아내고 그 다음 단계에서는 이들 집합들로부터 신뢰도 설정 값을 모두 뽑아냅니다.
Apriori 알고리즘에서 사용하는 중요한 법칙은 빈도수가 높은 항목 집합의 모든 부분 집합도 다 빈도수가 높다는 사실입니다. 예를 들어 데이터에 {빵, 버터, 우유}가 최소 지지도에 의해 빈도수가 높다면 당연히 {빵, 버터}만을 봐도 빈도수가 높고, {버터, 우유}을 봐도 빈도수가 높습니다. 다시 말해 어떤 집합이 주어졌을 때 새로운 항목을 더해주면 지지도는 절대로 전보다 증가할 수 없습니다.
Apriori 알고리즘은 우선 사이즈 한 개의 빈도수가 높은 항목들을 먼저 구하고 그 다음에 이것들을 이용해 사이즈가 두 개인 빈도수가 높은 항목들의 집합을 구하는 방식으로 한 사이즈씩 차례로 수행합니다. 그렇기 때문에 데이터에 있는 사이즈가 가장 큰 빈도 높은 항목 집합의 크기가 k라면 대략적으로 데이터를 k번 스캔하게 됩니다(여기서 집합의 사이즈란 그 집합에 들어 있는 원소 개수를 말합니다). 사이즈가 k인 빈도 높은 항목들을 지금 막 구한 단계라고 합시다. 이 때 이들을 이용해 사이즈가 k+1인 후보 항목들의 집합들을 먼저 구합니다.
예를 들어 <그림 1>에서 사이즈가 2인 빈번 아이템 항목 L2에서 {B, C}와 {B, E}를 이용해 {B, C, E}라는 사이즈가 3인 후보 항목들의 집합이 만들어집니다. 이 때 이 집합의 원소로 구성된 사이즈가 2인 모든 부분 집합이 사이즈 2인 빈도 높은 항목 집합들에 다 들어있는지 체크하고 만일 하나라도 없다면 후보에서 탈락시킵니다. 여기서 {B, C, E}는 그것의 부분집합 {B, C}, {B, E}, {C, E}가 모두 빈도 높은 항목 집합들에 들어 있으므로 후보 집합에 해당됩니다. 즉 {A, B, C}나 {A, C, E}가 후보 항목에 들어갈 수 없는 이유로 {A, C}나 {A, E}가 빈도 높은 항목 집합에 들어 있지 않기 때문입니다. 이런 식으로 후보들을 만든 후에는 실제 데이터를 스캔해 후보들을 카운트하고 그런 후에 지지도를 만족하는 것들만 뽑아내 사이즈가 3인 후보 항목 집합을 만들어냅니다. 그 다음에는 다시 이들을 이용해 사이즈가 4인 후보들을 만들어 내고 더 이상 후보 집합을 만들지 못할 때까지 같은 과정을 반복합니다.


<그림 1> Apriori 알고리즘의 수행 과정


[ 연관 규칙 알고리즘의 성능 비교 ]   
연관 규칙 알고리즘의 성능 비교
연관 규칙은 항목 집합으로 표현된 트랜잭션에서 각 항목간의 연관성을 반영하는 규칙으로 Apriori 알고리즘이 처음 소개된 후, 데이터베이스 검색 횟수를 줄이거나 주기억 장치의 한계를 없애는 등의 발전된 알고리즘들이 발표되어 왔습니다. Apriori를 개선한 알고리즘으로는 AprioriTID, AprioriHybrid, DHP 등이 있으며 대부분 Apriori 알고리즘과의 비교를 통해서 진화된 알고리즘의 성능을 밝히고 있습니다. 그러나 연관 규칙 알고리즘의 성능 비교 측면에서 보면, 알고리즘마다 서로 다른 실험 환경에서 수행되었기 때문에 그들을 하나의 기준으로 비교한다는 것은 불가능합니다.



클러스터링
여러분이 여러 종류의 콩과 팥이 섞여 있는 자루를 가지고 있다면 그것을 무엇이라 지칭하겠습니다. 얼른 보기에 그 중에 조금 많이 들어 있는 종류를 보고 완두콩 자루라고 말할 수도 있고 강낭콩 자루라고 말할 수 있습니다. 클러스터링은 <그림 2>와 같이 자루에 담겨 있는 항목들의 크기 속성이나 색깔 속성 등을 기준으로 유사성을 계산하여 군집을 만드는 기법입니다.


<그림 2> 클러스터링 개념

클러스터링은 주어진 데이터 집합을 서로 유사성을 가지는 몇 개의 군집(cluster)으로 분할해 나가는 과정으로 하나의 군집에 속하는 데이터 간에는 서로 다른 군집 내의 데이터와는 구분되는 유사성을 갖게 됩니다. 달리 말하면 클러스터링은 데이터 내에 존재하는 상이한 그룹을 구분해 내는 기법이라고 볼 수도 있기 때문에 분류 작업과도 관련되어 있으나 어떠한 그룹도 사전에 정의되어 있지 않다는 점에서 분류 작업과 다릅니다. 예를 들어 고객의 구매 데이터를 바탕으로 그 구매 상품의 특징에 따라 고객을 여러 그룹으로 나누는 것이라 할 수 있습니다. 또 모든 고객의 신상 정보를 이용해 그 유사성에 따라 그룹을 나누는데 사용할 수도 있습니다. 자료 구조적으로 보면 n개의 점을 K개의 그룹으로 나누는 것을 말합니다. 클러스터링 기법은 여러 가지 알고리즘이 개발됐는데 알고리즘에 따라 다른 군집을 만들어 냅니다. 그러므로 모든 알고리즘의 특성을 잘 알고 있어야 자기 응용 분야에 맞는 것을 잘 사용할 수 있습니다. 또한 숫자 형태의 데이터인가 범주 형태의 데이터인가에 따라 다른 형태의 알고리즘이 존재합니다.

by aDeuxist | 2005/11/29 17:21 | DATA MINING | 트랙백(2) | 핑백(1) | 덧글(4)
트랙백 주소 : http://adeuxist.egloos.com/tb/971440
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Tracked from Man of Action at 2010/08/17 20:35

제목 : 데이터 마이닝 테크닉 - Apriori 알고리즘 /..
유동하 (mozala@hufs.ac.kr) Apriori 알고리즘연관 규칙을 찾아주는 알고리즘 중에서 가장 먼저 개발됐고 또 가장 많이 쓰이는 알고리즘은 Apriori 알고리즘입니다. 이 알고리즘은 두 가지 단계로 구성됩니다. 우선 첫 번째 단계에서는 최소 지지도 설정 값에 따라 빈도수가 높은 항목의 집합들을 찾아내고 그 다음 단계에서는 이들 집합들로부터 ...more

Tracked from at 2014/03/11 00:31

제목 : http://helenmccrory.org/
line6...more

Linked at links for 2010-0.. at 2010/05/14 09:32

... .pdf &#8211; Powered by Google 문서도구 TV Anytime YJ : 데이터 마이닝, 걷히는 안개를 바라보면서 [2/2] YJ : 데이터 마이닝 테크닉 &#8211; Apriori 알고리즘 / 클러스터링 세번째 단락에.. &#039;즉 {A, B, C}나 {A, C, E}가 후보 항목에 들어갈 수 없는 이유로 {A, C}나 {A, E}가 ... more

Commented by 한현구 at 2009/09/01 21:40
좋은 정보 감사합니다.
Commented by 허경 at 2010/08/17 20:29
잘 보고 갑니다.
좋은 정보 감사드려요~
제 블로그로 퍼갑니다.
혹시 문제가 된다면 말씀해주세요.
바로 삭제하겠습니다.
Commented by 김현욱 at 2012/09/28 12:35
그림 1 알고리즘 수행과정에서 트랜잭션 데이터베이스에서 TID 300 레코드가 ABCE가 아니라 ACE가 맞는거 같네요
Commented by 김문종 at 2014/02/07 14:20
잘 보고 갑니다
자료 블로그로 퍼갈게요. 문제되면 말씀 주세요!

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
전체
ROBOT
Ubiquitous
Ubibot
DATA MINING
인공지능
Agent
미분류
이전블로그
more...
이글루링크
최근 등록된 덧글
담아갈게요~
by 안녕하세요 at 08/08
감사합니다!^^ 많은 도움이 되..
by kgreb at 06/11
잘 보고 갑니다 자료 블로그로 퍼..
by 김문종 at 02/07
그림 1 알고리즘 수행과정에서 트..
by 김현욱 at 09/28
잘 보고 갑니다. 좋은 정보 감사..
by 허경 at 08/17
좋은 정보 감사합니다.
by 한현구 at 09/01
오웃! 로봇과 마이닝!! ㅋㅋ 근데 ..
by 남쉐이 at 12/01
rss

skin by jiinny
X