3.5 组织数据

数据挖掘是从大量数据中寻找规律的技术。一种基本的数据挖掘工具称为聚类（cluster），就是组织信息，把性质相似的信息分到同一组里，这种组称为簇。有时，每两个数据点之间的相似度都可以具体表示，这时就会用TSP来处理信息。把两点之间的相似度数值作为旅行费用，数据点关系越密切，相似度数值就越高，因此总费用最大的哈密顿通路就会使相似点彼此接近，通路的片段也就可以作为备选的簇。然后通常由研究者人工完成最后的分类。他们选出序列的自然分界点，从而在这些点处把通路分成几段。¹

_{1. Lenstra, J. K. 1974. Operations Research 22, 413–414.}

上面这种两步走的方法可以被另一种简洁的技巧取代。新方法的提出者是Sharlee Climer和Weixiong Zhang。²他们在解决这道TSP题目时，添加的“虚城市”个数不是1，而是k+1。每一个“虚城市”与其他任何城市之间的旅行费用都是0。由于不同簇的两点之间费用较低，而相同簇的两点之间费用较高，因此一条好的TSP路线就会把“虚城市”插入在不同簇的数据点之间，尽量避免降低总费用。所以，k+1个“虚城市”恰好可以作为k个簇的分界点。

_{2. Climer, S., W. Zhang. 2006. J. Mach. Learn. Res. 7, 919–943.}

Climer和Zhang使用这种“TSP+k”方法进行基因表达数据聚类分析，利用Concorde代码计算最优路线，通过改变k的值研究不同的簇数目对数据分析的影响。他们开发的软件可以得到图3-9这样的图像。图中的数据集是拟南芥（Arabidopis）的499个基因在五种不同环境条件下的表达情况，灰色阴影代表基因表达水平数值，白色实线则表示各个簇的分界线。

图3-9　基因表达数据（Sharlee Climer和Weixiong Zhang供图）

3.5.1 音乐之旅

在计算机音乐领域，人们同样借助TSP来理解大量由计算机编码的音乐。Elias Pampalk和Masataka Goto（后藤真孝）在日本产业技术综合研究所工作。用户借助他们发明的MusicRainbow（音乐彩虹）系统，可以找到适合自己音乐品味的其他艺术家（音乐人）。Pampalk和Goto收集了558位艺术家演绎的15 336首曲目。他们首先通过计算比较这些曲目的音频属性，建立了一种测定艺术家相似度的方法。然后，他们使用TSP模型，用一条环形路线串起所有艺术家，使彼此相似的艺术家在路线上的次序也比较接近。模型中的城市就是艺术家，而两地之间的旅行费用就是两人之间的相似度。

有了这条环形路线，用户就可以通过旋转一个旋钮在音乐库中进行选择。MusicRainbow设备配有计算机屏幕，用来显示艺术家的信息。屏幕上有一系列彩色的同心圆，分别对应了音乐的不同高级分类，比如摇滚（rock）和爵士（jazz），从而表明了艺术家的种种标识属性。MusicRainbow系统的一大亮点在于，所有标识信息都是自动搜索网页获得的，因此任何音乐库都可以很方便地使用该系统。

图3-10　MusicRainbow设备（Elias Pampalk供图）

Elias Pampalk还曾经参与另一项音乐方面的TSP应用项目。另外两名合作者是奥地利林兹大学的Tim Pohle和Gerhard Widmer。他们的目的是把一批音乐曲目组织起来，整理出一个循环链表，让相似的曲目在链表上位于邻近的位置。这样一来，用户使用音乐播放器时，可以通过旋转一个转盘，选出一首契合自己当下心情的曲目。播放器放完这首曲目之后，便会接着播放一系列类似的曲目。这三位研究者设计的播放器名为Traveller's Sound Player（旅行者的音频播放器），通过比较两首曲目的音色相似度，来测量两者之间的“距离”。他们使用了3000多首曲目作为一个测试用例，并用TSP模型求出了总距离最短的环形路线排列次序，得到了相应的循环链表。

上面这两个例子的涉及面都比较广，但是也有范围比较局限的应用实例。纽约大学的Drew Krause在自己作曲时借助了TSP的力量。在音乐中，流畅平稳的过渡称为级进旋律（conjunct melody），能给人带来愉悦之感。Krause在安排和弦时使用Concorde代码，就是为了让每个和弦转到下一个和弦的变化幅度都尽可能小。在这个TSP模型中，城市是他要用到的一组和弦，两点间的旅行费用则定义为两个和弦的对应音符之间相差的半音数之和。

3.5.2 电子游戏速度优化

为了表现出木材、金属等物质材料的真实质感，现在的新型电子游戏在显示物体时都需要使用大量数据。这种显示数据的基本组成部分称为纹理（texture）。目前，有的纹理库包含成千上万种纹理，从砖石到铁锈，各种纹理应有尽有。在游戏里，为了描绘显示的所有物体的表面，任意一幕场景都需要一组特定的纹理，也就是一个纹理组。由此产生了一大挑战，即如何尽快获取纹理数据并在机器屏幕上显示出来，从而使场景切换时可以流畅过渡。这里正是TSP的用武之地。

DVD代表数字视频光盘（digital video disk）。¹DVD的数据读取速度与数据存储方式有关，这是它的一个基本特性。具体说来，读取顺序存储的数据远远快于乱序存储的数据。因此，纹理数据在光盘上的存储位置布局会严重影响显示游戏场景所需的时间。要是能让游戏各场景对应的各个纹理组按照顺序存储就好了，但是要想实现这种美梦，重复用到的纹理就必须储存好几个副本。另一种思路则是恰当选择纹理数据布局，使分隔（break）的总数尽可能小。这里的分隔指的是一组纹理分散在不同位置的情况，具体说来，如果这组纹理分布在光盘的k个区间内，那么就会产生k-1个分隔。回忆一下之前提到的绘制基因组图谱的例子，应用的方法是一样的，只需要把细胞系换成纹理组就可以了。这里的TSP模型中，城市代表不同的纹理，两点之间的旅行费用代表只包含两个纹理之一的纹理组数。正如基因组图谱的情形那样，这次同样不能直接得到环形路线，只能得到哈密顿通路，再用我们的老办法，增加一个“虚城市”把通路转化成回路。

_{1. 1995年正式确立DVD规格时，DVD被重新定义为digital versatile disk，即数字多功能光盘或数字通用光盘。——译者注}

加拿大企业Digital Extremes的Glen Miner阐述了这项应用。这家公司使用Concorde程序求解纹理数据储存布局，做了相关的试验，并公布了TSP模型带来的显著改进。