10차시 영수증 수천 장에서 찾은 가장 강한 규칙 — 그것은 왜 뻔할까

학습 목표

개념에서
상품이 늘면 볼 묶음이 폭발한다는 것과, 최소 지지도·가지치기가 그것을 어떻게 줄이는지 설명할 수 있다.
손으로
송장 4,000장에서 규칙을 뽑아 향상도 위 목록을 만들고, 뻔한 규칙을 걷어 내고 다시 읽을 수 있다.
확인에서
규칙 하나를 발견인지 상식인지 판정하고, 담당자에게 추천할 규칙과 그 까닭을 적을 수 있다.

여는 장면 · 5분

왜 우리 동네 편의점 영수증으로 하지 않을까

9차시에서는 매점 영수증 24장을 손으로 세었습니다. 오늘은 수천 장으로 갑니다. 그런데 이 교과서는 우리나라 편의점·마트의 장바구니 자료를 쓰지 못합니다. 공개된 것이 없기 때문이에요. 왜 없을까요?

대신 쓰는 것은 영국의 한 온라인 선물가게가 남긴 1년 치 거래입니다. 오른쪽은 그 가게의 송장 한 장 — 상품 11개가 적혀 있고, 이 한 장만으로 쌍 55개가 만들어집니다. 송장이 4,000장이면 어떻게 될까요?

송장 한 장상품 11개

자료: UCI Online Retail · 송장 536415(2010-12-01) — 교과서가 읽는 retail_baskets.csv에 든 그대로

표 1상품이 늘면 볼 묶음은 이렇게 늘어난다쌍 = m(m−1)/2 · 셋 묶음 = m(m−1)(m−2)/6

상품 가짓수 m	쌍	셋 묶음	어디쯤
10	45	120	9차시 매점
50	1,225	19,600	작은 가게
100	4,950	161,700	—
120	7,140	280,840	오늘 쓰는 자료
1,000	499,500	166,167,000	편의점 한 곳

상품이 열 배가 되면 쌍은 약 백 배, 셋 묶음은 약 천 배가 됩니다. 다 세어 보고 고르는 방법은 어느 순간 쓸 수 없게 돼요. 자료: 두 조합 공식으로 계산 · 120개 줄은 코드 ①이 찍는 값과 같다

먼저 예측

송장 4,000장에서 향상도가 가장 높은 1위 쌍이 나옵니다. 그 두 상품은 어떤 사이일 것 같나요? 한 문장으로 적어 두세요 — "빵과 우유처럼 함께 쓰는 물건"처럼요. 3정거장 미션 ③에서 실제 1위와 맞대어 봅니다.

내 예측 한 문장 이 기기에만 저장돼요 · 선생님께 가지 않아요

체크포인트 1

상품이 120개면 쌍이 7,140개라는 것과, 1위 쌍이 무엇일지 내 예측 한 문장을 적어 두었다.

다음 정거장 · 개념 15분 →

개념 · 15분

규칙은 쏟아진다 — 문제는 '무엇을 한 상품으로 볼까'

2-1영수증 한 장은 한 사람의 기록이다

영수증 한 장은 한 사람이 언제 어디서 무엇을 샀는지의 기록입니다. 몇 장만 이어 붙여도 사람을 알아볼 수 있어요. 가게 쪽에서 보면 무엇이 무엇과 함께 팔리는지가 곧 영업 비밀입니다. 그래서 공개된 장바구니 자료는 아주 드물고, 있는 것도 가게 이름과 고객을 지운 외국 연구용 자료뿐이에요.

Ⅰ-7 에서 가져옴지운 것 같아도 드문 조합 하나로 사람이 다시 드러날 수 있습니다(재식별). 장바구니 자료를 공개할 때 날짜를 달 단위로 뭉개거나 드문 상품을 지우는 까닭입니다.

오늘 쓰는 UCI Online Retail은 영국 온라인 선물가게의 2010년 12월 ~ 2011년 12월 거래 54만 줄을 연구진이 고객 분석에 쓴 뒤 공개한 자료입니다(CC BY 4.0). 원장이 취소 송장을 빼고 영국 송장만 남긴 뒤 많이 팔린 상품 120개로 줄여 송장 4,000장짜리 파일로 구웠어요.

외국 자료라 상품도 명절도 우리와 다릅니다. 그러니 규칙의 '내용'은 우리 가게에 그대로 옮길 수 없습니다. 여기서 옮겨 오는 것은 내용이 아니라 방법과 함정이에요.

2-2조합 폭발 — 그래서 문턱을 둔다

상품이 m 개면 쌍은 m(m−1)/2, 세 개 묶음은 m(m−1)(m−2)/6 입니다(표 1). 다 볼 수 없으니 최소 지지도를 문턱으로 세워 "몇 번 이상 함께 나온 쌍만 보겠다"고 먼저 거릅니다. 문턱을 두 배로 올릴 때마다 남는 규칙은 3분의 1 아래로 줄어요(코드 ②).

문턱은 데이터가 정해 주지 않습니다. '몇 번 이상 함께 나와야 믿을까'라는 분석가의 선택이에요. 낮추면 읽을 수 없을 만큼 쏟아지고, 올리면 드물지만 값진 규칙이 사라집니다.

여기에 한 가지를 더 쓸 수 있습니다. 아프리오리 원리 — 쌍이 든 송장은 두 상품 각각이 든 송장의 일부이므로, 쌍의 지지도는 두 상품 각각의 지지도보다 클 수 없습니다. 혼자서도 문턱에 못 미치는 상품이 낀 쌍은 세어 볼 필요가 없어요. 이것을 가지치기라고 부릅니다.

그런데 이 자료에서는 가지치기가 한 개도 걸러 내지 못합니다. 원장이 많이 팔린 120개만 남겼기 때문에 가장 드문 상품도 송장의 3.4%에 들거든요(코드 ④). 문턱 0.05 까지 올려야 52개가 빠져 셀 쌍이 7,140에서 2,278로 줍니다. 가지치기는 '드문 것이 많을 때' 효과를 냅니다.

도구 이야기이 단원이 모델마다 꺼내 쓰던 scikit-learn 에는 연관 규칙이 없습니다. 세 자는 9차시 식 그대로 pandas 로 셉니다 — 한 도구가 모든 분석을 하지는 않아요(2차시 '도구마다 맞는 물음').

가지치기셀 쌍

문턱 0.01 → 드문 상품 0개문턱 0.05 → 52개

자료: 코드 ④가 찍는 값 — 7,140 → 2,278

