Ağ verisi üzerinde ilgili ve rastgele alt uzaylar seçerek birlikte öğrenme
Relevant and random subspaces for co-training in networked data
Yazar: KADRİYE BAĞLIOĞLU
Danışman: DOÇ. DR. ZEHRA ÇATALTEPE
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2013
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Gün geçtikçe finansal ağlar, gen düzenleyici ağlar, elektrik dağıtım ağları yanında Facebook, Twitter, Linkedln gibi sosyal ağlar da hayatımızda vazgeçilmez bir hale gelmiştir. Bu ağların ve kullanıcılarının hızla artması ağ bilgisi içeren veri miktarının günden güne artması anlamını taşımaktadır. Bu veri artışına paralel olarak ağ verisi üzerinde çözülmesi gereken problemlerin önemi ve miktarı da hızla artmıştır. Bu sebeple, ağ verisi içeren problemlerin yapay öğrenme yöntemleri ile çözülebilmesi önem kazanmıştır.
Bu tez çalışmasında, ağ verisi üzerinde düğüm sınıflandırma problemi için önceki çalışmalarda kullanılmış olan iki yöntem kullanılmıştır. Bunlar, içerik tabanlı ve öz yinelemeli kollektif sınıflandırma yöntemleridir. Bu yöntemlerin yanında, ağ verisi üzerinde uygulanan birlikte öğrenme (co-training) yöntemi irdelenmiştir. Önceki çalışmalarda ağ verisi üzerinde kullanılmış olan ve bu çalışmada incelenen yöntemler, sadece verinin içerik bilgisinden faydalanmakta olan içerik tabanlı sınıflandırma yöntemi (CO) ve verinin sınıflandırılmasında hem içerik hem de ağ bilgisinden faydalanmayı hedefleyen özyinelemeli kollektif sınıflandırma algoritmasıdır (ICA).
Özyinelemeli sınıflandırma algoritması veri üzerindeki ağ bilgisini komşularının etiket bilgilerini kullanarak elde etmektedir. Bu amaçla öncelikle etiketlenmemiş verileri geçici olarak etiketleyerek kullanmaktadır. Bunun ardından yapılan sınıflandırmalar ile sınıflandırma sonuçları doğrultusunda etiketleri güncelleyerek kullanmaktadır. Fakat ağ verisi üzerinde bilinen veri miktarı azaldıkça geçici etiketleme oranı artmaktadır. Bu da ağ verisinden elde edilen bilginin daha belirsiz hale gelmesine neden olmaktadır. Bu durumu önlemek amacıyla, çalışma kapsamında, Barış Şenliol'un 2010 yüksek lisans tezinde olduğu gibi ağ verisinden elde edilen bilgilerin verilerin etiketleri bilinmediği durumda da tüm veriler için bilinen öznitelikler ile elde edilmesi konusu incelenmiştir. Bu kapsamda bir düğümün kendi ve komşularının öznitelikleri kullanılarak zenginleştirilmiş öznitelikler farklı şekillerde (ve,veya, toplam...) oluşturulmuş ve varolan sınıflandırma algoritmaları üzerindeki etkileri araştırılmıştır. Yapılan deneylerde, zenginleştirme yöntemlerinin, veriye bağımlı olmakla beraber, başarım üzerinde olumlu etkilerinin olduğu görülmüştür. 
Ağ verisi problemleri için tezde kullanılan diğer yöntem birlikte öğrenme (co-training) yöntemidir. Ağ bilgisi içermeyen veri kümeleri üzerinde birlikte öğrenme yöntemi,Yusuf Yaslan ve Zehra Çataltepe?nin (2010) önceki çalışmaları esas alınarak kullanılmıştır. Bu çalışmada veriye ait öznitelikler üzerinde ilgili ve rastgele alt uzaylar oluşturulur bu alt uzaylarda eğitilen sınıflandırıcılar birleştirilerek birlikte öğrenme yapılır. Tez kapsamında ise bu yöntem ağ verisi üzerinde test kümesinde olup öznitelik ve bağlantıları bilinen ama etiketleri bilinmeyen düğümlerin, zenginleştirilmiş öznitelikler de kullanılarak eğitime dahil edilmesi ile uygulanmıştır. Ağ verisi üzerinde birlikte öğrenme yöntemleri kullanarak başarımın arttırılması hedeflenmiştir. Birlikte öğrenme algoritmasının alt uzayları ilgili ve rastgele olarak seçilmesini sağlayan Rel-RASCO (Relevant Random Subspaces for CoTraining, Yusuf Yaslan ve Zehra Çataltepe, 2010) yönteminin ağ verisi üzerinde uygulanması ve tezde önerilen bu yöntemin ağ zenginleştirilmiş öznitelikler ile kullanıldığı Rel-RASCONet (Enriched Relevant and Random Subspaces for CoTraining) yöntemi karşılaştırılmıştır. Yapılan deneylerle zenginleştirilmiş özniteliklerin katkısı ile oluşturulan Rel-RASCONet metodunun, sadece düğüm öznitelikleri kullanan Rel-RASCONet yöntemine göre daha başarılı olduğu görülmüştür. Bu yöntemlerin dışında farklı bir yöntem olan EnrSelCO (Enriched and Selected Subspaces for Co-training) kullanılmıştır. EnrSelCO yöntemi zenginleştirilmiş öznitelikler ile altuzaylar oluşturup ve bu alt uzaylar üzerinde öznitelik seçme yöntemleri uygulayarak altuzayların özniteliklerinin kalitesinin arttırılmasını amaçlamaktadır. Oluşturulan zenginleştirilmiş ve seçilmiş öznitelik altuzayları üzerinde sınıflandırıcılar eğitilerek birlikte öğrenme işlemi uygulanmıştır. Az sayıda, kaliteli ve ağ bilgisi içeren öznitelik altuzaylarının oluşturulması bu yöntem ile sağlanmıştır. Yapılan deneyler ile bu yöntem diğer yöntemler ile karşılaştırılmış ve az sayıda öznitelikler ile başarımının daha iyi olduğu görülmüştür.
Bu konular dışında, çalışma kapsamında ağ verisi üzerinde uygulanan birlikte öğrenme yönteminin davranışı incelenmiştir. Yapılan deneyler ile sınıflandırıcı sayısının ve öznitelik alt uzaylarının boyutunun birlikte öğrenme başarımına olumlu etkisinin olduğu, fakat zaman ve kaynak bakımından sınıflandırıcı sayısı ve öznitelik alt uzayları boyutunun dengelenmesi gerektiği görülmüştür.  Gözlenen diğer bir sonuç,  yapılan eğitimler sırasındaki iterasyonlar ile başarımın olumsuz etkilenebildiği, algoritmanın erken durdurulması ile başarımın arttırılabileceğidir. Yapılan deneylerde iterasyonlarda eğitim ve test başarımlarının paralel olarak ilerlediği görülmüştür. Bu nedenle eğitim verisinin başarımının azaldığı yerde durulmasının başarıma olumlu etkisinin olduğu gözlemlenmiştir.
Çalışma kapsamında incelenen diğer konu öznitelik uzaylarının boyutlarının azaltılmasıdır. Öznitelik uzaylarının boyutunun azaltılması öznitelikler üzerindeki gürültünün azaltılarak kaliteli özniteliklerin kullanılmasını sağlar. Çalışma kapsamında ağ verisi üzerinde uygulanan algoritmalar ve birlikte öğrenme yöntemi için oluşturulan alt uzayların öznitelik seçme yöntemlerinin kullanılması ile performansları incelenmiştir. ICA ve CO üzerinde az sayıda öznitelik ile makul başarımların elde edildiği görülmüştür. Öznitelik seçme yönteminin etkisi hem zenginleştirilmiş öznitelikler hem de verinin öznitelikleri üzerinde incelenmiştir.

