4.2 Overview of Algorithms Our algo

4.2 Overview of Algorithms
Our algorithm for extracting significant correlations is based on the DTree storage and is listed in Algorithm1. Due to lack of space, we present our algorithm for the sliding time interval and conventional correlation formula (see Section3). The other approaches, using fixed or global intervals, can be reduced from it by considering subsequent time intervals of constant sizes (fixed), or the entire time series (global).
The process of mining sentiment time series is performed in a top-down fashion, going from higher to lower granularities in a DTree and from root to leaf nodes in a demographics lattice. Our approach achieves hierarchical correlation management and pruning through remembering for every pair of groups which of the identified time intervals to refine or exclude at the next granularity level. Lines13 and 16 of the algorithm only show the invocation of these functions, assuming that the corresponding time interval pruning takes an immediate effect on the next iteration.
In the second loop, we sequentially access the time series, while computing correlations between demographic groups in the third loop, where candidates are evaluated going from higher order nodes to their children. If a high correlation is detected for some candidate groups (line12), then their positively correlated children are excluded, meaning that the corresponding lattice branches are not revisited in subsequent iterations of the loop. This pruning asserts the maximality of identified correlations and also reduces the candidate set.
The described algorithm employs the sliding interval approach, where correlation interval boundaries are determined in a greedy fashion: by comparing correlation coefficients between a forward (sliding) interval w next of a fixed size, and an interval that runs from the previous boundary w prev. We note, that while the sliding time interval w next is updated for all demographics pairs as we scan the time series, the correlation time intervals w prev are computed and maintained for each demographics pair individually, and their starting boundaries do not necessarily coincide (however, all their ending boundaries border with w next while it slides). When global or fixed time interval approaches are used, it is possible to prune candidate demographic groups on-the-fly according to their estimated value of correlation, so that less and less computations are needed as we advance along the time series.
Finally, for all detected pairs of groups and correlation intervals, the algorithm can start the greedy generalization step, described in Algorithm 2. It iteratively supersedes groups with their maximal parents until they are disjoint and highly correlated.
Computing and storing correlation coefficients for all combinations of demographics nodes is only possible for small lattices, since it requires a quadratic space on the size of a lattice. But since we are interested in finding only high and significant correlations, it is possible to compute and store only such values, while still being able to answer queries with a good precision. In the following sections, we describe how correlation pruning and compression enable efficient implementation of our method.

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

