標籤傳播演算法 - Platform For AI

標籤傳播演算法LPA（Label Propagation Algorithm）是基於圖的半監督學習方法，其基本思路是節點的標籤（community）依賴其相鄰節點的標籤資訊，影響程度由節點相似性決定，並通過傳播迭代更新達到穩定。標籤傳播聚類組件能夠輸出圖中所有節點均收斂時各節點對應的組。

演算法說明

圖聚類是根據圖的拓撲結構，進行子圖的劃分，使得子圖內部節點的串連較多，子圖之間的串連較少。
在用一個唯一的標籤初始化每個節點之後，該演算法會重複地將一個節點的標籤社群化為該節點的相鄰節點中出現頻率最高的標籤。當每個節點的標籤在其相鄰節點中出現得最頻繁時，演算法就會停止。

配置組件

方法一：可視化方式

在Designer工作流程頁面添加標籤傳播聚類組件，並在介面右側配置相關參數：

參數類型	參數	描述
欄位設定	頂點表：選擇頂點列	頂點表的點所在列。
	頂點表：選擇權值列	頂點表的點的權重所在列。
	邊表：選擇源頂點列	邊表的起點所在列。
	邊表：選擇目標頂點列	邊表的終點所在列。
	邊表：選擇權值列	邊表邊的權重所在列。
參數設定	最大迭代次數	最大迭代次數，預設值為30。
執行調優	進程數	作業並存執行的節點數。數字越大並行度越高，但是架構通訊開銷會增大。
執行調優	進程記憶體	單個作業可使用的最大記憶體量，單位：MB，預設值為4096。如果實際使用記憶體超過該值，會拋出`OutOfMemory`異常。

方法二：PAI命令方式

使用PAI命令配置標籤傳播聚類組件參數。您可以使用SQL指令碼組件進行PAI命令調用，詳情請參見情境4：在SQL指令碼組件中執行PAI命令。

PAI -name LabelPropagationClustering
    -project algo_public
    -DinputEdgeTableName=LabelPropagationClustering_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DinputVertexTableName=LabelPropagationClustering_func_test_node
    -DvertexCol=node
    -DoutputTableName=LabelPropagationClustering_func_test_result
    -DhasEdgeWeight=true
    -DedgeWeightCol=edge_weight
    -DhasVertexWeight=true
    -DvertexWeightCol=node_weight
    -DrandSelect=true
    -DmaxIter=100;

參數	是否必選	預設值	描述
inputEdgeTableName	是	無	輸入邊表名。
inputEdgeTablePartitions	否	全表讀入	輸入邊表的分區。
fromVertexCol	是	無	輸入邊表的起點所在列。
toVertexCol	是	無	輸入邊表的終點所在列。
inputVertexTableName	是	無	輸入頂點表名稱。
inputVertexTablePartitions	否	全表讀入	輸入頂點表的分區。
vertexCol	是	無	輸入頂點表的點所在列。
outputTableName	是	無	輸出表名。
outputTablePartitions	否	無	輸出表的分區。
lifecycle	否	無	輸出表的生命週期。
workerNum	否	未設定	作業並存執行的節點數。數字越大並行度越高，但是架構通訊開銷會增大。
workerMem	否	4096	單個作業可使用的最大記憶體量，單位：MB，預設值為4096。如果實際使用記憶體超過該值，會拋出`OutOfMemory`異常。
splitSize	否	64	資料切分的大小，單位：MB。
hasEdgeWeight	否	false	輸入邊表的邊是否有權重。
edgeWeightCol	否	無	輸入邊表邊的權重所在列。
hasVertexWeight	否	false	輸入頂點表的點是否有權重。
vertexWeightCol	否	無	輸入頂點表的點的權重所在列。
randSelect	否	false	是否隨機播放最大標籤。
maxIter	否	30	最大迭代次數。

使用樣本

添加SQL指令碼組件，輸入以下SQL語句產生訓練資料。

drop table if exists LabelPropagationClustering_func_test_edge;
create table LabelPropagationClustering_func_test_edge as
select * from
(
    select '1' as flow_out_id,'2' as flow_in_id,0.7 as edge_weight
    union all
    select '1' as flow_out_id,'3' as flow_in_id,0.7 as edge_weight
    union all
    select '1' as flow_out_id,'4' as flow_in_id,0.6 as edge_weight
    union all
    select '2' as flow_out_id,'3' as flow_in_id,0.7 as edge_weight
    union all
    select '2' as flow_out_id,'4' as flow_in_id,0.6 as edge_weight
    union all
    select '3' as flow_out_id,'4' as flow_in_id,0.6 as edge_weight
    union all
    select '4' as flow_out_id,'6' as flow_in_id,0.3 as edge_weight
    union all
    select '5' as flow_out_id,'6' as flow_in_id,0.6 as edge_weight
    union all
    select '5' as flow_out_id,'7' as flow_in_id,0.7 as edge_weight
    union all
    select '5' as flow_out_id,'8' as flow_in_id,0.7 as edge_weight
    union all
    select '6' as flow_out_id,'7' as flow_in_id,0.6 as edge_weight
    union all
    select '6' as flow_out_id,'8' as flow_in_id,0.6 as edge_weight
    union all
    select '7' as flow_out_id,'8' as flow_in_id,0.7 as edge_weight
)tmp
;
drop table if exists LabelPropagationClustering_func_test_node;
create table LabelPropagationClustering_func_test_node as
select * from
(
    select '1' as node,0.7 as node_weight
    union all
    select '2' as node,0.7 as node_weight
    union all
    select '3' as node,0.7 as node_weight
    union all
    select '4' as node,0.5 as node_weight
    union all
    select '5' as node,0.7 as node_weight
    union all
    select '6' as node,0.5 as node_weight
    union all
    select '7' as node,0.7 as node_weight
    union all
    select '8' as node,0.7 as node_weight
)tmp;

對應的資料結構圖：

添加SQL指令碼組件，輸入以下PAI命令進行訓練。

drop table if exists ${o1};
PAI -name LabelPropagationClustering
    -project algo_public
    -DinputEdgeTableName=LabelPropagationClustering_func_test_edge
    -DfromVertexCol=flow_out_id
    -DtoVertexCol=flow_in_id
    -DinputVertexTableName=LabelPropagationClustering_func_test_node
    -DvertexCol=node
    -DoutputTableName=${o1}
    -DhasEdgeWeight=true
    -DedgeWeightCol=edge_weight
    -DhasVertexWeight=true
    -DvertexWeightCol=node_weight
    -DrandSelect=true
    -DmaxIter=100;

右擊上一步的組件，選擇查看資料 > SQL指令碼的輸出，查看訓練結果。

| node | group_id |
| ---- | -------- |
| 1    | 3        |
| 3    | 3        |
| 5    | 7        |
| 7    | 7        |
| 2    | 3        |
| 4    | 3        |
| 6    | 7        |
| 8    | 7        |