2-3'향상도 > 1' 이 여기서는 거의 거르지 않는다

9차시에서 향상도 1은 '관계없음'의 기준선이었습니다. 1보다 크면 우연보다 자주 함께 나온다는 뜻이었지요. 그런데 이 가게에서 규칙 14,280개를 세어 보면 97.1%가 1을 넘습니다. 거의 전부예요.

까닭은 송장의 크기에 있습니다. 송장당 상품 수가 중앙값 4개 · 평균 7.0개 · 최대 87개로 제각각이라, 큰 송장 한 장이 수백 쌍을 한꺼번에 담습니다. 상품 31개 이상인 송장은 4,000장 가운데 109장뿐인데, 그 109장이 '함께' 237,603번 가운데 51.4%를 만들어요(그림 1).

그래서 이 자료에서 향상도 1은 기준선 노릇을 못 합니다. 같은 자를 써도 자료가 달라지면 기준선이 옮겨 간다 — 9차시가 가르친 전제('송장들이 서로 비슷하다')가 깨진 자리입니다.

그럴듯한 말

“향상도가 1보다 크니 이 둘 사이에는 관계가 있다.”

반만 맞다

데이터가 한 말

100.0%관계를 모두 지운 가짜 가게에서도
향상도가 1을 넘는 규칙의 비율

가짜 가게 = 송장마다 상품 수는 그대로 두고, 상품은 인기 비율대로 제비뽑기로 다시 담아 상품 사이의 관계를 모두 지운 가게입니다. 관계가 하나도 없는데 향상도는 거의 다 1을 넘어요(중앙값 2.48). 기준선은 자료의 모양이 정한다 — 1을 그냥 믿지 말고 대조군과 견줍니다.

자료: 코드 ⑥이 찍는 값 — 진짜 97.1% · 중앙값 2.30 / 가짜 100.0% · 중앙값 2.48

그림 1큰 송장 109장이 '함께'의 절반을 만든다가로 = 송장 한 장에 든 상품 수

송장 대부분은 작습니다(중앙값 4개). 그런데 상품 31개 이상인 109장이 쌍을 세는 일의 51.4%를 혼자 만들어요. 이 109장을 빼고 다시 세면 향상도가 1을 넘는 비율이 97.1%에서 75.0%로 떨어집니다. 자료: retail_baskets.csv 송장 4,000장(원장 계산) · 51.4% · 75.0%는 판 점검 출력값

2-4가장 강한 규칙은 대개 뻔하다 — 그리고 향상도에는 천장이 있다

이 가게는 같은 물건을 색·무늬별로 따로 팝니다. 찻잔세트(분홍) · 찻잔세트(초록) · 찻잔세트(장미)처럼요. 이 책에서는 그렇게 갈라 놓은 상품 하나하나를 조각이라고 부릅니다 — 괄호 앞이 품목, 괄호 안이 색·무늬입니다. 상품 120가지는 사실 품목 47가지가 조각으로 나뉜 것이에요.

향상도 위 8쌍을 뽑아 보면 7쌍이 같은 품목의 다른 조각입니다(코드 ③). 1위는 찻잔세트(분홍) & 찻잔세트(초록) — 향상도 13.0, 함께 든 송장 162장. 찻잔을 색깔별로 세트로 산다는 것은 발견이 아니라 상식이지요. 그러니 가장 센 규칙은 가게가 아니라 상품을 조각으로 나눠 적은 방식이 만든 것입니다.

뻔한 쌍을 치우는 길은 둘입니다. 걷어 내기는 세는 방식은 그대로 두고 목록에서 그 쌍만 빼는 일이고, 붙여 세기는 조각 여럿을 한 상품으로 세어 4,000장을 처음부터 다시 세는 일이에요. 둘은 다른 1위를 내놓습니다 — 어느 쪽을 쓸지, 무엇을 한 상품으로 볼지는 분석가가 정합니다.

그런데 같은 품목 217쌍을 걷어 내도 이번에는 같은 무늬 시리즈가 올라옵니다 — 머핀컵(빈티지성탄) & 종이냅킨(빈티지성탄) 12.1. 품목은 다르지만 크리스마스 한 벌로 묶여 파는 상품이에요. 이것을 두 번째 뻔함이라고 불러 둡시다.

왜 이런 쌍이 늘 위에 설까요. 향상도에는 천장이 있기 때문입니다. 함께 든 송장은 적은 쪽 상품의 장수를 넘을 수 없으므로, 한 쌍이 오를 수 있는 가장 큰 향상도는 1 ÷ (둘 중 더 흔한 상품의 지지도)예요. 드문 상품끼리일수록 천장이 높습니다. 조각으로 잘게 나눈 상품은 하나하나가 드물어지니, 조각 쌍은 애초에 높이 오를 수 있는 자리에 서 있는 셈입니다.

그림 2향상도의 천장 — 머핀컵(빈티지성탄) & 종이냅킨(빈티지성탄)송장 4,000장 기준

두 상품이 각각 159장 · 162장에 들어 있고 함께 든 것은 78장입니다. 함께는 적은 쪽 159장을 넘을 수 없으므로 천장은 4,000 ÷ 162 = 24.7, 실제 향상도는 12.11 — 천장의 절반쯤까지 올라온 쌍이에요. 자료: 원장 판 점검 출력 — 78장 · 12.11 · 천장 24.7

같아야 할 것 같은 두 숫자를 나란히 놓으면 오늘 배울 것이 한눈에 보입니다.

향상도 > 1 인 규칙의 비율 · 큰 송장을 빼면

97.1%송장 4,000장 전부

→

75.0%큰 송장 109장을 빼면

기준선을 밀어 올린 것은 큰 송장 109장이었다.

1위 향상도 · 세는 단위만 바꾸면

13.0조각 120개로 세면

→

5.2품목 47개로 붙여 세면

자료는 그대로인데 1위가 무너졌다 — 분석 단위.

머핀컵 & 종이냅킨 · 함께 든 송장과 향상도

78장조각끼리 · 향상도 12.1

인데

208장품목끼리 · 향상도 2.8

함께는 늘었는데 향상도는 내려앉았다 — 천장이 24.7에서 6.4로.

가지치기로 줄어드는 셀 쌍

7,140문턱 0.01 — 그대로

2,278문턱 0.05

드문 상품이 없으면 가지치기는 놀고 있다.

자료: 위 네 쌍의 숫자는 모두 3정거장 코드 ② · ③ · ④ · ⑤ · ⑥이 찍는 값이다.

규칙 하나를 읽는 네 물음 — 차례로

