Spark'a Dayalı İyileştirilmiş İlişkilendirme Kuralları Algoritması Araştırması
Ye Lu, Dong Zengshou
(Elektronik Bilgi Mühendisliği Okulu, Taiyuan Bilim ve Teknoloji Üniversitesi, Taiyuan 030024, Shanxi)
Apriori algoritmasının bilgi patlaması çağında büyük verilerle karşılaştığı, hesaplama döngüsü büyük ve algoritma verimliliği düşük ilişkilendirme kuralı sorunlarına yönelik olarak veri geçiş sayısını azaltmak için veriler belirli bir veri yapısında depolanır; budama işlemleri bağlantı işleminden önce gerçekleştirilir, Budama işleminin değerlendirme koşullarını değiştirin; aynı zamanda, geliştirilmiş IApriori algoritması, bellek tabanlı büyük veri paralel hesaplama işleme çerçevesi ApacheSpark ile birleştirilir ve Spark (Spark + IAprior) tabanlı geliştirilmiş bir Apriori algoritması önerilir. Deneysel sonuçlar, Spark + IApriori algoritmasının, küme ölçeklenebilirliği ve hızlanma açısından Apriori algoritmasından daha iyi olduğunu göstermektedir.
İlişkilendirme kuralları; Apriori; MapReduce; Hadoop; Spark
Çin Kütüphanesi Sınıflandırma Numarası: TP391
Belge tanımlama kodu: Bir
DOI: 10.16157 / j.issn.0258-7998.2017.06.032
Çince alıntı biçimi: Ye Lu, Dong Zengshou. Spark'a Dayalı Geliştirilmiş İlişkilendirme Kuralları Algoritması Araştırması. Elektronik Teknoloji Uygulaması, 2017, 43 (6): 126-129.
İngilizce alıntı biçimi: Ye Lu, Dong Zengshou. Spark'a dayanan geliştirilmiş bir ilişkilendirme kuralları algoritması. Application of Electronic Technique, 2017, 43 (6): 126-129.
0 Önsöz
Apriori algoritması, ilişkisel kural madenciliğinde en klasik olanıdır ve İnternetin gelişmesiyle birlikte talebi karşılayamaz hale gelmiştir. Google, 2004 yılında MapReduce çerçevesini önerdi ve ardından MapReduce'a dayalı Hadoop ortaya çıktı. LI N ve diğerleri, Harita işleminin aday öğe setlerini hesapladığı ve Azaltma işleminin sık öğe setlerini saydığı paralel bir sık öğe seti madenciliği algoritması (PApriori) önerdi.Ancak, tekrarlanan Harita ve Azaltma operasyonları gerektirir; Guo Jian ve ark. CMR-Apriori algoritması, algoritmayı işlemek için kodlama ve MapReduce kullanır, ancak Hadoop'un ara sonuçları HDFS'ye kaydetmesi gerekir ve yinelemeli işlemleri desteklemez. UC Berkeley AMP laboratuvarı bir Spark hesaplama çerçevesi önerdi, Spark, gerçek zamanlı veri işlemeyi büyük ölçüde geliştirebilen, kümenin yüksek hata toleransını ve büyük veri ortamında yüksek ölçeklenebilirliği sağlayan bellek tabanlı bir paralel hesaplama çerçevesidir. Qiu Hongjian ve diğerleri, Spark RDD çerçevesine dayalı sık bir öğe seti madenciliği (YAFIM) algoritması önerdi.Deneyler, Spark'ın performansının MapReduce çerçevesinden çok daha yüksek olduğunu, ancak çok fazla aday öğe kümesi olduğunda etkinin ideal olmadığını gösteriyor; RATHEE S ve diğerleri. Adayları nesilden nesile eleyerek veri setinin performansını artıran bir R-Apriori algoritması önerdi.YAFIM algoritmasına kıyasla, R-Apriori'nin daha fazla avantajı var; Gui Feng, FP-Growth algoritmasının analizine dayalı DPBM'yi önerdi Algoritma, aday öğe kümesini büyük ölçüde azaltmak için küresel budama teknolojisini tanıtarak.
1 Apriori algoritması
Apriori algoritması basit bir veri yapısı kullanır ve yürütme süreci açıktır, ancak işlem boyutu büyük ve minimum destek küçük olduğunda, yürütme verimliliği azalacaktır. Apriori algoritma problemleri şu şekilde özetlenmiştir:
(1) İşlem veri tabanının her yüksek boyutlu ürün seti oluşturulduğunda taranması gerekir.İşlem veri tabanı çok büyük olduğunda, ağır G / Ç yükü, büyük hesaplama döngüsü ve düşük algoritma verimliliğine neden olur.
(2) Sık kullanılan öğe setlerinden aday öğe setlerinin oluşturulması sürecinde, bağlantı ve budama işlemleri gereklidir.Zaman karmaşıklığı yüksektir ve algoritma verimliliği düşüktür.
(3) Algoritma, çok sayıda aday öğe kümesi oluşturacak ve bu da doğrudan hesaplamada büyük miktarda fazlalığa yol açacak ve bu da algoritmayı verimsiz kılacaktır.
2 Spark çerçevesine dayalı geliştirilmiş Apriori algoritması
2.1 Apriori algoritması iyileştirmesi
Önceki bölümde bahsedilen problem (1) için iyileştirme stratejisi, veri tabanının taramalarının sayısını azaltmak için verileri belirli bir veri yapısında depolamaktır.Bu makale Şekil 1'de gösterilen depolama yapısını kullanmaktadır.
Bu veri yapısını kullanarak, veritabanının tekrar tekrar taranması engellenebilir ve zaman karmaşıklığı büyük ölçüde azaltılabilir. Aday kümenin desteğini sayarken, yalnızca desteğin anahtar değeri olarak kullanılması ve ardından karşılık gelen alt simge öğelerinin dizisi üzerinde bir AND işlemi yapılması ve son olarak, aday kümenin desteği olarak sıfır olmayan sayının sayılması gerekir.
2.2 Spark + IApriori algoritması
Spark'ın kendisi bir bilgi işlem çerçevesidir.Veri hesaplarken, genellikle harici bir dosya sisteminden veri okur. Spark'ın kendisi bellek yinelemede iyidir, özellikle çalışma kümesine dayalı bellek yinelemesinde çok etkilidir. Dağıtılmış bir büyük veri ambarı varsa, veri ambarı birçok kişi tarafından kullanılır. Bazı kişiler aynı işi kullanabilir ve aynı işlemi gerçekleştirebilir. Hadoop'ta, tekrarlanan hesaplamalar gerekir. Spark'ta, birinin aynı şeyi yaptığını görürseniz Birisi veri ambarıyla etkileşim kurmak istediğinde, çalışma setinin sonuçlarını doğrudan yeniden kullanabilir ve bu da bilgi işlem hızını büyük ölçüde artırabilir. Spark'ın Hadoop'un MapReduce'a göre avantajı, MapReduce tabanlı bilgi işlem motorunun genellikle depolama ve hata toleransı için diske ara sonuçları vermesidir. Spark, yürütme modelini, ara aşama sonuçlarını HDFS'ye çıkarmadan, yönlendirilmiş döngüsel olmayan grafik yürütme planı DAG olarak özetler. Aynı zamanda, Spark'ın veri formatı, bellek düzeni, yürütme stratejisi ve herhangi bir programlama ek yükü açısından iyi avantajları vardır.
Önceki bölüm temelinde, geliştirilmiş algoritma IApriori, bellek tabanlı büyük veri paralel hesaplama işleme çerçevesi Apache Spark ile birleştirilmiştir ve Spark paralel hesaplama işleme çerçevesine (Spark + IAprior) dayalı gelişmiş bir Apriori algoritması önerilmiştir. Algoritma akış şeması aşağıdaki gibidir. şekil 2. Algoritma temel olarak iki adıma bölünmüştür: (1) yerel sık öğe kümeleri oluşturun; (2) genel sık öğe kümeleri oluşturun.
3 deney
3.1 Çevre yapısı
Spark'ın hantal hizmet dağıtımı nedeniyle, yapılandırma dosyalarının manuel olarak düzenlenmesini ve bağımlılık paketlerinin indirilmesini gerektirir.Bu deneyde, Cloudera yöneticisi, GUI modunda CDH kümesini yönetmek için kullanılır ve sihirbaz tarzı kurulum adımları sağlar.
(1) Deneysel ortam:
İşlemci: Intel (R) Pentium (R) CPU 3.20 GHz;
Yüklü bellek RAM: 16 GB;
Sistem türü: 64 bit işletim sistemi;
(2) Çevre inşaat süreci:
Cloudera Manager 5'i yerel Yum yazılım kaynağından yükleyin: önce güvenlik duvarını ve selinux'u kapatmanız, / etc / selinux / config dosyasını değiştirmeniz, ardından Apache httpd web sunucusunu kurmanız, CM kaynak paketini cm5.0.2-centos6.tar.gz'yi indirmeniz ve aynı zamanda serbest bırakmanız gerekir CM kaynak dosyasını açın, sıkıştırılmış cm klasörünü web dizinine taşıyın ve izinleri ayarlayın, postgresql yükleyin, istemci yapılandırmasını kaynak dosyasını bulacak şekilde değiştirin, CM5 kurulum dosyası cloudera-manager-installer.bin'i indirin, CM5'i kurun ve verin Cloudera-manager-installer.bin'e yürütülebilir izinler ekleyin, CM yönetim sayfasında oturum açın ve Şekil 3'te gösterildiği gibi kullanıcı adı ve şifre yönetici olarak http: // localhost: 7180 / arayüzünde oturum açın.
Hive, HBase, Impala, Spark ve diğer hizmetleri CDH5'e kurun: RPM-GPG-KEY-cloudera'yı indirin (bu, rpm paketini kontrol etmek için kullanılan dosyadır), CentOS-6.5-x86_64'ü tüm sunuculara kurun ve güvenlik duvarını ve selinux'u kapatın , Zamanın tutarlı olmasını sağlayın. Tüm kök kullanıcı parolalarının tutarlı olmasını sağlayın. Bir Hadoop kümesinde en az 3 düğüm vardır ve bu test ortamında 5 düğüm web sunucusunun / var / www / html / redhat / cdh dizinine kaydedilir ve cm.worker.com üzerine PostgreSQL kurulur, Şekil 4 ~ Şekil 6 Hive, HBase, Impala ve Spark için kurulum ve konfigürasyon şemaları.
3.2 Deneysel sonuçlar
Deneysel veriler web sitesi Sık Kullanılan Öğeler Kümesi Madencilik Veri Kümesi Deposundan seçilir ve iki veri tabanı, T10I4D100K ve Kazalar esas olarak test için seçilir.
Algoritma geçerlilik testi: Veri setinin desteğinin düğüm sayısı ile tutarlı olmasını sağlamak amacıyla, Spark + IApriori algoritması, MapReduce çerçevesine (MapReduce + Apriori) ve Spark çerçevesine (Spark +) dayalı Apriori algoritmasına dayalı Apriori algoritması ile karşılaştırılır. Apriori) veri setinin kopya sayısı ile algoritmanın çalışma süresi arasındaki ilişkiyi karşılaştırmak ve bulmak. Bu makale, farklı veri tabanlarına göre farklı destek seviyelerini kurar. Küme, biri Ana düğüm ve kalan 4'ü bağımlı düğümler olmak üzere 5 düğüm kullanır.Deneysel karşılaştırma sonuçları Şekil 7 ve Şekil 8'de gösterilmektedir. Şekil 7 ve Şekil 8'den veri kopya sayısı arttıkça yani veri miktarı arttıkça MapReduce + Apriori algoritmasının çalışma süresinin neredeyse doğrusal olarak arttığı görülmektedir.Veri miktarı ne kadar büyükse işlem hızındaki hızlı düşüş de o kadar artar. . Bunun nedeni, MapReduce hesaplama çerçevesini temel alan Hadoop'un ara sonuçları HDFS'ye kaydetmesi gerektiğidir ve MapReduce, verileri adım adım işler. Spark çerçevesi altındaki algoritmanın daha hızlı çalıştığı Şekil 7 ve Şekil 8'den açıkça görülebilir. Hadoop hesaplama çerçevesinde bunun nedeni, Spark'ın tüm veri analizini bellekteki "gerçek zamanlı" zamana yakın bir sürede tamamlayacak olması ve Spark'ın toplu işlem hızının MapReduce'tan yaklaşık 10 kat daha hızlı olmasıdır. Aynı zamanda Şekil 7 ve Şekil 8'den Spark çerçevesine dayalı olarak geliştirilmiş Apriori algoritmasının çalışma verimliliğinin Apriori algoritmasından daha yüksek olduğu ve Spark + IApriori algoritmasının etkili olduğunu kanıtladığı görülmektedir.
Tek bir deneyde kazara oluşan hataların etkisini ortadan kaldırmak için, bu makale temel olarak Spark + IApriori algoritmasının performansını aşağıdaki iki yönden değerlendirir:
(1) Kümenin ölçeklenebilirliği: Belirli veri seti desteği ve veri hacmi öncülüğünde, veri seti düğümü ile algoritmanın çalışma süresi arasındaki ilişkiyi bulun; Kümenin ölçeklenebilirliğini test etmek için, bu makale ayrıca farklı veritabanlarına göre farklı ayarlar belirler Şekil 9 ve Şekil 10, farklı veri seti düğümleri ve algoritmanın çalışma süresi arasındaki ilişkiyi yansıtır. Farklı veri kümeleri için, algoritma çalışma süresi ve düşüş eğilimi de farklıdır. Bunun nedeni, farklı veri kümeleri için verilerin yatay ve dikey boyutları, yerel sık öğe kümesinin boyutu ve minimum destek minsup kümesi farklı olacaktır.
(2) Kümenin hızlanma oranı: algoritmanın çalışma süresinin tek bir düğüm ve birden çok düğüm üzerindeki oranı:
Bunlar arasında t1, algoritmanın tek bir düğümde çalışma süresini temsil eder ve ti, düğümlerde işin çalışma süresini temsil eder.
Bu deneyde, Spark + IApriori algoritmasının hızlanma oranını test etmek için, hızlanma oranı, deneyin diğer parametreleri tutarlı tutularak düğüm sayısı değiştirilerek test edilmiş, deneysel sonuçlar Şekil 11 ve Şekil 12'de gösterilmiştir. Hızlanmanın doğrusal olamamasının ana nedeni, kümeler arasındaki iletişim süresidir.
Özetle, Spark + IApriori algoritması, MapReduce çerçevesi altındaki Hadoop platformunu temel alan Apriori algoritmasından daha üstündür; aynı zamanda Spark + IApriori algoritması, Spark platformu altında veri ölçeklenebilirliği ve hızlanma açısından Spark çerçevesindeki Apriori algoritmasından üstündür.
4. Sonuç
İlişkilendirme kuralları kavramının tanıtılmasına ve Apriori algoritmasının analizine dayanarak, bu makale Apriori algoritmasının veri miktarının çok büyük olduğu büyük hesaplama döngüleri, budama işlemlerinin yüksek hesaplama karmaşıklığı ve çok sayıda gereksiz aday madde seti gibi problemlere sahip olduğunu bulmuştur.Bu problemleri çözmek için, Algoritmanın veri yapısı ve budama işlemi geliştirildi ve ardından Spark hesaplama çerçevesi ile birleştirilerek Spark + IApriori algoritması önerildi. Deneyler, Spark + IApriori algoritmasının etkinliğini ve küme ölçeklenebilirliği ile hızlanmadaki avantajlarını doğrular.
Referanslar
LI N, ZENG L, HE Q. MapReduce'a dayalı Apriori algoritmasının paralel uygulaması. 201213. ACM Uluslararası Yazılım Mühendisliği, Yapay Zeka, Ağ ve Paralel ve Dağıtılmış Hesaplama Konferansı, IEEE Computer Society.Kyoto, Japonya, 2012: 236-241 .
Guo Jian. Kodlama ve MapReduce'a dayalı geliştirilmiş Apriori algoritması araştırması. 201310. Web Bilgi Sistemi ve Uygulama Konferansı (WISA 2013), IEEE Bilgisayar Topluluğu, Yangzhou, Jiangsu, Çin, 2013: 294-299.
Gao Yanjie. Spark teknolojisi ile veri işleme, uygulama ve performans optimizasyonu.China Machine Press, 2014.
Qiu Hongjian, Gu Rong, Yuan Chunfeng.YAFIM: Spark.2014 IEEE 28th International Parallel and Distributed Processing Symposium Workshops, IEEE Computer Society.Phoenix, AZ, United States, 2014: 1664-1671.
RATHEE S, KAUL M, KASHYAP A.R-apriori: Spark.PIKM 2015-Proceedings of the 8th Ph.D. Workshop in Information and Knowledge Management.Melbourne, VIC, Avustralya, 2015: 27-34.
GUI F, MA Y, ZHANG F, et al. Spark'a dayalı bir dağıtılmış sık ürün seti madencilik algoritması. 2015 IEEE 19. Uluslararası Tasarımda Bilgisayar Destekli İşbirlikli Çalışma Konferansı Bildirileri. Calabria, İtalya, 2015: 271-275.
