Veri analizi ve veri madenciliği: OLAP, yıldız şema, birliktelik kuralları

Dönemin son konusu veritabanını “kaydı tutan sistem” olmaktan çıkarıp “karar vermeye yarayan sistem” olarak görmek. İki parçası var. Birincisi veri ambarı (data warehouse) ve OLAP: büyük veriyi farklı boyutlarda özetlemek. İkincisi veri madenciliği (data mining): veride insanın gözüyle bulamayacağı kalıpları bulmak. Final sınavında bu konudan genelde kavram soruları ve küçük hesaplar gelir: support ve confidence hesapla, ROLLUP kaç satır üretir, entropi ne, k-means bir iterasyon. Bilmen gerekenler:

1. OLTP günlük işi, OLAP analizi yapar. Tasarımları da bu yüzden farklı.
2. Yıldız şema: ortada olgu tablosu, etrafta boyut tabloları.
3. ROLLUP $n+1$, CUBE $2^n$ gruplama kümesi üretir.
4. Confidence simetrik değildir. Lift, kuralın bağımsızlıktan ne kadar iyi olduğunu söyler.
5. Sınıflandırmada etiket var, kümelemede yok.

OLTP, OLAP ve veri ambarı

Şimdiye kadar kurduğumuz üniversite veritabanı bir OLTP (online transaction processing) sistemiydi. Öğrenci derse kaydolur, not girilir, kredi güncellenir. Her işlem birkaç satıra dokunur, saniyede yüzlerce olur, normalize edilmiş tablolar (9-11. haftalar) güncelleme anomalilerini önler.

Rektörlüğün sorusu ise farklıdır: “Son beş yılda her bölümün her dönem ortalama başarısı nasıl değişti?” Bu bir OLAP (online analytical processing) sorgusudur. Milyonlarca satırı okur, gruplar, toplar. Hiçbir şey güncellemez.

Veri ambarı (data warehouse), farklı kaynaklardan gelen verinin tek bir şemada, uzun dönemli ve analize uygun biçimde toplandığı depodur. Kaynaklardan ambara veri ETL ile taşınır: çıkar (extract), dönüştür (transform: birimleri, kodları, isimleri tek tipe getir, kirli veriyi temizle), yükle (load). Ambar genelde gece toplu olarak güncellenir.

Yıldız şema

Örnek olarak kampüs kafeteryalarının satışlarını analiz edelim. Bir satış olayının ölçüleri (measures) adet ve tutardır. Bu olayı tarif eden bağlam ise boyutlardır (dimensions): hangi ürün, hangi kafeterya, hangi ay.

              dim_item(item_id, item_name, category)
                          |
 dim_date(date_id, month) -- fact_sales(date_id, store_id, item_id, qty, amount) -- dim_store(store_id, campus)

(Ortadaki çizgiler yabancı anahtar bağlantısı.) Boyut tabloları: dim_item = {1 Tost Food, 2 Simit Food, 3 Cay Drink, 4 Kahve Drink}, dim_store = {K1 Galata, K2 Rumeli}, dim_date = {1 Sep, 2 Oct}. Olgu tablosu:

Yıldız şemada (star schema) boyutlar tek tablodur ve normalize edilmemiştir: dim_item içinde kategori adı tekrar eder. Kar tanesi şemada (snowflake schema) boyutlar da normalize edilir, örneğin kategori ayrı bir dim_category tablosuna çıkar. Kar tanesi yer kazandırır, ama sorgulara ekstra join ekler.

TUZAK · olgu tablosu küçük değildir. Öğrenciler sık sık “boyut tabloları büyük, olgu tablosu küçük” diye yazar. Tersi doğru. Her satış bir olgu satırıdır, milyonlara ulaşır. Ürün ya da şube sayısı ise sınırlıdır.

Veri küpü ve OLAP işlemleri

Üç boyutu (ürün kategorisi, kampüs, ay) eksen olarak düşünürsen satışlar bir küpün hücrelerine yerleşir. Buna veri küpü (data cube) denir. Her hücre bir kombinasyonun toplamıdır. Her boyuta bir de “hepsi” (ALL) değeri eklenince, iki değerli üç boyut için $(2+1)^3 = 27$ hücre olur.

Pivot sonucu (tutar):

Pivot SQL’de CASE ile yazılır: SUM(CASE WHEN month = 'Sep' THEN amount END) AS Sep.

ROLLUP, CUBE ve GROUPING SETS

Standart SQL’de (SQL:1999 sonrası) birden çok gruplama seviyesini tek sorguda almak için GROUP BY uzantıları var:

SELECT campus, category, SUM(amount) AS total
FROM fact_sales f JOIN dim_item i USING (item_id) JOIN dim_store s USING (store_id)
GROUP BY ROLLUP (campus, category);

ROLLUP(campus, category) şu üç gruplama kümesinin (grouping sets) birleşimidir: (campus, category), (campus), (). Toplanan kolon sonuçta NULL olarak görünür:

CUBE(campus, category) ise dört kümenin hepsidir: ROLLUP’takilere (category) eklenir, iki satır daha gelir: (NULL, Drink, 2400) ve (NULL, Food, 2400). Toplam 9 satır. Genel kural: $n$ öznitelik için ROLLUP $n+1$, CUBE $2^n$ küme üretir. GROUPING SETS ((campus), (category)) gibi bir yazımla istediğin kümeleri elle de seçebilirsin.

SQLite bu uzantıları desteklemez. GROUP BY ROLLUP(campus) yazınca “no such function: ROLLUP” hatası alınır. Aynı sonucu UNION ALL ile üretiriz:

SELECT campus, category, SUM(amount) FROM ... GROUP BY campus, category
UNION ALL
SELECT campus, NULL, SUM(amount) FROM ... GROUP BY campus
UNION ALL
SELECT NULL, NULL, SUM(amount) FROM ...;

TUZAK · NULL iki anlama gelebilir. ROLLUP satırındaki NULL “bu kolon üzerinden toplandı” demektir. Ama veride gerçekten NULL kategori varsa ikisi karışır. Standart SQL bunun için GROUPING(category) fonksiyonunu verir: toplam satırında 1, normal satırda 0 döner.

Veri madenciliği: birliktelik kuralları

Veri madenciliği (data mining), büyük veride yararlı ve beklenmedik kalıpları otomatik bulmaktır. Başlıca görevler: birliktelik kuralları (association rules), sınıflandırma (classification), kümeleme (clustering), regresyon ve aykırı değer tespiti.

Birliktelik kuralı “X alan Y de alır” biçimindedir: $X \Rightarrow Y$. Kafeteryadaki 8 fiş:

Üç ölçü:

$supp(X) = \frac{X\text{'i içeren işlem sayısı}}{N} \qquad conf(X \Rightarrow Y) = \frac{supp(X \cup Y)}{supp(X)} \qquad lift(X \Rightarrow Y) = \frac{conf(X \Rightarrow Y)}{supp(Y)}$

Support simetriktir, confidence değildir. Lift ise yine simetriktir: $lift = \frac{supp(X \cup Y)}{supp(X)\,supp(Y)}$. Lift > 1 ise X, Y’nin olasılığını artırır. Lift < 1 ise azaltır: tost alan müşteri ortalamadan az çay alıyor.

Apriori

Bütün ürün kombinasyonlarını saymak üstel maliyetlidir. Apriori şu ilkeye dayanır: sık (frequent) bir kümenin her alt kümesi de sıktır. Tersi: bir alt kümesi seyrek olan aday saymaya gerek kalmadan atılır. Minimum support sayısı 2 ile:

C1 sayımı : cay 5, kahve 3, simit 4, su 2, tost 4          → L1 = hepsi
C2 sayımı : cay+kahve 0, cay+simit 4, cay+su 1, cay+tost 2, kahve+simit 0,
            kahve+su 1, kahve+tost 2, simit+su 1, simit+tost 1, su+tost 0
L2        : {cay,simit}:4, {cay,tost}:2, {kahve,tost}:2
C3 aday   : {cay,simit,tost} → {simit,tost} seyrek, BUDANIR
            {cay,kahve,tost} → {cay,kahve} seyrek, BUDANIR
C3 boş    → dur

Kurallar, sık kümelerden üretilip minimum confidence eşiğiyle süzülür. Örneğin eşik 0.75 ise {cay, simit} kümesinden hem cay ⇒ simit (0.8) hem simit ⇒ cay (1.0) geçer.

Sınıflandırma ve karar ağaçları

Sınıflandırma (classification), etiketi bilinen eğitim verisinden (supervised learning) bir model öğrenip yeni kaydın sınıfını tahmin etmektir: “Bu öğrenci dersi geçer mi?” Karar ağacı (decision tree) her düğümde bir özniteliğe göre veriyi böler. Hangi özniteliğin seçileceğine entropi ile karar verilir:

$H(S) = -\sum_i p_i \log_2 p_i \qquad Gain(S, A) = H(S) - \sum_v \frac{|S_v|}{|S|} H(S_v)$

10 öğrencilik bir eğitim kümesinde 5 kişi geçmiş, 5 kişi kalmış: $H = 1$ (en karışık durum). Devam durumu (attendance) ‘yes’ olan 5 kişiden 4’ü geçmiş, ‘no’ olan 5 kişiden 1’i geçmiş. Her dalın entropisi $-0.8\log_2 0.8 - 0.2\log_2 0.2 = 0.722$, kazanç $1 - 0.722 = 0.278$. Bu veride çalışma süresi (high/low) da aynı 4’e 1 ve 1’e 4 dağılımı verdiği için kazancı yine 0.278. Eşitlikte herhangi biri seçilebilir. Başka bir karşılaştırma için: 3 geçen 1 kalan bir düğümün entropisi 0.811, 2’ye 2 olanınki 1’dir. Saf (tek sınıflı) düğümde entropi 0’dır ve ağaç orada yaprak olur.

Kümeleme ve k-means

Kümeleme (clustering) etiket olmadan (unsupervised) benzer kayıtları gruplar. En bilinen algoritma k-means:

1. k merkez seç.
2. Her noktayı en yakın merkeze ata.
3. Her merkezi kendi kümesinin ortalamasına taşı.
4. Atamalar değişmeyene kadar 2 ve 3’ü tekrarla.

Noktalar A(1,2), B(2,1), C(2,3), D(8,8), E(9,7), F(7,9), k = 2, başlangıç merkezleri c1 = (1,2), c2 = (2,3):

iter 1: A→c1 (d²: 0 / 2)   B→c1 (2 / 4)   C→c2 (2 / 0)   D,E,F→c2
        c1 = (1.5, 1.5)    c2 = ((2+8+9+7)/4, (3+8+7+9)/4) = (6.5, 6.75)
iter 2: C için d²: c1'e 2.5, c2'ye 34.3125 → C, c1'e geçer
        c1 = (1.67, 2)     c2 = (8, 8)
iter 3: atama değişmedi → dur.  SSE = 2.667 + 4 = 6.667

k-means sonucu başlangıç merkezlerine bağlıdır. Kötü bir başlangıç daha uzun sürebilir ya da kötü bir yerel minimumda kalabilir. Pratikte algoritma farklı başlangıçlarla birkaç kez çalıştırılır ve SSE’si en küçük sonuç seçilir.

Sık yapılan hatalar