Geri Dön

Algorithms for sparsity constrained principal component analysis

Seyrek kısıtlı temel bileşen analizi için algoritmalar

  1. Tez No: 828250
  2. Yazar: FATİH SELİM AKTAŞ
  3. Danışmanlar: PROF. DR. MUSTAFA ÇELEBİ PINAR
  4. Tez Türü: Yüksek Lisans
  5. Konular: Endüstri ve Endüstri Mühendisliği, Industrial and Industrial Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2023
  8. Dil: İngilizce
  9. Üniversite: İhsan Doğramacı Bilkent Üniversitesi
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Endüstri Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 103

Özet

Klasik Temel Bileşen Analizi problemi, orijinal veri kümesinin boyutunu azaltırken varyansyonun çoğunluğunu koruyan bir lineer dönüşüm bulmayı hedefler. Ekstra seyreklik kısıtı, katsayıların çoğunu sıfıra sabitler ve lineer dönüşümün yorumlanmasını kolaylaştırır. Seyreklik kısıtlı Temel Bileşen Analizi için iki yaklaşım sunuyoruz. İlk olarak, çok yüksek boyutlu problemlerde kullanılabilecek hesaplamalı olarak ucuz sezgisel yöntemler geliştiriyoruz. Sezgisel yöntemlerimiz, doğrusal cebir yaklaşımları ve teorik garantilerle haklı çıkarılmıştır. Ayrıca, optimizasyon modeli için gerekli koşulları uygulayarak algoritmalarımızı güçlendiriyoruz. İkincisi, yarı belirli uzayda dışbükey olmayan log-toplam cezası kullanıyoruz. Bu fonksiyonun kardinalite fonksiyonuyla bağlantısını gösteriyor ve bu problemi çözmek için PCA Sparsified adlı bir dizi dışbükey optimizasyon problemini çözen bir algoritma geliştiriyoruz. Bu algoritmanın teorik özelliklerini analiz ediyor ve sayısal uygulaması hakkında yorum yapıyoruz. Ayrıca, önceki yaklaşımlarla birlikte kullanılabilecek bir ön işleme yöntemi türetiyoruz. Son olarak, yaptığımız sayısal deneylerden elde ettiğimiz bulgular, açgözlü algoritmalarımızın yüksek boyutlu problemlere kolayca ölçeklendiğini ve birçok problemde halihazırda mevcut olan algoritmalarla oldukça rekabetçi olduğunu hatta bazı durumlarda devamlı olarak geride bıraktığını göstermektedir. Ayrıca, PCA Sparsified'in açıklanan varyans açısından düşük boyutlu problemlerdeki etkinliğini gösteriyoruz. Hesapsal olarak pahalı olmasına rağmen, yerel ve açgözlü yaklaşımları sürekli olarak geride bırakmaktadır.

Özet (Çeviri)

The classical Principal Component Analysis problem consists of finding a linear transform that reduces the dimensionality of the original dataset while keeping most of the variation. Extra sparsity constraint sets most of the coefficients to zero which makes interpretation of the linear transform easier. We present two approaches to the sparsity constrained Principal Component Analysis. Firstly, we develop computationally cheap heuristics that can be deployed in very high-dimensional problems. Our heuristics are justified with linear algebra approximations and theoretical guarantees. Furthermore, we strengthen our algorithms by deploying the necessary conditions for the optimization model. Secondly, we use a non-convex log-sum penalty in the semidefinite space. We show a connection to the cardinality function and develop an algorithm, PCA Sparsified, to solve the problem locally via solving a sequence of convex optimization problems. We analyze the theoretical properties of this algorithm and comment on the numerical implementation. Moreover, we derive a pre-processing method that can be used with previous approaches. Finally, our findings from the numerical experiments we conducted show that our greedy algorithms scale to high dimensional problems easily while being highly competitive in many problems with state-of-art algorithms and even beating them uniformly in some cases. Additionally, we illustrate the effectiveness of PCA Sparsified on small dimensional problems in terms of variance explained. Although it is computationally very demanding, it consistently outperforms local and greedy approaches.

Benzer Tezler

  1. Zaman-frekans analizinde yeni dönüşümler ve uygulama alanları

    New transforms in time-frequency analysis and their applications

    YAZGAN ERER

    Yüksek Lisans

    Türkçe

    Türkçe

    1993

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    PROF.DR. AHMET H. KAYRAN

  2. Türkçe sözcük anlam belirsizliği giderme

    Word sense disambiguation for Turkish

    BAHAR İLGEN

    Doktora

    Türkçe

    Türkçe

    2015

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. EŞREF ADALI

    YRD. DOÇ. DR. AHMET CÜNEYD TANTUĞ

  3. Algorithms for interference immunity and efficient radio resource utilization in wireless communications systems

    Kablosuz iletişim sistemlerinde girişim direnci ve verimli radyo kaynağı kullanımı için algoritmalar

    ARMED TUSHA

    Doktora

    İngilizce

    İngilizce

    2023

    Elektrik ve Elektronik Mühendisliğiİstanbul Medipol Üniversitesi

    Elektrik-Elektronik Mühendisliği ve Siber Sistemler Ana Bilim Dalı

    PROF. DR. HÜSEYİN ARSLAN

  4. Seyreklik ve sözlük öğrenme yaklaşımlarının sınıflandırma ve yüz tanımaya uygulanması

    Classification and face recognition application of sparsity and dictionary learning based methods

    BERNA AZİZOĞLU

    Yüksek Lisans

    Türkçe

    Türkçe

    2017

    Elektrik ve Elektronik Mühendisliğiİstanbul Teknik Üniversitesi

    Elektronik ve Haberleşme Mühendisliği Ana Bilim Dalı

    DOÇ. DR. ENDER METE EKŞİOĞLU