Sıralı Örüntü Madenciliği (Sequential Pattern Mining)

Eğer veri madenciliği ile ilgileniyorsanız mutlaka adını duymuşsunuzdur. Sıralı örüntü madenciliği veri madenciliğinin bir konusudur ve sıralı bir şekilde ilerleyen değerlerin bulunduğu veri örnekleri arasında, istatiksel olarak uygun örüntüleri bulmayı amaçlar. Örneğin bir mağazada alışveriş yapan müşterilerin 3 ay içerisinde önce bilgisayar, sonraki tarihlerde CD-ROM ve en son dijital kamera satın almaları örüntüsü gibi. Bu alanda birçok önemli bilişimsel problem vardır: verimli veritabanları oluşturmak ve bu veritabanlarında tutulan dizilere erişim için indeksler üretmek, sıklıkla tekrar eden örüntüleri elde etmek, benzerlik için dizileri karşılaştırmak (DNA’daki gibi) ve dizinin kayıp elemanlarını yeniden oluşturmak. Genelde sıra madenciliği problemleri, metin işleme algoritmalarına dayanan karakter dizisi madenciliği (string mining) ve ilişki kuralı öğrenimine (association rule learning) dayanan eleman kümesi madenciliği (itemset mining) olarak iki gruba ayrılır.

Karakter dizisi madenciliği

Karakter dizisi madenciliği, sınırlı sayıda harf bulunan bir alfabenin kullanılarak oluşturulduğu elemanlarda, belirli örüntülerin aranması ile ilgilenir. Fakat örüntünün kendisi çok uzun olabilir. Alfabe olarak günlük hayatta kullandığımız ASCII karakter kümesinden oluşturulan, protein dizilimleri oluşturmak için DNA veya aminoasitlerde kullanılan ‘A’, ‘G’, ‘C’ ve ‘T’ nükleotit isimleri örnek olarak verilebilir. 

Karakter dizilerindeki alfabe düzeninin analizinde kullanılan biyoloji uygulamaları, gen ve protein dizilimlerinin özelliklerinin tespit edilmesi için incelenmesinde kullanılabilir. Amaç sadece, bir proteindeki DNA’da bulunan harflerin dizilimini bilmek değildir. Bunun yerine dizilimin bir anlam ifade etmesi için, yapısının ve hangi biyolojik fonksiyonu ifade ettiğinin bilinmesi gerekir. Bunun için öncelikle her dizilimde bulunan ayrı bölgeler ve yapısal birimler tanımlanır ve devamında her yapısal birime bir fonksiyon atanır. Bunun sağlanması için önceki çalışılan dizilimler ile verilen dizilimin karşılaştırılması gereklidir. Eğer karakter dizisinde eklemeler, silinmeler veya mutasyonlar varsa dizilerdeki benzerliği bulmak oldukça karmaşıklaşır.

Eleman Kümesi Madenciliği

Sıralı örüntü madenciliğinde, eleman kümelerinin oluşma sıklığı ve hangi sıra ile oluştuğu da incelenir. Örneğin, eğer bir müşteri araba almışsa, 1 hafta içerisinde sigorta yaptıracağı öngörülebilir. Veya borsada, Nokia ve Samsung hisseleri yükselişte ise HTC ve IPhone’un da 2 gün içerisinde hisse senetlerinde yükselişi beklenebilir.

Eleman kümesi madenciliği genellikle pazarlama uygulamalarında, sıklıkla birlikte ortaya çıkan ürünlerin düzenliliğinin keşfedilmesinde kullanılır. Örneğin bir süpermarketteki müşterinin alışveriş sepetlerindeki işlemi analiz edelim: Eğer bir müşteri soğan ve patatesi birlikte alıyorsa, aynı alışveriş esnasında kırmızı et de alacağını öngörebiliriz.

Eleman kümelerin madenciliğinde yaygın olarak kullanılan iki teknikten söz edebiliriz: 

• Etkili ön bilgi algoritması (influential apriori algorithm).
• FP-Growth tekniği.

Sonraki yazımda görüşmek üzere..

Büyük Veride Analiz İşlemlerinde MapReduce Kullanımı