4.2 ภาพรวมอัลกอริทึม อัลกอริทึมของเราสำหรับการแยกความสัมพันธ์งมากตามเก็บ DTree และอยู่ใน Algorithm1 เนื่องจากขาดพื้นที่ เรานำเสนอเราอัลกอริทึมสำหรับช่วงเวลาเลื่อนและสูตรความสัมพันธ์ทั่วไป (ดู Section3) อื่น ๆ วิธีการ โดยใช้ fixed หรือช่วง ที่ส่วนกลางสามารถลดลงจากมัน โดยพิจารณาช่วงเวลาขนาดคง (fixed), หรือชุดตลอดเวลา (ส่วนกลาง) กระบวนการของการทำเหมืองแร่ความเชื่อมั่นอนุกรมเวลาจะดำเนินการในแฟชั่นบนลง ไป จาก granularities ใน DTree สูง และ จากรากใบโหนในตาข่ายข้อมูลประชากร เราให้การจัดการความสัมพันธ์แบบลำดับชั้นและตัดผ่านการจดจำสำหรับทุกคู่ของกลุ่ม identified ซึ่งเวลาช่วงเวลาเพื่อปรับปรุง หรือไม่รวมที่ระดับความละเอียด Lines13 และ 16 ของอัลกอริทึมแสดงเฉพาะจากการเรียกฟังก์ชันเหล่านี้ สมมติว่าเวลาสอดคล้องกันที่ตัดช่วงใช้ผลทันทีในการเกิดซ้ำถัดไปนั้น ในการวนรอบที่สอง เราตามลำดับเข้าชุดเวลา ในขณะประมวลผลความสัมพันธ์ระหว่างกลุ่มประชากรในวงที่สาม ที่มีผู้สมัครประเมินเด็กไปจากโหนสูงสั่ง หากตรวจพบความสัมพันธ์ที่สูงสำหรับ ผู้สมัครบางรวม (line12), แล้วเด็กมีความสัมพันธ์เชิงบวกไม่รวม ซึ่งหมายความ ว่า สาขาตรงตาข่ายไม่สำคัญในการวนรอบซ้ำตามมา ตัดนี้ asserts maximality ของความสัมพันธ์ identified และยัง ช่วยลดการตั้งผู้สมัคร ใช้อัลกอริทึมที่อธิบายวิธีช่วงเลื่อน ซึ่งมีกำหนดขอบเขตช่วงความสัมพันธ์ในแฟชั่นโลภ: โดยการเปรียบเทียบความสัมพันธ์ coefficients ระหว่างช่วงไปข้างหน้า (บานเลื่อน) w ถัดไปของขนาด fixed และช่วงเวลาที่วิ่งจากขอบก่อนหน้าก่อนหน้า. w เราทราบ ว่า ในขณะที่ช่วงเวลาเลื่อน ถัดไป w คือปรับปรุงสำหรับคู่ข้อมูลประชากรทั้งหมดเราสแกนชุดเวลา ช่วงเวลาความสัมพันธ์ก่อนหน้า w มีคำนวณ และรักษาสำหรับประชากรแต่ละคู่แต่ละ และขอบเริ่มต้นไม่จำเป็นต้องทับกัน (อย่างไรก็ตาม ขอบเขตทั้งหมดของพวกเขาสิ้นสุดชายแดน ด้วย w ถัดไปในขณะที่เลื่อน) เมื่อโลก หรือช่วงเวลา fixed วิธีใช้ เป็นไปได้ที่ผู้สมัครกลุ่มประชากรบน-the-fly ตามค่าการประเมินของความสัมพันธ์ ดังนั้นจำเป็นต้องประมวลผลที่น้อย ลงเมื่อเราเลื่อนไปตามลำดับเวลา ในที่สุด สำหรับคู่ที่ตรวจพบทั้งหมดของกลุ่มและความสัมพันธ์ช่วง อัลกอริทึมสามารถเริ่มขั้นตอนลักษณะทั่วไปโลภ อธิบายในอัลกอริทึม 2 มันปรับปรุงต้นแทนกลุ่มกับผู้ปกครองสูงสุดจนกว่าพวกเขาจะมีความสัมพันธ์สูง และไม่เป็นสมาชิกร่วม ประมวลผล และจัดเก็บความสัมพันธ์ coefficients สำหรับชุดทั้งหมดของประชากรโหนเท่านั้นสำหรับเล็กนี่ เนื่องจากมันต้องมีช่องว่างกำลังสองขนาดของตาข่าย แต่เนื่องจากเราสนใจ finding สูงเท่านั้นและความสัมพันธ์งมาก มันเป็นไปได้ในการคำนวณ และเก็บเฉพาะค่าดังกล่าว ในขณะที่ยังคง ความสามารถในการตอบแบบสอบถาม ด้วยความแม่นยำดี ในส่วนต่อไป เราอธิบายวิธีตัดความสัมพันธ์และการบีบอัดที่เปิดใช้งานประสิทธิผลของวิธีการของเรา

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

