Archive for Nisan, 2015

Kemmi Normalleştirme (Quantile Normalization)


Written By: Şadi Evren ŞEKER

Quantile Normalization in the literature, and in many Turkish sources as the quantitative normalization translated into the concept (the root of the word qunatity, so I chose to use the word that comes from numerical or kemiyet).

Kemmi normalization is simply a method used to make two or more different data sets with similar distributions. statistical normalization. Accordingly, it is important that the numbers in the data set are in order of rank rather than their values ​​and the normalization system is based on this.

Let us examine the operation of the system through an example:

A 15 4 3
B 12 1 4
C 13 4 6
D 14 2 8

We have 3 different datasets given above (each column containing numerical values ​​for each row A to D is considered a different dataset)

The statistical properties of these datasets are different from each other and comparisons are error. Therefore, we are trying to bring the kemm to the same statistical distribution characteristics using normalization.

Our first step is to determine the rank of each value in that column:

A 4. 3.1.
B 1. 1 2.
C.2.3.3.
D 3. 2. 4.

The order of each element in the relevant column is given above. Then, we sort each column from small to large. For example, the data in our first column was in the order of {15, 12, 13, 14}, and when we rank them from small to large, we expect to obtain {12,13,14,15}. The columns are listed as follows:

A 12 1 3
B 13 2 4
C 14 4 6
D 15 4 8

After sorting, we actually find the average of each row so that each column has the same distribution. That is, we will find the property of the elements in the first second row of the common distribution, since they will have the same distribution. To do this, we find the average of each row element:

A 12 1 3 (12 + 1 + 3) / 3 = 16/3 = 5.3
B13.24 (13 + 2 + 4) / 3 = 19/3 = 6.3
C14.46 (14 + 4 + 6) / 3 = 26/3 = 8.6
D 15 4 8 (15 + 4 + 8) / 3 = 27/3 = 9

Now we can update the corresponding row in each column according to these average values. In other words, we will update the values ​​in the columns by typing 5.3 ına in the first order and 6.3 ına in the second order:

A 9 8.6 5.3
B 5.3 5.3 6.3
C 6.3 8.6 8.6
D 8.6 6.3 9

In all cases, the same numbers are present in all columns and the differences between the columns (eg, average of each column, standard deviation, etc.) have disappeared. Each column was updated with values ​​that were relatively identical in the same statistical distribution.


Ters Parça Algoritması (Reverse Factor Algorithm)


Yazan : Şadi Evren ŞEKER

Algoritma iki dizgiyi (string) karşılaştırmak için kullanılır. Basitçe bir dizgide aranan daha kısa dizginin öncelikle aşağıdaki şekilde karşılaştırılması ile başlanır. Ardından şayet uyum sağlanıyorsa bulundu olarak sonuç döndürülür, şayet uyum sağlanmıyorsa iki ihtimal vardır, dizgilerin karşılaştırılan kısımlarından uyan en uzun eke kadar kaydırma yapılır veya hiç uyuşma yoksa aranan dizgi kadar kaydırma yapılır.

Öncelikle bu kaydırma durumunu anlayalım. Uzun olan dizginin kısa olan dizgi kadarlık ilk kısmı aşağıdaki şekilde karşılaştırılacak.

reverse_factoring_algo1

Diyelim ki aradığımız uyum bulundu, o zaman bulduk diyerek sonucu döndürebiliriz.

reverse_factoring_algo2

Diyelim ki aradığımız uyum bulunamadı, o zaman acaba en azından bir kısmı uyuyor mu diye bakarak uyan kısmına kadar kaydırıyoruz.

reverse_factoring_algo3

Şayet hiç uymuyorsa, kısa olan dizgi kadar kaydırarak kalanını aramaya devam ediyoruz.

reverse_factoring_algo4

Algoritmanın mahareti, bu iki dizgiden bir kısmının uyup uymadığını nasıl bulduğunda saklı. Bunun için bir ek ağacı (suffix tree) oluşturuluyor ve bu ağaç kullanılarak hızlı bir şekilde iki dizginin ne kadarlık kısmının uyduğu tespit edilebilir. Biz de bir örnek üzerinde bu karşılaştırmayı yapalım. Bunun için öncelikle iki örnek dizgiyi aşağıdaki şekilde alalım:
Dizgi 1 : GCATCGGCGAGAGTATACAGTACG
Dizgi 2 : GCAGAGAG , boyutu 8 harf

