Question

DOM是形成网页结构的元素集合。如果你曾经查看过网页的源代码，你就已经看到了DOM的各个模块。它们包括例如body、div、class和id这样的元素和标签。我们需要处理这些元素来提取所需的数据。

让我们来看看Google网页的DOM。为了查看其内容，请在该页面上单击右键，并单击“检查元素”。对于Firefox或Chrome浏览器，这个操作应该是相同的。这将打开开发人员选项卡，允许你查看页面的源信息。打开之后，在左上角挑选元素选择器，并单击其中一个价格栏跳转到相应的元素。如图3-3所示。

图3-3

你注意到的第一件事情可能是，发现div标签中没有任何定价数据。如果将鼠标悬停在价格栏上，将出现一个显示费用的提示，但这一切都是使用JavaScript完成的，并不是DOM。事实上，唯一可用的信息是价格栏的高度。那么，我们如何获得不在那里的数据呢？靠推断！

页面确实给了我们足够的线索来推断价格，那就是使用价格栏的高度。你会注意到，为每个城市所列出的是最好的票价。你可以在条形图的左手边看到它。此div提供了文本类型的价格，如图3-4所示的屏幕截图。

你还会注意到，每个城市都有一个条匹配了最低的票价。相比其他的条，这个条加入了更暗的阴影来突出显示。因为有一个独特的类来产生这种颜色，因此我们能够对它进行定位。一旦我们找到了它，就可以使用它的高度除以价格来确定每个像素所对应的价格。使用这种方法，推导出每个航班的价格就成为了一个简单的数学练习。

图3-4　

让我们现在编写代码。

第一步是将页面源文件提供给BeautifulSoup。

s = BeautifulSoup(driver.page_source, "lxml")  

然后我们可以获取所有最佳价格的列表。

best_price_tags = s.findAll('div', 'FTWFGDB-w-e') 
best_prices = [] 
for tag in best_price_tags: 
     best_prices.append(int(tag.text.replace('$',''))) 

由于拥有最便宜票价的城市上升到了最高的排名，我们可以直接使用它。

best_price = best_prices[0]

接下来，我们将得到包含每个条的高度的列表。

best_height_tags = s.findAll('div', 'FTWFGDB-w-f') 
best_heights = [] 
for t in best_height_tags: 
     best_heights.append(float(t.attrs['style']\
     .split('height:') [1].replace ('px;',''))) 

同样，我们只需要第一个。

best_height = best_heights[0]

然后我们可以计算每个高度像素所对应的价格。

pph = np.array(best_price)/np.array(best_height)

接下来，我们将检索每个城市所有航班的价格条的高度。

cities = s.findAll('div', 'FTWFGDB-w-o') 

hlist=[] 
for bar in cities[0]\
     .findAll('div', 'FTWFGDB-w-x'): 
     hlist.append(float(bar['style']\
                           .split('height: ')[1]\
                           .replace('px;','')) *pph)
fares = pd.DataFrame(hlist, columns=['price'])

任务完成了，我们现在有一个数据框，包含了两个月内最便宜的票价。下面来看看。

fares.min() 

上述代码生成图3-5的输出。

图3-5

我们的最低票价应该与页面上看到的一样，而事实确实如此。现在再看看完整的列表，如图3-6所示。

图3-6

一切看起来不错。我们现在可以继续建立异常值检测了。

通过聚类技术识别异常的票价

机票全天都在不断地更新。如果我们试图确定远低于正常的票价，不使用机器学习的技术怎么行？这看上去似乎是相当简单，但是当你开始思考可用的选项时，它很快就变得比预期复杂得多。

一个选择是获得每个城市的价格并设置一个阈值，如果它们跌到比阈值还低的价格，你就发送一个提醒。这可能行得通，不过是将比目前最低价格少一定量的百分比设置为提醒的条件，还是将具体的美元金额设置为提醒条件？还有，如何设置它？如果由于季节性因素导致票价自然下降，又该怎么办呢？也许你可以检查每个价格条和中间值相比偏离了多少。如果价格接近平稳的时候，出现一个很小幅度的下降呢？也许你可以对比每个价格条与其相邻条的高度。如果错误票价出现在不止一天中，又会如何？正如你所见，这件任务不是看上去那么简单的。鉴于此，我们如何避免为每个城市存储定价数据、处理季节性因素，并试图设置阈值的烦恼呢？这里使用聚类算法。