4.2 ภาพรวมของขั้นตอนวิธี
ขั้นตอนวิธีการของเราสำหรับการสกัดนัยสำคัญความสัมพันธ์ Fi ลาดเทจะขึ้นอยู่กับการจัดเก็บ DTree และเป็น บริษัท จดทะเบียนใน Algorithm1 เนื่องจากการขาดของพื้นที่เรานำเสนอขั้นตอนวิธีการของเราสำหรับช่วงเวลาเลื่อนและสูตรความสัมพันธ์ทั่วไป (ดู Section3) วิธีการอื่น ๆ โดยใช้ช่วงเวลาที่คงที่หรือระดับโลก fi, สามารถลดลงได้จากมันโดยพิจารณาช่วงเวลาต่อมาที่มีขนาดคงที่ (คงที่) หรือซีรีส์ตลอดเวลา (ทั่วโลก).
กระบวนการของการทำเหมืองอนุกรมเวลาความเชื่อมั่นที่จะดำเนินการในด้านบนลง แฟชั่นไปจากที่สูงขึ้นเพื่อละเอียดการลดลงใน DTree และจากรากโหนดใบในตาข่ายประชากร วิธีการของเราประสบความสำเร็จในการจัดการความสัมพันธ์ลำดับชั้นและตัดแต่งกิ่งผ่านจดจำสำหรับคู่ของกลุ่มทุกที่ในช่วงเวลา Fi เอ็ดระบุการปรับแต่งหรือไม่รวมอยู่ในระดับความละเอียดต่อไป Lines13 และ 16 ของขั้นตอนวิธีแสดงเฉพาะอุทธรณ์ของฟังก์ชั่นเหล่านี้สมมติว่าเวลาที่สอดคล้องกันการตัดแต่งกิ่งช่วงเวลามีผลทันทีในการย้ำต่อไป.
ในวงที่สองเราตามลำดับเข้าถึงอนุกรมเวลาในขณะที่การคำนวณความสัมพันธ์ระหว่างกลุ่มประชากรใน วงที่สามผู้สมัครที่ได้รับการประเมินไปจากโหนดที่สูงขึ้นเพื่อให้เด็กของพวกเขา หากมีความสัมพันธ์สูงมีการตรวจพบสำหรับกลุ่มผู้สมัครบางคน (line12) แล้วเด็กความสัมพันธ์เชิงบวกของพวกเขาได้รับการยกเว้นหมายความว่าสาขาที่สอดคล้องตาข่ายไม่ได้มาเยือนในการทำซ้ำที่ตามมาของวง การตัดแต่งกิ่งนี้อ้าง maximality ของระบุความสัมพันธ์ Fi เอ็ดและยังช่วยลดการตั้งค่าผู้สมัคร.
อัลกอริทึมอธิบายพนักงานวิธีการช่วงเวลาเลื่อนที่สัมพันธ์ขอบเขตช่วงเวลาจะถูกกำหนดในแฟชั่นโลภ: โดยการเปรียบเทียบ COEF สัมพันธ์ cients Fi ระหว่างไปข้างหน้า (เลื่อน) ช่วง W ต่อไปของ ขนาดคงที่และช่วงเวลาที่ไหลจากเขตแดนก่อนหน้าก่อนหน้า W เราทราบว่าในขณะที่ช่วงเวลาที่เลื่อน W ต่อไปจะมีการปรับปรุงสำหรับทุกประชากรคู่ในขณะที่เราสแกนอนุกรมเวลาที่ช่วงเวลาที่ความสัมพันธ์ W ก่อนหน้าจะมีการคำนวณและการบำรุงรักษาแต่ละคู่ประชากรรายบุคคลและขอบเขตเริ่มต้นของพวกเขาไม่จำเป็นต้องตรง (อย่างไร ทั้งหมดเขตแดนตอนจบของพวกเขาต่อไปชายแดน W ในขณะที่มันสไลด์) เมื่อแนวทางช่วงเวลาทั่วโลกหรือ Fi เวลาคงที่จะใช้มันเป็นไปได้ที่จะตัดกลุ่มประชากรผู้สมัครบนล้ำหน้าด้วย Y ฟลอริด้าตามค่าประมาณของความสัมพันธ์เพื่อให้การคำนวณน้อยลงและน้อยที่มีความจำเป็นในขณะที่เราก้าวไปพร้อมชุดเวลา.
สุดท้ายสำหรับ ทุกคู่ที่ตรวจพบในกลุ่มและช่วงเวลาที่ความสัมพันธ์อัลกอริทึมสามารถเริ่มต้นขั้นตอนทั่วไปโลภอธิบายไว้ในขั้นตอนวิธีการ 2 มันซ้ำแทนกลุ่มกับผู้ปกครองสูงสุดของพวกเขาจนกว่าพวกเขาจะเคลื่อนสูงและมีลักษณะร่วมกัน.
คอมพิวเตอร์และการจัดเก็บ COEF สัมพันธ์ cients Fi สำหรับการรวมกันทั้งหมดของโหนดประชากร จะเป็นไปได้สำหรับโปรยขนาดเล็กเพราะมันต้องใช้พื้นที่กำลังสองกับขนาดของตาข่ายที่ แต่เนื่องจากเรามีความสนใจใน Fi เท่านั้น nding สูงและมีนัยสำคัญความสัมพันธ์ Fi ลาดเทก็เป็นไปได้ในการคำนวณและจัดเก็บเฉพาะค่าดังกล่าวขณะที่ยังคงความสามารถในการตอบแบบสอบถามที่มีความแม่นยำที่ดี ในส่วนต่อไปนี้เราจะอธิบายวิธีการตัดแต่งกิ่งความสัมพันธ์และการบีบอัดช่วยให้การดำเนินงานของ EF Fi ประสิทธิภาพของวิธีการของเรา

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

