[發明專利]一種基于有向圖關聯規則音樂云推薦算法

在審

• 申請號: 201610015143.9
• 申請日: 2016-01-11
• 公開（公告）號: CN105718509A
• 公開（公告）日: 2016-06-29
• 發明（設計）人: 柯新生
• 申請（專利權）人: 北京交通大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京衛平智業專利代理事務所(普通合伙) 11392
• 代理人: 董琪

1.一種基于有向圖關聯規則音樂云推薦算法，其特征在于，包括如下步驟：

A:建立數據庫

建立數據庫的流程包括：建立關系型數據庫、Hbase型數據庫，以及從關系型數據庫向Hbase型數據庫遷移；

B構建有向圖關聯規則算法

B1制訂支持度計算策略；

B2構建有向圖的存儲方式；

B3一般有向圖關聯構建；

B4完全頻繁項集有向圖構建：依據頻繁項集的子集都是頻繁項集，非頻繁項集的超集都是非頻繁項集，在有向項集圖存儲的1，2項頻繁集的基礎上進行項集并操作和支持該項集的交易列表的交操作便發現所有頻繁項集；

B5最大頻繁項集的有向圖構建。

2.如權利要求1所述的基于有向圖關聯規則音樂云推薦算法，其特征在于：建立數據庫的具體步驟為：

A1建立關系型數據庫：以音樂特征元組為元素，用二位表型的關系模型數據庫表示音樂特征數據及其數據之間的聯系；

A2建立Hbase型數據庫：建立基于列儲存的分布式Hbase型數據庫，以便能后期輕松改變硬件數量，提高錯誤兼容性；

A3從關系型數據庫向Hbase型數據庫遷移。

3.如權利要求2所述的基于有向圖關聯規則音樂云推薦算法，其特征在于：從關系型數據庫向Hbase型數據庫遷移的具體步驟為：

A31由解析器(Schemaparser)解析由外部工具把傳統RDBMS(關系數據庫管理系統)數據庫導出的表模式定義文檔；

A32用表模式轉換器(Convertor)把傳統RDBMS的表模式定義轉換成Hbase的表模式；

A33用表模式適配器(Adapter)保存、讀取已經由表模式轉換器所轉換過的表模式定義到指定文件中，并為其他模塊查找新的表模式定義提供接口；

A34用數據表管理器(TableManager)把從初在傳統RDBMS數據庫中的數據遷移到Hbase數據庫中對應新定義的表中；

A35令在關系型數據庫中原有的表集合為A，遷移后的在HBase數據庫中的表集合為B。

4.如權利要求1所述的基于有向圖關聯規則音樂云推薦算法，其特征在于：制訂支持度計算策略的具體步驟為：

B11設計Tidlist存儲方式：定義一個關聯項的Tidlist的長度與其數據庫中交易數相等，用n個二進制位來表示一個項的Tidlist，即n/8個字節；每一個字節中的一個位取值0、1對應數據庫中相應的交易不支持或支持項。

5.如權利要求1所述的基于有向圖關聯規則音樂云推薦算法，其特征在于：構建有向圖的存儲方式的具體步驟為：

B21使用鄰接矩陣存儲表示圖G＝(V，E)各頂點信息之間的關系矩陣，用定義：如果(i，j)∈E，則A.edge[i][j](該邊權值)的值取1，否則為0；

B211保存節點中有與其邊關聯的另一頂點的下標和指向同一鏈表中的下一個邊結點的指針；

B212保存該邊權值。

6.如權利要求1所述的基于有向圖關聯規則音樂云推薦算法，其特征在于：一般有向圖關聯構建的具體步驟為：

B31確定有向圖的結點：將所有大于最小支持度s的項按支持度降序排列組成有向項集圖的結點V＝{B,E,A,C,D}；

B32添加有線圖中的弧：按順序從結點集V中選擇一個結點作為出發結點；

B33依次選擇點為出發結點，刪除支持度不符合的點，直到結點集為空。

7.如權利要求1所述的基于有向圖關聯規則音樂云推薦算法，其特征在于：完全頻繁項集有向圖構建的具體步驟為：

B41定義候選集：一個項集的所有子集的支持度均大于或等于最小支持度的頻繁項集為候選集；

B42有且只有n項頻繁項集{V₁,V₂,…,V_n}中任何一個項在有向項集圖中都存在一條指向結點V_n+1的弧，則{V₁,V₂,…,V_n,V_n+1}為候選集。

8.如權利要求1所述的基于有向圖關聯規則音樂云推薦算法，其特征在于：最大頻繁項集的有向圖構建的具體步驟為：

B51將數據庫中的有關頻繁項集的信息保存在有向項集圖中，利用深度優先的搜索策略，發現最大頻繁項集；

B511在訪問圖的某一起始結點V；

B512由V出發，訪問它的鄰接結點再從w₁出發訪問的w₁鄰接結點w₂；

B513從w₂出發進行上述訪問；

B514直到鄰接表為空時或支持度不滿足要求時就生成了一個最大頻繁項集；

B515將生成的最大頻繁項集保存在最大頻繁項集的集合中；

B516返回上一層結點或選擇其他鄰接點繼續進行m上述的訪問；

B517刪除那些是已經發現的最大頻繁項集的子集的頻繁項集；

B518直到生成所有的最大頻繁項集為止。