有许多聚类算法可用，但是对于这里所处理的数据类型，我们将使用被称为基于密度的空间聚类算法（DBSCAN），它适合带有噪声数据的应用。这是一种非常有效的算法，倾向于使用和人类相同的方式来识别点的集群。图3-7是来自scikit-learn文档中的可视化图像。它演示了DBSCAN在不同数据分布范围内的有效性。

图3-7

你可以看到，它是相当强大的。让我们现在讨论一下算法的工作原理。

为了理解DBSCAN算法，首先我们需要讨论两个参数的设置，以使得算法能够运作。第一个参数称为epsilon。此参数确定在同一聚类中两个点彼此之间的距离。如果epsilon设置得非常大，那么任何两个点则更可能聚集在一起。第二个参数称为最小点数。这是创建聚类所需点的最小数量（包括当前点）。如果最小的点数是1，那么每个点都将成为一个聚类。如果最小点数大于1，那么有可能某些点就不隶属于任何聚类。然后这些点就被认作噪声——也就是DBSCAN中的N。

DBSCAN算法是如下进行的。从所有点的集合中随机选择一个点。从这一个点出发，搜索所有方向上的和当前点相距epsilon距离的范围。如果在epsilon距离的范围内，存在等于或多于最小点数的点，那么这个范围内所有的点就隶属于一个聚集（图3-7中的彩色区域）。针对每个新加入该聚类的点，重复该过程。继续此操作，直到没有任何新的点可以添加到此聚类。此时，第一个聚类就完成了。现在，从已经完成的聚类之外，随机选择新的点再次开始。重复同样的过程，直到没有新的聚类可以形成。

我们已经了解了算法的工作原理，现在将其应用到机票的数据上。我们将首先创建一个简单的图像来检视票价。

fig, ax = plt.subplots(figsize=(10,6)) 
plt.scatter(np.arange(len(fares['price'])),fares['price']) 

上述代码的输出如图3-8所示。

图3-8

我们可以看到票价平稳了几个星期，然后开始急剧上升。大多数人可能将这些看作 4个主要的聚类。现在编写代码来识别和显示这些集群。

首先，我们将设置一个price数据框，然后可以将DBSCAN对象传入其中。

px = [x for x in fares['price']] 
ff = pd.DataFrame(px, columns=['fare']).reset_index()

然后，我们需要为聚类导入几个库。

from sklearn.cluster import DBSCAN 
from sklearn.preprocessing import StandardScaler

最后，下面的代码将DBSCAN算法应用于票价数据并输出一个可视化图像。

X = StandardScaler().fit_transform(ff) 
db = DBSCAN(eps=.5, min_samples=1).fit(X) 

labels = db.labels_ 
clusters = len(set(labels)) 
unique_labels = set(labels) 
colors = plt.cm.Spectral(np.linspace(0, 1, len(unique_labels))) 
plt.subplots(figsize=(12,8)) 

for k, c in zip(unique_labels, colors): 
     class_member_mask = (labels == k) 
     xy = X[class_member_mask] 
     plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=c, 
               markeredgecolor='k', markersize=14) 

plt.title("Total Clusters: {}".format(clusters), fontsize=14, 
          y=1.01)

让我们逐行地解释。在第一行，我们使用StandardScaler()方法，这个对象将获取数据，对每个点减去平均值，然后除以标准差^[1]。这个步骤使所有的数据位于相同的基础之上，并为算法读取了这些数据。标准化之后的数据被传递给了DBSCAN对象。这里设置了前面讨论的两个参数。我们将eps或者epsilon距离设置为0.5，并将min_samples设置为1。下一行代码将labels设置为算法的labels数组输出。每个点（因为min_points设置为1）都将关联一个聚类ID。这些聚类将被标记为从0到n-1，其中n是聚类的总数。接下来的两行代码获得聚类的总数及其唯一标签，而以colors开头的代码为我们的图像生成了有颜色的图。剩余的代码对图像进行了设置，包括对每个聚类应用唯一的颜色，并使用聚类的总数为图像设置标题。

