基于LDA和tfidf的文档图的子图测试

由于被GCN需要塞入整张图才能计算的特性卡住（为什么我们没有V100？），我当时开始寻找解决方案，一个方向是去寻找GCN的min-batch实现，GCN已经出现几年了不可能没人解决这个问题。另一个方向是考虑从文档图中提取独立的子图，因为如果能抽取出独立子图，就可以单独对子图进行计算。

（这部分实验进行于2019年12月左右）

结论

因为是自己做的东西，并且现在回头看上去这个实验挺傻啦吧唧的，所以就把结论放在最前面：

LDA和TF-IDF相似度文档图抽取不出子图

主题/关键词的数量稍多之后，必然是全图联通的。

而如果控制主题/关键词的数量小于一定值之后，图中确实会出现独立的节点/小子图，但根据正态分布，绝大多数文档都会有头部的那些高频主题词。

结果就是整个文档图的大部分节点仍然是全联通的，剩下的一些只有低频主题词的尾部文档是独立的，构成一些独立的单节点子图，或是两三篇文档的子图。没有任何实际意义。

使用LDA、基于tfidf的文本相似度对文本进行处理。对于前者，若两篇文档间有重叠的主题词，则在两篇文档间添加一条边；对于后一个实验，人工控制相似度阈值创建边。

数据集为ask Ubuntu，仅使用极小部分进行实验（2752篇）

LDA设定输出主题数为100和500，并调整概率阈值。增大主题数的思路是，主题数越多，主题结果会越分散，那么文档图中的边会越稀疏。

tfidf不能调整输出主题数量，故仅调整概率阈值。

调整LDA输出主题的阈值和主题数进行实验

	原版	0.1	0.2	0.3	0.4	0.5
平均主题数	1.64	1.43	1.26	1.13	1.01	0.91
文档平均边数	2716	2615	2617	2630	2545	2299

100个主题

	原版	0.1	0.2	0.3	0.4	0.5
平均主题数	1.64	1.44	1.25	1.12	1.01	0.91
文档平均边数	2608	2616	2633	2613	2532	2282

500个主题

LDA原版为概率大于1e-8即输出该主题

结论：

TFIDF部分仅调整创建文档边的相似度阈值

相似度阈值	0	0.01	0.03	0.06	0.1	0.3	0.5
文档平均边数	2730	1770	683	182	44.6	0.96	0.1

结论：使用相似度可以明显的减少图中的边数。

但平均边数低并不代表能分离出子图，整个图仍然可能是全连通的，所以需要测试子图的分布。由于没有现成的子图搜索算法，我使用了一个近似的办法：随机采样十个点，进行邻居搜索，记录由当前点所有能到达的邻居节点。采样点能到达的邻居节点的数量基本代表了大图的子图规模。

相似度阈值/采样编号	0	1	2	3	4	5	6	7	8	9
0.1	2752	2752	2752	2752	2752	2752	2752	2752	2752	2752
0.2	2135	2135	2135	2135	2135	1	2135	2135	2135	2
0.3	346	1	1	5	1	6	346	2	346	1
0.4	1	1	1	1	4	1	1	1	1	1
0.31	4	1	1	1	1	3	246	1	1	8
0.32	1	1	4	209	1	1	1	209	209	1
0.33	1	1	1	1	61	1	1	2	1	1

结论：数据的聚集性非常明显，即使使用较高的阈值，使得边较为稀疏，强行弄出出一些小子图，也会存在大量无法收录到子图的文档节点。

任何主题算法，结果再好也就是完美捕捉出tag信息。于是我决定直接基于tag构建图看看图张啥样。

和LDA一样，两个文档共享一篇tag就创建边，如果只是看图的形状的话权重是无所谓的。

已经没有当时的图了，但我还记得可视化跑出来效果大概是这样。

前文就已经提过了，根据正态分布，大多数文档共享少量高频特征才是自然的。最终直接使用tag构建图让我意识到了这点，意识到了我这个思路的愚蠢。

指望数据自然的分成可以计算的小簇简直就是做梦，那么我需要解决GCN的batch采样问题，所以我下一步摸索到了graphSAGE——一个通过采样近似模拟GCN的模型。