Önceki yazımda da anlattığım gibi eğer elimizde oldukça büyük hacimli veriler varsa şu anki ilişkisel veritabanı yönetim sistemleri ile bu verileri saklayabilmemiz ve analiz edebilmemiz mümkün değil. Google tarafından 2004 yılında yayımlanan bir sistem ile bu işlemleri gerçekleştirebilmemiz mümkün hale gelmiştir. Bu sisteme ise MapReduce adını vermişler. Tanımsal olarak MapReduce, büyük veri kümeleri üzerinde dağıtık ve paralel bir şekilde işlem yapmayı sağlayan bir programlama modelidir.  Bu sistem aslen 1960′lı yıllarda geliştirilen fonksiyonel programlamadaki map ve reduce fonksiyonlarından esinlenmiştir. Veriler işlenirken bu iki fonksiyon kullanılır.

• Map(): Filtreleme ve sıralama işlemlerini gerçekleştirir. Örneğin elimizde öğrencilerin bilgileri varsa, adlarına göre ayrı ayrı kuyruklar oluşturup bunlar üzerinde sıralama işlemleri gerçekleştirebiliriz.
• Reduce(): İşlemin sonuçlarının birleştirilmesini ve dökümünü sağlar. Şekildeki gibi her bir kuyruktaki şekilleri sayarak isimlerine göre frekanslarının bulunmasını sağlar. 

MapReduce sistemi, dağıtık sunucuları harekete geçirir, çeşitli görevleri paralel olarak çalıştırılmasını sağlar, sistemin çeşitli parçaları arasındaki veri akışını kontrol eder, ve tüm bu işlemleri sistemde redundancy ve hata toleransı sağlayarak gerçekleştirir. 

MapReduce modeli fonksiyonel programlamada yaygın olarak kullanılan map ve reduce fonksiyonlarından esinlenmiştir fakat MapReduce çatısı altında aynı işleri yürütmezler. Ayrıca, MapReduce Framework’ünün en önemli fonksiyonları, asıl map ve reduce fonksiyonları değildir, fakat çeşitli uygulamalarda bu fonksiyonların çalışma motoru optimize etmesiyle, ölçeklenebilirliğe ve hata toleransına ulaşılabilir.

MapReduce çok sayıda bilgisayar (node/düğüm) kullanarak büyük veri kümeleri arasında paralelleştirilebilir problemleri çözmeye yarar. Çok sayıdaki bilgisayarların hepsi aynı yerel ağı kullanıyorlarsa ve benzer donanımlara sahiplerse cluster(küme), coğrafi olarak farklı alanlara yayılmışlarsa ve farklı donanım konfigürasyonlarına sahiplerse grid olarak adlandırılırlar.


İşlenilen veri, veritabanındaki gibi (yapılandırılmış) veya dosya sistemindeki gibi (yapılandırılmamış) bir ortamda bulunabilir. MapReduce’un kalıcı girdi ve çıktıları genellikle dağıtık bir dosya sisteminde saklanır. Geçici veriler ise genellikle yerel diskte saklanır ve reducer’lar tarafından uzaktan getirilir. MapReduce, yerel verileri kendisine daha yakın konumdaki kaynaklarda işleyerek veri aktarımında oluşan gecikmeleri optimize edebilir ve hız artışı sağlayabilir.

Map adımı:

İlk (ana) düğüm girdiyi alır, daha küçük alt problemlere böler ve işçi düğümlere iletir. İşçi düğüm çok seviyeli ağaç yapısının ilk düğümlerinde bulunuyorsa bu işlemi çocuklara aktarmak suretiyle tekrar gerçekleştirebilir. İşçi düğümler ise küçülen problemi işler ve ana düğüme geri iletir.

Reduce Adımı:

Ana düğüm tüm alt problemlerden gelen çözümleri toplar ve birleştirerek belirli bir biçimde dökümünü sağlar.