얼마나 자주함께 든 송장이 몇 장인가 — 지지도. 몇 장짜리 규칙인지 먼저 본다
어느 쪽으로A를 산 사람 중 B도 산 비율(신뢰도)은 방향마다 다르다
우연보다 몇 배향상도 — 그리고 천장과 나란히 본다. 천장이 높으면 오르기도 쉽다
새로운가같은 품목인가 · 같은 무늬인가 · 같은 철에 몰리는가. 셋 다 아니어야 발견이다

네 번째 물음은 계산으로 끝나지 않습니다. 이미 아는 사실인지 아닌지는 사람이 판단합니다 — 그 판단을 돕는 것이 다음 정거장의 「조각 붙이기 판」이에요.

체크포인트 2

조합 폭발 · 문턱 · 가지치기 · 조각과 천장을 말할 수 있다. 이제 4,000장을 직접 세어 1위를 본다.

다음 정거장 · 손으로 20분 →

손으로 · 20분

4,000장을 세어 1위를 뽑고, 그 1위를 무너뜨린다

실행 칸은 칸마다 혼자 돕니다 — 자료를 ../data/에서 다시 읽으니 앞 칸의 변수에 기대지 않아요. 처음 실행은 몇 초 걸립니다(고장이 아닙니다 — pandas 와 matplotlib 을 이 쪽에서 처음 준비합니다, 쪽마다 한 번).

송장 4,000장의 모든 쌍을 센다

4분

상품 120개로 만들 수 있는 쌍은 7,140개입니다(표 1). 그 가운데 실제로 한 번이라도 함께 나온 쌍은 몇 %쯤일까요? 절반? 8할? 숫자를 하나 짚어 두세요.

기본 코드 ①은 채워져 있습니다. 그대로 ▶ 실행해 송장 수 · 상품 수 · 송장당 상품 수와, 모든 쌍을 세는 데 걸린 시간을 확인하세요.

# ── 예측: 가능한 쌍 가운데 실제로 함께 나온 쌍은 몇 %쯤? ──
import time
from itertools import combinations
import pandas as pd
from pyodide.http import open_url

df = pd.read_csv(open_url("../data/retail_baskets.csv"))
장바구니 = df.groupby("InvoiceNo")["Description"].apply(set)
N = len(장바구니)
크기 = 장바구니.map(len)
m = df["Description"].nunique()
print(f"[1] 송장 {N:,}장 · 상품 {m}가지")
print(f"    송장당 상품 수 — 평균 {크기.mean():.1f}"
      f" · 중앙값 {크기.median():.0f} · 최대 {크기.max()}")

t = time.perf_counter()
쌍수 = {}
for 바구니 in 장바구니:          # 송장마다 모든 쌍을 센다
    for a, b in combinations(sorted(바구니), 2):
        쌍수[(a, b)] = 쌍수.get((a, b), 0) + 1
걸린 = 1000 * (time.perf_counter() - t)
가능 = m * (m - 1) // 2
print(f"[2] 상품 {m}개 → 만들 수 있는 쌍 {가능:,}개")
print(f"    실제로 함께 나온 쌍 {len(쌍수):,}개"
      f" · '함께' {sum(쌍수.values()):,}번 · {걸린:.0f} ms")

도전 combinations(sorted(바구니), 2) 의 2 를 3 으로 바꾸면 셋 묶음을 셉니다. 걸리는 시간이 얼마나 늘어나는지 재 보세요(표 1의 280,840이 이 셈의 크기입니다).

탐구 송장당 상품 수가 평균 7.0인데 중앙값이 4입니다. 이 두 숫자의 차이가 '가능한 쌍이 전부 나왔다'는 결과와 어떻게 이어지는지 생각해 보세요(그림 1).

만들 수 있는 쌍과 실제로 나온 쌍이 둘 다 7,140인 것을 보았다.
'함께' 센 횟수 237,603번이 쌍 7,140개에 골고루 퍼진 것이 아니라는 것을 그림 1에서 확인했다.

가능한 쌍 7,140개가 함께 나왔다. 이것은 상품이 골고루 팔려서가 아니라 때문이고, 그래서 '함께 나왔다'만으로는 .

확인 문제 1에 적어 제출 →

문턱을 올리면 규칙은 몇 분의 몇이 되나

4분

쌍마다 방향을 둘로 펴면 규칙은 14,280개입니다. 그 가운데 향상도가 1을 넘는 규칙은 몇 %일까요? 9차시의 감각으로 짚어 보세요 — 3할? 5할?

기본 빈칸 ①에 '지지도가 문턱 이상이고 향상도가 1보다 큰 규칙'을 고르는 조건을 채우고 ▶ 실행합니다. 두 조건을 & 로 잇고, 각 조건은 괄호로 묶어야 해요(pandas 의 규칙입니다).

# ── 예측: 향상도 > 1 인 규칙은 전체의 몇 %일까? ──
from itertools import combinations
import pandas as pd
import matplotlib.pyplot as plt
from pyodide.http import open_url

# ───── [준비] 규칙표 — 9차시의 세 식(방향 둘) ─────
df = pd.read_csv(open_url("../data/retail_baskets.csv"))
장바구니 = df.groupby("InvoiceNo")["Description"].apply(set)
N = len(장바구니)
상품수 = df.groupby("Description")["InvoiceNo"].nunique()
쌍수 = {}
for 바구니 in 장바구니:
    for a, b in combinations(sorted(바구니), 2):
        쌍수[(a, b)] = 쌍수.get((a, b), 0) + 1
행 = []
for (a, b), n in 쌍수.items():
    for A, B in [(a, b), (b, a)]:
        신뢰 = n / 상품수[A]
        향상 = 신뢰 / (상품수[B] / N)
        행.append((A, B, n / N, 신뢰, 향상, n))
열 = ["A", "B", "지지도", "신뢰도", "향상도", "함께"]
규칙 = pd.DataFrame(행, columns=열)
넘 = (규칙["향상도"] > 1).mean()
print(f"[3] 규칙 {len(규칙):,}개 가운데 향상도 > 1 은"
      f" {넘:.1%}")

문턱들, 남은수 = [0.001, 0.005, 0.01, 0.02, 0.05], []
for 문턱 in 문턱들:
    # [빈칸 ①] 지지도가 문턱 이상이고 향상도가 1 보다 큰 규칙
    조건 = ?????
    남음 = 규칙[조건]
    남은수.append(len(남음))
    print(f"    지지도 ≥ {문턱:<5} → {len(남음):>6,}개")

