基於分布式圖模型的流式細胞計數據自動門控方法與流程
2023-07-01 00:56:51 3
本發明涉及流式細胞計技術，尤其涉及一種基於分布式圖模型的流式細胞計數據自動門控方法。
背景技術：
流式細胞計技術是目前較為先進的單細胞測量技術。是對懸液中的單細胞或其他生物粒子,通過檢測標記的螢光信號，實現高速、逐一的細胞定量分析和分選的技術。質譜流式細胞計技術是在流式細胞計基礎上發展出的新一代單細胞測量技術。利用稀土元素同位素標記特定抗原，控制抗原和單細胞表面的抗體特異性結合，接著氣化細胞，控制其等離子體進入質譜，質譜對於同位數的技術結果代表著該細胞上被標記抗原的表達程度。而抗原表達程度和細胞的功能、種類密切相關，這個尺度的測量結果為免疫系統的研究，包括細胞的篩選、分型等提供了巨大的幫助。
大部分研究的基礎是依靠這些標誌物，逐步篩選出感興趣的細胞亞群進而進行研究，這個過程稱為門控。傳統的門控方法是利用已有的領域知識，依靠具有關鍵信息的標記物的二維圖，按照一定的層次，逐步從原始數據中手動分離出感興趣的細胞亞群。幾個商業化軟體也是在這個基礎上為使用者提供速度更快、交互性更強的操作：FCS Express、FlowJo、CytoBank等。隨著單細胞數據維度的升高，門控變得越來越不可行。
學術界引入計算方法，著重在用非監督性學習——聚類來替代對數據集的人為的門控工作，大致方向包括基於密度，基於幾何等。其中Cytobank的提供的聚類算法中只有比較基礎的k-means和層次聚類等。而相較於這些方法，基於圖的方法由於不需要對數據有著預先的形態假設，輸入參數在較大的範圍內都輸出穩定的結果，對於稀少亞群具有識別和保留能力，能還可以銜接進一步的半監督學習和遷移數據挖掘模型，成為較好的選擇。
傳統的人工門控都是採樣一個二維散點圖劃分策略，費時費力，人為主觀因素大，不具可重複性，對於高維度無能為力，複雜度為O(m^2)，m為數據點的維數。而這種方法，對於定義不好的組織(比如肝、脾)也沒有金標準。
傳統的聚類算法沒有辦法處理好模型假設和數據分布之間的一致性。比如k‐means是一個幾何空間的多邊形劃分，很容易將一個多邊形空間內明顯分割的兩塊數據區域合併成一類；DBSCAN等依靠密度的聚類算法需要預估計密度核寬，因而對於尺寸小於這個核寬的區域就存在不適應性等。相較於這些方法，基於圖的方法則很大程度上同時保持了全局和局部的數據特徵。
常規的圖算法計算過程往往會需要全局遍歷節點和邊，面對大規模的實驗數據時會面臨很大的時間和內存消耗。比如第一步通常需要構造kNN圖，則需要遍歷計算所有數據點之間兩兩距離，複雜度為O(n^2)，n為數據點個數，同時預存邊的權值。其他操作中，比如權值更新，邊的增刪，也存在許多按元素的操作方法，按照單線程的方式進行效率低下。當數據點到達百萬數量級以後，常規的單機配置已經讓內存消耗和計算時間變得難以忍受，這會限制通量越來越高的實驗數據處理。
技術實現要素：
本發明的目的在於針對現有技術的不足，提供一種基於分布式圖模型的流式細胞計數據自動門控方法。
本發明的目的是通過以下技術方案來實現的：一種基於分布式圖模型的流式細胞計數據自動門控方法，包括以下步驟：
(1)根據GraphLab框架將輸入的細胞計數據文件變換為RDD類型，得到流式細胞計數據X＝{x1,x2,...,xN}；
(2)輸入流式細胞計數據X＝{x1,x2,...,xN}、鄰域大小k、隨機重複的次數r；N為數據點個數。輸出C＝{c1,c2,...,cN}，代表每個數據點被分配到的標籤，即門控後的結果；
(3)基於隨機投影樹和GraphLab框架分布式構造kNN圖：
在Gather階段，每個線程上隨機生成若干超平面v，將每個數據點視為節點，本線程上的節點x選擇滿足最遠點距離要求x·v≤median({z·v:z∈S}+δ)的節點自動成為鄰居，在Scatter階段節點x與鄰居節點之間的邊的權值為1，與非鄰居節點之間的邊的權值為0，當發現每個節點鄰居個數達到k時，自動跳出，從而構建得到kNN圖；S為節點的集合，δ為任意常數，median表示取中值。為了達到需要的精度，反覆執行2‐3次，取圖的交集以保證準確度，得到最終的kNN圖；
(4)通過GraphLab框架的Gather階段遍歷每一個節點x的所有邊；通過GraphLab框架的Scatter階段，根據所有的和該節點連接的節點Vk(x)計算Jaccard係數Jk(xi,xj)，將kNN圖變成帶權值圖；
(5)對得到的帶權值圖執行圖割算法，得到一次劃分C＝{c1,c2,...,cN}和目標函數Q值，Q值的計算如(2)：
其中，J代表整幅帶權值圖的權值，δ(ci,cj)表示delta函數，當輸入相等取1，否則取0。deg(vi)代表節點i的度，本模型中沒有負權值，m表示帶權值圖中邊的權值之和的1/2。
(6)重複r次步驟4，選擇r次中最大Q值對應的C作為門控後的結果。
進一步，所述步驟5包括以下子步驟：
a)初始化每一個節點自成一個社群；
b)並行遍歷節點，對於節點i的鄰域Vk(x)的每一個節點j∈Vk(x)，計算如果將i歸入j所屬的社群cj中Q值的增加值ΔQ，尋找ΔQ最大的歸入方式。在計算ΔQ的過程中通過Gather階段，讀取邊權值和邊所對應的節點，在Apply階段將每條邊的權值加到對應節點的屬性上，計算出每個節點的度，並給予節點一個臨時標籤代表其所屬的社群。根據每個節點的度和臨時標籤計算得到ΔQ。
其中∑in是社區C內部節點之間邊的權值和，∑tot是該歸入方式執行後所有被連接歸入C的邊的權值之和，ki是節點i所有連接邊的權值之和，ki,in是節點i連接進入社群C後所有帶入邊的權值之和，m是整個網絡所有邊的權值之和。
c)選擇ΔQ最大的歸入方式後，所有社群內部的點聚合成一個新的點，社群增加一條自連邊，自連邊的權值是社區C內部節點之間邊的權值和，社群和社群之間邊的權值是聚合之前兩個社群的有連接的成員之間邊的權值之和。將聚合後的圖回帶到步驟b)中執行相同的操作。
d)重複b)和c)，直到ΔQ收斂。
本發明的有益效果是：將分布式技術應用於流式細胞計數據的門控計算；對於圖模型所有按元素操作的並行化計算，提高程序執行性能。基於隨機投影樹的kNN搜索策略，降低構造圖的時間到線性複雜度。Spark的分布式存儲方式可以處理更大規模的數據集(百萬數據點以上)。利用隨機投影樹加快了kNN的搜索效率。對於邊權值的操作進行了並行化。割圖算法採用了並行化的社群劃分算法。本發明通過分布式計算框架實現對流式細胞計數據的門控過程進行基於圖模型的聚類分析，對原始數據進行自動的劃分，從而提升數據分析效率和準確度，降低劃分過程的重複勞動和人為主觀因素。
附圖說明
圖1為GraphLab構造存儲圖的方法；
圖2為Gather‐Apply‐scatter架構；
圖3為聚類算法流程圖；
圖4中(a)為k‐d樹原理，(b)為隨機投影樹原理。
具體實施方式
下面結合附圖和具體實施例對本發明作進一步詳細說明。
本發明使用基於圖的聚類算法來實現流式細胞計數據的自動門控，即通過在該數據集上構造、修飾並且劃分圖來實現數據的聚類。通過假設數據整體的分布模式和選擇相似性度量，通過內部指標(或稱為目標函數)的優化來實現穩定聚類結果的輸出，依靠外部指標(和人為標註進行對比)來說明自身的準確性。非監督學習過程直接，易於高效實現，相較於傳統的門控策略可以極大地解放人力，同時產生結果具有可重複性。
而為了提升計算性能，使得該方法可以在未來適應更為龐大的數據集，更快地給予研究者反饋信息，本發明採用基於Spark的GraphLab分布式計算框架，該框架提供了成熟的基於圖的數據挖掘模型函數藉口，可以幫我們在分布式的框架上實現這一算法。GraphLab分布式計算框架具體如下：
GraphLab的並行化主要依靠於頂點，頂點是最小並行粒度和通信粒度，而邊是機器學習算法中數據依賴性的表現方式。GraphLab的存儲模式是將單個頂點存儲到多個機器上，分為master‐mirror，而對於某條邊，GraphLab將其部署到某一臺機器上，從而每一臺機器上有一個本地圖，如圖1所示。而本地id到全局id存在一個映射表，圖的節點是一個進程上所有線程共享的，在並行計算過程中，各個線程分攤所有頂點的gather→apply→scatter操作，如圖2所示。
每個頂點每一輪迭代經過gather‐>apple‐>scatter三個階段。
1)Gather階段
工作頂點的邊(可能是所有邊，也有可能是入邊或者出邊)從領接頂點和自身收集數據，記為gather_data_i，各個邊的數據graphlab會求和，記為sum_data。這一階段對工作頂點、邊都是只讀的。
2)Apply階段
Mirror將gather計算的結果sum_data發送給master頂點，master進行匯總為total。Master利用total和上一步的頂點數據，按照業務需求進行進一步的計算，然後更新master的頂點數據，並同步mirror。Apply階段中，工作頂點可修改，邊不可修改。
3)Scatter階段
工作頂點更新完成之後，更新邊上的數據，並通知對其有依賴的鄰結頂點更新狀態。這scatter過程中，工作頂點只讀，邊上數據可寫。
在執行模型中，GraphLab通過控制三個階段的讀寫權限來達到互斥的目的。在gather階段只讀，apply對頂點只寫，scatter對邊只寫。並行計算的同步通過master和mirror來實現，mirror相當於每個頂點對外的一個接口人，將複雜的數據通信抽象成頂點的行為。
對於常規的圖操作，Graphlab也提供了可直接調用的API，例如元素訪問graphlab.Edge、元素的融合graphlab.aggregate等。
本發明提供的一種基於分布式圖模型的流式細胞計數據自動門控方法，如圖3所示，包括以下步驟：
(1)根據GraphLab框架將輸入的細胞計數據文件變換為RDD類型，得到流式細胞計數據X＝{x1,x2,...,xN}；
(2)輸入流式細胞計數據X＝{x1,x2,...,xN}、鄰域大小k、隨機重複的次數r；N為數據點個數。輸出C＝{c1,c2,...,cN}，代表每個數據點被分配到的標籤，即門控後的結果；
(3)基於隨機投影樹和GraphLab框架分布式構造kNN圖：
在Gather階段，每個線程上隨機生成若干超平面v，將每個數據點視為節點，本線程上的節點x選擇滿足最遠點距離要求x·v≤median({z·v:z∈S}+δ)的節點自動成為鄰居，在Scatter階段節點x與鄰居節點之間的邊的權值為1，與非鄰居節點之間的邊的權值為0，當發現每個節點鄰居個數達到k時，自動跳出，從而構建得到kNN圖；S為節點的集合，δ為任意常數，median表示取中值。為了達到需要的精度，反覆執行2‐3次，取圖的交集以保證準確度，得到最終的kNN圖；
(4)通過GraphLab框架的Gather階段遍歷每一個節點x的所有邊；通過GraphLab框架的Scatter階段，根據所有的和該節點連接的節點Vk(x)計算Jaccard係數Jk(xi,xj)，將kNN圖變成帶權值圖；
(5)對得到的帶權值圖執行圖割算法，得到一次劃分C＝{c1,c2,...,cN}和目標函數Q值，Q值的計算如(2)：
其中，J代表整幅帶權值圖的權值，δ(ci,cj)表示delta函數，當輸入相等取1，否則取0。deg(vi)代表節點i的度，本模型中沒有負權值，m表示帶權值圖中邊的權值之和的1/2。該步驟的具體實現步驟如下：
a)初始化每一個節點自成一個社群；
b)並行遍歷節點，對於節點i的鄰域Vk(x)的每一個節點j∈Vk(x)，計算如果將i歸入j所屬的社群cj中Q值的增加值ΔQ，尋找ΔQ最大的歸入方式。在計算ΔQ的過程中通過Gather階段，讀取邊權值和邊所對應的節點，在Apply階段將每條邊的權值加到對應節點的屬性上，計算出每個節點的度，並給予節點一個臨時標籤代表其所屬的社群。根據每個節點的度和臨時標籤計算得到ΔQ。
其中∑in是社區C內部節點之間邊的權值和，∑tot是該歸入方式執行後所有被連接歸入C的邊的權值之和，ki是節點i所有連接邊的權值之和，ki,in是節點i連接進入社群C後所有帶入邊的權值之和，m是整個網絡所有邊的權值之和。
c)選擇ΔQ最大的歸入方式後，所有社群內部的點聚合成一個新的點，社群增加一條自連邊，自連邊的權值是社區C內部節點之間邊的權值和，社群和社群之間邊的權值是聚合之前兩個社群的有連接的成員之間邊的權值之和。將聚合後的圖回帶到步驟b)中執行相同的操作。
d)重複b)和c)，直到ΔQ收斂。
(6)重複r次步驟4，選擇r次中最大Q值對應的C作為門控後的結果。