让我们来看看图3-9中票价数据的输出。

图3-9

正如你所见，算法已经确定了四个不同的聚类，这正是我们所期望的。我刚刚告诉你该算法使用这些参数运作得有多好，而现在就准备修改参数了。为什么要破坏完美的结果？好吧，让我们来看看几个引入虚构票价的场景。

使用目前的票价系列和相同的参数，让我们再引入一个新的票价。

首先，将序列中的数据点#10替换掉。我们将其从656美元更改为600美元，如图3-10所示。

图3-10

你会注意到在接近图形底部的位置，这个点形成了自己的聚类。然而，尽管这个票价与其他的价格明显分开，但是还不足以引起我们注意。

让我们增加epsilon参数，这样我们只会聚出两个分组：典型的票价和不正常的票价。

我们现在保持相同的虚构票价，不过将epsilon增加到1.5，如图3-11所示。

图3-11

你可以看到现在有两个聚类。我们600美元的票价已经被放在了主聚类，而在图顶部最右侧的票价已经形成了自己的聚类。这看起来很合理，因为最右边的票价是一个明显的异常值。让我们再测试一下，需要多远的距离才能将虚构的票价放在自己的聚类里？

图3-12的截图展示了让虚构票价进一步远离后的结果。

在图3-12中，将其删除到550美元，我们可以看到它仍然是主聚类的一部分。

图3-13中，将其降至545美元，会使其形成自己的聚类。这似乎是一个合理的水平，不过现在让我们使用其他城市运行另外几个场景试试看。

图3-14是东京成田机场的数据序列。其中有个单一的聚类，这是我们所希望的。现在换一个虚构的票价。我们将序列中#45的票价从970美元替换为600美元。这是一个大幅的下降——远远超过之前数据序列中由于111美元下跌而触发一个新的集群——但它显然在通常的价格范围内，所以我们不想形成一个新的聚类。

图3-12

图3-13

图3-14

从图3-15中你可以看到没有形成新的聚类。虚构的票价和其左右邻近的两个票价之间有如此大的距离，为什么还会导致这种情况？这是因为我们正在处理整个序列，而不仅仅是每个点最近的邻居。最有可能的是，虚构的数据点受到其左边点的影响而加入到聚类。让我们再试一个场景。让我们将一个票价置换到右边——进一步远离左下角的聚类，如图3-16所示。

图3-15

图3-16

这里我们将#55的票价从1176美元换成700美元。这会导致一个新的聚类。票价是在全系列票价的范围之内，但是现在它当然是一个异常点。然而，我们很可能不想被告知这种异常。

由于我们不希望在每次有多个集群时都被提醒，因此需要为希望被告知的场景设置规则。

首先，由于我们正在寻找错误的票价，因此期望它们等于所显示的最低价格。我们可以按照聚类来分组并检索最低的价格。

pf = pd.concat([ff, pd.DataFrame(db.labels_, 
                                      columns=['cluster'])], axis=1) 
pf

图3-17

上述代码生成图3-17的输出。

以下代码将按照聚类来分组并显示分组中最低的价格和成员的数量。

rf=pf.groupby('cluster')['fare'].agg(['min','count']) 
rf

上述代码生成图3-18的输出。

这里我们还预计错误聚类将小于主聚类。我们对错误聚类的大小设置一个限制，要求它小于总数的百分之10。在这种情况下，它将少于七个票价。这个数字将根据不同聚类的数量和大小而变化，但这应该是一个可行的数字。为了查看分位数的细节，可以使用下面这行代码。

rf.describe([.10,.25,.5,.75,.9])

上述代码生成图3-19的输出。

图3-18

图3-19

让我们再添加一个条件。为最低价集群和次低价集群之间设置一个最小距离。这样做将防止像在图3-20中看到的情况。

图3-20

这里的费用是最低的，但它只是比其他聚类范围低那么一点点。设置最小距离将减少我们收到的误报。让我们先将最小距离设置为100美元。

现在我们有了自己的异常检测规则，下面来看看如何将全部的模块组合起来，完成实时票价提醒应用程序。