| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | |||||
| 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 24 | 25 | 26 | 27 | 28 | 29 | 30 |
다른 곳의 bubble sort는 잘못된 곳이 많다.
특히,10-i-1의 위치가 잘못된 곳이 많다.
int main()
{
int arr[10] = { 3, 7, 4, 8, 6, 2, 13, 1, 9 ,5 };
for (int i = 0; i < 10 - 1; i++)
{
for (int j = 0; j < 10 - i - 1; j++)
{
int tmp;
if (arr[j] > arr[j + 1])
{
tmp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = tmp;
}
}
}
#include <stdio.h>
int n; // 정점의 총 갯수
int map[30][30], visit[30]; // 인접 행렬과 방문 여부를 나타내는 배열
void DFS(int v)
{
int i;
visit[v] = 1; // 정점 v를 방문했다고 표시
for (i = 1; i <= n; i++)
{
// 정점 v와 정점 i가 연결되었고, 정점 i를 방문하지 않았다면
if (map[v][i] == 1 && !visit[i])
{
printf("%d에서 %d로 이동\n", v, i);
// 정점 i에서 다시 DFS를 시작한다
DFS(i);
}
}
}
int main()
{
int start; // 시작 정점
int v1, v2;
scanf("%d%d", &n, &start);
while (1)
{
scanf("%d%d", &v1, &v2);
if (v1 == -1 && v2 == -1) break; // -1과 -1이 입력되면 무한 루프 탈출
map[v1][v2] = map[v2][v1] = 1; // 정점 v1과 정점 v2가 연결되었다고 표시
}
DFS(start); // DFS 시작!
return 0;
}
===================================================================================================
#include<stdio.h>
int n, min;
int map[10][10];
int count;
/*
5
1 1 1 1 1
0 0 0 0 1
1 1 1 1 1
1 0 1 0 0
1 1 1 1 1
*/
void DFS(int x, int y, int l)
{
if (x == n - 1 && y == n - 1)
{
count++;
return;
}
map[y][x] = 0;
// 위로 이동 가능?
if (y > 0 && map[y - 1][x]) DFS(x, y - 1, l + 1);
if (y < n-1 && map[y + 1][x]) DFS(x, y + 1, l + 1);
if (x > 0 && map[y][x - 1]) DFS(x -1 , y , l + 1);
if (x < n-1 && map[y][x + 1]) DFS(x +1, y , l + 1);
map[y][x] = 1;
}
int main()
{
int i, j;
scanf("%d", &n);
min = n * n; // 모든 경로를 돌아다녀도 n * n이니, 이를 최소값으로 지정해둔다
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &map[i][j]);
DFS(0, 0, 1); // DFS 시작!
printf("최단 거리: %d\n", min);
return 0;
}
===================================================================================================
#include <stdio.h>
int n; // 입력되는 정점의 최댓값
int rear, front; // 전단과 후단을 나타내는 변수
int map[30][30], queue[30], visit[30]; // 인접 행렬과 큐와 방문 배열
void BFS(int v)
{
int i;
visit[v] = 1; // 정점 v를 방문했다고 표시
printf("%d에서 시작\n", v);
queue[rear++] = v; // 큐에 v를 삽입하고 후단을 1 증가시킴
while (front < rear) // 후단이 전단과 같거나 작으면 루프 탈출
{
// 큐의 첫번째에 있는 데이터를 제외하고 제외된 값을 가져오며, 전단 1 증가
v = queue[front++];
for (i = 1; i <= n; i++)
{
// 정점 v와 정점 i가 만나고, 정점 i를 방문하지 않은 상태일 경우
if (map[v][i] == 1 && !visit[i])
{
visit[i] = 1; // 정점 i를 방문했다고 표시
printf("%d에서 %d로 이동\n", v, i);
queue[rear++] = i; // 큐에 i를 삽입하고 후단을 1 증가시킴
}
}
}
}
int main()
{
int start; // 시작 정점을 나타내는 변수
int v1, v2;
scanf("%d%d", &n, &start);
while (1)
{
scanf("%d%d", &v1, &v2);
if (v1 == -1 && v2 == -1) break;
map[v1][v2] = map[v2][v1] = 1;
}
BFS(start); // BFS 시작!
return 0;
}
===================================================================================================
#include <stdio.h>
int n, cnt; // 맵의 크기와 카운트 변수
int map[10][10]; // 맵을 나타내는 2차원 배열
int x[100], y[100], l[100]; // 좌표와 길이를 담을 배열
// 큐에 좌표 정보와 길이를 삽입하는 함수
void enqueue(int _x, int _y, int _l)
{
x[cnt] = _x;
y[cnt] = _y;
l[cnt] = _l;
cnt++;
}
void BFS(int _x, int _y)
{
int pos = 0;
// 시작점의 좌표 정보와 길이를 큐에 삽입한다
enqueue(_x, _y, 1);
// 더 이상 방문할 지점이 없거나, 도착 지점에 도착하면 루프를 탈출한다
while (pos < cnt && (x[pos] != n - 1 || y[pos] != n - 1))
{
// 두 번 방문하게 하면 안되므로, 이미 지나갔다는 표시를 해둔다
map[y[pos]][x[pos]] = 0;
// 위로 갈 수 있다면, 위 지점의 좌표 정보와 길이를 큐에 삽입한다
if (y[pos] > 0 && map[y[pos] - 1][x[pos]] == 1)
enqueue(x[pos], y[pos] - 1, l[pos] + 1);
// 아래로 갈 수 있다면, 아래 지점의 좌표 정보와 길이를 큐에 삽입한다
if (y[pos] < n - 1 && map[y[pos] + 1][x[pos]] == 1)
enqueue(x[pos], y[pos] + 1, l[pos] + 1);
// 왼쪽으로 갈 수 있다면, 왼쪽 지점의 좌표 정보와 길이를 큐에 삽입한다
if (x[pos] > 0 && map[y[pos]][x[pos] - 1] == 1)
enqueue(x[pos] - 1, y[pos], l[pos] + 1);
// 오른쪽로 갈 수 있다면, 오른쪽 지점의 좌표 정보와 길이를 큐에 삽입한다
if (x[pos] < n - 1 && map[y[pos]][x[pos] + 1] == 1)
enqueue(x[pos] + 1, y[pos], l[pos] + 1);
// 큐의 다음 순서의 지점을 방문한다
pos++;
}
// cnt가 pos보다 크다면, 도착 지점에 무사히 도착한 것이라고 말할 수 있다.
// 위의 반복문은 도착점에 도착하게 되면 루프를 바로 빠져나오기 때문에,
// 길이를 삽입하는 큐의 마지막 요소가 최단 경로의 길이라고 할 수 있다.
if (pos < cnt)
printf("최단 경로 길이: %d\n", l[pos]);
}
int main()
{
int i, j;
scanf("%d", &n);
min = n * n;
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &map[i][j]);
BFS(0, 0); // BFS 시작!
return 0;
}
=================
#include<stdio.h>
int N;
int scan[30][30];
int Ndanji = 2;
int sol[1000] = { 0, };
int cnt = 1;
void danji(int x, int y)
{
scan[x][y] = Ndanji;
if (scan[x][y + 1] == 1) { cnt++; danji(x, y + 1); }
if (scan[x][y - 1] == 1) { cnt++; danji(x, y - 1); }
if (scan[x - 1][y] == 1) { cnt++; danji(x - 1, y); }
if (scan[x + 1][y] == 1) { cnt++; danji(x + 1, y); }
}
void main()
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
scanf("%1d", &scan[i][j]);
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (scan[i][j] == 1)
{
danji(i, j);
sol[Ndanji] = cnt;
Ndanji++;
cnt = 1;
}
}
}
int tmp;
for (int i = 0; i < Ndanji; i++)
{
for (int j = 0; j < Ndanji -1-i; j++)
{
if (sol[j] > sol[j + 1])
{
tmp = sol[j];
sol[j] = sol[j+1];
sol[j+1] = tmp;
}
}
}
printf("%d\n", Ndanji-2);
for (int i = 2; i < Ndanji; i++)
{
printf("%d\n", sol[i]);
}
}
| 순열, 중복순열, 조합, 중복조합 (0) | 2016.08.06 |
|---|---|
| 정올 지하철 (0) | 2016.07.23 |
| 공부 순서 (0) | 2016.06.13 |
| bubble sort (0) | 2016.03.12 |
전형적인 DFS인 단지번호 붙이기는 DFS 로직만 알고 있다면 쉽게 접근할 수 있다.
단지번호 붙이기는 그냥 숫자만 올리고, 정렬하는 것만 유의하면 된다.
특히 bubble sort를 진행할 때 어떤 블로그들에선 완전히 잘못된 내용으로 접근하는 경우가 있다. 비교를 정말 쓸데 없는 부분까지 하는경우가 있는데,
https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC에 나와있는 바처럼 짧게 기술할 수 있다.
암튼 결론은 버킹검
| DFS 정복!! 레벨 별 (0) | 2016.06.22 |
|---|---|
| 예산 관리 (0) | 2016.06.18 |
| 정올 더하기 (0) | 2016.06.17 |
| NQueen - 정올 1889번 (0) | 2016.02.16 |
| 단지번호 붙이기 (0) | 2016.02.14 |
정올 1889번 NQueen문제의 답
http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1162&sca=3030
backtracking을 활용한 것이다.
backtracking이란.. dfs를 통해 구현하는 중에 가지치기를 진행하는 수법이라고 한다.
#include <stdio.h>
#include <stdlib.h> //abs 함수를 사용하기 위해서임
int promising(int); // 할만한지 안한지 체크하는 함수.
int n;
int col[255] = { 0, }; // 행에 놓이는 값. 예를 들어 col[1] = 5라면 2번째 에는 5번째에 있다는 내용임
int cnt =0; // 해결되는 값
void queens(int i) {
if (promising(i))
{
if (i == n)
{
cnt++; // 총 개수를 구함
}
else
{
for (int j = 1; j <= n; j++) {
col[i + 1] = j;
queens(i + 1);
}
}
}
}
int promising(int i) { // 직선, 대각선으로 만나는지 검사
int k = 1, promising = 1;
while (k < i && promising) {
if (col[i] == col[k] || abs(col[i] - col[k]) == abs(i - k)) //직선이나 대각선상에 있는가를 검사
{
promising = 0;
}
k++;
}
return promising;
}
int main() {
scanf("%d", &n);
queens(0);
printf("%d", cnt);
}
| DFS 정복!! 레벨 별 (0) | 2016.06.22 |
|---|---|
| 예산 관리 (0) | 2016.06.18 |
| 정올 더하기 (0) | 2016.06.17 |
| 단지번호 붙이기 - 정올 1695번 (2) | 2016.02.25 |
| 단지번호 붙이기 (0) | 2016.02.14 |
재작년 10월엔가 찾아갔던 에스토니아 탈린.
헬싱키에서 배를 타고 몇시간만 가면 탈린이 나온다.
백야 즈음해서 간지라.. 날씨가 너무나 좋았다.
정말 사랑스럽고 또 사랑스러웠던 하루였다.
밤새 술을 마셔도 또 아침이 오니까.. 이 얼마나 행복했을꼬!!!
출장이후에 이곳 에스토니아에 대한 관심이 부쩍 늘어났다.
파노라마로 찍은 사진... 진짜 아름답다. 또 가고 싶다.
인터넷에서 찾아본 three drakon의 수프가 기억에 남는다.
엄청 맛있다. 마치 유럽 중세시장의 어둑어둑한 상점에서 먹는 느낌이다.
음; 특히 남자라면 von krahli는... 꼭 가봐야할 것같다. 이 곳의 점원들이 모두 엄청난 미녀이기 때문이다.;;;;
1년에 한 번즈음 볼 수 있는 미녀를 한번에 다봤다고 생각해야하나... -_-;
아쉽게도 용기가 없어 사진찍지는 못 ㅡㅜ함
이곳에서 제공하는 스테이크도 꽤 맛있었다. 오리고기로 기억..
단지번호 붙이기
#include <stdio.h>
/*
7
0 1 1 0 1 0 0
0 1 1 0 1 0 1
1 1 1 0 1 0 1
0 0 0 0 1 1 1
0 1 0 0 0 0 0
0 1 1 1 1 1 0
0 1 1 1 0 0 0
*/
#include<stdio.h>
int N;
int map[100][100] = { 0, };
void dfs(int sero, int garo, int cnt)
{
map[sero][garo] = cnt;
if (sero - 1 >= 0 && map[sero - 1][garo] == 1) {
dfs(sero - 1, garo, cnt); }
if (sero + 1 < N && map[sero + 1][garo] == 1) {
dfs(sero + 1, garo, cnt); }
if (garo - 1 >= 0 && map[sero][garo - 1] == 1) {
dfs(sero, garo - 1, cnt); }
if (garo + 1 < N && map[sero][garo + 1] == 1) {
dfs(sero, garo + 1, cnt); }
}
void main()
{
freopen("input.txt", "r", stdin);
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
scanf("%1d", &map[i][j]);
}
}
int cnt = 1;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (map[i][j] == 1)
{
cnt++;
dfs(i, j, cnt);
}
}
}
int Area[100] = { 0, };
int tmp = cnt - 1;
int k = 2;
for (int i = 0; i<N; i++)
{
for (int j = 0; j<N; j++)
{
if (map[i][j])
{
Area[map[i][j] - 2]++;
}
}
}
for (int i = 0; i< cnt -2; i++)
{
for (int j = 0; j< cnt-2-i; j++)
{
if (Area[j] > Area[j + 1])
{
int tmp = Area[j + 1];
Area[j + 1] = Area[j];
Area[j] = tmp;
}
}
}
printf("%d\n", cnt-1);
for (int i = 0; i < cnt - 1; i++)
{
printf("%d\n", Area[i]);
}
}
| DFS 정복!! 레벨 별 (0) | 2016.06.22 |
|---|---|
| 예산 관리 (0) | 2016.06.18 |
| 정올 더하기 (0) | 2016.06.17 |
| 단지번호 붙이기 - 정올 1695번 (2) | 2016.02.25 |
| NQueen - 정올 1889번 (0) | 2016.02.16 |
우선 http://www.elinux.org/RPi_Bluetooth_LE 에서 참조했다.
가장 먼저 준비해야하는 사항은 Raspberry PI와 BLE 모듈이다.
특히 Raspberry 와 연결되는 BLE 모듈의 선택이 중요한데, CSR(회사이름)에서 만든 제품을 준비하는 것이 좋다고 한다.
CSR의 BLE모듈이 시장을 선점했나..
암튼, Raspberry PI에서 Bluez라고 하는 Bluetooth stack을 다운로드 받아주자.
중간에 rasbperry ssh가 계속 끊겨서 session keep alive 시간을 연장해주었다.
SSH serverWith administrator / root access, the option could just be disabled in the server. Set the related options in the global SSHd configuration file as the following, and restart the SSHd service. ClientAliveInterval 30 TCPKeepAlive yes ClientAliveCountMax 99999 In Linux, sudo service sshd restart - See more at: https://docs.oseems.com/general/application/ssh/disable-timeout#sthash.3h3oNIi2.dpuf |
참고하시고, 가던길 계속 가도록 하자..
Raspberry에서 bluetooth를 연계할 수 있도록 만들어주는 Bluez(http://www.bluez.org/)를 인스톨하자!!
현재 최신 버전은 5.3 버전이다.
크게 4단위로 구성된다.
1. 개발 Library를 다운로드 받자.
sudo apt-get install libdbus-1-dev libdbus-glib-1-dev libglib2.0-dev libical-dev libreadline-dev libudev-dev libusb-dev make
2. bluez 소스코드를 다운로드 받자.
mkdir -p BLE/bluepy
cd BLE/bluepy
wget https://www.kernel.org/pub/linux/bluetooth/bluez-5.30.tar.xz
tar xvf bluez-5.30.tar.xz
cd bluez-5.30
./configure --disable-systemd
make
4. 설치하자
sudo make install
자 여기까지만 하면 일단 준비가 완료가 된 것이나 마찬가지다.
CSR에서 만든 BLE 모듈을 준비하는 것이 가장 중요하다는 거~~~!!!!
Vi 에디터에서 HTML 같은 텍스트 파일을 열어보면 각 행의 끝에 ^M 이런 이상한 기호가 붙어 있는 경우가 있습니다. 캐럿 기호 + 대문자 M으로 되어 있습니다. 이것은 개행문자 즉 줄바꿈 문자가 깨진 흔적입니다. 주로, 같은 파일 안에 "유닉스 개행문자"와 "도스 개행문자"가 섞여 있을 때 이런 현상이 발생합니다. 다음은, 이 ^M 기호를 치환(바꾸기) 기능으로 지우는 방법입니다.
Vim 에서 Esc키를 한 번 눌러 명령어 모드로 나온 후, 다음의 정규식을 입력합니다. 복잡한 정규식은 아니고, 각행의 끝($)에 있는 ^M 기호를, 모두(g) 공백(//)으로 바꾸는(%s) 것입니다.
주의! 그런데 위의 정규식에서 빨간색으로 된 ^M 이라는 문자열을 직접 글자 그대로 타이핑하면 안됩니다. 반드시 키보드의 Ctrl+V 키와 Ctrl+M 키를 눌러서 간접적으로 입력해야 합니다. Ctrl키를 누른 상태에서 vm 이라는 2글자를 소문자로 연속으로 입력하면 됩니다.
그러면 이제 텍스트 파일의 모든 ^M 기호가 깨끗이 삭제되었을 것입니다. 파일은 유닉스 텍스트 Unix Text 로 변환됩니다.
데이터마이닝 기법 : 연관규칙의 탐사
(포항공대 전 치 혁 교수)
1. 서언
연관규칙(association rule)이란 간단히 말하면 데이터의 항목들 간의 조건-결과 식으로
표현되는 유용한 패턴을 말한다. 연관규칙의 탐사는 기업의 활동, 특히 마케팅에서 가장 널리 사용되고 있다. 예를 들면, 미국의
슈퍼마켓에서 목요일 기저귀를 사는 고객은 맥주도 동시에 구매한다는 연관성을 알아냈다고 한다. 이때, 조건은 ‘목요일, 기저귀’이며
결과는 ‘맥주’라 할 수 있다. 이와 같은 연관규칙의 탐사가 가능하게 된 것은 컴퓨터기술의 발전을 들 수 있겠다. 한 고객이
슈퍼마켓의 계산대에서 계산할 때 쇼핑카트에 담긴 물품들이 바코드를 통하여 컴퓨터에 데이터베이스 형태로 입력되고 이로부터 고객들의
구매행태를 분석할 수 있게 되었다.
위에서 언급한 데이터의 형태는 소위
바스켓(basket) 데이터라 한다. 이 때 한 고객, 즉 한 바스켓의 정보를 하나의 트랜잭션(transaction)이라 한다.
바스켓 형태의 데이터에서는 주로 트랜잭션 내의 연관성을 살펴보고자 하는 것으로, 수많은 트랜잭션을 분석하여 빈번히 나타나는 규칙을
찾아내는 것이다. 이렇게 찾아낸 규칙은 마케팅에 활용된다. 예를 들어, 위의 기저귀-맥주의 규칙을 활용하여 기저귀와 맥주를
가까운 곳에 진열함으로써 매출 신장을 기할 수 있다. 이와 같이 바스켓 데이터로부터 연관규칙을 탐사하는 것을
시장바구니분석(market basket analysis)이라 한다.
연관규칙의 탐사는 한 고객의 시간에 따른
구매정보를 활용하여 이루어지기도 한다. 예를 들면, 가전제품 대리점에서 고객별 시간별 구매제품의 데이터를 활용하여 ‘제품 A를
사는 고객은 추후에 제품 B도 구매한다’는 연관규칙을 이끌어낼 수 있을 것이다. 이와 같은 패턴을 얻어 제품 A를 구매하였으나
제품 B를 구매하지 않은 고객에게 판매활동을 할 수 있다. 이런 시간에 따른 고객데이터를 시퀀스(sequence) 데이터라 한다.
당
연한 사실이지만 탐사에서 도출된 연관규칙은 분명하고 유용한 것이어야 한다. 유용하다(useful)는 것은 새롭고도 실행가능하며
설명할 수 있는 것을 말한다고 하겠다. 이에 비해 사소한(trivial) 규칙이란 이미 잘 알려진 사실을 말한다. 예를 들면,
‘페인트를 사면 페인트 붓을 산다’ 는 규칙 같은 것이다. 또한, 설명할 수 없는 규칙은 데이터의 오류일 가능성도 있으며 마케팅에
활용할 수 없기 때문에 역시 유용하다고 볼 수 없다.
2. 연관규칙의 정의 및 성능척도
데이터베이스가 총 n개의 트랜잭션 데이터로 구성되며 전체 m개의 항목으로 구성된다고 하고 이를 I 라 하자. 연관규칙 R은 조건부와 결과부로 구성되며 항목집합인 X와 Y에 대하여 ‘X가 일어나면 Y 도 일어난다’는 의미로 다음과 같이 표현할 수 있다.
R : X ⇒ Y
여기서 X,Y⊆I 이고, X∩Y=Φ이어야 한다. 따라서 연관규칙을 탐사함은 적절한 항목집합 X와 Y를 선택하는 문제로 볼 수 있으며 이를 위해 몇 가지 척도를 고려하고 있다. 우선, 항목집합 X 및 규칙 R에 대한 지지도(support)는 각각 다음과 같이 정의된다.
supp(X) = 집합 X의 항목을 동시에 포함하는 트랜잭션 수의 전체 수(n)에 대한 비율
supp(R) = supp(X∪Y)
즉, 규칙 R에 대한 지지도는 집합 X 또는 집합 Y에 있는 항목을 동시에 포함하는 트랜잭션수의 비율을 나타낸다.
예 1. 다음과 같은 5개의 트랜잭션을 고려해 보자.
| 트랜잭션 |
항목 |
| 1 | b, c, g |
| 2 | a, b, d, e, f |
| 3 | a, b, c, g |
| 4 | b, c, e, f |
| 5 | b, c, e, f, g |
이때 전체 항목집합 I는 I = {a, b, c, d, e, f, g} 이다. 몇 가지 항목집합에
대한 지지도를 구하면 다음과 같다.
supp({a}) = 2/5 = 0.4, supp({b, c}) = 4/5 = 0.8
다음과 같은 규칙을 고려해 보자.
R: “항목 b와 항목 c가 일어나면, 항목 g도 일어난다”
이 때 규칙 R에 해당하는 항목집합 X와 Y는 다음과 같다.
X={b, c}, Y={g}.
이 경우 X 및 규칙 R에 대한 지지도는 각각 아래와 같이 산출된다.
supp(X) = supp({b, c}) = 0.8
supp(R) = supp({b, c, g}) = 3/5 = 0.6
연관규칙 R의 가치를 평가할 때 통상 다음과 같이 정의되는 신뢰도(confidence)를 사용한다.
conf(R)= supp(X∪Y)/supp(X)
이 신뢰도는 조건부 확률의 개념으로 집합 X(조건)가 발생한다고 할 때 집합 Y(결과)도 동시에
발생할 확률을 의미한다. 즉, 트랜잭션에 X의 항목들을 포함하는 경우 Y의 항목들도 동시에 포함할 확률을 나타내며, 신뢰도가 큰
규칙일수록 의미가 크다고 하겠다.
또한, 신뢰도 이외에 연관규칙의 개선도(lift or improvement)를 함께
사용하는데, 이는 결과가 단독으로 발생할 빈도에 대한 조건과 연계하여 결과가 발생할 가능성의 빈도의 비로 정의된다.
개선도가 1이 됨은 
가 성립하므로 항목 집합 X와 Y의 발생이 독립임을
의미한다고 하겠다. 그리고 개선도가 1 전후의 값에 따라 다음과 같은 해석을 할 수 있다.
- lift(R) > 1인 경우, X와 Y의 발생이 양의 상관관계
- lift(R) < 1인 경우, X와 Y의 발생이 음의 상관관계
따라서 개선도가 1보다 큰 규칙이야말로 우연한(랜덤한) 관계가 아닌 필연적 관계를 나타낸다고
하겠다.
3. 연관규칙의 탐사
연
관규칙의 탐사는 결국 신뢰도 또는 개선도가 높은 규칙 R을 트랜잭션 데이터로부터 도출하는 과정이다. 따라서 규칙이 R : X ⇒
Y의 형태일 때 적절한 항목집합 X와 Y를 찾는 것이라 할 수 있겠다. 그러나 모든 항목의 조합을 고려하여 성능이 좋은 규칙을
찾는 일은 쉬운 것이 아니므로 이를 위한 효율적인 알고리즘이 요구된다. 예로써 예 1.의 7개 항목으로 구성된 5건의 트랜잭션
데이터에 대하여 집합 X의 후보가 되는 경우수를 볼 때, 1개 항목으로 구성되는 경우가 7가지, 2개의 항목으로 구성되는 경우가
21가지, 3개의 항목으로 구성되는 경우가 35가지 등이 될 것이다.
연관규칙의 탐사를 위한 알고리즘으로 기본적이며 가장
널리 사용되는 것은 1994년에 Agrawal 및 Srikant가 발표한 Apriori 알고리즘으로 다음의 두 단계로 구성된다.
단계 1. 미리 결정된 최소지지도 smin 이상의 지지도를 갖는 모든 빈발 항목집합들(large itemsets)을 찾는다.
단계 2. 빈발 항목집합 L에 대한 부분집합 A를 고려한다. 미리 결정된 최소신뢰도 cmin에 대하여 supp(L)/supp(A) ≥ cmin 이면, R: A ⇒ (L-A) 형태의 규칙을 출력한다. 즉, 이 규칙의 지지도는 supp(R)=supp(L)이며, 신뢰도는 conf(R)=supp(L)/supp(A) 가 된다.
3.1. 빈발 항목집합 생성
빈발 항목집합을 도출하기 위하여 우선 하나의 항목으로 이루어지는 후보집합군(C1)을 형성하고
최소지지도 이상을 갖는 집합군(L1)을 생성한다. 다음으로 L1으로부터 두개의 항목으로 이루어지는 후보집합군(C2)를 만들고
최소지지도 이상을 갖는 집합군(L2)을 생성하며, 다시 L2로부터 세 항목으로 이루어지는 후보집합군(C3)과 빈발 항목집합군
L3를 만드는 등 이러한 과정을 더 이상 새로운 집합이 생성되지 않을 때까지 반복한다.
로부터 
를 생성할 때 접합(join)연산자(*)를 사용한다.
L1으로부터 C2를 만드는 경우에는 L1의 한 항목에 대한 모든 조합이 2-항목 집합인 C2가 될 것이다. 그러나 L2에서 두
집합의 조합은 최대 4개의 항목을 포함할 수 있으므로 C3를 형성할 때 L2의 집합 중 하나의 항목이 동일한 것들만 대상으로
하여야 한다. 마찬가지로 L3로부터 C4를 형성할 때는 L3의 집합 중 두개의 항목이 동일할 때 가능하게 된다. 예로써,
L2=[{a,b}, {a,c}, {b,d}]라 할 때 {a,b,c}와 {a,b,d}가 3-항목 집합의 후보가 될 것이다. 그러나,
C3를 구성할 때 {a,b,c}는 제외된다. 왜냐하면, {a,b,c}의 지지도는 {b,c}의 지지도 이하인데 {b,c}가 L2에
포함되지 않았다는 것은 이의 지지도가 최소지지도 미만이라는 것을 나타내기 때문이다. 이러한 과정은 Apriori 알고리즘 중
'apriori-gen' 함수에 의하여 수행된다.
예 2. (예 1.의 계속). 예 1.의 트랜잭션 데이터를 바탕으로 빈발 항목집합을 만들어보자. 우선, C1은 다음과 같다.
C1=[{a}, {b}, {c}, {d}, {e}, {f}, {g}]
최소 지지도를 0.4(5개의 트랜잭션 중 2개)라 하면 1-항목으로 이루어지는 빈발 항목집합군은 다음과 같다.
L1=[{a}, {b}, {c}, {e}, {f}, {g}]
2-항목 빈발집합의 후보 C2에 다시 최소지지도 0.4를 적용하면 L2는 다음과 같다.
L2=[{a,b}, {b,c}, {b,e}, {b,f}, {b,g}, {c,e}, {c,f}, {c,g}, {e,f}]
C3를 구성하기 위하여 L2의 집합에 접합연산자를 적용하면 다음과 같다.
C3=[{b,c,e}, {b,c,f}, {b,c,g}, {b,e,f}, {c,e,f}]
이 때 {a,b,c} 는 {a,c}가 L2에 포함되지 않았으므로 C3에 포함될 수 없음을 볼 수
있다.
C3의 모든 집합은 최소지지도 이상이므로 L3는 C3와 동일하다.
Apriori 알고리즘을 단계별로 정리하면 다음과 같다.
단계 0. 최소지지도 smin을 정한다.
k=1
C₁=[{i₁},{i₂},...,{im}]
L₁={c∈C₁| supp(c) ≥ smin
단계 1. k=k+1
Lk-1로부터 Ck 형성 (apriori-gen 함수)
단계 1-1. (join) Lk-1의 집합들을 접합하여 k- 항목 집합군을 형성한다.C= Lk-1 * Lk-1
단계 1-2. (prune) C의 (k-1)- 항목 부분집합이 Lk-1에 속하지 않을 때 이를 모두 제거한 후 Ck를 형성한다. Ck=Φ이면 Stop.
단계 2. Ck의 집합 중 지지도가 최소지지도 이상인 것을 모아 Lk를 생성한다.
Lk={c∈Ck | supp(c) ≥ smin}
3.2. 규칙의 탐사
앞에서 언급한 바와 같이 규칙의 탐사를 위하여 우선 도출된 빈발 항목집합 L 각각에 대한 부분집합
A를 고려한다. 여기서 L은 위의 L2, L3 등을 포함한다. 그리고, 미리 결정된 최소신뢰도 cmin에 대하여
supp(L)/supp(A) ≥ cmin 이면, R: A ⇒ (L-A) 형태의 규칙을 출력한다. 즉, 이 규칙의 신뢰도
conf(R)=supp(L)/supp(A) 가 cmin 이상 되도록 하는 것이다.
현실의 경우 결과부에 하나의 항목만을
포함시키는 규칙을 도출하는 것이 이의 적용성 때문에 널리 사용되나, Agrawal & Srikant (1994)의
알고리즘에는 모든 가능한 규칙을 보다 효율적으로 탐사하는 방법이 소개되고 있다.
예 3. 예 1.의 트랜젝션 데이터에 대하여 예 2.에서 구해진 빈발 항목집합군 중 집합 L={b,c,g}을 고려해 보자. 이 때 결과부에 1-항목을 포함하는 규칙의 후보와 이에 대응되는 신뢰도는 다음과 같다.
R1: {b,c}⇒{g} conf(R1)=0.6/0.8 = 0.75
R2: {b,g}⇒{c} conf(R2)=0.6/0.6 = 1
R3: {c,g}⇒{b} conf(R3)=0.6/0.6 = 1
따라서 최소신뢰도를 0.7이라 하면 R1, R2, R3 모두 최소신뢰도 이상이 된다.
4. 결언