fig, ax = plt.subplots()
ax.bar([str(t) for t in 문턱들], 남은수)
for i, n in enumerate(남은수):
    ax.text(i, n, f"{n:,}", ha="center", va="bottom")
ax.set_xlabel("최소 지지도(문턱)")
ax.set_ylabel("남는 규칙 수(향상도 > 1)")
ax.set_title("문턱을 올리면 남는 규칙 수")
plt.show()

# ── 예측: 향상도 > 1 인 규칙은 전체의 몇 %일까? ──
from itertools import combinations
import pandas as pd
import matplotlib.pyplot as plt
from pyodide.http import open_url

# ───── [준비] 규칙표 — 9차시의 세 식(방향 둘) ─────
df = pd.read_csv(open_url("../data/retail_baskets.csv"))
장바구니 = df.groupby("InvoiceNo")["Description"].apply(set)
N = len(장바구니)
상품수 = df.groupby("Description")["InvoiceNo"].nunique()
쌍수 = {}
for 바구니 in 장바구니:
    for a, b in combinations(sorted(바구니), 2):
        쌍수[(a, b)] = 쌍수.get((a, b), 0) + 1
행 = []
for (a, b), n in 쌍수.items():
    for A, B in [(a, b), (b, a)]:
        신뢰 = n / 상품수[A]
        향상 = 신뢰 / (상품수[B] / N)
        행.append((A, B, n / N, 신뢰, 향상, n))
열 = ["A", "B", "지지도", "신뢰도", "향상도", "함께"]
규칙 = pd.DataFrame(행, columns=열)
넘 = (규칙["향상도"] > 1).mean()
print(f"[3] 규칙 {len(규칙):,}개 가운데 향상도 > 1 은"
      f" {넘:.1%}")

문턱들, 남은수 = [0.001, 0.005, 0.01, 0.02, 0.05], []
for 문턱 in 문턱들:
    # [빈칸 ①] 지지도가 문턱 이상이고 향상도가 1 보다 큰 규칙
    조건 = (규칙["지지도"] >= 문턱) & (규칙["향상도"] > 1)
    남음 = 규칙[조건]
    남은수.append(len(남음))
    print(f"    지지도 ≥ {문턱:<5} → {len(남음):>6,}개")

fig, ax = plt.subplots()
ax.bar([str(t) for t in 문턱들], 남은수)
for i, n in enumerate(남은수):
    ax.text(i, n, f"{n:,}", ha="center", va="bottom")
ax.set_xlabel("최소 지지도(문턱)")
ax.set_ylabel("남는 규칙 수(향상도 > 1)")
ax.set_title("문턱을 올리면 남는 규칙 수")
plt.show()

도전 문턱들에 0.1 과 0.2 를 더해 보세요. 막대가 어디에서 0이 되는지, 그 자리가 무엇을 뜻하는지 적어 두세요.

탐구 출력 첫 줄의 97.1% 를 보세요. 9차시에서 향상도 1은 '관계없음'의 기준선이었는데, 여기서는 거의 모든 규칙이 그 선을 넘습니다. 왜일까요? 아래 미션 ③의 판 [가짜 가게]가 답을 보여 줍니다.

다 함께 2분 선생님이 미션 ③의 판에서 [가짜 가게]를 켜 줍니다 — 송장 크기는 그대로 두고 상품만 제비뽑기로 다시 담아 관계를 모두 지운 가게예요. 관계가 하나도 없는데 향상도 > 1 이 몇 %가 되는지 보세요. 그 셈을 직접 하는 것은 코드 ⑥입니다.

문턱을 두 배로 올릴 때마다 규칙이 3분의 1 아래로 주는 것을 막대에서 보았다.
0.05 에서 남은 규칙이 4개뿐인 것을 보았다 — 너무 올리면 볼 것이 없다.
판의 [가짜 가게]에서 향상도 > 1 이 100.0%가 되는 것을 보았다.

문턱은 데이터가 아니라 가 정한다. 너무 낮추면 , 너무 올리면 . 그리고 이 자료에서 '향상도 > 1' 은 이다.

확인 문제 4에 적어 제출 →

1위를 읽고, 그 1위를 만든 손을 찾는다

8분

여는 장면에 적어 둔 내 예측입니다. 1위 쌍의 두 상품은 어떤 사이였나요?

기본 먼저 [4] 만 보고 위 8쌍을 하나하나 '발견인가, 상식인가' 판정해 보세요. 그다음 빈칸 ②에 '괄호 앞 이름(품목)이 같은 쌍인가'를 채웁니다 — 앞(센["A"]) 과 앞(센["B"]) 를 == 로 견주면 참/거짓 열이 나와요.

# ── 예측: 향상도 1위 쌍의 두 상품은 어떤 사이일까? ──
from itertools import combinations
import pandas as pd
from pyodide.http import open_url

df = pd.read_csv(open_url("../data/retail_baskets.csv"))
장바구니 = df.groupby("InvoiceNo")["Description"].apply(set)
N = len(장바구니)
상품수 = df.groupby("Description")["InvoiceNo"].nunique()
쌍수 = {}
for 바구니 in 장바구니:
    for a, b in combinations(sorted(바구니), 2):
        쌍수[(a, b)] = 쌍수.get((a, b), 0) + 1
# 향상도는 방향이 없다 — 쌍마다 한 줄
행 = [(a, b, n / N, n * N / (상품수[a] * 상품수[b]), n)
      for (a, b), n in 쌍수.items()]
열 = ["A", "B", "지지도", "향상도", "함께"]
센 = pd.DataFrame(행, columns=열).query("지지도 >= 0.01")

def 찍기(표):
    for _, r in 표.nlargest(8, "향상도").iterrows():
        print(f"   {r['함께']:>4}장  {r['향상도']:5.1f}"
              f"   {r['A']} & {r['B']}")

print("[4] 지지도 ≥ 0.01 · 향상도 위 8쌍")
찍기(센)
# [빈칸 ②] 괄호 앞 이름(품목)이 같은 쌍인가
앞 = lambda s: s.str.split("(").str[0]
같은계열 = ?????
print(f"[5] 같은 품목 {같은계열.sum()}쌍을 걷어 내고 다시")
찍기(센[~같은계열])
# 도전: 괄호 안(무늬)이 같은 쌍도 걷어 내면 위로 무엇이 오나?

# ── 예측: 향상도 1위 쌍의 두 상품은 어떤 사이일까? ──
from itertools import combinations
import pandas as pd
from pyodide.http import open_url

