多標籤分類問題可以正式表述如下：
假設有K類標籤y={c1,c2,..,cK}，給定網路G=(V,E,Y)，其中V是頂點集，E是邊集，Yi⊆y是頂點vi⊆V的類標籤，並且已知道一些頂點vi∈VL(VL⊆V)的值，我們如何推斷其餘頂點VU=V-VL的Yi值（或針對每個標籤的機率分布）？
基本介紹
- 中文名：多標籤分類
- 外文名：Multi-label classification
- 分類：社交網路特性
一．定義,二．多標籤分類方法,
一．定義
社交網路中的行為是海量的、多種多樣的。例如：撰寫一篇部落格，瀏覽一組照片，點擊一個廣告，購買一件商品，訂閱特定新聞話題等等。我們的任務是預測社交網路中的行為。該問題可以被轉化成多標籤分類問題（Multi-label Classification）。
給定一個社交網路，並已知其中一些用戶（節點）的行為標籤信息，我們的任務是分類同一網路中其他未分類節點的行為標籤。假設一個網路中的所有行為可以用K類標籤
來描述，每個標籤
的值為1或0。比如，一個用戶可能加入多個興趣小組，
表示該用戶加入了興趣小組，否則
。我們的研究問題可以正式表述如下：
假設有K類標籤
，給定網路
，其中V是頂點集，E是邊集，
⊆y是頂點
的類標籤，並且已知道一些頂點
（
⊆V）的
值，我們如何推斷其餘頂點
的 值（或針對每個標籤的機率分布）？
二．多標籤分類方法
關聯分類方法（relational classifier）基於馬爾科夫依賴性假設（Markov dependency assumption），利用行為標籤間的依賴性來提升分類器的性能。麥克斯卡西(Macskassy)等提出了的加權投票關聯分類模型（weighted vote relational neighborhood classifier），該方法對於結構簡單的網路分類較為有效，但難以處理異構網路中的行為標籤分類問題。然而，許多真實世界的網路被認為是由多種類型的節點和連結組成的異構網路。因此，研究者提出一種基於潛在組（latent groups)為異構網路連線或類標籤建模的方法。Ji 等為異構信息網路，提出了一個基於排名的分類模型對標籤排名。當分類數據對象時，模型根據每個標籤的重要性為每個對象排名，以提供標籤的匯總信息。戈德堡(Goldberg)等發現在社交媒體中，即使節點間不是相似標籤，該節點也會連結到另一個節點。他們使用兩條邊的類型來表明連結對象之間是親密或是分歧的類別標籤，並且將連結類型信息引入到判定學習中。希瑟利(Heatherly)等引入了一個連結類型關係貝葉斯分類器，和其他連結類型一樣，根據鄰居的標籤來預測節點的類別標籤。關聯分類方法的優勢在於利用鄰接節點的標籤信息，對於一些不太複雜且規模較小的關係數據，能夠獲得較好的分類精度。但節點的特徵難以通過關聯分類模型從數據中學習獲得。因此難以描述節點和節點間的影響和互動關係。
唐(Tang)等提出了Edge-cluster算法來捕獲每個實體潛在的關係，實現對節點社會特徵的提取，再通過構造分類器實現標籤分類，該方法能有效處理包含數百萬邊的網路。該方法的思想是通過抽取社會維來表達網路成員的潛在隸屬社團來區分一個網路中的異構關係，並建議採用軟聚類方案的社區隸屬關係作為社會維度，再將社會維度視為節點的特徵向量用於分類。
王(Wang)和蘇克山噶(Sukthankar)提出了SCRN算法融合了關聯分類器和社會特徵提取方法。利用社會特徵計算網路中的每個實例與多標籤的子集關聯；同時引入一個類別傳播機率，融契約質性和特徵相似性，解決了異構網路多標籤分類的問題。SCRN算法也有不足之處。它僅能利用與待分類節點直接相鄰的節點，限制了對鄰接信息的充分利用，且無法有效學習孤立節點的標籤；同時該方法只能解決靜態的網路分類問題，沒有考慮特徵與標籤間的潛在時序因果關聯，難以處理數據流環境的複雜行為標籤學習問題。