Yapacağımız karşılaştırma öncesi, dizgi 2 için bir otomat oluşturuyoruz (sonlu durum otomatı (finite state machine). Otomat oluştururken aslında bizim Dizgi 1 içerisinde aramak istediğimiz dizgi 2 ihtimallerinin bir kümesini kabul eden otomat oluşturma hedefimiz var. Yani öncelikli olarak baktığımız dizgi2’nin tamamının (8 harfinin de ) içerilmesi, şayet bulamıyorsak, dizgi2’nin bir alt kümesi olan ve ilk 7 harfinin içerildiği bir durum bulmak (yani 1 kere yana kaydırılmış hali olarak düşünülebilir). Dolayısıyla otomatı oluşturacağımız alt küme L(S) ile gösterilecek olursa aşağıdaki şekildedir:

L(S) = { GCAGAGAG, GCAGAGA, GCAGAG, GCAGA, GCAG, GCA, GC, G, {} }

Kümenin sonunda ayrıca bir boş küme elemanı bulunmakta ve hiçbir harfin uymaması durumunu ifade etmektedir. Yukarıdaki kümedeki elemanları kabul eden sonlu durum otomatı (Finite state machine) aşağıdaki şekilde çizilebilir:

 

reverse_factoring_algo5

Dizgi de tekrar eden bazı alt dizgiler olduğu için yukarıdaki şekilde bir otomat oluşturuldu. Şimdi bu otomat kullanılarak bir ek ağacı (suffix tree) oluşturulabilir:

reverse_factoring_algo6

Yukarıdaki ek ağacı bizim dizgi karşılaştırmalarımızda kullanacağımız ve ne kadarlık son kısmın benzediğini bulmamıza yarayacak ağaç. Ağaç üzerinde her düğüme (node) birer numara verilmiş ve ayrıca ağacın yapraklarının altına da o yaprağa kadar izlenen yoldaki dizginin uzunluğu yazılmıştır.

Şimdi örnek olarak bir karşılaştırma durumunu ele alalım. Örneğin karşılaştırma işlemi aşağıdaki gibi dizgi1’in 6. Karakterinden itibaren dizgi 2’yi karşılaştırıyor olalım:

reverse_factoring_algo7

Yapacağımız işlem, pencereye dahil olan kısmı itibariyle (pencere boyutumuz dizgi 2’nin boyutu yani 8) en son karakter ile dizgi2’yi karşılaştırmak. Yani aslında karşılaştırılan ilk harfler aşağıdaki şekilde:

reverse_factoring_algo8

Ardından ek ağacındaki bir sonraki harfi yani aslında penceredeki sondan ikinci karakter ile dizgi2’nin ikinci karakterini aşağıdaki şekilde karşılaştırıyoruz ve bu işlem uyuşma olduğu sürece devam ediyor:

reverse_factoring_algo9

Sonuçta uyuşma olmayan noktaya erişildiğinde duruyoruz ve uyuşma olduğu kadar kaydırma işlemi yapıyoruz:

reverse_factoring_algo10

Aslında yukarıda dizgi üzerinde anlatılan bu işlem yapılırken ağaç üzerinde aşağıdaki şekilde bir yol izlenmiş ve 6 numaralı bitiş durumu ile otomat sonlandırılmıştır.

reverse_factoring_algo11
Algoritmanın ön işleme süresi, yani ek ağacını oluşturma süresi dizgi 2’nin boyutu ile orantılıdır ve bu boyut m ise karmaşıklığı O(m) olacaktır. Ardından arama süresindeki algoritma karmaşıklığı ise dizgi1’in boyutu ile orantılı olarak O(mn) olarak bulunacaktır.

Diğer Dizgi Arama Algoritmaları:

Kaynaklar
• Algorithms for finding patterns in strings, A. V. Aho, Handbook of Theoretical Computer Science, Vol. A, Elsevier, Amsterdam, 1990, pp.255-300.
• The myriad virtues of suffix trees, Apostolico, A., Combinatorial Algorithms on words, NATO Advanced Science Institutes, Series F, Vol. 12, 1985, pp.85-96
• The Boyer-Moore-Galil string searching strategies revisited, Apostolico, A. and Giancarlo, R., SIAM, Comput. 15, 1986, pp98-105.
• Average running time of the Boyer-Moore-Horspool algorithm, Baeza-Yates, R. A. and Regnier, M. Theoret. Comput. Sci., 1992, pp.19-31.
• Analysis of algorithms and Data Structures, Banachowski, L., Kreczmar, A. and Rytter, W., Addison-Wesley. Reading, MA,1991.
• Speeding up on two string matching algorithms,
• Presentation of Prof. R. C. T. Lee and L. C. Chen ,Algorithmica, Vol.12, 1994, pp.247-267, CROCHEMORE, M., CZUMAJ, A., GASIENIEC, L., JAROMINEK, S., LECROQ, T., PLANDOWSKI, W. and RYTTER, W.


  • Copyright © 1996-2010 Bilgisayar Mühendisinin Notları. All rights reserved.
    iDream theme by Templates Next | Powered by WordPress