df = pd.read_csv(open_url("../data/retail_baskets.csv"))
장바구니 = df.groupby("InvoiceNo")["Description"].apply(set)
N = len(장바구니)
상품수 = df.groupby("Description")["InvoiceNo"].nunique()
쌍수 = {}
for 바구니 in 장바구니:
    for a, b in combinations(sorted(바구니), 2):
        쌍수[(a, b)] = 쌍수.get((a, b), 0) + 1
# 향상도는 방향이 없다 — 쌍마다 한 줄
행 = [(a, b, n / N, n * N / (상품수[a] * 상품수[b]), n)
      for (a, b), n in 쌍수.items()]
열 = ["A", "B", "지지도", "향상도", "함께"]
센 = pd.DataFrame(행, columns=열).query("지지도 >= 0.01")

def 찍기(표):
    for _, r in 표.nlargest(8, "향상도").iterrows():
        print(f"   {r['함께']:>4}장  {r['향상도']:5.1f}"
              f"   {r['A']} & {r['B']}")

print("[4] 지지도 ≥ 0.01 · 향상도 위 8쌍")
찍기(센)
# [빈칸 ②] 괄호 앞 이름(품목)이 같은 쌍인가
앞 = lambda s: s.str.split("(").str[0]
같은계열 = 앞(센["A"]) == 앞(센["B"])
print(f"[5] 같은 품목 {같은계열.sum()}쌍을 걷어 내고 다시")
찍기(센[~같은계열])
# 도전: 괄호 안(무늬)이 같은 쌍도 걷어 내면 위로 무엇이 오나?

도전 괄호 안(무늬)이 같은 쌍까지 걷어 내 보세요. 안 = lambda s: s.str.split("(").str[1] 을 만들어 조건에 | 로 이으면 됩니다. 그러면 위 일곱이 '큰 가방'끼리가 되고, 8위에 처음으로 계열 밖 규칙 — 재활용가방(빨강물방울) & 수면등(빨강버섯) 6.5 · 62장 — 이 올라옵니다.

탐구 걷어 내도 걷어 내도 비슷한 것이 올라옵니다. 몇 번을 걷어 내야 '발견'이 나올까요? 아니면 걷어 내기로는 안 되는 걸까요? 아래 판에서 확인합니다.

1위 13.0 을 만든 것은 가게일까요, 상품을 조각으로 나눠 적은 방식일까요. 아래 판에서 세는 단위를 손으로 빚어 확인합니다 — 조각을 붙이면 4,000장이 그 자리에서 다시 세어져요. (이 판에 9분을 씁니다 — 개념 정거장에서 아껴 둔 몫이라 미션 ③의 8분과 따로입니다.)

시뮬레이터

조각 붙이기 판

1위 향상도 13.0 은 어디서 왔나 — 세는 단위를 바꾸면 순위가 바뀐다

1몇 번 붙여야 1위가 무너질지 예측을 골라 잠근다
21위의 두 조각을 붙여 4,000장을 다시 세게 한다
3가위로 규칙을 정해 한꺼번에 붙이고, 남은 쌍을 심판에 보낸다

① 내 예측 — 고르면 잠긴다

② 1위의 두 조각을 붙인다

③ 가위 — 규칙으로 한꺼번에

뻔한 쌍 걷어 내기 (세는 단위는 그대로)

대조군 — 교사 장면

심판 카드 열기 영문 원래 이름 · 달별 판매

순위판 · 조각 120개지지도 ≥ 0.01 · 향상도 위 8쌍

향상도 = 함께 든 송장 수 ÷ (두 상품이 서로 상관없이 팔렸다면 함께 들었을 장수) · 천장 = 4,000 ÷ 더 흔한 쪽의 송장 수 — 한 쌍이 오를 수 있는 가장 큰 향상도

같은 품목 = 괄호 앞 이름이 같은 쌍 · 같은 무늬 = 괄호 안 이름이 같은 쌍 · 붙이기는 두 조각을 한 상품으로 세어 4,000장을 다시 센다(걷어 내기는 목록에서 빼기만 한다)

1위 향상도—천장의 —

위 8쌍 중 같은 품목—

상품 단위—

붙인 횟수0

향상도 > 1—

심판에 보낸 칸0/2

도전 1

예측을 잠그고 [일곱 번]을 눌러라 — 일곱 번 붙이는 동안 계기 '같은 품목'은 몇에서 몇으로 갔나?

도전 2

가위를 [괄호 앞으로 붙여 세기]로 돌려라 — 1위 향상도는 얼마로 내려앉고, 그 쌍은 천장의 몇 %까지 오른 쌍인가?

도전 3

붙여 세기 순위판에서 두 칸을 심판에 보내라 — 둘 다 '계열 밖' 판정을 받으면 성공이다.

자료: retail_baskets.csv 송장 4,000장 · 상품 120가지를 쪽 안에 실었다(원장이 구운 그대로). 판이 세는 규칙은 코드 ③ · ⑤와 같고, 쪽이 열릴 때 원장 값(1위 13.05 · 같은 품목 7/8 · 끝까지 40번 · 붙여 1위 5.21 · 향상도 > 1 97.1%)으로 스스로 검산합니다. 대조군 두 가지는 코드 ⑥과 같은 제비뽑기(씨앗 0)로 구운 송장이라 100.0% · 27.7%가 코드 출력과 같습니다.

위 8쌍 가운데 7쌍이 같은 품목의 다른 조각인 것을 코드 ③에서 확인했다.
같은 품목 217쌍을 걷어 내도 위로 같은 무늬 시리즈(빈티지성탄)가 올라오는 것을 보았다.
판에서 한 쌍씩 붙이기로는 1위가 안 무너지는 것을 보았다.
가위를 '괄호 앞'으로 돌리자 1위가 13.0 → 5.2로 내려앉는 것을 보았다.

1위 향상도 13.0 을 만든 것은 이다. 같은 자료인데 를 바꾸자 1위가 로 내려앉았고, 그러니 규칙을 보고할 때는 를 함께 적어야 한다.

확인 문제 3에 적어 제출 →

가지치기를 재 보고, 추천할 규칙 두 개를 고른다

4분

아프리오리 가지치기는 '혼자서도 드문 상품'을 먼저 버립니다. 이 자료에서 혼자 지지도가 0.01 아래인 상품은 120개 가운데 몇 개일까요? 숫자를 하나 짚어 두세요.

기본 코드 ④는 채워져 있습니다. 그대로 ▶ 실행해 문턱마다 걸러지는 상품 수와 셀 쌍의 수를 확인하세요.