Abstract:
In our modern lives, there are many different kinds of data that contain network information in them, such as telephone networks, financial networks, electricity distribution networks, gene regulatory networks. In addition to these types of networks, with the information age and the spread of the Internet caused to born new datas that constains network information, for instance Facebook, Twitter, LinkedIn and other social networks. By the huge increase in the data that contains network information, network problems to be solved on this data have increased in importance. To overcome this issue machine learning techniques are available. Machine learning is an subsection of artificial intelligence. It aims to learn from data. In this thesis, our goal is learning labels from networked data. In order to this aim, we analyse several collective classification techniques and adapt co-training to networked data.
Classification of networked data that contains the network nodes, using both network and node informations is an important problem to be solved. For this reason, the scope of work focused on this issue. Another problem is mentioned in this thesis is labbeled data cost. Labelling data is costly, decreasing this cost is an important problem. For this reason, in this study our experiments little labeled data(such as %40 training, %60 testing data). Other problem, we come up in this thesis size of datasets. This problem causes increasing classification time.
In this study, we mention collective classsification. Collective classification is an classifiying tecnique which uses networked data. Networked data includes links between nodes (such as communication of networked data includes peaple connected via communication link).  In addition to this, collective classification tecniques uses features information , neighbours features labels information and testing data labels  (Sen, Namata, 2008). We use in our experiments  three networked dataset for experiments. Cora and Citeseer datasets are scientific. WebKB contains website informations. We gave this datasets details in this thesis.
We use two methods which have been used in collective classification problems with the previous works. These are Iterative Classification Algorithm (ICA) and Content based classification algorithm Content Only (CO). CO does not use network information while classification. Collective classification algorithms such as ICA, classify known test nodes of networks using label informations that test nodes gave to each other.. In the collective classification, classifiers make classification according to the collective attributes of both the node and the node's neighbors. However, usage of the estimated labels of the neighborhoods causes decreases in clasification performace especially in the case of that the test set contains a great number of neighborhoods or neighborhoods that close to each other.  It is observed that, because of the fact that estimated labels caries some amount of error, the performance of the classification is diminishing during the iterations. In order to prevent the situation and  use network information, the information obtained from network data using attributes of nodes can be used as enriched features. In previous work, enrichment of features are uses (Senliol, 2010). We use this feature enrichment method technique. In this study, different types of enrichment methods such as And, Count, Or  are used for enrichment of the features. Feature enrichment methods are used  In the experiments, on the data enrichment methods have proved to be a positive impact on performance. 
The other method which we used in experiments on networked data is co-training algorithm. This method focuses on the problem of a large number of unlabeled data. For this reason, it aims to take advantage of unlabeled data, taking part in training during the training. For this reason, it is an semi-supervised learning technique.  In addition, this method aims to create a more powerful classifiers by combining the results of weak classifiers which are creating using the different wiews of the data. This method has been proposed in 1998 by Blum and Mitchel. ICML was selected as the best work of last 10 years, in 2008.
Co-training is an complex technique that have many subsections. In this study, we mention on these subsections: Subspece selection of data for  creating different classfiers and early stopping of co-training. 
Subspece selection methods are examined and two new techniques EnrSelCo and Rel-RASCONet are suggest with this study. In previous works, there are many different subspace selection methods for co-training. Random Subspace Selection for co-training (RASCO) is the one of them. It is an easy algorithm which partioned subspaces randomly. Other technique is Relevant and Random subspaces for Co-training(Rel-RASCO) . Rel-RasCONet aims to using relevant and random subspaces in order to create more powerfull classifiers. This technique suggest by Yusuf Yaslan and Zehra Çataltepe in 2010. Their study shows that Rel-RasCO is better than RASCO, so that in this study we use Rel-RASCO subspace selection method. On the other hand, Rel-RASCONet which is an extension of  Rel-RASCO. Rel-RASCONet  uses enrichment features and uses test data while training is suggested in this study. These two methods is compared. It has been observed that Rel-RASCONet performance is better than Rel-RASCO. In addition to this, we analyse the relevance factor. We compare training relevance and testing relevance of features relations for different types of sampling size. We show that sampling rhich partiones data %50 training and %50 test has the best relation between training and testing relevance of features.
The other subspace selection method for co-training which used in the study is Enriched Relevant and Random Subspaces for Co-Training (EnrSelCO). EnrSelCo method creates sub-spaces using enriched features after apply them feature selection. This creation of subspaces aims to improve the quality of attributes. Created subspaces with the method provides a small number of high-quality attribute that contains the network information. Experiments conducted with this method compared with other methods. 
Other issue is early stopping while co-training. The experiments have been showed that progressing in line with the achievements of the training and testing iterations. Therefore, using training achievement while early stopping prevents decreasing accuracy with iterations. In this study, we measure the training and testing performance at different points while co-training. These points are training best accuracy, training decreasing accuracy, training start accuracy and training end accuracy. We show that both training and testing performance at the and is the worst accuracy. Testing accuracies best point is training best point or training decreasing point. This results shows that early stopping using training accuracy metric increase the testing accuracy for co-training.
In addition to these issues, behaviours of co-training method applied on the network data were analyzed. We observed with the experiments that size of the classifiers and size of subspaces dimensions have positive effects on the performance of  learning. In the same time, they have negative effects on time and  resources so that these factor balance was needed. 
Additiona,l analyzing issue for co-training is combining classifiers and chosing the test data which is added to training in this thesis. For this issue we compare two methods. These are  majority voting and getting maximum of the classifier results. We show that majority voting is better than the other method. Other experiment is using f-measure of training while combining classifiers. This method is costly. It does not gives more better accuracy in our experiments. It must be improve with future works.
Another issue examined in the scope of thesis to reduce the size of the attribute spaces using feature selection methods. Reducing the size of spaces, reducing the noise on the quality attributes attribute enables the use more qualified attributes. We use minimum redundancy and maximum relevance feature selection (mRMR). ICA and CO were obtained on a small number of attributes and achievements are reasonable. In addition to this, we use enrichment features for CO and ICA. As well as the effect of enriched and selected features on the networked data analyzed.
In conclusion, in this thesis collectice classification techniques CO and ICA are examined.  Feature selection and enrichment methods are apply to CO and ICA. Experiments shows that feature selection and enrichment has positive effects on accuracy. Feature enrichment type is afects accuracy directly. We show that if network information in dataset is high or enrichment type shows best accuracy. It must be investigate that decide true enrichment type analysing datasets. Co-training algorithms Rel-RASCO, Rel-RASCONet and EnrSelCO are examined. Early stopping and behaviours of co-training issue is investigated. We show that Rel-RASCONet and EnrSelCO increase accuracies but they have some deficiencies. Both of algorithm diversities of subspaces must be investigate. Additionally, finding optimum subspace size and subspaces feature size using dataset information automatically can be future work. Additional searching issue for Rel-RASCONet is measuring relevance factor with different types of relevance metrics. On the other hand, co-training algorithm is complex algorithm and it has high time complexity. 
Thesis is organised as follows. 
?	Section 1:  We introduce the thesis scope and aim in this section. 
?	Section 2: In this section, background of thesis is given. These are classifiers,  sampling, classification, co-training, performance criterias. 
?	Section 3: This section contains operations which are apply to the features. These are feature selection and feature enrichment techniques. 
?	Section 4: This section contains collective classification algorithms and co-training algorithms details. 
?	Section 5: Datasets using in our experiments are explained in this section.
?	Section 6: The results of the experiments, setups, discussion on what we have observed in this study and future research directions are given in Section 6.