[發明專利]一種面向全排列數據的多變量可視分析方法

有效

• 申請號: 201810860167.3
• 申請日: 2018-08-01
• 公開（公告）號: CN109271567B
• 公開（公告）日: 2022-07-26
• 發明（設計）人: 孫國道;周志秀;趙銀;劉義鵬;蔣莉;梁榮華
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06F16/904
• 分類號: G06F16/904;G06K9/62
• 代理公司: 杭州斯可睿專利事務所有限公司 33241
• 代理人: 王利強

一種面向全排列數據的多變量可視分析方法，包括以下步驟：(1)對原始數據集合中的有限項目使用全排列算法得出所有排序方案；(2)根據原始數據中各個項目兩兩之間的連接屬性，分別對排序方案添加連接屬性信息；(3)通過MDS算法將所有排序方案降維聚類；(4)可視化分析：MDS view聚類視圖、PCP View平行坐標視圖、Perm View矩陣視圖，各個視圖之間交互分析，引導用戶選擇自己感興趣的方案集群和排序方案。本發明從大量的全排列方案中挖掘出特殊的集群模式，將排列方案之間的相似性和差異性通過可視化讓用戶從中分析并結合自己的需求得出最佳的排序方案。

技術領域

本發明涉及一種面向全排列數據的多變量可視分析方法。

背景技術

全排列是組合學中最常見和最基本的主題之一，在科學，工程和商業領域出現了許多問題。而且也出現在數學、組合數學、計算機科學、運籌學、計算分子生物學、自然語言處理、甚至配色方案等許多基礎和應用學科中。

最常見的情況是許多現實世界的問題在數學上是難以處理的。在這些情況下，需要排列組合技術來計算，枚舉或表示解決應用程序問題過程中的可能解決方案。由于在實際應用中的基本性質和重要性，研究者們廣泛研究了組合序列的產生，例如排列和組合。

我們在日常生活或工作要求中遇到一些規則的排列項目。如旅行計劃的最佳旅行順序，音樂創作中音符的最佳組合，還有最有效的電路組合設計等。大多數情況下，排列的目的是根據要求找到最佳的解決方案或模式。通過排列一個集合中不同項目，獲得不同排列序列的方案，用戶通過測試篩選，選擇心目中最優的結果。但是，全排列問題是一個NP問題，排列集合的數目伴隨著項目的增加呈現指數級別的增長。這將會耗費用戶大量的時間去手動測試衡量所有排列的方案，與此同時增加了用戶探索不同序列變化帶來不同的復雜度。

發明內容

為了解決上述缺點，使用可視化分析技術來解決多變量全排列數據的分析問題應運而生，通過可視化技術，探索從排列中搜索最佳序列的過程，比較序列之間的差異和從排列中找出一些模式，以幫助用戶做出決策；本發明從多變量全排列數據中獲得排序信息和統計屬性，理解每個排列方案的含義，便于用戶視覺上比較，幫助用戶決策找出最佳排序方案，本發明提供了一種面向全排列旅游數據的多變量可視分析方法，通過d3.js進行可視化組件的設計。與當前關于全排列的研究不同，本發明通過對全排列聚類算法的改進，幫助用戶發現模式，從可視化的角度出發，呈現所有排序方案。用戶可以根據自己的要求選擇排序方案，同時可以查看排序的多變量信息，用以輔助用戶比較理解排序的順序不同，導致的連接屬性的不同。

為了解決上述技術問題本發明提供如下的技術方案：

一種面向全排列數據的多變量可視分析方法，包括以下步驟：

1)、對原始數據集合中的有限項目使用全排列算法得出所有排序方案；假設原始數據為一組集合，集合包含n個需要排列的項目item：S＝{item-1，item-2，item-3…item-n}，對每個item 設置id，然后全排列得出所有目的地的不同排序P＝{P1{1，2，3…n},P2{1，3，2…n},…,Pn！{n，n-1，n-2…1}}，不同排序P中方案的數量為Sum＝n！；

2)、根據原始數據中各個項目兩兩之間的連接屬性，分別對上一步得到的排序方案添加其對應的連接屬性信息；假設原始數據中項目之間連接的有三個屬性分別用T，P，D來表示，則排序方案{1，2，3…n}對應的連接屬性向量為：

L1＝{T1-2，P1-2，D1-2，T2-3，P2-3，D2-3，T3-4，P3-4，D3-4…T(n-1)-n，P(n-1)-n，D(n-1)-n}；