基本介紹
- 中文名：間隔因子
- 外文名：Interval factor
- 作用：給扇區編號
- 有助於：獲取最佳的數據傳輸率
- 用於：硬碟
一種基於間隔因子的動態編碼方案,動態IFPL編碼,靜態性能分析,動態性能分析,關於時間序列相似性問題中間隔因子,時間序列的特點,一種時間間隔算法,試驗結果,
一種基於間隔因子的動態編碼方案
傳統的前綴編碼和區間編碼在XML數據更新時都需要重新編碼，當文檔更新頻繁時這種消耗是無法承受的，已有的動態編碼大多不能完全支持動態更新。在FPES編碼方法基礎上採用一種基於間隔因子的分數前綴編碼方案 ( Interval Fraction Prefix Labeling Scheme，IFPL) ，利用間隔因子解決預留空間用完的問題，使得其在特殊情況下也不需要重新編碼，二次編碼率為零。實驗表明，相對於FPES的IFPL方案以一定的空間消耗換取了對文檔動態更新的完全支持，特別是在文檔規模越大時優勢越明顯。
動態IFPL編碼
分數編碼的優點是可以在兩個分數之間插入無數個分數。
插入一個新結點主要有以下六種特殊處理：
( 1) 沒有兄弟。那么新結點的前綴碼是父結點的前綴加順序碼，分數碼只需在父結點的分子加上1，間隔因子中表示層數的order加1，其餘部分不變，在C下面添加E，E的編碼應該是1，4_1 >。
( 2) 最左插入，右兄弟的最後一個字母不是a。那么新結點前綴碼與右兄弟一樣，順序碼是右兄弟減1，分數碼是父結點和右兄弟的分子分母各自相加，間隔因子與右兄弟一樣，在C旁邊加F，F的編碼應該是1，3_1 >。
( 3) 最左插入，且右兄弟的最後一個字母是a。那么新結點前綴碼和順序碼與右兄弟一樣，分數碼是父結點和右兄弟的分子分母各自相加，間隔因子的order與右兄弟一樣，但interval是右兄弟的inter-val加1，在F旁邊加G，G的編碼應該是2，3_2 >。
( 4) 最右插入，順序碼是左兄弟的順序碼加1，分數碼是左兄弟與父結點的右兄弟的分子分母相加，間隔因子與左兄弟一樣，在C旁邊加H，H的編碼應該是1，3_1 >。
( 5) 兩結點之間插入，且右兄弟的最後一個字母是a。順序碼與右兄弟相同，分數碼為左右兄弟相加，間隔因子order不變，interval由左右兄弟相加得到。在G和F之間插入I，I 的編碼應該是3，3_5 >。
( 6) 兩結點之間插入，且右兄弟的最後一個字母不是a，分數碼為左右兄弟相加，間隔因子order不變。在C 和H之間插入J，J的編碼應該是2，3_1 >。
靜態性能分析
編碼方案的靜態性能評價主要看初始狀態下文檔所需要的編碼時間以及編碼長度。用 IPFL、FPES、浮點數編碼方案分別對測試文檔進行編碼。IFPL、FPES 方案的編碼時間要短於浮點數編碼方案。這是因為浮點數是一種區域編碼，每個結點需要遍歷兩次； 而IFPL和FPES只要遍歷一次，時間上花銷小。FPES的平均編碼長度最短，這是因為浮點數編碼需要兩個浮點數來表示區域中的start和end值，當文檔規模比較大時，這種編碼方案顯然比字母編碼的空間消耗大； 而IFPL由於間隔因子的存在，相對於FPES來說編碼長度稍長。
動態性能分析
考慮三種編碼方案在數據更新時的動態性能，試驗採取XMark5作為參考樣本，分別插入1、10、100、500、1000個結點，觀察動態編碼時間。
IFPL編碼速度明顯快於FPES、浮點數兩種編碼方案，這是因為浮點數編碼的特點在於增加了編碼長度，一旦有溢出就需要對整個文檔重新編碼，不能真正完全支持編碼動態更新。而FPES最左插入和兩點間插入時可能出現字母用完的現象，雖然不需要對整棵樹進行重新編碼，二次編碼率得到一定的降低，但仍不為零。IFPL編碼利用了間隔因子，用少量空間代價換取了對動態更新的完全支持，二次編碼率為零，特別是當插入的結點越多，IFPL 編碼優越性越明顯。因此，IFPL編碼方式在有新結點插入時表現的時間性能最為突出。
關於時間序列相似性問題中間隔因子
作為一種非平凡問題，大多數時間序列相似性檢索解決方法中涉及到了對原數據的降維處理技術。在有效保持原序列中信息量的同時，儘量減低計算複雜度是這些算法的關鍵。時序特徵值表示方法針對了時間序列中的特徵值採取自適應的算法，通過時間序列中的若干特殊的數據點，從而發現一組合適的滑動視窗大小，並根據序列變化的程度來決定滑動視窗相似比較的方式。
時間序列的特點
從水文角度指出時間序列是基本概念將某種隨機變數按出現時間的順序排列。平穩時間序列是指其中隨變數的時間序列，它的前期演變過程的統計相關規律在未來的一段時間內是不變的，也就是說它的數學期望值與方差是不變的，它的相關函式只與時間間隔有關而與時間無關。
經典的時間序列分析方法多數基於傳統的統計學中建模的手段，在維數較高時間序列資料庫環境下，這樣的分析方法往往達不到性能上的要求。隨著數據挖掘技術的發展，時間序列分析逐漸離開了數學建模的道路，而開始更多地關注時間序列的降維。從時間序列序列本身進行相似性分析，時間序列的相似性研究的難點是相似性定義和算法時間複雜度。由於相似性含義隨著套用領域及查詢目標的不同而不同，所以採用何種方法度量相似或不相似包括距離公式和序列變換的選擇是算法的關鍵。
對於所有的數據進行先要進行必要的正則化( Normalize) ，即設定時序Q，用公式
Q=(Q- mean(Q))/STD(Q)
非正則化的時序比較在數據挖掘領域是沒有任何意義的，用普通的統計方法就可以直接解決非正則化的時序比較的問題。既考慮了觀測數據在時間序列上的依存性，又考慮了到隨機波動的干擾，更加重要還要考慮了有效保持原序列中信息量的同時，儘量減低計算複雜度。
一種時間間隔算法
不失一般性 ，總能把時間序列轉正則化為N(0，1)的隨機分布。
任何時間序列上的變化，如果是同一區間可以認為是微小變化，可從輕考慮； 反之，則是要注意的。這樣就可以計算出有關變化的時間間隔。算法在設定好劃分數組後，簡單可行，快速。在實際套用中往往對多個劃分數組進行反覆測試，再跟據不同的數據特徵、時間間隔特點和套用領域得到合適時間序列分段 ( warping window or envelope，滑動視窗) 大小，注意到算法是自適應性的，其有效地解決了如何有效確定該數據的難題，其得到的結果可以套用於多種不同的算法中。
試驗結果
通過對典型的20個數據集 ( 所有數據都經過正則化 ) 和Euclidean、DTW算法進行比較，這兩種方法在此數據集上，結果遠好於PAA，SAX，DFT，DWT。
該算法是一種可靠、快速自適應的時間序列相似性查找算法。還可以通過時間間隔的一些特點對時間序列關聯規則所起的影響，使關聯規則在這個領域的得到進一步一些運用。