MapReduce, dağıtık olarak map ve reduction işlemlerinin çalıştırılabilmesine olanak tanır. Her bir map işlemini diğerlerinden bağımsız olarak yürütür. Aslında bu paralellik bağımsız veri kaynakları sayısı ve bu veri kaynaklarının yakınında bulunan işlemci sayısına oranla sınırlıdır. Benzer olarak indirgen kümeleri (reducer), aynı anda aynı anahtarı kullanan map işleminin bütün çıktılarını alarak reduction evresini gerçekleştirebilirler. Bu süreci işleyen, daha sıralı çalışan algoritmalar da var fakat genelde verimsiz çalışıyorlar. MapReduce ise, elimizde yetersiz sunucular olsa bile daha geniş veri kümelerinde uygulanabilir. Örneğin geniş bir sunucu kümesiyle bir petabyte’lık bir veride, MapReduce kullanılarak birkaç saat içerisinde sıralama işlemi tamamlanabilir. Paralelliğin sağlanması ile eğer girdi verisi hala elimizde ise, işlem esnasında herhangi bir sunucu çökse bile, yapılan iş tekrar zamanlanabilir.

MapReduce’un işlem sırası:

• Map() girdisinin hazırlanması: MapReduce sistemi, Map işlemcilerini tanımlar, her işlemcinin üzerinde çalışacağı K1 girdi anahtarının atamasını yapar, ve işlemciye bu anahtar değeri ile ilişkili bütün girdi verisini iletir.
• Kullanıcının tanımladığı Map() kodunun çalıştırılması: Map() fonksiyonu her bir K1 anahtar değeri için yalnızca bir kez çalışır ve K2 anahtar değerleri tarafından düzenlenecek çıktıyı oluşturur.
• Map çıktısının karıştırılarak (shuffle) reduce işlemcilerine iletilmesi: MapReduce sistemi Reduce işlemcilerini tanımlar ve K2 anahtar değerini, çalıştıracak her işlemciye birer birer atar, ve o anki işlemciye bu anahtar ile ilişkili bütün Map’in oluşturduğu çıktı verisini aktarır.
• Kullanıcının tanımladığı Reduce() kodunun çalıştırılması: Map adımından oluşturulan her K2 anahtar değeri ile ilişkili değer için bir Reduce() fonksiyonu çalıştırılır.
• Son çıktının üretilmesi: MapReduce sistemi bütün Reduce çıktısını toplar ve son ürünü oluşturmak için K2 anahtarı ile sıralar.

Bu 5 adımı mantıksal olarak üstteki gibi bir sıra halinde çalıştığını düşünebiliriz – her adım, başlamak için önceki adımın bitmesini bekler. Ama pratikte ise adımlar tabi ki iç içedir.

Genelde girdi verisi önceden farklı sunuculara dağıtılmış olur ve bazen Map sunucularına yerel olarak temsil edilen veriler atanarak 1. Adım oldukça basitleştirilmiş bir hale getirilir. Benzer olarak 3. Adımda da, Reduce işlemcilerine yerel Map fonksiyonundan oluşturulan veri aktarılarak bu adım hızlandırılabiliyor.

MapReduce'e mantıksal açıdan bakalım

MapReduce’ün Map() ve Reduce() fonksiyonları (anahtar,değer) alacak şekilde yapılandırılmışlardır. Map fonksiyonu veri alanını (data domain) içeren bir çift veri alır ve farklı bir domain çıktı listesini return eder:

• Map(k1,v1) -> list(k2,v2)

Map fonksiyonu girdi veri kümesindeki her çift veriye paralel olarak uygulanabilir. Her Map fonksiyonunun çağrımı için ayrı ayrı birer liste oluşturulur. Sonrasında MapReduce sistemi bütün listelerden aynı anahtarlı veri çiftlerini toplar ve her anahtara bir grup düşecek şekilde gruplar.

Sırayla aynı domaindeki verilerden ayrı bir liste üreten Reduce fonksiyonu daha sonra her gruba paralel olarak uygulanabilir.

• Reduce(k2, list(v2)) -> list(v3)

Her Reduce çağırımı, bir kez çağırıldığı zaman birden fazla değeri geri döndürebilecek kapasitede olsa bile genellikle bir v3 değeri veya bir null değeri döndürür. Bütün fonksiyon çağırımlarından toplanan değerler belirlenen sonuç listesine aktarılır.

Böylece MapReduce sistemi (anahtar,değer) çiftlerinin bulunduğu listeyi değer listesine dönüştürür. Bu davranış, fonksiyonel programlamada keyfi değerlerin bulunduğu bir listeyi alan ve listedeki tüm değerleri sadece tek bir değer olarak düzenleyerek geri döndüren map ve reduce fonksiyonlarından faklıdır.

