BİL204U-ALGORİTMALAR
Ünite 8: Algoritma Örnekleri
Giriş
Algoritma kavramı belirli bir problemin çözülmesine veya bir amaca ulaşılmasına yönelik olarak kurgulanan işlem basamaklarını ifade eder. Bu tanımdan yola çıkarak çözüme giden yolda farklı amaçlar veya problemler için farklı yaklaşımlar izlenmesi farklı algoritma türlerinin ve örneklerinin ortaya çıkmasına olanak tanımıştır. Özellikle problem alanına bağlı olarak izlenecek çözüm yöntemleri ve ilgili yaklaşımlar çeşitlilik göstermektedir. İzleyen bölümlerde üç alanda kullanılan algoritma örnekleri sunulacaktır. Bunlardan ilki makine öğrenmesi çatısı altında yer alan farklı problemlerde sıklıkla kullanılan örneklerdir. Bu bölümde makine öğrenmesi kavramı, sınıflandırması ve yöntemleri sunulacaktır. Ardından yapay sinir ağları kavramı tanıtılacaktır. İkinci bölüm, evrimsel algoritmalar sınıfında yer alan genetik algoritmalardır. Sonuncusu ise kriptografi alanında kullanılan algoritma örnekleridir.
Makine Öğrenmesi Algoritmaları
Makine öğrenmesi insanların öğrenme yeteneklerini taklit etmeyi hedefleyen algoritmaların kullanıldığı bir araştırma alanıdır. Öğrenme yeteneğinin taklit edilmesi ile verilerin sınıflandırılması ve/veya kümelenmesi, veri değerinin tahmini vb. gibi birçok farklı problemin çözümüne ulaşılması mümkündür.
Makine öğrenmesi alanında kullanılan yaklaşımlar gözetimli ve gözetimsiz olmak üzere temel iki sınıfa ayrılır. Bu iki sınıfa ek olarak özellikle girdi olarak kullanılan etiketli veri kümesinin yetersiz olması durumunda kullanılacak yaklaşımları içeren yarı-gözetimli ve pekiştirmeli öğrenme yöntemleri de mevcuttur. İlgili sınıflandırma kitabın 161. sayfasındaki Şekil 8.1’de verilmiştir.
Gözetimli öğrenmede, verileri sınıflandıran veya veri değerlerini tahmin eden algoritmaları eğitmek için etiketli bir veri kümesi kullanılır. Gözetimli öğrenme yaklaşımında etiketli veriler ile eğitilen sistem belirli bir öğrenme düzeyine ulaştıktan sonra etiketsiz veri üzerinde tahminlemeyi gerçekleştirebilir. Kitabın 162. sayfasındaki Şekil 8.2’de ilgili süreç bir şema halinde verilmiştir.
Gözetimli öğrenme süreci içinde öğrenme aşamasında kullanılan veri kümesinin büyüklüğü, kümede yer alan örneklerin temsil yetkinliği vb. gibi unsurlar eğitim aşamasının performansını etkiler. Gözetimli öğrenmede iki temel problem üzerinde çözüm üretilebilir. Bunlardan ilki sınıflandırma problemidir. Sınıflandırma verilen bir örneğin bilinen sınıflardan hangisine ait olduğunun saptanmasıdır. Bu sürecin girdisi sınıfları belirlenmiş/etiketlenmiş örneklerden oluşan bir veri kümesidir. Veri kümesindeki örneklere ait özniteliklerin saptanması sürecin izleyen aşamasıdır.
Sınıflandırma problemlerinde kullanılan algoritmalar tahminleme sürecinde kullandıkları fonksiyon türüne bağlı olarak kategorize edilebilir. Algoritmalar doğrusal,
olasılıksal, örneğe dayalı veya sembolik fonksiyonlar kullanabilir. Örneğin; karar destek makineleri ve lojistik regresyonda doğrusal fonksiyonlar yer alırken Naive Bayes, Gizli Markov modelinde olasılık tabanlı yaklaşımlar mevcuttur. Örneğe dayalı algoritmalardan en yaygın kullanımı olan k-en yakın komşu algoritmasıdır. Bu algoritmada basitçe verilen bir örneğin sınıf etiketi tahminlenirken kendisine en yakın k adet örneğin sınıf etiketi göz önünde bulundurulur.
Gözetimli algoritmalar sınıflandırma dışında değer tahminleme amaçlı da kullanılırlar. Bu durumda ilgili problem sürekli bir problem olarak kabul edilerek regresyon ismiyle anılır. Regresyon algoritmalarında mevcut örneklerin değerleri göz önünde bulundurularak bir tahminde bulunulur. Örneğin, ev büyüklüğü ve fiyat bilgisinin yer aldığı bir örneklem kullanılarak büyüklüğü verilen bir evin satış fiyatı tahmini yapılabilir. İlgili algoritmalara doğrusal regresyon, Lasso regresyonu örnek verilebilir.
Gözetimsiz öğrenme algoritmaları insan müdahalesine gerek olmadan veri içinde saklı kalıpları veya veri gruplamalarını keşfetmeyi amaçlar. Gözetimsiz algoritmaların gözetimli öğrenme ile farkı eğitim sürecinin olmamasıdır. Bu sürecin bulunmaması etiketli veri kümesi ihtiyacını da ortadan kaldırır. Diğer bir bakış açısıyla etiketli veri olmaması durumunda gözetimsiz yöntemler tercih edilir. Sınıflandırma problemine benzer şekilde verilerin belirli kümeler altında toplanması işlemi kümeleme algoritmaları ile sağlanır. Bu yaklaşımda her bir örnek kendine en benzer örnekler ile bir küme oluşturur ancak ilgili kümeye bir sınıf etiketi atanamaz. Gözetimsiz öğrenmenin diğer bir uygulama hedefi ise bir modeldeki öznitelik sayısını, boyut azaltma yoluyla düşürmek için kullanılmasıdır. Birincil bileşen analizi (PCA) ve tekil değer ayrıştırma (SVD) boyut azaltmaya yönelik iki yaygın yaklaşımdır. Kümeleme algoritmalarından ise beklenti- maksimizasyonu (EM), hiyerarşik kümeleme, DBSCAN gibi yaygın kullanımı olan örnekler mevcuttur.
Yarı gözetimli öğrenme, gözetimli öğrenmeye benzer yapıdadır. Ancak sadece etiketli veri kullanan gözetimli öğrenmeden farklı olarak hem etiketli hem de etiketsiz verileri kullanır. Bu algoritmalarda sınırlı sayıdaki etiketli veri kullanılarak ilk eğitim gerçekleştirilir. Ardından bir miktar etiketsiz veri tahminleme süreci sonucunda etiketlenerek eğitim veri kümesi genişletilir. Bu işlem yeteri kadar etiketli veri örneği elde edilene kadar tekrarlanarak süreç tamamlanır.
Pekiştirmeli öğrenme algoritmaları yazılım etmeninin (İng. agent) verilen ortamda en yüksek ödül miktarına ulaşabilmesi için hangi eylemleri yapması gerektiği üzerine kurulmuştur. Ortamın genel olarak bir Markov karar süreci olarak modellendiği bu algoritmalarda ödül miktarını yükselten davranışlara yönelik bir eğilim geliştirilmesi temel öğrenme modelini oluşturur. Pekiştirmeli öğrenme, doğru girdi/çıktı eşleşmelerinin diğer bir deyişle etiket bilgisinin verilmemesi, optimal olmayan eylemlerin
düzeltilmemesi, ortamla etkileşimin sürekli olması gibi çeşitli yönleriyle gözetimli öğrenmeden ayrışmaktadır.
Makine öğrenmesi yöntemlerinin başarımlarını ölçmek için çeşitli başarım metrikleri kullanılır. Bu metriklere doğruluk (İng. accuracy), hata matrisi (İng. confusion matrix), kesinlik (İng. precision), duyarlılık (İng. recall), F1 değeri, ortalama kare hatası örnek olarak verilebilir. Doğruluk değeri sınıflandırma problemlerinde doğru sınıfa atanan (tahminlenen) örnek sayısının toplam örnek sayısına oranıdır. Hata matrisi gerçekleşen ve tahminlenen değerleri gösteren bir matristir. Kitabın 163. sayfasındaki Şekil 8.3’te ikili bir sınıflandırma problemi için örnek hata matrisi verilmiştir. Bu problem örneğinde iki sınıf yer alır ve matris sınıflardan biri baz alınarak hazırlanır. TP değeri sınıflardan birincisine ve TN değeri ise ikincisine doğru şekilde tahminlenmiş örnek sayısını ifade eder. FP değeri ikinci sınıfta olması gerekirken hatalı şekilde birinci sınıfa atanan, FN ise birinci sınıfta olması gerekirken hatalı şekilde ikinci sınıfa atanan örnek sayısıdır. Matris değerleri incelendiğinde TP ve TN değerlerinin yüksek olması yüksek bir sınıflandırma başarımına dair gösterge olarak kabul edilir.
Kesinlik metriği hata matrisinde yer alan TP değerinin TP+FP değerine bölünmesi ile elde edilir. Diğer bir deyişle verilen bir sınıf için doğru tahminlenen örnek sayısının o sınıf etiketi ile etiketlenen toplam örnek sayısına oranıdır. Çok sınıflı problemlerde her bir sınıf için ilgili değer hesaplanarak ortalama kesinlik değeri başarım sonucu olarak kullanılır. Duyarlılık değeri ise verilen bir sınıf için doğru tahminlenen örnek sayısının (TP) o sınıfa ait toplam örnek sayısına (TP+FN) oranı olarak hesaplanır. Diğer bir deyişle bir sınıfa ait örneklerin ne oranda o sınıfa ait olarak tahminlendiğini gösteren bir göstergedir. Bu iki metriğin harmonik ortalaması F1 değerini verir. Ortalama kare hatası ise regresyon problemlerinde sıklıkla kullanılan bir performans metriğidir. Basitçe, tahminlenen değer ile gerçek değer arasındaki farkların ortalamasıdır. Ortalama kare hatası değerinin yüksek olması tahminlerin hatalı olduğu ve tahminlerde gerçek değerlerden uzaklaşıldığına dair belirti olarak kabul edilir.
Karar Ağaçları
Sembolik fonksiyonların kullanıldığı parametrik olmayan algoritmaların en bilinen örneği karar ağaçlarıdır. Karar ağaçlarında temel amaç veri kümesini adımsal olarak böl- fethet yöntemiyle alt gruplara bölerek çözüme yaklaşmaktı. Karar ağaçlarında kök düğüm, düğümler, yapraklar (terminal düğüm) şeklinde isimlendirilen yapılar bulunur (164. Sayfa Şekil 8.4).
Karar ağaçlarında özniteliklerin değerlerine dair sorular ile ağaç katmanları oluşturulur. Hangi öznitelik değerine önce bakılacağı ise bilgi kazanımı (İng. information gain) veya kazanım oranı (İng. gain ratio) gibi metrikler kullanılarak belirlenir.
Quinlan (1986) tarafından önerilen ID3 karar ağacı bilgi kazanımı metriğini kullanan ilk ağaç türlerindendir. ID3
karar ağaçlarında iki kavram önem taşır. Bunlardan ilki entropidir. Entropi basitçe veri kümesindeki düzensizliğin bir ifadesidir. Örneğin; kırmızı ve mavi topların olduğu bir torbada, mavi topların sayısı kırmızı topların sayısı ile aynı ise rastgele seçilen bir topun rengini tahmin etmek kolay olmayacaktır. Diğer bir deyişle düzensizlik yüksektir. Ancak tek bir kırmızı top ve 10 adet mavi topun olduğu bir torbada düzensizlik azdır dolayısıyla tahminleme de daha başarılı olacaktır.
Yapay Sinir Ağları
Yapay sinir ağları insan beyninin karar verme mekanizmasının taklit edilmesine dayalı bir algoritmalar grubudur. Bu algoritmaların temel amacı bir dizi verideki temel ilişkileri tanımaya çalışmaktır.
Yapay sinir ağlarının temel birimi sinir hücresidir. Sinir hücreleri biyolojik sinir hücrelerine benzer bir yapıda tasarlanmıştır. Kitabın 165. Sayfasındaki şekil 8.5’te yapay bir sinir hücresinin genel görünümü verilmiştir. Yapay sinir hücrelerine verilen girdiler (xi) belirlenen ağırlık değerleri (wi) ile ağırlıklandırılarak hücre gövdesinde toplanır/birleştirilir. Hücre gövdesinde yin çıktısı üretilir. Bu çıkış sinyali bir aktivasyon fonksiyonu tarafından işlendikten sonra y sonuç çıktısı ortaya çıkar.
Yapay sinir hücrelerinin girdi işleme sürecinde aktivasyon fonksiyonu, ağırlık değeri ve toplama/birleştirme fonksiyonu temel bileşenler olarak kabul edilir. Bu bileşenlerin başarımı sinir ağının sonuç performansını doğrudan etkiler. Aktivasyon fonksiyonu olarak basitçe verilen bir eşik değerin üstündeki değerleri 1, altındaki değerleri -1 olarak atayan bir işaret fonksiyonunun yanı sıra sigmoid, doğrusal, basamak vb. gibi listelenebilecek çok çeşitli fonksiyonlar kullanılabilmektedir (Sayfa 165. Şekil 8.6).
Çok sayıda yapay sinir hücresinin farklı yapılarda birbirine bağlanmasıyla oluşan yapılar yapay sinir ağlarını oluşturur. Yapay sinir ağları temelde üç ana katmanda incelenir: giriş katmanı, ara (gizli) katmanlar ve çıkış katmanı. Veriler ağa giriş katmanından iletilir. Ara katmanlarda işlenerek oradan çıktı katmanına gönderilirler. Katman sayısına bağlı olarak sinir ağları iki temel gruba ayrılır: tek katmanlı algılayıcılar, çok katmanlı yapay sinir ağları.
Tek katmanlı algılayıcılarda bir girdi bir de çıktı katmanı olur. Çok katmanlı ağlarda ise giriş, gizli katmanlar ve çıktı katmanı yer alır (Sayfa 168 Şekil 8.8).
Genetik Algoritmalar
Evrimsel algoritmalar sınıfında yer alan genetik algoritma (GA) doğal seçilim sürecinden esinlenen bir meta-sezgisel arama ve optimizasyon algoritmasıdır. Genetik algoritmalar, mutasyon, çaprazlama ve seçim gibi biyolojik işlemleri kullanarak optimizasyon ve arama problemlerine yüksek kaliteli çözümler üretmek için yaygın olarak kullanılır. Bu yaklaşımda, verilen problemin arama uzayında yer alan her bir örneği bir kromozom dizini (genetik gösterim) ile ifade edilir. Problem için pek çok
çözümü içeren çözüm kümesine ise popülasyon adı verilir. Genetik algoritmaların işleyişi sırasında mevcut popülasyon üzerinde uygulanarak popülasyonun değişmesine sebep olan işlemlere, genetik operatörler denir. Bunlar seçme, tekrar üreme, çaprazlama ve mutasyon operatörleridir. Genetik algoritmaların kullanımında tipik olarak aşağıdaki basamaklar izlenir:
1. Başlangıç popülasyonu rastlantısal olarak üretilir. 2. Popülasyon içindeki tüm örneklerin amaç/uygunluk fonksiyonu değerleri hesaplanır. 3. Üreme, çaprazlama ve mutasyon operatörleri uygulanır. 4. Oluşturulan her yeni örnek amaç/uygunluk fonksiyonu değerleri hesaplanır. 5. Amaç fonksiyonu değerleri kötü/düşük olan örnekler popülasyondan çıkarılır. 6. 3-5 arasındaki adımlar tekrar edilir.
Çaprazlama
Genetik algoritmalarda çaprazlama operatörü ile ebeveyn olarak seçilen iki örneğin temsil ettiği çözümlerin belirli parçaları karşılıklı olarak değiştirilir. Çaprazlama işlemine bir örnek kitabın 169. Sayfasındaki Şekil 8.9’da gösterilmiştir. Bu örnekte tek bir çaprazlama noktası belirlenmiş ve bu noktadan sonra gelen kısımlar iki örnekte yer değiştirmiştir. Çaprazlama işleminde tek veya çok çaprazlama noktaları rastgele seçilebilirler. Çaprazlama sonrası oluşan bireyler yeni popülasyona aktarılırken ebeveynler ise mevcut popülasyona geri bırakılırlar. Genel olarak, mevcut popülasyondaki örnek sayısına ulaşılıncaya kadar çaprazlama işlemi devam ederek yeni örnekler üretilir.
Mutasyon
Genetik algoritmalarda yeni popülasyonlarda örnekler kendi ebeveynlerinin özelliklerini alarak oluşturuldukları için geçmiş nesillerde yer almayan bir özelliğe rastlanmaz. Bu sebeple örneğin tüm örneklerin ilk değerinin 1 olduğu bir popülasyondan ilk değeri 0 olan yeni bir örnek üretmek mümkün olmaz. Mutasyon operatörü ile nesiller arası kaybedilen veya hiç varolmamış bu tip farklılıkların üretilmesi sağlanır. Çaprazlama işleminden sonra seçilen örneklerin bazı bölümleri değiştirilerek yani mutasyona uğratılarak yeni örnekler oluşturulur. Kitabın 169. Sayfasındaki şekil 8.10’da bir mutasyon örneği verilmiştir. Bu örnekte ilk ve dördüncü değerler mutasyona uğratılmıştır.
Kritografik Algoritmalar
Kriptografik algoritmalar, mesajları şifrelemek ve deşifre etmek için kullanılan süreç veya kurallar dizisidir. Temel olarak istenmeyen kişilerin verilere erişememesini sağlayarak verileri koruyan süreçlerdir. Bu algoritmaların, güvenli ve kimliği doğrulanmış finansal işlemlerin sağlanması da dahil olmak üzere çok çeşitli kullanımları vardır.
Kriptografik algoritmalar temel olarak simetrik ve asimetrik olmak üzere iki sınıfta değerlendirilebilir. Ancak bazı sistemler, her iki sınıflandırmanın bir melezini kullanır.
Simetrik Şifreleme Algoritmaları
Simetrik anahtar veya paylaşılan anahtar algoritmaları olarak da bilinen simetrik algoritmalar, yalnızca yetkili iki tarafça bilinen bir anahtarın kullanılmasıyla çalışır. Bunlar blok şifreler veya akış şifreleri şeklinde uygulanabilirken, mesajın hem şifrelenmesi hem de şifresinin çözülmesi (deşifreleme) için genelde aynı anahtar kullanılır (171. Sayfa Şekil 8.11).
Simetrik şifrelemede teknik olarak, şifreleme anahtarı e ve şifre çözme anahtarı d’nin tam olarak aynı olması gerekmez. Gerekli olan tek şey, e’yi bildiğiniz zaman d’yi ve d’yi bildiğiniz zaman e’yi belirlemenin sayısal olarak önemsiz olmasıdır. Ancak çoğu pratik simetrik şifreleme şemalarında e ve d aynıdır. Veri Şifreleme Standardı (DES) ve Gelişmiş Şifreleme Standardı (AES), simetrik şifreleme algoritmalarının en popüler örnekleridir.
Simetrik algoritmalar anahtar boyunun kısa olması, donanım ile kullanılabilmeleri, hızlı olmaları gibi güçlü yanlara sahiptir. Bunun yanısıra güvenli anahtarın dağıtımındaki zorluk, kimlik doğrulama ve bütünlük ilkeleri hizmetlerini güvenli bir şekilde yerine getirmenin kolay olmaması gibi farklı açılardan ise zayıflıkları vardır.
Asimetrik Şifreleme Algoritmaları
Asimetrik şifreleme algoritmaları, bir genel anahtar ve bir özel anahtar olmak üzere bir çift anahtar gerektirir. Bu algoritmalarda şifrelemek için genel anahtar ve şifre çözmek için farklı, ancak matematiksel olarak ilişkili bir özel anahtar kullanılır (172. Sayfa Şekil 8.12). Bu yaklaşımda genel anahtar biliniyor ise özel anahtarı belirlemek hesaplama açısından olanaksız olmalıdır. Bu sebeple açık anahtarlı şifrelemede, tipik olarak, gerçekleştirmesi nispeten kolay olan ancak kolayca tersine çevrilemeyen matematiksel problemler yer alır. Örneğin, büyük bir tamsayıyı bileşen asal sayılarına geri almayı ve eliptik eğri ayrık logaritma fonksiyonunu çözmeyi gerektiren işlemler vardır. RSA algoritması asimetrik şifreleme algoritmalarının en yaygın örneklerinden biridir. Algoritma iki büyük asal sayının çarpımını çarpanlarına ayırmanın pratik zorluğuna dayanır.
Asimetrik şifrelerin farklı anahtar kullanılarak oluşturulması sebebi ile şifrelemenin kırılması simetrik şifrelemeye göre daha zordur. Farklı anahtarlar kullanılması sebebi ile simetrik şifrelemede karşılaşılan anahtar dağıtma problemi de mevcut değildir. Bununla birlikte anahtarları kullanarak bilgileri çözme işlemlerinde CPU zamanının çok fazla olması asimetrik şifrelemenin zayıf yönüdür.