4.3.2 Compressing Correlations Alth

4.3.2 Compressing Correlations
Although the pruning techniques help to efficiently compute top k correlations, the number of these correlations can sometimes grow very large. There exists a tradeoff between the precision and recall of storing top-k correlations, which is defined by size k. Improving both characteristics is only possible for larger top-k sizes. In contrast, performance and scalability requirements demand top-k size to be small. This problem can be addressed by compressing top-k correlations, as described below.
We propose two algorithms of top-k compression: a greedy algorithm of triangulation correlation compression, TCC, and clustering correlation compression, CCC, based on density clustering. Nevertheless, other existing methods of clustering and graph compression can be adapted to compress top-k correlations.
Triangulation correlation compression TCC
Given correlation coefficients between two demographics nodes and a third one, we can estimate upper and lower limits for the correlation between them. Based on the correspondence between correlation coefficients and angles of vectors, representing local deviations of time series to their mean, we can apply the triangular in equality, which gives us the following lemma:
The detailed proof can be found in [3]. From the above in equality it follows that the transitivity of a positive and a negative correlation holds only if l 2 1 + l 2 2 >1. This property requires absolute correlation values between two time series to be above 0.7 in order for the inequality to have any valuable prediction power. We note that this property is naturally achievable between nodes in a demographics lattice thanks to regularity and monotonicity of aggregated data. Therefore, Lemma 3 suits to our needs to compactly store correlations and recover missing values.
The simple greedy compression algorithm is listed in Algorithm 3. It removes elements from the top-k, which can be approximate dusing the triangulation principle. The compression process starts with a sorted list of correlations, which size is larger thank. Correlations are removed from the list one by one, being replaced with the next candidate in the list (k+1) until the removal of any correlation introduces an error, larger than the one gained by adding a candidate. TCC algorithm can be further optimized by removing several correlations at once, until their approximations do not depend on each other. Such an optimization leads to a considerable performance benefit, since the approximation errors are not recomputed at every modification of a top-k list. However, the algorithm may become less optimal in this case. For the lack of space, we evaluate only the basic version of TCC, leaving possible extensions of this method for a future work.

ผลลัพธ์ (ไทย) 1:

4.3.2 อัดความสัมพันธ์ แม้ว่าความช่วยเหลือเทคนิคตัดกับ efficiently คำนวณความสัมพันธ์ด้าน k จำนวนของความสัมพันธ์เหล่านี้สามารถบางครั้งขยายขนาดใหญ่มาก มีดีระหว่างความแม่นยำและเรียกคืนการจัดเก็บความสัมพันธ์ด้าน k ซึ่งถูกกำหนด โดยขนาดเคพัฒนาทั้งสองลักษณะได้เฉพาะสำหรับขนาดใหญ่ด้านบน-k ตรงกันข้าม สมรรถนะและภาระความต้องต้องการ k ด้านบนมีขนาดเล็ก ปัญหานี้สามารถส่ง โดยการบีบอัดความสัมพันธ์ด้าน k ตามที่อธิบายไว้ด้านล่าง เรานำเสนอสองอัลกอริทึมการบีบอัดบน k: อัลกอริทึมโลภอัดความสัมพันธ์ระบบสามสกุล TCC และสหสัมพันธ์การบีบอัด CCC คลัสเตอร์ตามความหนาแน่นของคลัสเตอร์ อย่างไรก็ตาม วิธีการอื่น ๆ ที่มีอยู่ของคลัสเตอร์และกราฟการบีบอัดสามารถปรับให้บีบอัด k ด้านความสัมพันธ์การบีบอัดความสัมพันธ์ระบบสามคัน รับ coefficients ความสัมพันธ์ระหว่างประชากรโหนสองและสามอยู่ เราจะได้ประเมินขีดจำกัดบน และล่างสำหรับความสัมพันธ์ระหว่างพวกเขา อิงการติดต่อระหว่าง coefficients สัมพันธ์และมุมของเวกเตอร์ การเป็นตัวแทนท้องถิ่นส่วนเบี่ยงเบนของอนุกรมเวลาของพวกเขาหมายถึงอะไร เราสามารถนำการสามเหลี่ยมในความเสมอภาค ซึ่งทำให้เรามีหน่วยการต่อไปนี้:หลักฐานโดยละเอียดสามารถพบได้ใน [3] จากข้างต้นในความเท่าเทียมกัน มันตามว่า transitivity บวกและความสัมพันธ์เชิงลบที่เก็บถ้า l 2 1 + l 2 2 > 1 คุณสมบัตินี้ต้องมีค่าความสัมพันธ์ระหว่างสองเวลาชุดจะสูงกว่า 0.7 ในใบสั่งสำหรับอสมการมีพลังงานใด ๆ มีค่าทำนาย เราทราบว่า คุณสมบัตินี้จะทำได้ตามธรรมชาติระหว่างโหนในตาข่ายข้อมูลประชากรจากสม่ำเสมอและ monotonicity ของการรวบรวมข้อมูล ดังนั้น 3 หน่วยการเหมาะกับเราต้องการเก็บความสัมพันธ์อย่างมิดชิด และกู้คืนค่าหายไป อัลกอริทึมบีบอัดโลภง่ายอยู่ในอัลกอริทึม 3 มันเอาองค์ประกอบจากด้านบน-k ซึ่งสามารถประมาณ dusing หลักการระบบสามสกุล ขอบคุณที่จะเริ่มกระบวนการบีบอัดกับรายการเรียงลำดับของความสัมพันธ์ ขนาดที่มีขนาดใหญ่ ความสัมพันธ์จะถูกลบออกจากรายการหนึ่งโดยหนึ่ง ถูกแทนที่ ด้วยผู้สมัครถัดไปในรายการ (k + 1) จนกระทั่งการกำจัดของความสัมพันธ์ใด ๆ แนะนำข้อผิดพลาด มากกว่าหนึ่งได้ โดยการเพิ่มผู้สมัคร อัลกอริทึม TCC สามารถปรับเพิ่มเติม โดยการเอาความสัมพันธ์หลายครั้ง จนกระทั่งเพียงการประมาณตนไม่ขึ้นกับแต่ละอื่น ๆ การเพิ่มประสิทธิภาพนำไปสู่ผลประโยชน์มีประสิทธิภาพมาก เนื่องจากข้อผิดพลาดประมาณไม่มี recomputed ที่ทุก modification ของรายการยอดนิยม-k อย่างไรก็ตาม อัลกอริทึมอาจดีที่สุดน้อยในกรณีนี้ สำหรับการขาดพื้นที่ เราประเมินเฉพาะรุ่นพื้นฐานของ TCC ออกจากส่วนขยายเป็นไปได้ของวิธีการนี้สำหรับการทำงานในอนาคต

ผลลัพธ์ (ไทย) 2:

4.3.2 การบีบอัดความสัมพันธ์
แม้ว่าเทคนิคการตัดแต่งกิ่งช่วย EF Fi อย่างมีประสิทธิภาพคำนวณความสัมพันธ์ K ด้านบนจำนวนของความสัมพันธ์เหล่านี้บางครั้งสามารถเจริญเติบโตได้ขนาดใหญ่มาก มีการถ่วงดุลอำนาจระหว่างความแม่นยำและการเรียกคืนของการจัดเก็บความสัมพันธ์ด้านบน-K ซึ่งเป็นนิยามตามขนาด K อยู่ การปรับปรุงลักษณะทั้งสองเป็นไปได้เฉพาะสำหรับขนาดใหญ่ด้านบนขนาด-K ในทางตรงกันข้ามประสิทธิภาพและ scalability ต้องการเรียกร้องขนาดด้านบน-K จะมีขนาดเล็ก ปัญหานี้สามารถแก้ไขโดยการบีบอัดความสัมพันธ์ด้านบน-K ตามที่อธิบายไว้ด้านล่าง.
เราเสนอสองขั้นตอนวิธีการของการบีบอัดบน K: อัลกอริทึมโลภของการบีบอัดสมการความสัมพันธ์ทีซีซีและการบีบอัดความสัมพันธ์การจัดกลุ่ม CCC ขึ้นอยู่กับการจัดกลุ่มความหนาแน่น แต่วิธีการที่มีอยู่อื่น ๆ ของการจัดกลุ่มและการบีบอัดกราฟสามารถนำไปปรับใช้ในการบีบอัดความสัมพันธ์บน k.
การบีบอัด Triangulation สัมพันธ์ บริษัท ทีซีซี
ได้รับความสัมพันธ์ cients COEF Fi ระหว่างสองโหนดประชากรและหนึ่งในสามเราสามารถประมาณขีด จำกัด บนและล่างสำหรับความสัมพันธ์ระหว่างพวกเขา บนพื้นฐานของการติดต่อระหว่าง cients Fi COEF ความสัมพันธ์และมุมของเวกเตอร์ที่เป็นตัวแทนของการเบี่ยงเบนในท้องถิ่นของชุดเวลาที่จะหมายถึงพวกเขาเราสามารถนำไปใช้เป็นรูปสามเหลี่ยมในความเท่าเทียมกันซึ่งจะช่วยให้เราแทรกต่อไปนี้:
หลักฐานรายละเอียดสามารถพบได้ใน [3] จากข้างต้นในความเท่าเทียมกันก็ต่อว่ากริยาของบวกและความสัมพันธ์ทางลบถือเพียง L 2 1 + L 2 2> 1 ถ้า คุณสมบัตินี้ต้องใช้ค่าความสัมพันธ์ที่แน่นอนระหว่างสองชุดเวลาที่จะอยู่เหนือ 0.7 เพื่อให้ความไม่เท่าเทียมกันที่จะมีอำนาจในการทำนายใด ๆ ที่มีคุณค่า เราทราบว่าคุณสมบัตินี้เป็นธรรมชาติที่ทำได้ในระหว่างโหนดตาข่ายประชากรขอบคุณที่สม่ำเสมอและ monotonicity ของข้อมูลที่เก็บรวบรวม ดังนั้นบทแทรก 3 ชุดเพื่อตอบสนองความต้องการของเราที่จะเก็บความสัมพันธ์ดานและกู้คืนค่าที่ขาดหายไป.
วิธีการบีบอัดง่ายโลภจะปรากฏอยู่ในขั้นตอนวิธีการ 3 มันเอาองค์ประกอบของจากด้านบน-K ซึ่งสามารถ dusing ตัวอย่างหลักการสม กระบวนการบีบอัดที่เริ่มต้นด้วยรายการที่เรียงลำดับของความสัมพันธ์ซึ่งมีขนาดขอบคุณที่มีขนาดใหญ่ ความสัมพันธ์จะถูกลบออกจากรายการหนึ่งโดยหนึ่งถูกแทนที่ด้วยผู้สมัครต่อไปในรายการ (k + 1) จนถึงการกำจัดของความสัมพันธ์ใด ๆ แนะนำข้อผิดพลาดที่มีขนาดใหญ่กว่าคนที่ได้รับจากการเพิ่มผู้สมัคร อัลกอริทึมทีซีซีสามารถเพิ่มประสิทธิภาพต่อไปโดยการลบความสัมพันธ์หลายครั้งจนกว่าจะใกล้เคียงของพวกเขาไม่ได้ขึ้นอยู่กับแต่ละอื่น ๆ เช่นการเพิ่มประสิทธิภาพนำไปสู่ประสิทธิภาพมาก Bene Fi T เนื่องจากข้อผิดพลาดประมาณยังไม่ได้คำนวณใหม่ทุกไอออนบวก Modi Fi ของรายการด้านบน-K แต่วิธีที่ดีที่สุดอาจจะกลายเป็นน้อยกว่าในกรณีนี้ สำหรับการขาดพื้นที่ที่เราประเมินเฉพาะรุ่นพื้นฐานของทีซีซีออกจากส่วนขยายที่เป็นไปได้ของวิธีนี้สำหรับการทำงานในอนาคต

ผลลัพธ์ (ไทย) 3:

ความสัมพันธ์ 4.3.2 การบีบอัดแม้ว่าการตัดเทคนิคช่วย EF จึง ciently คำนวณความสัมพันธ์ K ด้านบน หมายเลขของความสัมพันธ์เหล่านี้บางครั้งสามารถขยายขนาดใหญ่มาก มีข้อเสียระหว่างความถูกต้องและเรียกคืนจากการจัดเก็บ top-k ความสัมพันธ์ ซึ่งเดอจึงเน็ดขนาด K . ปรับปรุงลักษณะเป็นเพียงที่เป็นไปได้สำหรับขนาด top-k ขนาดใหญ่ ในทางตรงกันข้าม , ประสิทธิภาพและ scalability ความต้องการความต้องการ top-k ขนาดจะเล็ก ปัญหานี้สามารถแก้ไขได้โดยการบีบอัด top-k ความสัมพันธ์ตามที่อธิบายไว้ด้านล่างเราเสนอสองขั้นตอนวิธีการบีบ top-k : ขั้นตอนวิธีการโลภของสามเหลี่ยมสหสัมพันธ์การบีบอัด , การบีบอัด ( TCC และการจัดกลุ่ม , CCC , ขึ้นอยู่กับความหนาแน่นของข้อมูล . แต่ที่มีอยู่อื่น ๆวิธีการแบ่งกลุ่มและการบีบอัดกราฟสามารถปรับการบีบอัด top-k สหสัมพันธ์สามเหลี่ยมสหสัมพันธ์อัดทีซีซีให้ความสัมพันธ์ coef จึง cients ระหว่างสองประชากรโหนดและหนึ่งในสาม เราสามารถประเมินขอบเขตบนและล่างสำหรับความสัมพันธ์ระหว่างพวกเขา บนพื้นฐานของการติดต่อระหว่างความสัมพันธ์ coef จึง cients และเวกเตอร์มุมแทน ส่วนท้องถิ่น อนุกรมเวลา หมายถึง เราสามารถใช้สามเหลี่ยมในความเสมอภาค ซึ่งจะช่วยให้เราแทรกต่อไปนี้ :หลักฐานรายละเอียดสามารถพบได้ใน [ 3 ] จากข้างต้นในความเสมอภาค มันเป็นไปตามที่ transitivity ของในเชิงบวกและในเชิงลบ ถ้าผมถือแค่ 2 1 + 1 2 2 1 คุณสมบัตินี้ต้องมีแน่นอนค่าสหสัมพันธ์ระหว่างสองชุดเวลาจะสูงกว่า 0.7 เพื่อความไม่เท่าเทียมกัน มีอำนาจพยากรณ์ใด ๆที่มีคุณค่า เราทราบว่าคุณสมบัตินี้คือธรรมชาติได้ระหว่างโหนดในประชากรขัดแตะขอบคุณ monotonicity ของเครื่องแต่งกายและรวบรวมข้อมูล ดังนั้น แทรก 3 เหมาะกับความต้องการของเรา ร้านแบบกะทัดรัด ความสัมพันธ์และกู้คืนค่าสูญหาย .ขั้นตอนวิธีการบีบอัดง่ายโลภอยู่ในขั้นตอนวิธี 3 . มันเอาองค์ประกอบจาก top-k ซึ่งสามารถประมาณ dusing ที่กระทบหลักการ ขั้นตอนการเริ่มต้นด้วยรายการที่เรียงลําดับของความสัมพันธ์ ขนาดที่ใหญ่กว่านี้ขอบคุณ ความสัมพันธ์จะถูกลบออกจากรายการหนึ่งโดยหนึ่งถูกแทนที่ด้วยผู้สมัครถัดไปในรายการ ( k + 1 ) จนถึงการกำจัดสัมพันธ์แนะนำข้อผิดพลาดขนาดใหญ่กว่าหนึ่งได้โดยการเพิ่มชื่อ ขั้นตอนวิธี TCC สามารถต่อเพิ่ม โดยเอาความสัมพันธ์หลายครั้ง จนใกล้เคียงของพวกเขาไม่ได้ขึ้นอยู่กับแต่ละอื่น ๆ เช่นการเพิ่มประสิทธิภาพ นำไปสู่การปฏิบัติมากครับจึงไม่ ตั้งแต่ประมาณข้อผิดพลาดจะไม่ recomputed ในทุก Modi จึงบวกของรายการ top-k . อย่างไรก็ตาม อัลกอริทึมอาจกลายเป็นที่เหมาะสมน้อย ในกรณีนี้ สำหรับการขาดของพื้นที่เราประเมินเฉพาะรุ่นพื้นฐานของ TCC ออกขยายเป็นไปได้ของวิธีการนี้เพื่อทำงานในอนาคต