Örnekler

Aşağıdaki örnek, dökümanlardaki her kelimenin oluşma sıklığını hesaplar:

    function map(String belgeAdi, String belgeIcerigi):
      for each kelime k in belgeIcerigi:
        emit (k, 1)

    function reduce(String kelime, Iterator parcaSayisi):
      kelimeSayisi = 0
      for each parca in parcaSayisi:
        kelimeSayisi += ParseInt(parca)
      emit (kelime, kelimeSayisi)

Burada girdi olarak verilen doküman splitting işleminde önce  satırlara sonra da kelimelere ayrılır. Her kelime bir unique key gibi ele alınır ve ayrı ayrı map fonksiyonu tarafından saydırılır. Sonra shuffling işleminde MapReduce Framework’ü, aynı anahtarlı tüm çiftleri bir araya getirir ve reduce’a iletir. Reducing işleminde aynı anahtarlı kelimeler saydırılır ve nihai sonuç olarak birleştirilir. Böylece bu fonksiyon, sadece girdi değerlerini kullanarak verilen kelimenin toplam görülme sıklığını elde etmiş olur.

Kullanım Alanları

MapReduce dağıtık şablon-temelli (pattern based) aramalarda, dağıtık sıralama işlemlerinde, web tarafından erişilen log istatistiklerinde, belgelerin kümelenmesi işlemlerinde, makine öğreniminde ve istatistiksel makine çevrimi olmak üzere geniş çaplı uygulamalarda kullanılıyor. Çok işlemcili sistemlerde, masaüstü  ağlarında, eyewire uygulaması gibi gönüllü işlem yapma ortamlarında, dinamik bulut sistemlerinde ve mobil tarafında da adapte bir şekilde çalışabiliyor.

MapReduce, Google’da dünyadaki tüm sitelerin indekslerini tamamen yenilemek için kullanılıyordu. Önceden de indeksi güncelleyen ve çeşitli analizler gerçekleştiren programlar kullanıyorlardı. Fakat MapReduce’un üretilmesi ile hepsi rafa kaldırıldı.

Şu an sadece Google değil, Facebook, Twitter, Linkedin, Foursquare gibi çok fazla veri toplayan sosyal ağ uygulamalarında kullanılıyor. Son 2 yılda üretilen verilerin geçen 10 seneden fazla olduğunu düşünürsek, MapReduce sisteminin geleceğinin parlak olduğunu söylemek yanlış olmaz.

MapReduce kütüphaneleri farklı optimizasyon seviyesindeki birçok farklı programlama dili ile yazılmışlardır. Açık kaynaklı popüler implementasyonu ise Apache Hadoop’tur. Sonraki yazımda Hadoop'tan bahsedeceğim, görüşmek üzere... 

Kaynaklar: Wikipedia, Devveri

Büyük Veri (Big Data) Nedir?

Son zamanlarda birçok çevre tarafından adının yaygın olarak kullanıldığı fakat tam olarak da ne olduğu hakkında herkesin pek az şey bildiği büyük verinin (big data) nasıl bir kavram olduğundan bahsedeceğim.

Günümüzde makul zamanda işlememiz gereken veri boyutu ekzabaytlara ulaştı. Bilim adamları meteoroloji, genetik, konnektomi, karmaşık fizik simülasyonları ve biyolojik ve çevresel araştırma gibi alanlardaki  büyük veri kümeleri üzerinde işlemler yapabilmesi kısıtlı seviyelere geldi. 
Bu sınırlar ayrıca arama motorları, finans ve ticari bilişime de etki etti.

Veriler bu hızlı çağda katlanarak artıyor, çünkü herkesin elinde bulundurduğu mobil cihazlardaki bilgi toplama birimleri, uzaktan algılayan sensörlü teknolojiler, yazılım logları, kameralar, mikrofonlar, radyo frekansı ile kimlik okuyucuları ve kablosuz sensör ağları kullanımı bu duruma yol açıyor. 1980’lerden beri dünyada kişi başına düşen veri miktarı neredeyse her 40 ayda bir ikiye katlandı ve 2012 rakamlarına bakacak olursak her gün 2.5 ekzabayt veri üretiliyor.