# ── 예측: 혼자 지지도 0.01 아래인 상품은 120개 중 몇 개? ──
import pandas as pd
from pyodide.http import open_url

df = pd.read_csv(open_url("../data/retail_baskets.csv"))
N = df["InvoiceNo"].nunique()
상품수 = df.groupby("Description")["InvoiceNo"].nunique()
m = len(상품수)
print(f"[6] 상품 {m}개 · 가장 드문 상품도 송장의"
      f" {상품수.min() / N:.1%} 에 든다")
for 문턱 in [0.01, 0.03, 0.05]:
    드문 = int((상품수 / N < 문턱).sum())
    남 = m - 드문
    print(f"    문턱 {문턱}: 드문 상품 {드문:>3}개 → 셀 쌍"
          f" {m * (m - 1) // 2:,} → {남 * (남 - 1) // 2:,}")
# 탐구: 원장은 많이 팔린 120개만 남겼다 — 무엇이 달라졌나?

도전 판의 가위 [괄호 앞]과 같은 일을 코드로 합니다. 코드 ⑤는 이름에서 괄호 안을 떼어 품목 47가지로 붙여 센 뒤, 향상도와 천장을 나란히 찍어요. 판의 순위판과 같은 다섯 쌍이 나오는지 맞대어 보세요.

# 조각 붙이기 판의 가위 '괄호 앞' 과 같은 일 — 1위는?
from itertools import combinations
import pandas as pd
from pyodide.http import open_url

df = pd.read_csv(open_url("../data/retail_baskets.csv"))
# 이름에서 괄호 안을 떼고, 한 송장 안에서 같은 품목은 하나로
df["Description"] = df["Description"].str.split("(").str[0]
df = df.drop_duplicates(["InvoiceNo", "Description"])
장바구니 = df.groupby("InvoiceNo")["Description"].apply(set)
N = len(장바구니)
수 = df.groupby("Description")["InvoiceNo"].nunique()
쌍수 = {}
for 바구니 in 장바구니:
    for a, b in combinations(sorted(바구니), 2):
        쌍수[(a, b)] = 쌍수.get((a, b), 0) + 1
행 = []
for (a, b), n in 쌍수.items():
    향상 = n * N / (수[a] * 수[b])
    천장 = N / max(수[a], 수[b])   # 함께 ≤ 적은 쪽 장수
    행.append((a, b, n / N, 향상, 천장, n))
열 = ["A", "B", "지지도", "향상도", "천장", "함께"]
규칙 = pd.DataFrame(행, columns=열).query("지지도 >= 0.01")
print(f"품목 {len(수)}가지로 붙여 세면 — 위 5쌍")
for _, r in 규칙.nlargest(5, "향상도").iterrows():
    print(f"   {r['함께']:>4}장  {r['향상도']:4.1f}"
          f"(천장 {r['천장']:4.1f})   {r['A']} & {r['B']}")

탐구 관계를 모두 지운 가짜 가게를 직접 만들어 봅니다. 코드 ⑥의 마지막 줄 주석대로 size=len(b) 를 size=7 로 바꾸면 송장 크기가 고르게 되고, 향상도 > 1 이 27.7%까지 떨어져요 — 97.1%를 만든 것이 관계가 아니라 송장 크기였다는 뜻입니다.

# 송장마다 상품 수는 그대로, 상품만 인기 비율대로 제비뽑기
from itertools import combinations
import numpy as np
import pandas as pd
from pyodide.http import open_url

df = pd.read_csv(open_url("../data/retail_baskets.csv"))
장바구니 = df.groupby("InvoiceNo")["Description"].apply(set)
인기 = df["Description"].value_counts(normalize=True)
rng = np.random.default_rng(0)   # 씨앗 — 늘 같은 가짜 가게
가짜 = [set(rng.choice(인기.index, size=len(b), replace=False,
                       p=인기.values)) for b in 장바구니]

def 향상도들(바구니들):
    N, 쌍, 수 = len(바구니들), {}, {}
    for b in 바구니들:
        for p in b:
            수[p] = 수.get(p, 0) + 1
        for a, c in combinations(sorted(b), 2):
            쌍[(a, c)] = 쌍.get((a, c), 0) + 1
    return np.array([n * N / (수[a] * 수[c])
                     for (a, c), n in 쌍.items()])

for 이름, 바구니들 in [("진짜 가게", list(장바구니)),
                    ("가짜 가게", 가짜)]:
    l = 향상도들(바구니들)
    print(f"{이름}: 향상도 > 1 {np.mean(l > 1):.1%}"
          f" · 중앙값 {np.median(l):.2f}")
# 도전: size=len(b) 를 size=7 로 — 송장 크기를 고르게 하면?

본 과제 이제 가게 담당자에게 추천할 규칙 두 개를 고릅니다. 규칙마다 지지도(함께 든 송장 수) · 신뢰도 · 향상도와 왜 뻔하지 않은가를 적어 확인 문제 3의 표에 채워 넣으세요. 판의 심판을 거친 쌍이 좋은 후보입니다.

문턱 0.01 · 0.03 에서 걸러지는 상품이 0개인 것을 보았다 — 가지치기가 놀고 있다.
0.05 에서야 52개가 빠져 셀 쌍이 7,140 → 2,278로 주는 것을 보았다.
코드 ⑤의 다섯 쌍이 판의 순위판 위 다섯과 같은 숫자인지 맞대었다.
추천할 규칙 두 개를 고르고 '왜 뻔하지 않은가'를 한 줄씩 적었다.

가지치기가 이 자료에서 안 먹히는 까닭은 이다. 그래도 가지치기를 배우는 까닭은 이고, 상품이 개인 가게라면 이야기가 달라진다.

확인 문제 2에 적어 제출 →

체크포인트 3

4,000장을 직접 세어 1위를 뽑았고, 세는 단위를 바꿔 그 1위를 무너뜨렸고, 담당자에게 추천할 규칙 둘을 골랐다.

다음 정거장 · 정리·확인 10분 →

정리·확인 · 10분

오늘의 탐험 일지

찾은 것
향상도 1위(13.0)는 가게가 아니라 상품을 조각으로 나눠 적은 방식이 만들었다 — 품목으로 붙여 세자 5.2로 내려앉았다.
도구의 한계
세 자는 무엇을 한 상품으로 볼지를 정해 주지 않는다. '향상도 > 1'도 이 가게에서는 97.1%를 통과시켜 기준선 노릇을 못 했다.
보고의 규칙
규칙을 보고할 때는 향상도와 함께 함께 든 송장 수 · 세는 단위 · 걷어 낸 것을 적는다. 그리고 천장과 나란히 놓아 '오를 수 있었던 최대'와 견준다.

