词云指北（上）：谈谈词云算法的发展_UTF_8

石力派

本文通过调研学术、商业、开源三个领域词云相关的产品，对词云相关算法、产品进行从上至下的总结，帮助读者快速了解词云相关的算法发展，并希望总结出当前字节跳动数据平台词云发展的路线。全文将分两次推送，第一篇专注分享词云算法的行业情况。第二篇介绍字节跳动数据平台词云实践。文 |橘子from 字节跳动数据平台前端团队DATA前言在开始正文之前，我们先聊聊词云究竟叫什么，是叫 wordle 还是叫 word / tag cloud首先，业界其实并没有对词云有特别严格的定义，但我们一般会这么认为：Word / Tag Cloud 泛指任何形似词云的可视化效果，不受限于 实现的算法，Wordle 名称来自提出螺旋线论文，可以说 Wordle 这个名字跟螺旋线算法较高强度的绑定。一般来说，在学术上，如果算法是基于螺旋线算法的，命名上就会在 Wordle 上进行变形，如：EdWordle 、ShapeWordle。DATA词云的设计空间常见的词云多为基于 wordle 算法（螺旋线算法）、使用字体大小进行权重编码、颜色随机分配(大多)、极少支持高自由度编辑的词云。而从学术界总结来看，词云是一个经历了20余年研究的领域，在视觉编码、布局方式、交互方式三个方面都有不少研究者对传统词云的设计空间进行扩展。01 - 视觉编码视觉编码是可视信息传递中重要的概念，词云中主要的视觉编码通道是文字本身，最常见的是以字体大小编码单词的重要性。除此之外, 也有一些工作使用 颜色、透明度等作为词频的冗余编码(指对同一维度同时使用多个通道进行编码), 或者表示除词频外的其他信息。例如，使用颜色编码聚类信息，如下图中，使用颜色编码来自同一文章的单词。另外，为了增强词云的数据分析能力，也有研究者为词云添加额外的图元来传递定量信息，但这会影响词云的美观程度。目前常见的是通过添加折线等方式来表现词频的变化趋势，如 SparkClouds 给标签云（词云的变种）添加迷你趋势线来展示时叙述数据。其中单词大小编码当前时间点的词频，趋势线反应词频变化曲线（所有趋势线 Scale 一致）。Parallel Tag Clouds 将平行坐标系与标签云相结合，来表达时序数据中同一单词在不同时间词频的变化。也有论文通过给单词附加额外的图元来表达词频信息：然而为词云添加过于复杂的视觉编码方式会损害词云自身的可读性和美观度，所以在选择使用非常规的视觉编码时，应该慎之又慎。02- 布局方法从词云发展来看，早期词云多使用行列式布局的方式，即标签云，此时的单词排序多使用字母表顺序。而经典的 Wordle 算法诞生并流行至今，其排序方法多与词频或其他单词重要性有关。与此同时，力导向布局也是词云中常见的布局方式。行列布局，即将单词在画布上从左到右/从上到下进行对齐排列，是早期常见的布局方式。有用户实验证明，这种布局方式能够有利于人们完成大小判断、关键词检索、文章主题提取等任务。但缺点是美观性较差。Wordle 算法，亦称为螺旋线算法。因其结果美观性强，螺旋线算法是最常使用的词云算法，但其算法复杂度较高。学术界有很多基础螺旋线算法的变种算法以适应不同的词云生成目的。力导向布局，其核心思想与图布局中的力导向算法一致，将单词视作点，并为点和点之间添加边，即可使用力导向模型对单词进行布局。不同单词之间的力的大小可以编码降维后的高维数据，例如语义数据，所以力导向排布多用于语义词云中应用。三种算法的详细例子将在后文中介绍。03- 交互方式常见的支持客制化的词云工具是用户通过对参数的调整（如单词朝向、颜色）等方式影响词云的结果，除了这种生成参数设定的情况外，也有论文支持用户通过交互来修改词云的布局。其交互方式形式比较多样，但可以根据交互的结果简单分为两类：重绘类操作和重排类操作。重绘类操作即用户的交互只会改变单词的颜色、透明度等外观，不会影响到词云的整体布局。重排类操作是指对单词进行放缩、移动、删除、添加和改变字体等操作。重排类操作可能会破坏原有布局的紧凑度和无重叠等特性，所以需要对编辑后的词云进行或大或小的重新布局算法（一般为小范围的调整）以保证美观度。关于更多创新交互方式的代表性论文会在后文中详细介绍。DATA词云分类从词云的功能性上对词云进行分类，但考虑到篇幅限制，本文只会对分类中较为经典 / 较为常用 / 较为前沿 的代表性算法进行详细的分析。01 - 语义词云语义词云是核心是词云的表意功能，在设计时通过将语义上相关或相近的词排布的更接近来更好的表达词云包含的文本含义 。该种词云的算法多为将高维空间的信息（如语义信息、相关性信息）通过 t-SNE 等算法降维投影到二维空间作为单词的坐标。因为在降维时并不会考虑单词的大小、重叠、碰撞等情况，初步降维的结果并不美观。大多算法会在降维后采用力导向模型对单词的位置进行调整，以提升词云的紧凑性和减少重叠。如下图，其生成结果中，语义相关的单词会聚合在一起形成单词簇，用户可以快速的获得哪些单词是高度相关的。这种降维的方式可以给我们启发，词云算法并不局限于使用螺旋线亦或者类似的算法对单词进行放置，也可以将高维数据降维后决定其位置，并可以传递一定量的高维信息。02- 形状词云带有形状限制的词云不仅可以提高词云的美观度，并且形状本身也对文本内容有暗示作用，可以提高了词云的表意能力。地理词云形状词云主要有两个应用领域，一个是基于地理位置的词云，其核心为表达地理相关的信息，需要在忠实于地理信息的基础上提高词云的美观度。此处以 Geo Word Clouds 为例介绍，下图为针对法国各地特色奶酪构建的奶酪词云，其整个词云外观为法国地图，各个奶酪名称在词云中的位置即为在真实地理中流行的地区 p.s. 地理位置不一定完全正确 p.p.s 奶酪这么多品种。左图为禁止旋转，右图为启用旋转：其输入为分布在地理区域内点的二维坐标，每个点都与一个或多个单词相关联，算法大致步骤为：使用 k-means 对有相同标签的点进行聚类。可能有相隔很远的两个点有相同的标签，此时会被聚集成两簇，如上图中的 Tomme。聚类后的每个簇各代表一个单词。聚类后，为每个簇设置合适的角度来更好的覆盖该簇的点。这里采用的是主成分分析，将单词旋转到最接近主成分方向的位置。采用贪婪的方式开始放置单词。将簇按照点集大小（权重）进行排序生成列表，放置单词时会依次选取列表最顶部的单词，以保证较大的点集有更高的准确率。每次迭代（尝试放置单词）时，会根据一定的规则（如旋转角度不能太大、保证单词对点集的覆盖率、单词大小与重要性成比例）去生成最佳的位置和字号大小。 如果不能成功放置，则缩小该单词的权重，并对列表进行重新排序。该算法的缺点主要有：首先该算法在挑选单词最佳位置时，会综合考虑 地理位置准确度、单词大小和权重的比例、单词对点集的覆盖率等指标，结果往往很难兼顾所有的指标。其效果可能因为了保持地理信息的准确度导致词云稀疏、亦或是为了保持词云的美观度丧失地理位置的准确度。针对地理词云的相关算法多有类似的问题。其他形状词云形状词云有一定的商业价值，主流的商业工具有 tagxedo wordart 均实现了一定程度的商业化，具体信息会在后续的商业工具中介绍。此处以学界前沿的 Shape Wordle 为例介绍形状词云的生成算法。其算法核心为支持形状感知的阿基米德螺旋线，其生成步骤为：对于复杂的凹多边形，首先使用 opencv watershed 算法分割成几个多边形对多边形计算 distance field（距离场），根据距离场生成螺旋线的算法稍复杂不易介绍，可简单理解为根据距离场提供的信息指导螺旋线的前进方向，最后生成出符合输入形状的螺旋线，如下图所示。在形状感知螺旋线的基础上使用常规词云放置单词的逻辑进行单词放置即可，其结果如下所示：可以看出，单词的排布非常贴合用户给定的形状。如果仅用用户提供的单词想完整的填充形状非常困难，会受到用户输入的单词数量、形状复杂的等多种显示。如上图鸽子图案，虽然单词已经非常贴合整体的形状，但其复杂形状处(鸟喙、翅膀细节)很难填充。故论文引入了二次填充的概念。即从文章中提取 top50单词为核心单词，使用形状感知的螺旋线布局，对top50-200的单词称之为填充单词，填充单词的大小与透明度远小于核心单词，对填充单词使用常规的扫描线算法进行填充。如下图所示，左图为仅包含核心单词，右图为经过二次填充的效果。该算法缺点主要是：算法复杂度较高，对图形的切割和距离场的求解都需要较高算力的计算。二次填充对用户观察核心单词有一定的影响。03- 可编辑词云可编辑词云是针对词云交互进行的扩展。传统的词云工具用户只能对部分参数(单词大小、旋转比例、颜色等)进行修改，很难对词云的细节进行针对性的调整。可编辑词云目的是提供方便有效的编辑方式，辅助用户对单词的细节进行调整，又不会破坏整体词云的紧凑性和美观度。此处以较为成熟的 EdWordle 为例介绍。其核心 idea 为将单词制作刚体，同时建立力学模型来辅助编辑。其核心为两个力：中心吸引力，其作用点为画布中心，随距离增强，目的为吸引远离画布中心的单词。邻接吸引力，作用点为临近的单词之间，随距离衰减，目的为提高词云的紧凑性。最终效果为，用户可以在力学模型的辅助下对词云进行非常有针对性的编辑，如将词语的中心的单词 移动/删除 后，其留下的空白会在力的作用下被附近的单词填充满，有效的提高了用户编辑的体验。可以非常方便地在 EdWordle 进行体验。该论文中也有两个有趣的贡献：两层次的刚体表示。 在对单词计算包围盒/刚体时，会针对权重>0.5 和 0.5 的单词，会进行字母级的建模以提高整体的紧凑度，对权重 实用性的一种可视化方案。目前常用的词云中会有诸多缺点。首先是单词颜色大多无明显含义，相当于浪费了一个有效的视觉通道。其次词频决定单词的大小，但单词的长度会影响用户的判断，导致长的单词看起来比短的单词更重要。另一个明显的问题是，东亚文字多为近方块字且分词结果较为单一（而英语词长短不一），会导致在视觉上针对字母语言设计的词云算法在东亚文字中效果并不好。下图为法语下图为中日韩三个东亚语言在同样的词云算法和参数下的结果，会看起来更加密集、有压迫感：在词云指北（下）中，我们将介绍数据平台前端团队自研的简单、易用、跨平台、高性能的图表库与图表研发框架，敬请期待。团队介绍字节跳动数据平台前端团队在公司内负责大数据相关产品的研发。我们在前端技术上保持着非常强的热情，除了数据产品相关的研发外，在数据可视化、海量数据处理优化、web excel、WebIDE、私有化部署、工程工具都方面都有很多的探索和积累。接下来本文还将介绍数据平台前端团队自研的简单、易用、跨平台、高性能的图表库与图表研发框架。- End -