背景:
有许多文本数据含有重要的地理信息,而现有的词云方法无法显示空间信息。
Geo word clouds:不但可以显示词频还可以显示词之间的空间关联。
输入:n个点(带有地理位置);
M:需要填充的地理区域;
M':填充完后的地理区域;
2.1 Requirements
- R1. 所有单词不相交;
- R2. 每个词都有少量的shapes;(一个点代表一个单词,如果相同的词的点相互关联,则将其连成一个词。一个簇是一个单词,根据簇大小决定文本大小,一个簇可视后是一个shape)
- R3/M1. 词的shapes要和它的点很好的吻合;(为了强调词云的空间性,shapes和点需要吻合。一个词覆盖的点越多,这个词和没有被覆盖的点的距离越小,这个词所代表的空间数据越好。)
- R4/M2. 有k个点的词的区域接近于(M'是可视化后的区域,M是原始区域)
- R5/M3. M'需要将M完美覆盖(不要越界,不要留太多空白)
- R6. 同一单词的shapes需要有相同的颜色(保证一致性)
- R7. 不要让着色影响单词的重要性。
2.2 Measures:
A.
( p:点;Cp:p所属的簇;Word(Cp):矩形限位框。)
在边框上或者内部的霍斯多夫距离为0。
为了测量词的shapes是否和它的点很好的吻合,需要用到Hausdorff距离。
Coverage error:
The sum of the error for all points measures how well all shapes in M' cover the whole data set.(可视化后的shapes结果与数据的吻合度,可以理解为聚类后的框与其可视化后的shapes的吻合度)
B.
为了给词定义合适的位置,有时候需要进行词的缩放,因此M2表示的就是词的大小能够代表其点数的程度。比如对于有k个点的词,缩放比例为x,则not represented的点数为|k-k*x| (Rep(c):簇c中not represented 的点数。C:所有簇。),因此缩小词会使得该值变大。
C.
How well does M' resemble M.
M'与M的差值。
3.布局算法
k-means算法将同一标签的点聚成簇,每一个簇放一个单词。单词的大小取决于簇中点的数量。
clustering之后对每一个簇确定一个旋转角度。对簇中的点确定特征向量,利用特征向量中的principal component。确定这些点的特征向量并使用向量中的主成分。角度的选取要与特征向量保持相近。旋转角度:正交、45度、10度。
词的位置:贪心算法。根据簇的大小(簇中包含的点数)进行排序,位置由大到小放置避免对于更大的簇会有大的误差。按像素进行词的位置的计算,没有被占据的像素可以利用。
如果词无法放置在准确的位置,我们需要按比例缩减它,这样词的中心距离簇的中心就会更小。则需要对其进行重新的大小排序。
Optimal size的设定(R4):(AM 为由像素计算的M)
4.着色:
为了满足R6和R7.
根据Hue光谱,颜色的排布随词的大小排。
相似大小的单词颜色要隔c个,以防相似大小的词颜色相似。因此c需要大于1,图中为c=3的情况。这样两个相邻的单词得到相同颜色的概率大大缩减。
5.实验
数据:
1.法国:125个不同的标签,关于奶酪品种
2.英国和爱尔兰:126个来自网络相册的不同的照片标签,545140个图像。
实现:Sage Math Cloud(基于Python的软件包)
5.1Allowed rotations(是否需要更多的角度选择?)
90度的coverage error(所有点距离限位框的距离和,与其原定位置的差值)最小,因为90度时空间整齐,选择性强,使得shapes与其原定位置相差小。
Words not represented 变大,因为在45度和10度时,把所有词放在原定位置有困难,因此需要缩小一些词,因此words not represented会更多。
Symmetric difference在90度时最小,因为90度时更紧密,使得M'与M差值最小。
5.2 Initial font size
100%到90% coverage error(所有点距离限位框的距离和,与其原定位置的差值)变大,因为所有字都变小,聚类的覆盖的点就变少了。90%到80%变小,因为可视化后的词比预定位置更接近。
随着字体变小,words not represented 就变小了。
随着字体变小,symmetric difference变大。(可以理解为:所有词都变小,地图上的总覆盖变小,因此M'与M相差较大)
5.3 Clustering
- a.一个点放一个词,则无法区分词频。
- b.是a和b这两个极端的中间值。标签应用的多个区域都可以观察到,并且词的数量不会太大。
- c.每一个词用一个簇,则无法看出地区差别。
- 1.点被聚类的时候coverage error(所有点距离限位框的距离和)会变大,因为点距离它的原本位置的误差变大。
- 2.如果不聚类的话,许多词的位置会重叠,这样许多词不能放在原本的位置,因此这些词需要缩小以放置在适合的位置,所以words not represented会变大。
- 3.(c)比(b)差的原因:簇变大,词也会变大,使得相似大小的词难以整齐排布填满地图。
5.4 Word placement
- 1.第一个被放置的词是Tomme,因为它的词频最大,根据聚类算法,将其分为两个簇,词放置在最佳的位置以覆盖尽可能多的点;
- 2.第二个词Faisselle,因为Tomme占据了Faisselle的右下角最佳位置,因此需要调整Faisselle的位置,保证覆盖尽可能多的点;
- 3.第三个是Crottin,放置方法与之前相同。
5.5 Running time
法国:30分钟(90度)
英国和爱尔兰:60分钟(90度)
如果把角度变为10度,时间增加了60%。
数据的预处理(聚类和归一化)仅分别花费了几秒和几分钟。
Conclusions
- 1.旋转角度为90度时,结果最紧凑;
- 2.实现方法:贪心算法;
- 3.所选择的聚类算法也会影响地图的覆盖,我们发现k-means算法是最好的。