Python에서 그래프를 어떻게 클러스터링할 수 있나요?
https://stackoverflow.com/questions/653496
-
19-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
G를 그래프라고 하자.따라서 G는 노드 집합이자 링크 집합입니다.그래프를 분할하는 빠른 방법을 찾아야 합니다.지금 작업 중인 그래프에는 120*160개의 노드만 있지만 곧 다른 맥락(의학이 아니라 웹 사이트 개발)에서 수백만 개의 노드가 있는 동등한 문제를 작업하게 될 수도 있습니다.
그래서 제가 한 일은 모든 링크를 그래프 행렬에 저장하는 것이었습니다.
M=numpy.mat(numpy.zeros((len(data.keys()),len(data.keys()))))
이제 노드 s가 노드 t에 연결되어 있으면 M은 위치 s,t에 1을 보유합니다.M이 대칭 M[s,t]=M[t,s]이고 각 노드가 M[s,s]=1에 연결되어 있는지 확인합니다.
잘 기억하면 M에 M을 곱하면 두 단계를 거쳐 도달한 꼭지점을 연결하는 그래프를 나타내는 행렬이 나온다.
그래서 나는 행렬의 0 개수가 더 이상 감소하지 않을 때까지 M에 그 자체를 곱하는 것을 계속합니다.이제 연결된 구성 요소 목록이 생겼습니다.이제 이 행렬을 클러스터링해야 합니다.
지금까지 나는 알고리즘에 꽤 만족하고 있습니다.나는 그것이 쉽고 우아하며 합리적으로 빠르다고 생각합니다.이 부분에서 어려움을 겪고 있습니다.
기본적으로 이 그래프를 연결된 구성 요소로 분할해야 합니다.
모든 노드를 살펴보고 노드가 무엇에 연결되어 있는지 확인할 수 있습니다.
그러나 행렬을 정렬하여 선을 재정렬하는 것은 어떻습니까?그러나 그것이 가능한지 모르겠습니다.
다음은 지금까지의 코드입니다.
def findzeros(M):
nZeros=0
for t in M.flat:
if not t:
nZeros+=1
return nZeros
M=numpy.mat(numpy.zeros((len(data.keys()),len(data.keys()))))
for s in data.keys():
MatrixCells[s,s]=1
for t in data.keys():
if t<s:
if (scipy.corrcoef(data[t],data[s])[0,1])>threashold:
M[s,t]=1
M[t,s]=1
nZeros=findzeros(M)
M2=M*M
nZeros2=findzeros(M2)
while (nZeros-nZeros2):
nZeros=nZeros2
M=M2
M2=M*M
nZeros2=findzeros(M2)
편집하다:
SVD 분해를 사용하는 것이 제안되었습니다.다음은 5x5 그래프 문제의 간단한 예입니다.19200x19200 정사각형 행렬에서는 클러스터를 보기가 쉽지 않기 때문에 이것을 사용하겠습니다.
import numpy
import scipy
M=numpy.mat(numpy.zeros((5,5)))
M[1,3]=1
M[3,1]=1
M[1,1]=1
M[2,2]=1
M[3,3]=1
M[4,4]=1
M[0,0]=1
print M
u,s,vh = numpy.linalg.linalg.svd(M)
print u
print s
print vh
기본적으로 여기에는 4개의 클러스터가 있습니다.(0), (1,3), (2), (4) 그러나 나는 여전히 SVN 이이 맥락에서 어떻게 도움이 될 수 있는지 알지 못한다.
해결책
실제 그래프 라이브러리를 사용하지 않겠습니까? 파이썬 그래프? 그것은 있습니다 연결된 구성 요소를 결정하는 기능 (예제는 제공되지 않지만). 전용 도서관이 요리 한 임시 그래프 코드보다 빠를 것이라고 생각합니다.
편집하다: 네트워크 파이썬 그래프보다 더 나은 선택 일 수있는 것 같습니다. 그것의 문서 (여기에 연결된 구성 요소 기능) 확실히.
다른 팁
Scipy에서는 사용할 수 있습니다 드문 매트릭스. 또한 매트릭스 자체를 곱할 수있는보다 효율적인 방법이 있습니다. 어쨌든, 당신이하려고하는 것은 SVD 분해로 할 수 있습니다.
또한 있습니다 그래프_도구 그리고 네트워크잇 연결된 구성 요소에 대한 효율적인 루틴을 갖고 있으며 둘 다 네트워크를 효율적으로 저장합니다.수백만 개의 노드로 작업하려는 경우 networkx로는 충분하지 않을 수 있습니다(순수한 Python afaik입니다).두 도구 모두 C++로 작성되었으므로 합리적인 실행 시간으로 대규모 그래프 분석을 처리할 수 있습니다.
Phil이 지적했듯이, 귀하의 방법은 대규모 그래프에 대해 계산 시간이 엄청나게 길어지며(일, 주, 월...) 백만 개의 노드로 구성된 그래프를 표현하려면 백만 기가바이트 정도의 메모리가 필요합니다. !
다음은 연결된 구성 요소를 사용하는 순진한 구현입니다. 깊이의 첫 번째 검색, 나는 얼마 전에 썼다. 매우 간단하지만 수천 개의 정점과 가장자리로 잘 조정됩니다 ...
import sys
from operator import gt, lt
class Graph(object):
def __init__(self):
self.nodes = set()
self.edges = {}
self.cluster_lookup = {}
self.no_link = {}
def add_edge(self, n1, n2, w):
self.nodes.add(n1)
self.nodes.add(n2)
self.edges.setdefault(n1, {}).update({n2: w})
self.edges.setdefault(n2, {}).update({n1: w})
def connected_components(self, threshold=0.9, op=lt):
nodes = set(self.nodes)
components, visited = [], set()
while len(nodes) > 0:
connected, visited = self.dfs(nodes.pop(), visited, threshold, op)
connected = set(connected)
for node in connected:
if node in nodes:
nodes.remove(node)
subgraph = Graph()
subgraph.nodes = connected
subgraph.no_link = self.no_link
for s in subgraph.nodes:
for k, v in self.edges.get(s, {}).iteritems():
if k in subgraph.nodes:
subgraph.edges.setdefault(s, {}).update({k: v})
if s in self.cluster_lookup:
subgraph.cluster_lookup[s] = self.cluster_lookup[s]
components.append(subgraph)
return components
def dfs(self, v, visited, threshold, op=lt, first=None):
aux = [v]
visited.add(v)
if first is None:
first = v
for i in (n for n, w in self.edges.get(v, {}).iteritems()
if op(w, threshold) and n not in visited):
x, y = self.dfs(i, visited, threshold, op, first)
aux.extend(x)
visited = visited.union(y)
return aux, visited
def main(args):
graph = Graph()
# first component
graph.add_edge(0, 1, 1.0)
graph.add_edge(1, 2, 1.0)
graph.add_edge(2, 0, 1.0)
# second component
graph.add_edge(3, 4, 1.0)
graph.add_edge(4, 5, 1.0)
graph.add_edge(5, 3, 1.0)
first, second = graph.connected_components(op=gt)
print first.nodes
print second.nodes
if __name__ == '__main__':
main(sys.argv)
다른 사람들이 지적했듯이 바퀴를 재발 명 할 필요는 없습니다. 최적의 클러스터링 기술에 많은 생각이 제기되었습니다. 여기 잘 알려진 클러스터링 프로그램입니다.
도서관이있는 것 같습니다 pymetis, 링크 목록이 주어지면 그래프를 분할 할 것입니다. 링크 된 노드의 원래 목록 (매트릭스 다중 형성 노드가 아님)을 전달하여 그래프에서 링크 목록을 추출하는 것은 상당히 쉽습니다.
M '= mm은 큰 순서에 반복적으로 수행하는 데 효율적이지 않습니다. 순서 n의 행렬에 대한 전체 매트릭스는 N 곱셈과 요소 당 n-1 첨가 비용이 들며, 그 중 n이 있습니다.2, 그것은 O (n3) 운영. "수백만 개의 노드"로 확장하는 경우 O (1018) 매트릭스 매트릭스 곱셈 당 작업, 그 중 여러 가지를 원합니다.
요컨대, 당신은 이런 식으로하고 싶지 않습니다. 그만큼 SVD 제안 Vartec에서 유일하게 적절한 선택이 될 것입니다. 최선의 선택은 단지 pymetis를 사용하고 그래프 파티션을 재창조하지 않는 것입니다.
SVD 알고리즘은 여기에 적용 할 수 없지만 Phil H는 정확합니다.