✍️ 문제마다 답을 쓰고 제출하기를 누르세요. 제출하면 모범 답안이 열리고, 제출한 답은 선생님께 전달됩니다.

1. ① 상품이 150개인 가게에서 쌍은 몇 개, 셋 묶음은 몇 개인가? 이 숫자가 분석 방법에 주는 뜻을 쓰시오. ② 그리고 오늘 자료에서 만들 수 있는 쌍 7,140개가 하나도 빠짐없이 함께 나온 까닭을 쓰시오.

📖 모범 답안

① 쌍은 150×149/2 = 11,175개, 셋 묶음은 150×149×148/6 = 551,300개이다. 묶음이 커질수록 수가 폭발하므로 모두 세어 보고 고르는 방법은 쓸 수 없다. 그래서 최소 지지도로 먼저 거르고(문턱), 혼자서도 드문 상품이 낀 묶음은 아예 세지 않는다(가지치기).

② 송장당 상품 수가 중앙값 4개 · 평균 7.0개 · 최대 87개로 제각각이라 큰 송장 한 장이 수백 쌍을 한꺼번에 담기 때문이다. 상품 31개 이상인 송장 109장이 '함께' 237,603번 가운데 51.4%를 만든다. 그래서 '함께 나왔다'는 사실만으로는 두 상품이 서로 당긴다고 말할 수 없다 — 이 자료에서는 향상도 > 1 조차 97.1%를 통과시킨다.

2. 혼자 지지도가 0.004인 상품이 있다. 이 상품이 낀 쌍의 지지도가 0.01을 넘을 수 있는가? 이유와 함께 쓰고, 그런데도 오늘 자료에서 가지치기가 한 개도 걸러 내지 못한 까닭을 덧붙이시오.

📖 모범 답안

넘을 수 없다. 두 상품이 함께 든 송장은 그 상품이 든 송장의 일부이므로 쌍의 지지도 ≤ 0.004 이다. 그래서 이런 상품이 낀 쌍은 세어 보지 않아도 문턱을 넘지 못한다는 것을 안다(아프리오리 원리).

그런데 오늘 자료에서는 문턱 0.01 · 0.03 에서 걸러지는 상품이 0개다. 원장이 많이 팔린 120개만 남겨 구웠기 때문에 가장 드문 상품도 송장의 3.4%에 들기 때문이다. 0.05 까지 올려야 52개가 빠져 셀 쌍이 7,140에서 2,278로 준다. 가지치기는 '드문 것이 많을 때' 효과를 낸다 — 상품 수천 개를 그대로 둔 진짜 가게라면 크게 줄어든다.

3. 향상도 위 규칙이 '찻잔세트(분홍) & 찻잔세트(초록)' 같은 것뿐이었다. 이를 매출 보고서의 '핵심 발견'으로 쓰면 무엇이 문제이고, 어떻게 쓰면 쓸모 있는지 쓰시오. 그리고 가게 담당자에게 추천할 규칙 두 개를 아래 표에 채우시오(미션 ④의 본 과제).

규칙 A & B	함께 든 송장	향상도(천장)	왜 뻔하지 않은가
첫째
둘째

📖 모범 답안

문제 — 같은 품목을 색깔별로 세트로 산다는 것은 이미 아는 사실이라 새 정보가 아니다. 게다가 그 향상도 13.0은 가게의 사실이 아니라 상품을 조각으로 나눠 적은 방식이 만든 값이다 (품목 47가지로 붙여 세면 1위가 5.2로 내려앉는다). 그런 목록을 '핵심 발견'으로 올리면 담당자는 바꿀 수 있는 일이 없는 보고서를 받는다.

쓸모 있게 쓰는 법 — ① 계열 단위 재고·진열에 쓴다("찻잔세트는 색을 한 묶음으로 채운다"). 뻔한 규칙도 이런 쓸모는 있다. ② 발견은 계열이 다른 상품 사이에서 찾는다 — 같은 품목, 같은 무늬, 같은 철을 먼저 걷어 낸 뒤에 남는 것을 본다.

추천 규칙 두 개(예) — 품목 47가지로 붙여 센 목록에서 고른다.

· 손뜨개틀 & 스냅카드게임 — 함께 56장 · 향상도 5.2(천장 16.2의 32%) · 신뢰도 0.32 / 0.23. 두 품목은 조각이 없어 무늬가 겹칠 수 없고, 판의 심판에서도 같은 철에 몰리지 않았다. '집에서 손으로 하는 놀이'라는 다른 이야기가 보인다.

· 레시피상자 & 재활용가방 — 함께 65장 · 향상도 4.7(천장 14.1의 33%) · 신뢰도 0.23 / 0.33. 품목도 무늬도 겹치지 않는다. 다만 보고할 때 둘 다 '부엌·장보기' 쓰임이라는 점은 함께 적는다 — 판정은 사람이 한다.

어느 쪽을 골라도 좋지만, 세 숫자와 '왜 뻔하지 않은가'를 함께 적어야 추천이 된다.

4. 최소 지지도를 0.001로 낮췄더니 규칙이 13,860개가 되었다. 그대로 담당자에게 넘기면 생길 일과, 넘기기 전에 할 일 두 가지를 쓰시오.

📖 모범 답안

생길 일 — 사람이 읽을 수 없고, 몇 장밖에 안 되는 우연한 규칙이 잔뜩 섞인다. 지지도 0.001은 4,000장 가운데 4장이면 통과라는 뜻이다. 게다가 이 자료에서는 향상도 > 1 조차 거의 거르지 못한다(97.1%).

할 일 두 가지 — ① 향상도와 함께 '함께 나온 송장 수'를 반드시 적어 드문 규칙을 표시한다 (몇 장짜리 규칙인지 보이지 않으면 향상도가 큰 값이 늘 위로 온다). ② 뻔한 규칙과 계절 상품을 걸러 짧은 목록으로 만든다 — 같은 품목, 같은 무늬, 같은 철. 그리고 문턱을 왜 그 값으로 골랐는지를 목록 위에 한 줄로 적는다.

5. 케이크 틀 → 쿠키 틀의 신뢰도가 0.58, 쿠키 틀 → 케이크 틀이 0.29라면 (가정한 예 — 이 데이터에서는 계열 밖 규칙이 향상도 위에 오지 않는다) 홈페이지의 '함께 사면 좋은 상품' 칸에는 어느 방향을 쓰겠는가? 까닭과 함께 쓰시오.

