[發明專利]一種基于關聯矩陣的不確定數據連接合并算法

在審

• 申請號: 201710050489.7
• 申請日: 2017-01-23
• 公開（公告）號: CN106897385A
• 公開（公告）日: 2017-06-27
• 發明（設計）人: 梁俊杰;王明鋒
• 申請（專利權）人: 武漢迎風聚智科技有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 武漢河山金堂專利事務所(普通合伙)42212
• 代理人: 胡清堂

技術領域

本發明涉及計算機軟件技術領域，具體地，涉及一種基于關聯矩陣，確定數據表的連接合并規則，解決不確定數據表的連接合并問題的算法。

背景技術

隨著互聯網技術的蓬勃發展，我們已經進入了大數據時代，要從海量的數據中提取出有價值的信息變得更加復雜。在網絡中存在許多看似相互獨立的數據，實際上他們都是對同一類對象從不同方面的描述，例如同一個人或同一件商品在不同的網站，由于網站關注的角度不同，其存儲的關于人或商品對象的屬性信息也不完全相同。如果能夠找到一種方法，整合多個不同來源且數據項含義不明確、數據對象不明確的數據，得到數據描述對象的詳細信息，則對人們了解對象全貌有很大的幫助。

其中，不確定數據連接合并算法本質是在數據項含義不明確的數據表間找出關聯記錄，并將關聯記錄進行連接合并。對于多個不同來源且數據項含義不明確、數據對象不明確的數據表，要將各表中表示同一對象的記錄合并在一起得到對象的全息影像，需要解決兩個主要問題，首先如何確定數據表的連接合并順序，避免可以進行合并的記錄被遺漏；其次如何降低大數據應用場景下，表關聯操作的計算復雜性問題，對于兩個不確定數據表如果直接進行連接匹配計算量非常大，如兩個維度分別為m維和n維的數據表，進行連接合并時需要進行m*n次屬性值相似匹配。

發明內容

為了克服現有技術的不足，本發明提供一種基于關聯矩陣的不確定數據連接合并算法，以解決數據項含義不明確、數據對象不明確的數據難以進行連接合并的問題。

本發明為解決上述技術問題所采用的技術方案是：一種基于關聯矩陣的不確定數據連接合并算法，包括以下步驟：

步驟1：引入屬性重要度，數據表中數據對象的某一屬性的重要度越高則表示該屬性對該類數據對象的區分度越大；計算數據表中各屬性的重要度，找出數據表所有屬性重要度的最大值；

假設對象r1{P₁,P₂}和r2{P₁,P₂}，對應的屬性值分別為r1(p₁₁,p₁₂)和r2(p₂₁,p₂₂)，r1和r2表示同一實體時，記為：當對象r1在屬性P₁上的取值p₁₁和對象r2在屬性P₁上的取值p₂₁相同時，r1和r2表示同一實體的概率為同樣

若說明屬性P₁相對屬性P₂對該類對象具有更大的區分度，則可以將條件概率作為屬性P₁的重要度，記為

為了方便計算，我們可以采用以下思路來計算屬性重要度：當r1和r2為不同的對象，p₁₁＝p₂₁相等的概率為P(p₁₁＝p₂₁|r1≠r2)，由條件概率知，P(p₁₁＝p₂₁|r1≠r2)與存在反比關系，因此屬性P₁的重要度

針對數據表T＝{P₁,P₂,...,P_n}，P_i的取值為統計P_i中每個不同屬性值的出現次數，如表1所列：

表1屬性P_i的取值分布

由于同一數據表中存在同一對象的概率很小，因此在大數據表中可以認為每一條記錄代表一個不同的對象，基于該假設，其值相等的概率為由于可得則屬性P_i的重要度為：

由于此值范圍較大，不利于后期記錄相似度的計算，因此對其進行平滑化處理和歸一化處理，得到：

其中W_{p max}表示數據表T所有屬性重要度的最大值。

步驟2：確定數據表之間的關聯度，并建立關聯矩陣；

步驟201，采用杰卡德相似系數來計算屬性相似度，并以此確定表間關聯屬性

杰卡德相似系數是衡量兩個集合相似度的一種指標，設表T_i、T_j在某個屬性上取值集合分別為PV_ia和PV_jb，它們的交集元素在并集中所占的比例，稱為兩個集合的杰卡德相似系數，即為屬性值集合PV_ia和PV_jb的相似度：