4.2 ภาพรวมของขั้นตอนวิธีขั้นตอนวิธีของเราเพื่อสกัด signi จึงไม่สามารถความสัมพันธ์จะขึ้นอยู่กับการจัดเก็บ dtree และอยู่ใน algorithm1 . เนื่องจากการขาดของพื้นที่ที่เรานำเสนอขั้นตอนวิธีของเราสำหรับการเลื่อนช่วงเวลาและสูตรสหสัมพันธ์แบบเดิม ( ดู section3 ) วิธีอื่น ๆ การใช้จึง xed หรือช่วงเวลาทั่วโลกจะลดลงจากมัน โดยพิจารณาตามช่วงเวลาของขนาดคงที่ ( จึง xed ) หรือทั้งชุดเวลา ( ทั่วโลก )กระบวนการของการทำเหมืองข้อมูลอนุกรมเวลาคือการเชื่อมั่นในการจากบนลงล่าง แฟชั่น ไปจากที่สูงขึ้นเพื่อลด granularities ใน dtree และจากรากกับโหนดใบในตารางสถิติ วิธีการบรรลุการจัดการความสัมพันธ์แบบลำดับชั้นและตกแต่งด้วยการจำคู่ของกลุ่ม ของ identi จึงเอ็ดช่วงเวลาเพื่อปรับแต่ง หรือแยกระดับ granularity ต่อไปทุก lines13 และ 16 ของขั้นตอนวิธีให้เรียกฟังก์ชันเหล่านี้ สมมติว่า เวลาที่สอดคล้องกันการตัดแต่งกิ่งช่วงจะมีผลทันทีในรูปถัดไปในการวนรอบสอง เราเข้าถึงเป็นอนุกรมเวลา ในขณะที่การคำนวณความสัมพันธ์ระหว่างประชากรกลุ่มต่างๆ ใน 3 ห่วงที่ผู้สมัครจะถูกประเมินจากโหนดเพื่อการศึกษาเด็กของพวกเขา ถ้าความสัมพันธ์สูง คือว่าบางกลุ่มผู้สมัคร ( line12 ) แล้ว ของพวกเขา มีความสัมพันธ์เชิงบวก เด็กจะถูกแยกออก หมายถึง สาขาที่ไม่ได้มาเยือนขัดแตะตามรอบวง การตัดแต่งกิ่งนี้ maximality asserts ของ identi จึงเอ็ดความสัมพันธ์และยังช่วยผู้สมัครชุดอธิบายขั้นตอนวิธีใช้วิธีการเลื่อนช่วงเวลาที่ความสัมพันธ์ช่วงเขตแดนมุ่งมั่นในแฟชั่นโลภ : โดยการเปรียบเทียบความสัมพันธ์ระหว่าง coef จึง cients ไปข้างหน้า ( เลื่อน ) ในช่วงต่อไปของ W จึง xed ขนาดและช่วงที่วิ่งจากขอบเขตเดิม W ก่อนหน้า . เราทราบว่าในขณะที่เลื่อนช่วงเวลา W ต่อไปคือการปรับปรุงทุกประเภทคู่ที่เราสแกนเวลาชุดความสัมพันธ์ช่วงเวลา W ) จะคำนวณและการรักษาสำหรับแต่ละคู่ของพวกเขาเริ่มจากประชากรและขอบเขตไม่จําเป็นต้องตรงกัน ( แต่ทั้งหมดของพวกเขาสิ้นสุดขอบเขตชายแดนกับ W ต่อไปในขณะที่มันสไลด์ ) เมื่อโลกหรือจึง xed ช่วงเวลาแนวทางที่ใช้ , มันเป็นไปได้ที่จะตัดผู้สมัครประชากรในกลุ่ม - fl Y ตามค่าประมาณของความสัมพันธ์เพื่อให้น้อยลงเป็นรูปตามที่เราล่วงหน้าตามอนุกรมเวลา .สุดท้าย ทั้งหมดที่ตรวจพบคู่ของกลุ่ม และช่วงทดสอบอัลกอริทึมสามารถเริ่มขั้นตอนการโลภ , อธิบายไว้ในขั้นตอนที่ 2 มันซ้ำ Supersedescollection of article headers กลุ่มผู้ปกครองสูงสุดของพวกเขาจนกว่าพวกเขาจะไม่ต่อเนื่องและมีความสัมพันธ์กันการคำนวณและการจัดเก็บความสัมพันธ์ coef จึง cients สำหรับชุดทั้งหมดของประชากรโหนดเป็นเพียงที่เป็นไปได้สำหรับโครงผลึกขนาดเล็ก เนื่องจากใช้พื้นที่กำลังสอง ในขนาดของตาข่าย แต่เราสนใจ จึงหาสูงเท่านั้น จึงไม่สามารถ signi และความสัมพันธ์ มันเป็นไปได้ที่จะคำนวณและจัดเก็บเฉพาะค่าดังกล่าว ในขณะที่ยังสามารถตอบแบบสอบถามมีความแม่นยำดี ในส่วนต่อไปนี้อธิบายวิธีการตัดแต่งกิ่ง เราจึงใช้ความสัมพันธ์และการบีบอัดให้ EF cient วิธีการของเรา