Büyük veri bilimde de kullanılıyor. Büyük Hadron Çarpıştırıcısı deneylerinde 150 milyon adet sensör kullanılıyor ve bu sensörler saniyede 40 milyon defa veri topluyor. Saniyede yaklaşık olarak 600 milyon defa çarpışma meydana geliyor ve bu çarpışmalardan %99.999’u filtrenerek, geriye kalan 100 çarpışma/sn ile ilgileniliyor.

Sonuç olarak sensör akışlarından gelen verilerin sadece %0.001’i bile kullanılsa da yıllık oluşan veri 25 petabaytı buluyor ve bu veri üzerinde çıkarsamalar yapılarak ve kopyalanmalar sonucu oluşan veri 200 petabaytı geçiyor.

Veriler bu seviyelerde gezindiği için geleneksel yöntemlerle iş yapmak zor hale geliyor. Çünkü veritabanlarının bu kadar veriyi üzerinde barındırabilmesi ve işlem yapabilmesi çok zor ve zaman açısından maliyetli. 

Bu şekilde halihazırda bulunan veri yönetimi araçları veya geleneksel veri işleme uygulamaları kullanılarak işlenmesinin mümkün olmadığı, çok büyük ve oldukça karmaşık veri yığınlarına büyük veri denilir.

Eğer elimizde oldukça büyük veriler varsa bu verilerin üzerinde yapılan iyileştirmeler, verilerin saklanması, aramaların yapılması, paylaşılması, başka birimlere aktarılması, üzerlerinde analizlerin gerçekleştirilmesi ve görselleştirilmesi  bize zorluk çıkarabilir. Böylesine büyük veri kümelerinin ortaya çıkabilmesinin nedenlerinden biri de küçük bir veri kümesi ile ilişkili verilerin birbirleri ile analizi sonucu ek bilgilerin türetilmesinin gerçekleşmesidir.

Büyük Verinin 4V'si
2001 yılında yapılan bir araştırma raporunda ve ilişkili konferanslarda META Grup analisti Doug Laney veri artışında yüzleşilecek sorunların ve sorumlulukların 3 boyutta seyir ettiğini tanımlamıştır:                              

• Volume (Hacim):  Şu an dünya üzerinde 7 miyar insan bulunurken elinde cep telefonu olanların sayısı ise 6 milyar seviyesinde. Durum bu seviyedeyken büyük veriyi  belki de gerçekten "büyük" yapan şey şu anki tutulan verilerin zamanla üssel olarak artması. Veriler bu hızlar artarken kuruluşların da bu verileri yönetmek için olan maliyetleri de artıyor.  Bu yüzden büyük verinin tutulacağı ortamın ayarlanması gerekiyor.
• Velocity (Hız): New York Stock Exchange her işlem seansında 1TB ticari bilgi tutuyor. 2016'da 18.9 milyar bilgisayar ağının oluşması bekleniyor. Veriler bu şekilde büyüyerek artarken çok hızlı bir şekilde sisteme aktarılıyor ve sistemin de bu hızla akan verileri karşılaması gerekiyor. Bu yüzden hız da büyük veriyi karşılayan bir diğer etmen haline geliyor.
• Variety (Çeşitlilik): Bilgi toplamada kullanılan sensörlerin artışı, sosyal ağlar, RSS'ler ve bu kaynaklardan gelen verilerin çeşitliliği büyük verinin önemini daha çok vurguluyor. Örneğin modern arabalarda benzin seviyesi ve gaz basıncını ölçen yaklaşık 100'e yakın sensör bulunuyor. 
• Veracity (Doğruluk): Üstte tanımlanan 3V'ye Gartner şirketi 2012 yılında bir V daha ekliyor. Veriler bu kadar hızlı toplanırken kalitesi de önem arz ediyor. Bir rapora göre bozuk verilerin Amerikan Hükümeti'ne yıllık maliyeti 3.1 trilyon dolar. Bu yüzden toplanan büyük verinin ayrıştırılmaya ihtiyacı var.

Sonraki yazımda büyük verinin nasıl işletileceğine değineceğim. Görüşmek üzere...

Kaynaklar: Wikipedia, Oracle, IBM, HP