📖 모범 답안

케이크 틀 화면에 쿠키 틀을 추천한다. 케이크 틀을 산 사람 가운데 쿠키 틀도 산 비율(0.58)이 그 반대(0.29)보다 훨씬 높기 때문이다.

신뢰도는 방향이 있다 — 같은 쌍이라도 어느 쪽에서 보느냐에 따라 값이 다르다. 반면 향상도는 방향이 없다(쌍 하나에 값 하나). 그래서 '무엇과 무엇이 관계있나'는 향상도로 찾고, '어느 화면에 무엇을 띄울까'는 신뢰도로 정한다. 코드 ②의 규칙표가 쌍마다 방향을 둘로 펴서 14,280줄이 되는 까닭이 여기에 있다.

6. 우리 학교 매점이 1년 치 영수증을 교과서 자료로 공개하겠다고 한다. 공개 전에 지워야 할 것 둘과, 지워도 남는 위험 하나를 쓰시오.

📖 모범 답안

지울 것 — ① 학생 번호 · 결제 카드처럼 사람을 가리키는 칸. ② 분 단위의 정확한 시각(같은 시간대에 산 사람이 몇 안 되면 시각만으로 누구인지 좁혀진다).

남는 위험 — 드문 조합이다. 특정 식품만 사는 사람처럼 흔치 않은 장바구니는 날짜와 함께 보면 누구인지 짐작된다(Ⅰ-7의 재식별). 그래서 공개 자료는 날짜를 달 단위로 뭉개거나, 드문 상품·드문 조합이 든 영수증을 지우거나, 묶어서 센 표만 낸다. 오늘 쓴 영국 자료도 가게 이름과 고객 번호를 지운 뒤에야 공개됐다.

더 알아보기

같은 표를 다르게 쓰는 사람들

현장

'이 상품을 산 고객이 함께 산 상품'

2003년 아마존 연구진(린든 · 스미스 · 요크)이 발표한 추천 방식은 상품-상품 협업 필터링입니다. 고객끼리 닮음을 재는 대신, 상품과 상품이 얼마나 함께 팔렸는지를 미리 표로 만들어 두고 어떤 상품 화면에서 그 표의 한 줄을 크기순으로 세워 보여 주는 방식이에요. 고객이 수천만 명이어도 계산이 상품 수에 매이므로 화면을 띄우는 동안 답이 나옵니다.

오늘 우리가 센 쌍 7,140개가 바로 이 표의 위쪽 절반입니다. 표는 같고, 쓰는 법이 달라요 — 추천은 '이 상품과 가장 많이 함께 팔린 것'을 줄 안에서 고르고, 연관 규칙은 향상도로 표 전체에서 규칙을 뽑습니다. 그래서 연관 규칙에는 오늘 본 함정 — 조각 · 천장 · 기준선 — 이 따라붙지만, 대신 사람이 읽고 설명할 수 있는 문장이 남습니다.

도해: 많이 팔린 상품 8개로 만든 상품×상품 공출현 표(원장 계산, 송장 4,000장). · 출처: G. Linden, B. Smith, J. York, Amazon.com Recommendations: Item-to-Item Collaborative Filtering, IEEE Internet Computing, 2003

자료의 내력

이 송장들은 어디서 왔나

영국의 한 온라인 선물가게가 2010년 12월부터 2011년 12월까지 남긴 거래 541,909줄입니다. 연구진(첸 등, 2012)이 고객을 나누는 연구에 쓴 뒤 공개했고, 지금은 UCI 저장소에서 누구나 받을 수 있어요(CC BY 4.0). 원자료 한 줄에는 송장번호 · 상품코드 · 상품명 · 수량 · 단가 · 고객번호 · 나라가 있습니다.

교과서가 읽는 파일은 여기서 세 칸만 남긴 것입니다 — 송장번호 · 상품명 · 날짜. 고객번호를 지우는 것은 사람을 가리키는 칸이기 때문이고, 취소 송장과 수량이 0 이하인 줄을 뺀 것은 그것이 '산 기록'이 아니기 때문이에요. 그다음 영국 송장만, 많이 팔린 상품 120개만 남겨 4,000장으로 줄였습니다.

한 가지 더 알아 둘 것이 있습니다. 이 가게에는 도매로 사 가는 고객이 섞여 있어요. 한 송장에 상품이 87개까지 드는 까닭이고, 오늘 향상도 > 1 이 97.1%가 된 까닭이기도 합니다. 자료를 모은 사정이 결과의 모양을 만든다 — 분석 전에 내력을 읽어야 하는 이유입니다.

도해: 원자료 한 줄의 칸 구조와 교과서가 남긴 세 칸, 그리고 4,000장으로 줄인 단계(원장 굽기 기록). · 출처: Online Retail, UCI Machine Learning Repository, CC BY 4.0, doi:10.24432/C5BW33 — 취소·비상품 줄 제외, 영국 송장, 상위 상품 120개, 상품명 한국어 대응으로 가공

크기 감각

편의점 하나면 셋 묶음이 1억 개

오늘 자료는 상품 120가지라 쌍이 7,140개였습니다. 편의점 한 곳에 상품이 1,000가지 있다면 쌍은 499,500개, 셋 묶음은 1억 6,616만 개가 돼요. 쌍 하나를 1밀리초에 센다 해도 셋 묶음은 이틀 가까이 걸립니다. 네 개짜리 묶음은 다시 그 약 250배예요.

이렇게 한 칸 갈 때마다 몇 배씩 뛰는 것을 조합 폭발이라 부릅니다. 체스판 첫 칸에 쌀 한 알, 다음 칸에 두 알씩 놓아 가다 나라의 쌀이 모자랐다는 옛 이야기와 같은 모양이에요. 그래서 아프리오리 같은 알고리즘은 세기 전에 세지 않아도 되는 것을 지우는 일부터 합니다.

여기서 배울 것은 계산의 요령이 아니라 감각입니다. 데이터가 커지면 방법이 달라져야 한다 — 같은 물음이라도 매점 영수증 24장에서는 손으로 세는 것이 답이었고, 4,000장에서는 문턱과 가지치기가 답이었으며, 수백만 장에서는 또 다른 방법이 필요합니다. 14차시에서 '어떤 방법을 골라야 할까'를 다시 만납니다.

도해: 상품 가짓수에 따른 쌍과 셋 묶음의 수(두 조합 공식, 세로는 로그 눈금).