基於圖上隨機遊走的分類算法研究

《基於圖上隨機遊走的分類算法研究》是依託揚州大學，由徐曉華擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：基於圖上隨機遊走的分類算法研究
• 項目類別：青年科學基金項目
• 項目負責人：徐曉華
• 依託單位：揚州大學

項目摘要

分類是機器學習中最為基礎和核心的研究內容，但是傳統的分類方法往往存在著前提假設過強或者先驗知識要求過多等限制條件。圖上的隨機遊走作為一種直觀易理解又套用廣泛的數學理論，為研究者們提供了一條嶄新且具有充分潛力的解決途徑。本項目研究將圖上的隨機遊走作為一項基本技術，為帶無標籤數據和不帶無標籤數據的兩種分類問題分別提出一種基於圖上隨機遊走的解決方案，即多層次隨機遊走標籤傳播學習模型和隨機遊走分類器模型。這兩種分類模型不但能分別覆蓋大部分的標籤傳播半監督學習算法和多數基於核方法和流形一致性假設的分類器，而且我們還可以在此基礎上，進一步結合其統一的幾何表示、代數解析以及正則化理論，設計新的標籤傳播算法和隨機遊走分類器。本項目的研究可以為圖上隨機遊走學習提供堅實的數學理論基礎，提高已有分類算法的效率和性能，並大大推動圖上隨機遊走在機器學習和數據挖掘領域套用的成熟性和廣泛性。

結題摘要

分類是機器學習中最為基礎的核心研究內容,但是傳統的分類方法往往存在著前提假設過強或先驗知識要求過多等限制。圖上的隨機遊走作為一種直觀易理解又套用廣泛的數學理論,為研究者們提供了一條嶄新而具有潛力的解決途徑。本項目研究將圖上的隨機遊走作為一項基本技術,為帶無標籤數據和不帶無標籤數據的兩種分類問題分別提出一種基於圖上隨機遊走的解決方案。 我們提出一種基於圖上隨機遊走的半監督學習模型。該隨機遊走半監督學習模型不但具有直觀的幾何解釋，統一的代數表達形式，而且還有正則化理論的支持。從這一學習模型，我們可以從理論上設計和分析更高效的半監督學習算法。 我們設計一種基於圖上隨機遊走的多層組件傳播算法，該算法具有清晰的時間序列上的狀態轉化、更好地利用已知標籤數據、並且能以較快的速度保證收斂性，從而取得更好的學習性能。我們提出了一種多層組件傳播的半監督分類算法，不僅證明了算法的解的收斂性，還與其它算法進行比較，從實驗上驗證其性能的優越性。 我們提出一種基於圖上隨機遊走的分類器模型。該隨機遊走分類器模型覆蓋了大部分具有二次形式的分類算法，統一大量基於核方法和基於流形一致性假設的分類器，並進行正則化方面的擴展。在此模型下設計了監督式譜空間分類器，通過引入中間流形橋，取得了比其他多種著名分類器具有更加優越的分類性能。 我們提出了一種基於圖上隨機遊走的分類器模型的組合隨機遊走分類器框架，盡最大可能地有效利用了訓練數據信息，減少訓練數據中噪聲干擾。在該框架下使用懶散遊走分類器設計了一種最佳化的組合懶散分類器，並將其用於亞細胞中蛋白質定位預測，取得了比SVM等預測方法更好的結果。 我們提出了一種基於圖上隨機遊走的半監督學習模型的多種群螞蟻半監督分類算法。該算法通過螞蟻種群信息素的變化來動態更新隨機最大生成樹，從而達到逐步逼近數據內在流形結構，取得比標籤傳播等半監督算法更好的分類效果。 我們設計了一種基於雙層隨機遊走的半監督聚類算法，用於處理既有必連約束又有不連約束的多類別半監督聚類問題。該算法通過建立受限的隨機遊走模型來確定每個點對約束的影響範圍和影響程度。在大量數據集上的實驗結果表明我們的算法優於同類半監督聚類算法。 我們還將隨機遊走學習的上述理論成果套用到社交網路發現、中醫藥數據挖掘、蛋白質定位預測、生物序列挖掘、並發系統建模等領域中，取得了很好套用效果。