다섯 단계로 좁혀 갑니다
모든 조합을 늘어놓고 시작해 단계마다 걸러 냅니다.
항목 집합 구하기 — 있을 수 있는 조합을 모두 만든다
빈발 항목 집합 구하기 — 지지도로 자주 나오지 않는 조합을 버린다
연관성 분석하기 — 향상도로 우연히 겹친 것을 걸러 낸다
연관 규칙 구하기 — 신뢰도로 규칙에 방향을 붙인다
결과 활용하기 — 찾은 규칙으로 무엇을 할지 정한다
세 숫자가 하는 일이 각각 다릅니다
지지도 · 향상도 · 신뢰도는 셋 다 「연관의 세기」를 측정하는 것처럼 보이지만, 거르는 대상이 서로 다릅니다. 지지도는 드물어서 볼 값어치가 없는 것을, 향상도는 많이 팔려서 우연히 겹친 것을 걸러 냅니다. 신뢰도는 먼저 어느 쪽에서 어느 쪽으로 가는 규칙인지를 정하고, 그 값이 낮은 규칙을 걸러 내는 문턱으로도 쓸 수 있습니다. 순서대로 써야 뜻이 통합니다.
어느 날 점심시간에 나온 매점 영수증 10장을 씁니다. 항목은 삼각김밥 · 우유 · 컵라면 · 초콜릿 · 이온음료 다섯 가지입니다. 다섯 단계를 끝까지 손으로 계산해 볼 것입니다.
단계 1 — 조합을 모두 만듭니다
그리고 왜 다 만들면 안 되는지를 곧바로 알게 됩니다.
어떤 항목끼리 연관이 있는지 알려면 있을 수 있는 조합을 모두 살펴봐야 합니다. 이렇게 만든 항목들의 묶음 하나하나를 항목 집합이라고 합니다. 묶은 항목이 k개인 집합들을 모아 k-항목 후보 집합이라고 부릅니다.
| 후보 집합 | 어떤 것들인가 | 개수 |
|---|---|---|
| 1-항목 | {삼각김밥}, {우유}, {컵라면}, {초콜릿}, {이온음료} | 5 |
| 2-항목 | {삼각김밥, 우유}, {삼각김밥, 컵라면}, {컵라면, 이온음료}… 두 개씩 고른 모든 짝 | 10 |
| 3-항목 | {삼각김밥, 우유, 초콜릿}, {컵라면, 이온음료, 초콜릿}… 세 개씩 고른 모든 묶음 | 10 |
| 4-항목 | 다섯 중 넷을 고르는 묶음. 하나씩 빼는 것과 같다 | 5 |
| 5-항목 | 다섯을 모두 담은 묶음 하나 | 1 |
| 합계 | 항목이 다섯 개일 때 만들 수 있는 항목 집합 | 31 |
합계 31은 그냥 나온 숫자가 아닙니다. 항목 하나하나에 대해 「넣는다 / 안 넣는다」 두 가지를 정하면 되므로, 다섯 항목이면 2를 다섯 번 곱한 32가지가 됩니다. 여기서 아무것도 안 넣은 경우 하나를 빼면 31입니다. 그래서 항목이 하나 늘 때마다 조합의 수는 두 배 남짓이 됩니다(31에서 63으로).
항목이 조금만 늘어도 감당이 안 됩니다
| 항목 수 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 항목 집합 수 | 1 | 3 | 7 | 15 | 31 | 63 | 127 | 255 |
마트라면 어떻게 될까요?
항목이 8개일 때 이미 255가지입니다. 30개면 10억 가지가 넘습니다. 큰 마트는 취급 상품이 수만 가지입니다. 전부 세어 보는 것은 어떤 컴퓨터로도 불가능합니다. 그래서 지지도로 가장 먼저 하는 일이 「버리는 일」입니다.
단계 2 — 지지도로 걸러 냅니다
열 장 중 몇 장에 나왔나를 세는 것이 전부입니다.
지지도(support)
지지도 = 그 항목 집합이 들어 있는 트랜잭션 수 ÷ 전체 트랜잭션 수
얼마나 자주 나오는가를 나타내는 비율입니다. 0과 1 사이의 값이고, 클수록 자주 나온다는 뜻입니다. 백분율로 적기도 합니다.
먼저 항목 하나씩
| 항목 | 나온 트랜잭션 | 횟수 | 지지도 |
|---|---|---|---|
| 삼각김밥 | T1, T2, T3, T4, T5 | 5 | 0.5 |
| 컵라면 | T3, T5, T6, T8, T9 | 5 | 0.5 |
| 초콜릿 | T2, T4, T7, T9, T10 | 5 | 0.5 |
| 우유 | T1, T2, T6, T7 | 4 | 0.4 |
| 이온음료 | T3, T8, T9 | 3 | 0.3 |
짝을 이룬 지지도 — 눈으로 세어 봅시다
{컵라면, 이온음료}가 둘 다 들어 있는 트랜잭션은 몇 장일까요? 아래 열 칸이 영수증 열 장입니다.
색칠된 세 장입니다. 그러므로 지지도({컵라면, 이온음료}) = 3 ÷ 10 = 0.3입니다.
열 가지 짝을 모두 구하면
| 항목 집합 | 둘 다 들어 있는 트랜잭션 | 지지도 | 최소 0.2 |
|---|---|---|---|
| {컵라면, 이온음료} | T3, T8, T9 | 0.3 | 통과 |
| {삼각김밥, 우유} | T1, T2 | 0.2 | 통과 |
| {삼각김밥, 컵라면} | T3, T5 | 0.2 | 통과 |
| {삼각김밥, 초콜릿} | T2, T4 | 0.2 | 통과 |
| {우유, 초콜릿} | T2, T7 | 0.2 | 통과 |
| {삼각김밥, 이온음료} | T3 | 0.1 | 탈락 |
| {우유, 컵라면} | T6 | 0.1 | 탈락 |
| {컵라면, 초콜릿} | T9 | 0.1 | 탈락 |
| {초콜릿, 이온음료} | T9 | 0.1 | 탈락 |
| {우유, 이온음료} | 없음 | 0.0 | 탈락 |
최소 지지도와 빈발 항목 집합
최소 지지도는 「이만큼은 나와야 살펴볼 값어치가 있다」고 정해 두는 문턱입니다. 여기서는 0.2로 정했습니다. 이 문턱을 넘은 항목 집합을 빈발 항목 집합이라고 부릅니다. 열 가지 중 다섯 가지가 남았습니다.
문턱은 사람이 정합니다. 높이면 볼 것이 적어져 편하지만 드물어도 값진 규칙을 놓치고, 낮추면 쓸데없는 조합까지 남습니다. 군집의 k와 마찬가지로 목적이 정하는 숫자입니다.
세 항목 묶음은 어떻게 될까요? {삼각김밥, 우유, 초콜릿}과 {삼각김밥, 컵라면, 이온음료}, {컵라면, 이온음료, 초콜릿}이 각각 한 장씩 나와 지지도가 모두 0.1입니다. 나머지 일곱 묶음은 한 장도 없어 0입니다. 세 항목 빈발 집합은 하나도 없으므로 여기서 멈춥니다. 항목을 하나 더 넣으면 조건이 더 까다로워질 뿐이라, 조합을 더 키워 봐야 지지도는 커질 수 없기 때문입니다. 그래서 문턱을 못 넘은 짝을 품은 묶음은 세어 보지 않고 버려도 됩니다.
남은 다섯 짝 중 {삼각김밥, 우유}를 보세요. 삼각김밥은 열 장 중 다섯 장, 우유는 네 장에 나오는 잘 팔리는 물건입니다. 둘이 두 장에서 겹친 것이 정말 서로 얽혀 있어서일까요, 아니면 둘 다 흔해서 저절로 겹친 것일까요?
단계 3 — 향상도로 우연을 걸러 냅니다
「서로 상관없다면 이만큼 겹쳤을 텐데」와 비교합니다.
둘 다 흔한 물건이면 아무 관계가 없어도 자주 겹칩니다. 그러니 겹친 횟수만 봐서는 안 되고, 「서로 상관이 없었다면 얼마나 겹쳤을까」와 비교해야 합니다.
향상도(lift)
향상도(A, B) = 지지도(A, B) ÷ (지지도(A) × 지지도(B))
분모의 지지도(A) × 지지도(B)가 「둘이 서로 상관없다면 이만큼 겹쳤을 것」이라는 예상값입니다. 실제로 겹친 정도를 이 예상값으로 나눈 것이 향상도입니다.
향상도 > 1
예상보다 더 자주 겹쳤다. 서로 얽혀 있다
향상도 = 1
예상한 딱 그만큼 겹쳤다. 서로 관계없다
향상도 < 1
예상보다 덜 겹쳤다. 오히려 따로 팔린다
빈발 항목 집합 다섯 가지의 향상도
| 항목 집합 | 지지도 | 상관없었다면 (지지도 곱) | 향상도 | 판정 |
|---|---|---|---|---|
| {컵라면, 이온음료} | 0.3 | 0.5 × 0.3 = 0.15 | 2.0 | 연관 있다 |
| {삼각김밥, 우유} | 0.2 | 0.5 × 0.4 = 0.20 | 1.0 | 관계없다 |
| {우유, 초콜릿} | 0.2 | 0.4 × 0.5 = 0.20 | 1.0 | 관계없다 |
| {삼각김밥, 컵라면} | 0.2 | 0.5 × 0.5 = 0.25 | 0.8 | 따로 팔린다 |
| {삼각김밥, 초콜릿} | 0.2 | 0.5 × 0.5 = 0.25 | 0.8 | 따로 팔린다 |
지지도만 봤다면 속을 뻔했습니다
{삼각김밥, 우유}는 지지도 문턱을 넘어 살아남았습니다. 그런데 향상도가 정확히 1.0입니다. 삼각김밥이 다섯 장, 우유가 네 장에 나오니 아무 관계가 없어도 두 장에서는 겹칠 만합니다. 실제로 딱 두 장에서 겹쳤습니다. 우연히 겹칠 만큼만 겹친 것입니다.
반면 {컵라면, 이온음료}는 상관없었다면 한 장 반쯤 겹쳤을 텐데 세 장에서 겹쳤습니다. 예상의 두 배입니다. 지지도로 살아남은 다섯 짝 중 예상보다 자주 겹친 것은 이것 하나뿐입니다.
「많이 함께 팔린다」와 「얽혀 있다」는 다른 말입니다. 지지도는 앞의 것을, 향상도는 뒤의 것을 측정합니다. 그래서 두 지표를 차례로 써야 합니다.
향상도에는 방향이 없습니다. 식을 보면 A와 B를 바꿔 넣어도 값이 똑같습니다. 그래서 향상도는 「둘이 얽혀 있다」까지만 말해 줄 뿐 「무엇을 사면 무엇을 사는가」는 말해 주지 못합니다. 그 일은 신뢰도가 맡습니다.
단계 4 — 신뢰도로 방향을 붙입니다
여기서 비로소 「A를 사면 B도 산다」는 규칙이 나옵니다.
신뢰도(confidence)
신뢰도(A → B) = A와 B가 함께 든 트랜잭션 수 ÷ A가 든 트랜잭션 수
A가 든 트랜잭션 가운데 B도 든 트랜잭션의 비율입니다. 영수증 한 장을 손님 한 명으로 치면 「A를 산 손님 중 B도 산 손님의 비율」입니다. A가 든 트랜잭션만 놓고 보므로 분모가 전체가 아니라 A의 개수입니다. 여기가 지지도와 다른 점입니다.
이렇게 화살표로 쓴 A → B를 연관 규칙이라고 하고, 앞의 A를 선행, 뒤의 B를 후행이라고 부릅니다.
방향을 바꾸면 값이 달라집니다
향상도로 살아남은 {컵라면, 이온음료}에 방향을 붙여 봅시다.
| 연관 규칙 | 계산 | 신뢰도 | 읽는 법 |
|---|---|---|---|
| 이온음료 → 컵라면 | 둘 다 3장 ÷ 이온음료 3장 | 1.00 | 이온음료를 산 손님은 모두 컵라면도 샀다 |
| 컵라면 → 이온음료 | 둘 다 3장 ÷ 컵라면 5장 | 0.60 | 컵라면을 산 손님 중 10명에 6명이 이온음료도 샀다 |
같은 짝인데 왜 값이 다를까요?
분모가 다르기 때문입니다. 겹친 세 장은 그대로인데, 이온음료는 세 장에만 있고 컵라면은 다섯 장에 있습니다. 그래서 이온음료 쪽에서 보면 세 장 중 세 장 모두, 컵라면 쪽에서 보면 다섯 장 중 세 장이 되는 것입니다. 지지도와 향상도는 방향이 없었지만 신뢰도는 방향이 있습니다. 값이 큰 「이온음료 → 컵라면」 쪽이 더 믿을 만한 규칙입니다.
향상도가 1.0이었던 {삼각김밥, 우유}의 신뢰도를 두 방향 모두 구해 보세요. 값이 0.4와 0.5로 그럭저럭 나옵니다. 신뢰도만 보고 규칙을 골랐다면 어떤 일이 벌어졌을까요?
단계 5 — 그래서 무엇을 할까요
규칙을 찾은 것으로 끝이 아닙니다. 어디에 쓸지 정해야 합니다.
매점 데이터에서 찾아낸 규칙
이온음료를 산 손님은 컵라면도 산다. 지지도 0.3 · 향상도 2.0 · 신뢰도 1.00입니다.
진열 바꾸기
두 물건을 가까이 놓습니다. 손님이 하나를 집었을 때 다른 하나가 눈에 들어오게 하는 것입니다.
묶어 팔기
세트로 만들어 조금 싸게 내놓습니다. 어차피 함께 사는 손님이 많으니 둘 다 팔릴 가능성이 커집니다.
재고 맞추기
하나가 동나면 다른 하나도 덜 팔릴 수 있습니다. 같이 채워 두어야 합니다.
신뢰도가 높은 쪽이 늘 쓸모 있을까요?
이온음료 → 컵라면의 신뢰도는 1.00입니다. 가장 믿을 만한 규칙입니다. 그런데 이온음료를 사는 손님은 이미 모두 컵라면을 삽니다. 그 손님들에게 컵라면을 권해 봐야 더 팔 것이 없습니다.
거꾸로 컵라면 → 이온음료는 신뢰도가 0.60뿐입니다. 그러나 이 말은 컵라면을 산 다섯 명 중 두 명은 아직 이온음료를 안 샀다는 뜻입니다. 그 두 명이 이온음료를 더 팔 수 있는 손님입니다. 그래서 컵라면 코너에 이온음료를 놓는 편이 실제로는 더 이득일 수 있습니다.
숫자가 큰 규칙과 써먹을 데가 있는 규칙은 다릅니다.
영수증 열 장으로 매점 운영을 바꿀 수는 없습니다
우리가 쓴 데이터는 열 장뿐입니다. 한두 장만 달랐어도 지지도와 향상도가 크게 흔들렸을 것입니다. 실제 분석에는 이보다 훨씬 많은 영수증을 씁니다. 계산 방법은 똑같지만, 적은 데이터에서 나온 규칙을 그대로 믿으면 안 됩니다.
세 숫자를 한자리에 놓고
이름이 비슷해 헷갈립니다. 분모가 무엇인지로 구별하세요.
| 지표 | 분자 | 분모 | 방향 | 무엇을 답하나 |
|---|---|---|---|---|
| 지지도 | 둘 다 든 트랜잭션 수 | 전체 트랜잭션 수 | 없음 | 얼마나 자주 함께 나오나 |
| 향상도 | 지지도(A, B) | 지지도(A) × 지지도(B) | 없음 | 겹친 것이 우연인가 아닌가 |
| 신뢰도 | 둘 다 든 트랜잭션 수 | A가 든 트랜잭션 수 | 있음 | A를 사면 B도 살 가능성이 얼마나 되나 |
지지도와 신뢰도의 차이
분자는 똑같습니다. 둘 다 「함께 든 트랜잭션 수」입니다. 분모만 다릅니다. 지지도는 전체로, 신뢰도는 A가 든 것으로 나눕니다. 그래서 신뢰도는 늘 지지도보다 크거나 같습니다.
왜 셋을 다 볼까
지지도가 낮으면 어쩌다 한 번이라 믿을 수 없고, 향상도가 1 언저리면 우연이라 뜻이 없으며, 신뢰도를 안 보면 어느 쪽으로 권해야 할지 모릅니다. 하나라도 빠지면 판단이 어긋납니다.
직접 채워 봅시다
본문에서 다루지 않은 {우유, 초콜릿}에 대해 세 숫자를 모두 구해 보세요. 항목마다 나온 트랜잭션은 『지지도로 걸러 냅니다』 절의 「먼저 항목 하나씩」 표에 있습니다.
| 구할 값 | 계산 과정 | 값 |
|---|---|---|
| 지지도 | ||
| 향상도 | ||
| 신뢰도(우유 → 초콜릿) | ||
| 신뢰도(초콜릿 → 우유) |
다 풀고 나서 열어 보세요
우유와 초콜릿이 함께 든 것은 T2와 T7 두 장이므로 지지도는 0.2, 향상도는 0.2 ÷ (0.4 × 0.5) = 1.0, 신뢰도는 우유 → 초콜릿이 2 ÷ 4 = 0.5, 초콜릿 → 우유가 2 ÷ 5 = 0.4입니다. 향상도가 1.0이므로 이 짝은 우연히 겹친 것입니다. 신뢰도가 0.5로 제법 커 보여도 규칙으로 쓸 수 없습니다.
핵심 정리
항목 집합
itemset
- 있을 수 있는 모든 조합을 만든 것
- 항목이 하나 늘 때마다 조합은 두 배 남짓
- 그래서 버리는 일이 먼저다
지지도
support
- 함께 든 트랜잭션 수 ÷ 전체 트랜잭션 수
- 최소 지지도를 넘으면 빈발 항목 집합
- 문턱은 사람이 정한다
- 항목을 더 넣으면 지지도는 커지지 않으므로, 문턱을 못 넘은 짝을 품은 묶음은 세지 않고 버린다
향상도
lift
- 지지도(A, B) ÷ 두 지지도의 곱
- 1보다 크면 연관, 1이면 우연, 1보다 작으면 따로
- 많이 팔려서 겹친 것을 걸러 낸다
신뢰도와 연관 규칙
confidence · association rule
- 함께 든 트랜잭션 수 ÷ A가 든 트랜잭션 수
- 방향이 있다. A → B와 B → A의 값이 다르다
- 값이 큰 규칙이 늘 써먹기 좋은 것은 아니다
확인 퀴즈
배운 내용을 확인해 봅시다.
트랜잭션 20장 중 12장에 {빵, 우유}가 함께 들어 있었습니다. 지지도는?
최소 지지도를 정하는 까닭으로 알맞은 것은?
두 항목의 향상도가 정확히 1로 나왔습니다. 무슨 뜻인가?
같은 짝인데 신뢰도가 방향에 따라 다른 까닭은?
지지도가 문턱을 넘었지만 향상도가 1인 짝을 어떻게 해야 하나?